資源簡介

(共26張PPT)
2.2 鏈表（第二課時）
單擊此處添加副標題
鏈表的創建
可以使用如下Python代碼創建一個空鏈表：
head = -1
#頭指針指向-1，表示鏈表為空
#創建一個空鏈表Item
頭指針變量head：存儲鏈表第一個節點在列表中的索引
Item = [ ]
鏈表的創建
節點
列表模擬單向鏈表的節點：
data next
根據實際問題的特點規劃好節點的數據區域和指針區域
列表
[data,next]
Item.append([data,next])
通過列表的append( )函數將節點保存到列表中
#索引：len(Item)-1
單向鏈表的創建
Item = [ [“張強”, ] , [“杜剛”, ] ]
head = _______
#存儲第一個節點在列表中的索引
1
-1
索引0
索引1
張強
head
杜剛
0
單向鏈表節點的訪問
鏈表中訪問指定節點只能通過頭指針指向的第一個節點開始訪問，其他節點通過節點間的指針依次訪問。
data1
data2
data3
head
data4
訪問變量
訪問變量
訪問變量
訪問變量
訪問變量== -1 ：訪問完最后一個節點
訪問變量：當前訪問節點在列表中的索引
Item = [ [“杜剛”, 2 ] , [“杜強”, 3 ]，
[“李彤”, -1 ] , [“李豐”, 0 ]]
head = 1
#依次訪問并輸出鏈表各節點數據
p=head #訪問變量，表示當前訪問節點的索引
print(Item[p][0],end=” ”) #輸出當前節點數據
p=Item[p][1] #訪問變量迭代更新為后繼的
#按照p的功能：
當前訪問節點的數據區域為：
當前訪問節點的后繼指針為：
Item[p][0]
Item[p][1]
Item = [ [“杜剛”, 2 ] , [“杜強”, 3 ]，
[“李彤”, -1 ] , [“李豐”, 0 ]]
head = 1
#依次訪問并輸出鏈表各節點數據
p=head #訪問變量，表示當前訪問節點的索引
#按照p的功能：
當前訪問節點的數據區域為：
當前訪問節點的后繼指針為：
Item[p][0]
while p!=-1:
print(Item[p][0],end=” ”) #輸出當前節點數據
p=Item[p][1] #訪問變量迭代更新為后繼的
Item[p][1]
杜強 李豐 杜剛 李彤
Item = [ [“杜剛”, 2 ] , [“杜強”, 3 ]，
[“李彤”, -1 ] , [“李豐”, 0 ]]
head = 1
#依次訪問并輸出鏈表各節點數據
p=head #訪問變量，表示當前訪問節點的索引
#按照p的功能：
當前訪問節點的數據區域為：
當前訪問節點的后繼指針為：
Item[p][1]
while p!=-1 :
print(Item[p][0],end=” ”) #輸出當前節點數據
p=Item[p][1] #訪問變量迭代更新為后繼的
p!= -1 and Item[p][0]!=”杜剛” ：
杜強 李豐
Item[p][0]
單向鏈表節點的插入
data1 next1
data3 next3
head
data1 next1
data2 next2
data3 next3
插入到鏈表最前面
data2 -1
data3 next3
-1
next2
插入到相鄰兩個節點之間
插入到鏈表最后面
單向鏈表節點的插入
data1 next1
data3 next3
head
插入到鏈表最前面
#新節點
Item[r][1] = head
#頭指針
head = r
已知鏈表的第一個節點的索引保存在head變量上，新節點在列表中的索引是r
索引r
單向鏈表節點的插入
插入到鏈表相鄰兩個節點之間
data1 next1
data2 next2
data3 next3
某相鄰兩個節點在列表中索引分別為pre和p，在其之間插入一個新節點；新節點在列表中索引為r
#新節點
Item[r][1] = p
#前驅節點
Item[pre][1] = r
索引pre
索引r
索引p
單向鏈表節點的插入
插入到鏈表最后面
#新節點
Item[r][1] = -1
#前驅節點
Item[p][1] = r
已知鏈表的最后一個節點的索引為p，新節點在列表中的索引是r
data2 -1
data3 -1
-1
索引r
r
單向鏈表節點的刪除
data1 next
data2 next
data3 next
data2 next
data3 -1
data1 next
data2 next
刪除第一個節點
head
刪除中間節點
刪除最后一個節點
單向鏈表節點的刪除
變量head保存了第一個節點在列表中索引
#頭指針
head = Item [head] [1]
刪除第一個節點
data1 next
data2 next
head
單向鏈表節點的刪除
data1 next
data2 next
data3 next
待刪除節點在列表中索引為p，其前驅節點在列表列表中索引為pre
索引pre
索引p
#前驅節點
Item[pre][1] = Item [p] [1]
刪除中間節點
單向鏈表節點的刪除
待刪除節點的前驅節點在列表中索引為pre
#前驅節點
Item[pre][1] = -1
刪除最后一個節點
data2 next
data3 -1
索引pre
-1
請同學們暫停視頻，回顧單向鏈表基本操作的實現，嘗試并完成“學習任務單”：一、體驗系統的基本功能。
簡易外來人員進出校園登記系統
入校登記
出校移除
按進校時間查看還在校內的外來人員
簡易外來人員進出校園登記系統基本功能架構圖
節點規劃
姓名+手機號 后繼指針
Item = [ ]
head = -1
（1）創建空鏈表，鏈表名為Item，頭指針為head
節點實現:
[姓名+手機號，后繼指針]
（2）杜剛、張強、李彤三人依次進校
將新節點插入到鏈表末尾
姓名+手機號 后繼指針
或者len(Item)-1
[data1,-1]
head=0
節點實現:
[姓名+手機號，后繼指針]
（2）杜剛、張強、李彤三人依次進校
將新節點插入到鏈表末尾
姓名+手機號 后繼指針
或len(Item)-1
Item[0][1]=1
node=[data2,-1] #在鏈表末尾插入節點，所以新節點后繼指針為-1
Item.append(node)#將新節點保存到列表中，索引為1
（2）杜剛、張強、李彤三人依次進校
將新節點插入到鏈表末尾
len(Item)-1
或len(Item)-1
Item[1][1]=2
node=[data3,-1] #在鏈表末尾插入節點，所以新節點后繼指針為-1
Item.append(node)#將新節點保存到列表中，索引為2
單鏈表中刪除指定節點節點
（3）李彤、杜剛依次出校
訪問到該節點的前驅節點→刪除節點
訪問到李彤所在節點時結束訪問：
·p變量保存了待刪節點的索引
·pre保存了前驅節點的索引
if p==head:#刪除第一個節點
head=Item[p][1]
elif Item[p][1]==-1:#刪除最后一個節點
Item[pre][1]=-1
else:#刪除中間節點
Item[pre][1]=Item[p][1]
（3）李彤、杜剛依次出校
（4）按進校時間查看在校內人員
遍歷單向鏈表
課堂小結
用列表模擬單向鏈表的基本操作
應用鏈表編程解決實際問題
【鞏固練習】完成課后作業練習
【拓展練習】回顧課堂上的實踐過程和程序，嘗試在資源包中“簡易外來人員進出登記系統.py”文件繼續完善項目。
課后作業

展開更多......

收起↑