22鏈表課件高二上學(xué)期選擇性必修1《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》第二章

導(dǎo)入小華規(guī)劃自駕游路線，出發(fā)地為杭州，目的地為北京，在規(guī)劃過程中經(jīng)過了多次更改。第一次依次加入的途徑地為上海、蘇州、南京、濟(jì)南、石家莊；第二次在南京和濟(jì)南之間加入了途徑地青島，取消了途徑地南京；用數(shù)組來實(shí)現(xiàn)其更改過程。杭州上海蘇州南京濟(jì)南石家莊北京青島導(dǎo)入小華規(guī)劃自駕游路線，出發(fā)地為杭州，目的地為北京，在規(guī)劃過程中經(jīng)過了多次更改。第一次依次加入的途徑地為上海、蘇州、南京、濟(jì)南、石家莊；第二次在南京和濟(jì)南之間加入了途徑地青島，取消了途徑地南京；用數(shù)組來實(shí)現(xiàn)其更改過程。杭州上海蘇州南京濟(jì)南石家莊北京青島數(shù)組的缺點(diǎn)：插入和刪除元素操作需要移動大量的元素頻繁增、刪數(shù)據(jù)導(dǎo)致數(shù)據(jù)規(guī)模不穩(wěn)，形成存儲空間“碎片”需要限定最大空間，造成資源浪費(fèi)鏈表適用于當(dāng)數(shù)據(jù)規(guī)模不確定或初始時(shí)確定但在處理過程中由于頻繁增、刪數(shù)據(jù)導(dǎo)致數(shù)據(jù)規(guī)模不穩(wěn)定的問題。單向鏈表的概念與基本操作信息技術(shù)選考課程一、鏈表的概念與特性1、概念：鏈表指的是將需要處理的數(shù)據(jù)對象以節(jié)點(diǎn)的形式，通過指針串聯(lián)在一起的一種數(shù)據(jù)結(jié)構(gòu)2、節(jié)點(diǎn)結(jié)構(gòu)保存數(shù)據(jù)元素保存相鄰結(jié)點(diǎn)的存儲地址一個(gè)鏈表的節(jié)點(diǎn)一、鏈表的概念與特性杭州next上海next蘇州next南京-1head（頭指針）單向鏈表head稱為

，data1節(jié)點(diǎn)稱為data2節(jié)點(diǎn)的

，data3節(jié)點(diǎn)稱為data2節(jié)點(diǎn)的

。頭指針（表頭）前驅(qū)節(jié)點(diǎn)后繼節(jié)點(diǎn)3、頭指針作用tail(1)鏈表的入口，只有通過頭指針才能進(jìn)入鏈表。(2)為循環(huán)鏈表設(shè)立一個(gè)邊界，便于數(shù)據(jù)處理時(shí)的邊界判斷和處理。一、鏈表的概念與特性4、分類？？杭州next上海next蘇州-1head①單向鏈表：當(dāng)只有一個(gè)指針用來指向其后繼節(jié)點(diǎn)。pre杭州nexthead②雙向鏈表：有兩個(gè)指針分別用于指向其前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)。pre上海nextpre蘇州-1一、鏈表的概念與特性4、分類？？杭州next上海next蘇州-1head③循環(huán)鏈表：把第一節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)使用指針連接（約瑟夫環(huán)）。pre杭州nextheadpre上海nextpre蘇州-1基于單鏈的循環(huán)鏈表基于雙鏈的循環(huán)鏈表一、鏈表特性同一鏈表中每個(gè)節(jié)點(diǎn)的結(jié)構(gòu)均相同每個(gè)節(jié)點(diǎn)的數(shù)據(jù)區(qū)域的數(shù)據(jù)類型相同，指針區(qū)域中的指針數(shù)量和功能是相同的。每個(gè)鏈表必定有一個(gè)頭指針，以實(shí)現(xiàn)對鏈表的引用和邊界處理鏈表的頭指針使用變量head表示，用來進(jìn)入鏈表。當(dāng)訪問鏈表中某一節(jié)點(diǎn)，只能從頭指針開始，通過指針鏈接依次訪問，不能像數(shù)組那樣使用下標(biāo)直接引用。

對于循環(huán)鏈表，一輪訪問的開始和結(jié)束都可以用借助頭指針指向位置來進(jìn)行判斷，即邊界處理。鏈表占用的空間不固定

鏈表的節(jié)點(diǎn)間是通過指針鏈接，相鄰節(jié)點(diǎn)存儲時(shí)不需要連續(xù)的空間。所以鏈表的存儲空間由節(jié)點(diǎn)數(shù)決定，改變節(jié)點(diǎn)數(shù)就能改變鏈表的存儲空間。二、鏈表的基本操作（創(chuàng)建/訪問/插入/刪除）單向鏈表的創(chuàng)建（用python二維列表模擬）a=[]head=-1#head值為-1，表示頭指針指向?yàn)榭?，該鏈表為空鏈表a=[["杭州",1],["上海",3],["蘇州",-1],["南京",2],["嘉興",0]]head=4#創(chuàng)建一個(gè)擁有5個(gè)節(jié)點(diǎn)的單向鏈表列表中有5個(gè)元素：

["杭州",1]、["上海",3]、["蘇州",-1]、["南京",2]、["嘉興",0]a[p]表示一個(gè)節(jié)點(diǎn)

如：a[4]=[“嘉興”,0]a[p][0]表示該節(jié)點(diǎn)的數(shù)據(jù)域

如：a[4][0]=“嘉興”a[p][1]表示該節(jié)點(diǎn)的指針（即索引）

如：a[4][1]=0datanext杭州1上海3蘇州-1南京2嘉興001234head→二、鏈表的基本操作（創(chuàng)建/訪問/插入/刪除）#輸出鏈表的所有節(jié)點(diǎn)數(shù)據(jù)data=[["杭州",1],["上海",3],["蘇州",-1],["南京",2],["嘉興",0]]head=4display(data,head)鏈表的訪問（遍歷）嘉興

杭州

上海

南京

蘇州datanext杭州1上海3蘇州-1南京2嘉興001234head→二、鏈表的基本操作（創(chuàng)建/訪問/插入/刪除）#輸出鏈表的所有節(jié)點(diǎn)數(shù)據(jù)data=[["杭州",1],["上海",3],["蘇州",-1],["南京",2],["嘉興",0]]head=4display(data,head)鏈表的訪問（遍歷）嘉興

杭州

上海

南京

蘇州defdisplay(data,head):p=headwhiledata[p][1]!=-1:print(data[p][0],end=“->")

p=data[p][1]print(data[p][0])datanext杭州1上海3蘇州-1南京2嘉興001234head→二、鏈表的基本操作（創(chuàng)建/訪問/插入/刪除）在鏈表頭部插入一個(gè)新節(jié)點(diǎn)索引datanext0杭州11上海32蘇州-13南京24嘉興0head5溫州4溫州

嘉興

杭州

上海

南京

蘇州嘉興next杭州next上海nexthead溫州next南京next蘇州next二、鏈表的基本操作（創(chuàng)建/訪問/插入/刪除）在鏈表的索引p=3之后插入一個(gè)新節(jié)點(diǎn)索引datanext0杭州11上海32蘇州-13南京24嘉興0head5溫州25data1nextdata2nextdata3-1headnewnext嘉興

杭州

上海

南京

溫州

蘇州二、鏈表的基本操作（創(chuàng)建/訪問/插入/刪除）在鏈表的索引p=3之前插入一個(gè)新節(jié)點(diǎn)data=[[6,1],[9,3],[10,-1],[8,2],[7,0]]pre_p=head=4p,newdata=3,5whiledata[pre_p][1]!=p:pre_p=data[pre_p][1]data.append([newdata,data[pre_p][1]])data[pre_p][1]=len(data)-1索引datanext061193210-1382470head55376958105data1nextdata2nextdata3-1headnewnextppre_p二、鏈表的基本操作（創(chuàng)建/訪問/插入/刪除）在鏈表的尾部插入一個(gè)新節(jié)點(diǎn)索引datanext0杭州11上海

32蘇州-13南京24嘉興0head5溫州-176981055data1nextdata2nextdata3-1headnew-1next二、鏈表的基本操作（創(chuàng)建/訪問/插入/刪除）刪除鏈表中索引為p的節(jié)點(diǎn)data1nextdata2nextdata3-1head索引datanext061193210-1382470head769102刪除的位置：頭結(jié)點(diǎn)中間節(jié)點(diǎn)尾結(jié)點(diǎn)#刪除索引為p的節(jié)點(diǎn)，返回鏈表新的頭指針headdefdel_node(data,p):globalheadifp==head: #刪除頭結(jié)點(diǎn),修改頭指針head=data[head][1]else:pre=head #pre為節(jié)點(diǎn)p的前驅(qū)節(jié)點(diǎn)whiledata[pre][1]!=panddata[pre][1]!=-1:pre=data[pre][1]ifdata[pre][1]==p:data[pre][1]=data[p][1]else:print("該節(jié)點(diǎn)不存在！")returnhead三、鏈表的應(yīng)用–數(shù)據(jù)合并97193287367-198195292388460-1鏈表data_a鏈表data_b思考：兩個(gè)鏈表的數(shù)據(jù)合并需要和數(shù)組的方法一樣嗎？數(shù)組訪問快，插入慢鏈表訪問慢，插入快三、鏈表的應(yīng)用–數(shù)據(jù)合并97193287367-198195292388460-1head_ahead_bk_ak_b情況1：插入到鏈表a的表頭位置。情況2：插入到鏈表a的中間位置。那如何知道當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)？情況3：鏈表b還有數(shù)據(jù)剩余。pre_a#初始化head_a=head_b=0k_a,k_b=head_a,head_bpre_a=head_a #鏈表a當(dāng)前節(jié)點(diǎn)的前驅(qū)節(jié)點(diǎn)97193287367-198195292388460-1head_ahead_bk_ak_bpre_awhilek_a!=-1andk_b!=-1:ifdata_a[k_a][0]>=data_b[k_b][0]:pre_a=k_ak_a=data_a[k_a][1]else:ifk_a==head_a:#頭部插入

data_a.append([data_b[k_b][0],head_a]) #將數(shù)據(jù)添加到列表尾head_a=len(data_a)–1 #更新頭指針pre_a=head_a #更新前驅(qū)節(jié)點(diǎn)k_b=data_b[k_b][1] #鏈表b指針指向下一個(gè)節(jié)點(diǎn)else: #中間插入

data_a.append([data_b[k_b][0],data_a[pre_a][1]])data_a[pre_a][1]=len(data_a)-1pre_a=data_a[pre_a][1] k_b=data_b[k_b][1]whilek_b!=-1: #鏈表b還有剩余數(shù)據(jù)未插入data_a.append(