2.2鏈表課件-高中信息技術(shù)浙教版選修1

2.2鏈表導(dǎo)入小華規(guī)劃自駕游路線，出發(fā)地為杭州，目的地為北京，在規(guī)劃過程中經(jīng)過了多次更改。第一次依次加入的途徑地為上海、蘇州、南京、濟南、石家莊；第二次在南京和濟南之間加入了途徑地青島，取消了途徑地南京；用數(shù)組來實現(xiàn)其更改過程。杭州上海蘇州南京濟南石家莊北京青島導(dǎo)入小華規(guī)劃自駕游路線，出發(fā)地為杭州，目的地為北京，在規(guī)劃過程中經(jīng)過了多次更改。第一次依次加入的途徑地為上海、蘇州、南京、濟南、石家莊；第二次在南京和濟南之間加入了途徑地青島，取消了途徑地南京；用數(shù)組來實現(xiàn)其更改過程。杭州上海蘇州南京濟南石家莊北京青島數(shù)組的缺點：插入和刪除元素操作需要移動大量的元素頻繁增、刪數(shù)據(jù)導(dǎo)致數(shù)據(jù)規(guī)模不穩(wěn)，形成存儲空間“碎片”需要限定最大空間，造成資源浪費鏈表適用于當數(shù)據(jù)規(guī)模不確定或初始時確定但在處理過程中由于頻繁增、刪數(shù)據(jù)導(dǎo)致數(shù)據(jù)規(guī)模不穩(wěn)定的問題。鏈表基本概念鏈表指的是將需要處理的數(shù)據(jù)對象以節(jié)點的形式，通過指針串聯(lián)在一起的一種數(shù)據(jù)結(jié)構(gòu)。鏈表基本概念：鏈表節(jié)點結(jié)構(gòu)保存數(shù)據(jù)元素保存相鄰節(jié)點的存儲地址頭指針（head）作用：一是鏈表的入口，只有通過頭指針才能進入鏈表二是為循環(huán)鏈表設(shè)立一個邊界，便于數(shù)據(jù)處理時的邊界判斷和處理鏈表基本概念根據(jù)每個節(jié)點中指針的數(shù)量分為：單向鏈表：雙向鏈表：循環(huán)鏈表：第一個節(jié)點和最后一個節(jié)點使用指針鏈接，這樣就形成了循環(huán)鏈表。next吳堅黃剛王林李豐headnextnextnext鏈表基本概念單向鏈表中各個節(jié)點在內(nèi)存中可以隨意存儲，每個節(jié)點使用指針指向其后繼節(jié)點的存儲地址。進入鏈表只能通過頭指針head，其他節(jié)點則需要經(jīng)過所有在它之前的節(jié)點才可以訪問，尾結(jié)點的指針指向為null，表示指向為空。鏈表基本概念鏈表的特性（1）同一鏈表中每個節(jié)點的結(jié)構(gòu)均相同數(shù)據(jù)類型相同指針數(shù)量和功能相同（2）每個鏈表必定有一個頭指針，以實現(xiàn)對鏈表的引用和邊界處理head（3）鏈表占用的空間不固定練習C鏈表的基本操作鏈表的基本操作有空鏈表的創(chuàng)建、節(jié)點訪問、節(jié)點的插入和刪除。Python中沒有直接定義鏈表結(jié)構(gòu)，可以使用其提供的列表來模擬實現(xiàn)。用列表的索引來代替地址指針，并規(guī)定列表索引均為正索引，當某個指針區(qū)域值為-1時表示指向為空，該節(jié)點為尾節(jié)點。a=[[“天津”,2],[“杭州”,3],[“北京”,-1],[“上海”,0]]head=1天津2杭州3北京-1上海00123head→鏈表的創(chuàng)建其中head值為–1，表示頭指針指向為空，該鏈表為空鏈表。創(chuàng)建鏈表時，首先要根據(jù)問題特點規(guī)劃節(jié)點的數(shù)據(jù)域和指針域，然后根據(jù)規(guī)劃創(chuàng)建一個空表和頭節(jié)點。接下來就可以根據(jù)輸入的實際數(shù)據(jù)形成節(jié)點并逐步插入到已有的鏈表中。Item=[]Head=-1鏈表的訪問鏈表只能通過頭指針（head）進行訪問，其他節(jié)點通過節(jié)點間的指針依次訪問。如圖，當想訪問單向鏈表中data3所在的節(jié)點時，需通過頭指針進入鏈表，再分別按照各個節(jié)點的指針指向經(jīng)過data1和data2所在節(jié)點，最后通過data2所在節(jié)點的指針才能訪問data3所在的節(jié)點。鏈表的插入3Newdatadata1data22data3-1head在單向鏈表data1和data2所處節(jié)點的中間位置插入一個新節(jié)點31012鏈表的插入1.在單向鏈表中插入新節(jié)點時，指針指向的修改是否必須有先后？如果將其順序逆轉(zhuǎn)，能否完成新節(jié)點的插入？為什么？Newdatadata1data22data3-1head31012練習5、2鏈表的插入鏈表的插入data[8][1]=data[1][1]data[1][1]=8實現(xiàn)語句：參考上圖，描述出在單向鏈表中插入第一個節(jié)點及尾節(jié)點的過程。鏈表的插入?yún)⒖荚谥虚g插入，描述出在單向鏈表中插入第一個節(jié)點及尾節(jié)點的過程。739-1508132012345head→739-1508132012345head→739-1508132012345head→插入數(shù)字6插入數(shù)字2插入數(shù)字10鏈表的插入?yún)⒖荚谥虚g插入，描述出在單向鏈表中插入第一個節(jié)點及尾節(jié)點的過程。a=[[7,3],[9,-1],[5,0],[8,1],[3,2]]head=4data=int(input())k_a=headq_a=headwhilek_a!=-1:ifdata>=a[k_a][0]:

_________________

_________________

else:ifk_a==head:

___________________

___________________

else:

___________________

___________________

breakifk_a==-1:

___________________

___________________

print(a)k_a=headforiinrange(len(a)):print(____________)___________________

q_a=k_ak_a=a[k_a][1]a.append([data,head])head=len(a)-1a.append([data,k_a])a[q_a][1]=len(a)-1a.append([data,k_a])a[q_a][1]=len(a)-1a[k_a][0]k_a=a[k_a][1]739-1508132012345head→數(shù)據(jù)合并

（1）算法設(shè)計

①初始化兩個空鏈表data_a和data_b，并使用head_a和head_b作為兩個鏈表的頭指針，其中data_a作為存儲結(jié)果的鏈表。②使用隨機函數(shù)randint(start,end)模擬生成兩個降序序列數(shù)據(jù)，生成新的結(jié)點在尾部插入。數(shù)據(jù)合并（1）算法設(shè)計

③使用變量k_a與k_b指向兩個鏈表中未合并的數(shù)據(jù)序列中最前面（值最大）的結(jié)點，初始化k_a=head_a，k_b=head_b，由于在鏈表data_a中需要進行插入結(jié)點的操作，必須記錄插入位置的前驅(qū)結(jié)點，使用變量q_a，初始化q_a=head。重復(fù)以下操作，直到k_a或k_b指向空（即某個鏈表元素全部處理完）：比較data_a[k_a][0]和data_b[k_b][0]的大小。若data_a[k_a][0]≥data_b[k_b][0]，則修改q_a與k_a相等，再將k_a指向下一個結(jié)點；否則將鏈表data_b中k_b指向的結(jié)點插入到鏈表data_a中，作為q_a指向結(jié)點的后繼結(jié)點，再將k_b指向鏈表data_b中的下一個結(jié)點。④若k_b未指向空，則將鏈表data_b剩余結(jié)點按順序插入鏈表data_a的尾部。⑤輸出鏈表data_a中每個結(jié)點的數(shù)據(jù)區(qū)域的值。數(shù)據(jù)合并程序?qū)崿F(xiàn)程序測試結(jié)果fromrandomimportrandintdata_a=[]head_a=-1data_b=[]head_b=-1tmp=randint(95,100)data_a.append([tmp,head_a])head_a=0foriinrange(1,20):tmp=data_a[i-1][0]-randint(1,5)data_a.append([tmp,data_a[i-1][1]])data_a[i-1][1]=iprint("鏈表結(jié)構(gòu)的原始數(shù)據(jù)序列一")print(data_a)鏈表結(jié)構(gòu)的原始數(shù)據(jù)序列一[[99,1],[98,2],[94,3],[93,4],[91,5],[89,6],[85,7],[84,8],[79,9],[75,10],[72,11],[71,12],[66,13],[64,14],[59,15],[54,16],[52,17],[48,18],[44,19],[43,-1]]數(shù)據(jù)合并程序?qū)崿F(xiàn)程序測試結(jié)果tmp=randint(95,100)data_b.append([tmp,head_b])head_b=0foriinrange(1,25):tmp=data_b[i-1][0]-randint(1,5)data_b.append([tmp,data_b[i-1][1]])data_b[i-1][1]=iprint("鏈表結(jié)構(gòu)的原始數(shù)據(jù)序列二")print(data_b)#初始化列表索引k_a=head_aq_a=head_ak_b=head_b鏈表結(jié)構(gòu)的原始數(shù)據(jù)序列二[[98,1],[95,2],[93,3],[91,4],[90,5],[89,6],[84,7],[80,8],[79,9],[75,10],[71,11],[69,12],[68,13],[63,14],[58,15],[56,16],[52,17],[47,18],[42,19],[41,20],[38,21],[34,22],[32,23],[29,24],[24,–1]]數(shù)據(jù)合并程序?qū)崿F(xiàn)程序測試結(jié)果while(k_a!=-1andk_b!=-1):ifdata_a[k_a][0]>=data_b[k_b][0]:q_a=k_ak_a=data_a[k_a][1]else:ifk_a==head_a:#在鏈表data_a的頭部插入結(jié)點data_a.append([data_b[k_b][0],head_a])head_a=len(data_a)-1q_a=head_ak_b=data_b[k_b][1]else:data_a.append([data_b[k_b][0],k_a])data_a[q_a][1]=len(data_a)-1q_a=data_a[q_a][1]k_b=data_b[k_b][1]99198294393491-101234567head→98195293390-10123head→數(shù)據(jù)合并程序?qū)崿F(xiàn)程序測試結(jié)果whilek_b!=-1:data_a.append([data_b[k_b][0],-1])data_a[q_a][1]=len(data_a)-1q_a=data_a[q_a][1]k_b=data_b[k_b][1]print("鏈表結(jié)構(gòu)的合并后數(shù)據(jù)序列")print(data_a)print("按鏈表鏈接順序輸出數(shù)據(jù)序列")tmp=head_awhiledata_a[tmp][1]!=-1:print(data_a[tmp][0],end="")tmp=data_a[tmp][1]print(data_a[tmp][0])鏈表結(jié)構(gòu)的合并后數(shù)據(jù)序列[[99,1],[98,20],[94,3],[93,22],[91,23],[89,25],[85,7],[84,26],[79,28],[75,29],[72,11],[71,30],[66,13],[64,33],[59,34],[54,16],[52,36],[48,37],[44,19],[43,38],[98,21],[95,2],[93,4],[91,24],[90,5],[89,6],[84,27],[80,8],[79,9],[75,10],[71,31],[69,32],[68,12],[63,14],[58,35],[56,15],[52,17],[47,18],[42,39],[41,40],[38,41],[34,42],[32,43],[29,44],[24,–1]]按鏈表鏈接順序輸出數(shù)據(jù)序列999898959493939191908989858484807979757572717169686664635958565452524847444342413834322924鏈表的刪除data1data22data3-1head將單向鏈表data1和data3中間的節(jié)點刪除掉10122鏈表的插入?yún)⒖荚谥虚g插入，描述出在單向鏈表中插入第一個節(jié)點及尾節(jié)點的過程。739-1508132012345head→739-1508132012345head→739-1508132012345head→插入數(shù)字6插入數(shù)字2插入數(shù)字10鏈表的刪除參考鏈表的插入，描述出在單向鏈表中刪除第一個節(jié)點、中間節(jié)點及尾節(jié)點的過程。739-150813201234head→739-150813201234head→739-150813201234head→刪除第一個節(jié)點刪除第3個節(jié)點刪除最后一個節(jié)點鏈表的插入?yún)⒖兼湵淼牟迦?，描述出在單向鏈表中刪除第一個節(jié)點、中間節(jié)點及尾節(jié)點的過程。a=[[7,3],[9,-1],[5,0],[8,1],[3,2]]head=4wz=int(input())k_a=headq_a=headc=0whilek_a!=-1:c=c+1ifc==wz:ifq_a==head:

____________________

else:

____________________

breakelse:

________________________

________________________

print(a)k_a=headforiinrange(len(a)):ifk_a!=-1:print(a[k_a][0])k_a=a[k_a][1]head=a[q_a][1]a[q_a][1]=a[k_a][1]q_a=k_ak_a=a[q_a][1]739-1508132012345head→練習B鏈表節(jié)點的訪問與遍歷（1）抽象與建模該問題中的關(guān)鍵數(shù)據(jù)是n個參與人員的初始編號，1至n的序列。從編號1開始計數(shù)，每過一個編號加1，當計數(shù)到m時將該編號從數(shù)據(jù)序列中移除，并從該編號的后一編號從1開始重新計數(shù)。而當計數(shù)到序列中最后一個編號，又從序列的開始編號繼續(xù)計數(shù)，從而將計數(shù)序列構(gòu)成一個環(huán)。重復(fù)這個過程，直到序列中只剩一個編號，該編號即為最后剩下人員的初始編號。鏈表節(jié)點的訪問與遍歷（2）設(shè)計數(shù)據(jù)結(jié)構(gòu)與算法該問題中數(shù)據(jù)規(guī)模在初始時可以確定（最大為n），但是在數(shù)據(jù)處理過程中需要按照規(guī)則不斷地移除數(shù)據(jù)，直至只剩一個為止。也就是說，數(shù)據(jù)規(guī)模在處理過程中逐漸變小，呈現(xiàn)不穩(wěn)定的特性，符合鏈表的應(yīng)用。

由于最終需要輸出初始編號信息，所以鏈表每個結(jié)點中數(shù)據(jù)區(qū)域用來保存初始編號，指針區(qū)域需要一個用來保存指向后繼結(jié)點的指針。同時由于序列中最大編號報數(shù)后會從序列中最小編號繼續(xù)報數(shù)，所以可以采用單向循環(huán)鏈表來組織數(shù)據(jù)?；阪湵磉@種數(shù)據(jù)結(jié)構(gòu)的設(shè)計，可以設(shè)計出相應(yīng)的算法如下：鏈表節(jié)點的訪問與遍歷算法如下：①創(chuàng)建一個由n個結(jié)點