資源簡介

(共29張PPT)
2.2 鏈表
課前學(xué)習(xí)任務(wù)
結(jié)合數(shù)組的特性和基本操作，針對如下例子設(shè)計數(shù)組以組織和存儲關(guān)鍵數(shù)據(jù)：
① 處理全班同學(xué)的信息，時常需要進行信息訪問；
② 處理學(xué)校外來人員信息，進校時登記信息，出校時移除信息。
鏈表基本概念
鏈表是將需要處理的數(shù)據(jù)對象以節(jié)點的形式，通過指針串聯(lián)在一起的一種數(shù)據(jù)結(jié)構(gòu)。
節(jié)點結(jié)構(gòu)
數(shù)據(jù)區(qū)域 指針區(qū)域
保存數(shù)據(jù)元素
保存相鄰節(jié)點的存儲地址
某節(jié)點
后繼節(jié)點
前驅(qū)節(jié)點
鏈表基本概念
根據(jù)節(jié)點中指針的數(shù)量可以分為:
單向鏈表：
雙向鏈表：
循環(huán)鏈表：
data next
prev data next
data next
datan nextn
···
鏈表的特性
① 鏈表占用的空間不固定；
② 每個鏈表中一般要有一個頭指針，以實現(xiàn)鏈表的引用和邊界處理；
③ 同一鏈表中每個節(jié)點的結(jié)構(gòu)均相同。
存儲地址 數(shù)據(jù)區(qū)域 后繼指針
0 “黃剛” 1
1 “李豐” -1
2 “王林” 0
3 “吳堅” 2
單鏈表存儲結(jié)構(gòu)
head
單鏈表示意圖
吳堅
2
第一個節(jié)點
head
王林
0
第二個節(jié)點
黃剛
1
第三個節(jié)點
李豐
-1
第四個節(jié)點
（尾節(jié)點）
請同學(xué)們暫停視頻，嘗試并完成“學(xué)習(xí)任務(wù)單”中的“學(xué)習(xí)任務(wù)一”。
【學(xué)習(xí)任務(wù)一】認識鏈表
為了滿足鏈表能在兩個方向都能進行遍歷的需求，請在圖1為每個節(jié)點補充正確的前驅(qū)指針。
存儲地址 數(shù)據(jù)區(qū)域 前驅(qū)指針 后繼指針
0 “黃剛” 1
1 “李豐” -1
2 “王林” 0
3 “吳堅” -1 2
圖1 雙向鏈表存儲結(jié)構(gòu)圖
head
單鏈表示意圖
吳堅
2
第一個節(jié)點
地址3
head
王林
0
第二個節(jié)點
地址2
黃剛
1
第三個節(jié)點
地址0
李豐
-1
第四個節(jié)點
地址1
3
2
0
【小要求】與數(shù)組的相關(guān)操作進行比較，各自的操作效率誰優(yōu)誰劣？為什么？
鏈表的基本操作
鏈表創(chuàng)建
節(jié)點訪問
節(jié)點插入
節(jié)點刪除
鏈表的基本操作——鏈表創(chuàng)建
數(shù)據(jù)區(qū)域 后繼指針
鏈表結(jié)構(gòu)：
“姓名+手機號”
頭指針head：指向第一個節(jié)點
單向鏈表
校外人員進出登記：信息插入和刪除
鏈表的基本操作——節(jié)點插入
data1 next1
data2 next2
data3 next3
修改新節(jié)點和前驅(qū)節(jié)點的指針
data1 next1
data3 next3
data2 -1
data3 next3
head
插入到第一個節(jié)點之前
插入尾節(jié)點之后
-1
next2
修改新節(jié)點指針和頭指針
修改新節(jié)點和前驅(qū)節(jié)點的指針
插入到兩個節(jié)點之間
①“李彤”入校；
存儲地址 數(shù)據(jù)區(qū)域 后繼指針
0 “杜剛+1xx.” -1
1 “張強+1xx.” 0
head
2 “李彤+1xx.” -1
2
張強
0
head
杜剛
-1
李彤
-1
新節(jié)點
2
鏈表的基本操作——節(jié)點插入
②“李豐”在“杜剛”之前入校；
存儲地址 數(shù)據(jù)區(qū)域 后繼指針
0 “杜剛+1xx.” 2
1 “張強+1xx.” 0
2 “李彤+1xx.” -1
head
3 “李豐+1xx.” 0
3
張強
0
head
杜剛
2
鏈表的基本操作——節(jié)點插入
李彤
-1
李豐
0
新節(jié)點
3
data1 next
data2 next
data3 next
刪除中間節(jié)點
修改前驅(qū)節(jié)點的后繼指針，讓待刪節(jié)點的前驅(qū)和后繼直接相連
鏈表的基本操作——節(jié)點刪除
data2 next
data3 next
data1 next
data2 next
刪除第一個節(jié)點
head
刪除最后一個節(jié)點
請同學(xué)們暫停視頻，嘗試并完成“學(xué)習(xí)任務(wù)單”上“【學(xué)習(xí)任務(wù)二】鏈表基本操作”。
【學(xué)習(xí)任務(wù)二】鏈表基本操作
存儲地址 數(shù)據(jù)區(qū)域 后繼指針
0 “杜剛+1xx.” 2
1 “張強+1xx.” 3
2 “李彤+1xx.” -1
3 “李豐+1xx.” 0
（1）“杜剛”出校，請在如下繪制節(jié)點鏈接關(guān)系，并在上述存儲結(jié)構(gòu)圖中進行相應(yīng)修改：
head
張強
3
head
杜剛
2
李彤
-1
李豐
0
2
2
【學(xué)習(xí)任務(wù)二】鏈表基本操作
存儲地址 數(shù)據(jù)區(qū)域 后繼指針
1 “張強+1xx.” 3
2 “李彤+1xx.” -1
3 “李豐+1xx.” 2
（2）“胡潔”在“張強”之前入校，請在如下修改節(jié)點鏈接關(guān)系，并在上述存儲結(jié)構(gòu)圖中進行相應(yīng)修改
head
張強
3
head
李彤
-1
李豐
2
4 “胡潔+1xx.” 1
胡潔
1
head
【學(xué)習(xí)任務(wù)二】鏈表基本操作
（3）“李彤”出校，請在如下修改節(jié)點鏈接關(guān)系，并在上述存儲結(jié)構(gòu)圖中進行相應(yīng)修改：
胡潔
1
head
李豐
2
李彤
-1
張強
3
存儲地址 數(shù)據(jù)區(qū)域 后繼指針
1 “張強+1xx.” 3
2 “李彤+1xx.” -1
3 “李豐+1xx.” 2
4 “胡潔+1xx.” 1
head
-1
-1
【學(xué)習(xí)任務(wù)二】鏈表基本操作
（4）“胡潔”出校，請在如下修改節(jié)點鏈接關(guān)系，并在上述存儲結(jié)構(gòu)圖中進行相應(yīng)修改：
胡潔
1
head
李豐
-1
張強
3
存儲地址 數(shù)據(jù)區(qū)域 后繼指針
1 “張強+1xx.” 3
3 “李豐+1xx.” -1
4 “胡潔+1xx.” 1
head
head
操作 數(shù)組 鏈表
訪問
插入
刪除
較高
與數(shù)組的操作做比較，各自的操作效率（選填：較高/較低）
較高
較高
較低
較低
較低
【學(xué)習(xí)任務(wù)二】鏈表基本操作
請同學(xué)們暫停視頻，嘗試并完成“學(xué)習(xí)任務(wù)單”上“【學(xué)習(xí)任務(wù)三】實踐鞏固——約瑟夫問題”。
【學(xué)習(xí)任務(wù)三】實踐鞏固——約瑟夫問題
n個人排成一圈，從某個人開始，按照順時針方向從1開始依次編號。從編號為1的人開始順時針“1，2，3，···，m，1，2，3，···，m”報數(shù)，報到m（m大于1）的人退出圈子。這樣不斷循環(huán)下去，圈子里的人數(shù)將不斷減少。由于人數(shù)是有限的（n個），因此最終會只剩下一個人，試問最后剩下的人的初始編號是多少？
分析上述問題，按照如下步驟進行實踐：
（1）抽象與建模
該問題中的關(guān)鍵數(shù)據(jù)是：
簡述問題解決的計算模型：
所有人員的初始編號
① 形成1.2.3...n的循環(huán)序列
② 從編號1開始計數(shù)，每過1個編號計數(shù)值加1，當計數(shù)到m時將該編號從循環(huán)序列中移除；并從該編號循環(huán)后一編號從1開始重新計數(shù)。重復(fù)這個過程，直到循環(huán)序列中只剩下一個編號，該編號即為最后剩下人員的初始編號。
分析上述問題，按照如下步驟進行實踐：
（2）設(shè)計鏈表與算法
鏈表設(shè)計：
鏈表中節(jié)點的數(shù)據(jù)區(qū)域保存
指針區(qū)域保存
【學(xué)習(xí)任務(wù)三】實踐鞏固——約瑟夫問題
初始編號
后繼節(jié)點地址
單向循環(huán)鏈表
尾節(jié)點指針區(qū)域指向第一個節(jié)點
頭指針指向編號1所在節(jié)點
（2）設(shè)計鏈表與算法
算法設(shè)計
【學(xué)習(xí)任務(wù)三】實踐鞏固——約瑟夫問題
①從第一個節(jié)點開始報數(shù)，每過1個節(jié)點報數(shù)值加1，將計到m的鏈表節(jié)點刪除；繼續(xù)從后繼節(jié)點開始，重新從1報數(shù)。重復(fù)這個過程，直至鏈表中只剩下一個節(jié)點。
②此時頭指針所指節(jié)點中的數(shù)據(jù)區(qū)域即保存了最終留下的初始編號。
存儲地址 數(shù)據(jù)區(qū)域 后繼指針
0 1
1 2
2 3
3 4
4 5
1
2
3
4
0
head
（3）模擬實現(xiàn)
①共5個人圍成圈，創(chuàng)建由5個節(jié)點組成的單循環(huán)鏈表，完善如下存儲結(jié)構(gòu)。
【學(xué)習(xí)任務(wù)三】實踐鞏固——約瑟夫問題
②從鏈表第一個節(jié)點依次報數(shù)，每報到3的節(jié)點從鏈接關(guān)系中刪除。并在上述結(jié)構(gòu)中及時修改相關(guān)節(jié)點的指針。最后留在圈子內(nèi)的初始編號： 。
存儲地址 數(shù)據(jù)區(qū)域 后繼指針
0 1 1
1 2 2
2 3 3
3 4 4
4 5 0
←報數(shù)值：1
←報數(shù)值：2
←報數(shù)值：3
3
←報數(shù)值：1
←報數(shù)值：2
←報數(shù)值：3
1
←報數(shù)值：1
←報數(shù)值：2
←報數(shù)值：3
1
←報數(shù)值：1
←報數(shù)值：2
←報數(shù)值：3
3
head
head
【學(xué)習(xí)任務(wù)三】實踐鞏固——約瑟夫問題
4
head
課堂小結(jié)
鏈表
概念
特性
基本操作
應(yīng)用鏈表解決實際問題的一般步驟
第一節(jié)
課后作業(yè)
完成課后作業(yè)練習(xí)

展開更多......

收起↑