1、與組數(shù)鏈2.2 鏈表表錄目鏈表的概念與特性01鏈表的基本操作02鏈表應(yīng)用解決實際問題03問題提出問題：想用python制作一個班級學(xué)生的抽獎程序輸入中獎人數(shù)，點抽獎顯示中獎人姓名。用數(shù)組保存中獎人姓名和暫時未中獎人姓名有什么弊端么？一、鏈表的概念鏈表指將需要處理的數(shù)據(jù)對象以節(jié)點的形式，通過指針串聯(lián)在一起的一種數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)區(qū)域指針區(qū)域?qū)嶋H需要處理的數(shù)據(jù)元素相鄰結(jié)點的存儲地址一、鏈表的概念data3nulldata1nextnewnextdata2nexthead前驅(qū)節(jié)點后繼節(jié)點一、鏈表的概念單向鏈表中各節(jié)點在內(nèi)存中可以非順序存儲每個節(jié)點使用指針指向其后繼節(jié)點的存儲地址通過head進(jìn)入鏈表，其他

2、節(jié)點則需經(jīng)過所有在它之前的節(jié)點才能訪問尾節(jié)點的指針指向null，表示指向為空一、鏈表的概念問題與討論：描述雙向鏈表和循環(huán)鏈表的節(jié)點結(jié)構(gòu)及其指針指向二、鏈表的特性同一鏈表中每個節(jié)點的結(jié)構(gòu)均相同每個鏈表必定有一個頭指針，以實現(xiàn)對鏈表的引用和邊界處理鏈表占用的空間不固定三、鏈表的基本操作鏈表的創(chuàng)建通過列表模擬實現(xiàn)鏈表實際應(yīng)用可以不帶頭節(jié)點，本章用列表索引來代替地址指針，規(guī)定列表索引均為正索引Head值為-1，表示頭指針指向為空，該鏈表為空鏈表三、鏈表的基本操作鏈表節(jié)點的訪問data3nulldata1nextnewnextdata2next三、鏈表的基本操作鏈表節(jié)點的插入新數(shù)據(jù)插入位置data3nu

3、lldata1nextnewnextdata2next指針指向的修改是否必須有先后？三、鏈表的基本操作鏈表節(jié)點的插入的列表實現(xiàn)data16data8-1newnextdata37data65data53data70data21data4201234567head列表索引數(shù)據(jù)區(qū)域指針區(qū)域在第3個節(jié)點，即data3節(jié)點后插入新節(jié)點next三、鏈表的基本操作data16data8-1newdata37data65data53data70data21data4201234567878在第3個節(jié)點，即data3節(jié)點后插入新節(jié)點三、鏈表的基本操作在第3個節(jié)點，即data3節(jié)點后插入新節(jié)點問題與討論：尾節(jié)點

4、之后插入新節(jié)點，節(jié)點指針該如何修改？描述在有8個節(jié)點的單向鏈表中刪除第一個節(jié)點、中間節(jié)點及尾節(jié)點的過程。三、鏈表的基本操作鏈表的插入應(yīng)用 例1 基于鏈表實現(xiàn)數(shù)據(jù)合并功能與數(shù)組合并功能類似，將兩個有序鏈表的數(shù)據(jù)合并到其中一個鏈表中。三、鏈表的基本操作鏈表的插入應(yīng)用三、鏈表的基本操作鏈表的插入應(yīng)用三、鏈表的基本操作鏈表的訪問與遍歷 例2 約瑟夫問題n個人排成一圈，從某個人開始，按順時針方向從1開始依次編號。從編號為1的人開始順時針“1,2,3，m,1,2,3,”報數(shù)，報到m(m1)的人退出圈子。這樣不斷循環(huán)下去，圈子里的人數(shù)將不斷減少。由于人數(shù)是有限的（n個），因此最終會只剩下一個人。試問最后剩下

5、的人的初始編號是多少？三、鏈表的基本操作鏈表的訪問與遍歷抽象建模： n個參與人員的初始編號，1至n的序列。 從編號1開始計數(shù)，每過一個編號加1，當(dāng)計數(shù)到m時將該編號從數(shù)據(jù)序列中移除，并從該編號的后一編號從1開始重新計數(shù)。 計數(shù)到序列中最后一個編號，又從序列的開始編號繼續(xù)計數(shù)，從而將計數(shù)序列構(gòu)成一個環(huán)。 三、鏈表的基本操作鏈表的訪問與遍歷設(shè)計數(shù)據(jù)結(jié)構(gòu)與算法： 數(shù)據(jù)規(guī)模初始時可以確定（最大為n）。 數(shù)據(jù)處理過程中需要按照規(guī)則不斷地移除數(shù)據(jù)，直至只剩一個為止。 數(shù)據(jù)規(guī)模逐漸變小，具有不穩(wěn)定特性，符合鏈表應(yīng)用。 最大編號報數(shù)后會從最小編號繼續(xù)報數(shù)，所以可采用單向循環(huán)鏈表來組織數(shù)據(jù)。三、鏈表的基本操作鏈表的訪問與遍歷編寫程序五、思考與