資源簡介

(共102張PPT)
課時2　鏈表
第二章　數組與鏈表
1.理解數組和鏈表的概念和特性。2.掌握數組和鏈表的基本操作。3.能運用數組和鏈表編程解決實際問題。
目 錄
CONTENTS
知識梳理
01
例題精析
02
隨堂檢測
03
鞏固與提升
04
知識梳理
1
1.鏈表的概念
(1)鏈表指的是將需要處理的數據對象以______的形式，通過______串聯在一起的一種數據結構。
(2)每個節點一般包括兩個區域：____________和____________。
(3)每個鏈表有個______——head(也稱頭指針)，是鏈表的入口，也便于循環鏈表在數據處理時的邊界判斷和處理。
節點
指針
數據區域
指針區域
表頭
(4)鏈表的形式
鏈表的形式主要有：____________、____________、____________。
①單向鏈表：只有一個指針用來指向其______節點。單向鏈表如下圖所示。
②雙向鏈表：有兩個指針分別用于指向其______節點和______節點。雙向鏈表如下圖所示。
單向鏈表
雙向鏈表
循環鏈表
后繼
前驅
后繼
③循環鏈表：_________節點和____________節點使用指針鏈接。循環鏈表如下圖所示。
第一個
最后一個
2.鏈表的特性
(1)同一鏈表中每個節點的______均相同，有數據區域和指針區域組成。
(2)每個鏈表必定有一個_________，以實現對鏈表的引用和邊界處理。
(3)鏈表占用的空間_________。
可根據需求增刪節點，提高了存儲空間的利用率。
結構
頭指針
不固定
3.鏈表的基本操作
(1)鏈表的創建
(2)鏈表節點的訪問
鏈表只能通過頭指針進行訪問，其他節點通過節點間的指針依次訪問。
(3)鏈表節點的插入與刪除
插入操作：
插入datax節點
刪除data2節點
(4)鏈表節點的訪問與遍歷
訪問鏈表中的節點時，只能通過頭指針進入鏈表并通過指針鏈接依次訪問，直到找到目標位置上的節點。
4.鏈表的類實現
在Python中，鏈表除了可以使用列表來實現，還可以使用“類”實現?！邦悺笔且环N抽象的數據結構，它將數據及其操作封裝在一起。構造單向鏈表類的具體實現過程如下：
(1)自定義單向鏈表的節點類：
class Node：　　　#定義單鏈表節點類
def__init__(self，data，next＝None)：#初始
化節點包含兩個域self.data、self.next
　 self.data＝data #self.data域保存數據
　self.next＝next #self.next域保存指針，缺省值為None
(2)構造單向鏈表類：
class Link：　　　#定義單向鏈表類Link
　 def __init__(self)：　#初始化空鏈表
　 self.head＝None #空鏈表頭指針指向為空
例題精析
2
A.同一鏈表中每個節點的結構均相同 B.每個鏈表必定有一個頭指針
C.鏈表占用的空間不固定 D.創建的新鏈表中至少要有一個節點
D
解析　本題考查鏈表的基本性質。A選項鏈表節點包含數據區域和指針區域，每個節點中的數據區域中數據類型是相同的。B選項訪問鏈表的某一節點，只能從頭指針開始，依次訪問。C選項鏈表通過指針相連，相信節點存儲時不需要連續空間，因此鏈表空間是不固定的。D選項可以空鏈表，數據區域為空，頭指針為－1。
A.可隨機訪問任一節點
B.插入、刪除操作時不需要移動元素
C.不必事先估計存儲空間
D.所需空間與其長度成正比
解析　本題主要考查的是鏈表的特點。訪問鏈表中的某一節點時，只能從頭指針開始，通過指針鏈接依次訪問。因此答案為A。
A
例2 使用列表模擬單鏈表，其存儲結構如圖所示，遍歷該鏈表，將訪問到的節點的數據域的字符依次連接，得到字符串‘LOVE’，則指針域中的索引值依次為(　　)
解析　本題考查鏈表的構建和遍歷。L的后繼節點為O，因此其指針區域值為1；O的后續為V，指針區域值為0; V的后續為E，指針區域值為2；E為尾節點，因此指針區域值為－1。
C
A.0　1　2　3 B.3　1　0　2
C.2　0?。?　1 D.2　0　1?。?
變式訓練　利用列表模擬非循環鏈表a(可能存在已被刪除的節點)，下列程序運行完畢后，變量p表示尾節點的節點位置是(　　)
B
解析　本題考查鏈表的遍歷。A選項當前節點為p，當遍歷到節點為空時停止遍歷，因此遍歷結束后，p節點為空，其前驅t為尾節點。B選項當前節點為p，若當前節點的指針區域值為－1，結束遍歷，那么當前節點p為尾節點。C選項當前節點從頭節點開始遍歷，a[a[p][1]]指當前節點的后繼節點，若該節點的指針區域值為－1，表示該節點為尾節點，當前節點為尾節點的前驅。D選項鏈表a可能存在已被刪除的節點，因此len(a)的值可能大于節點總數。
例3 有如下 Python 程序段：
a＝[[3，1]，[2，2]，[3，3]，[3，4]，[17，5]，[2，6]，[3，－1]]
p＝head＝0
while p！＝－1:
q＝p
while q！＝－1:
t＝q
q＝a[q][1]
if q?。剑? and a[q][0]＝＝a[p][0]：
　　　　　a[t][1]＝a[q][1]
　　　　　q＝t
p＝a[p][1]
p＝head
while p?。剑?：
print(a[p][0]，end＝' ')
p＝a[p][1]
運行后程序的輸出結果是(　　)
A.3　2　17 B.3　2　17　2
C.3　2　17　2　3 D.17
解析　本題考查鏈表的操作。當a[q]節點上的值與a[p]節點上的值相同時，q指針往后移一位。程序的功能是將與p指針所指示的節點值相同的a[q]節點刪除。指針t的作用是維護了去重后鏈表最后一個節點的位置。輸出鏈表的所有非重復節點。
A
變式訓練　有如下 Python 程序段：
def guess(cur)：
q＝cur
p＝a[cur][1]
while p！＝－1：
if a[p][0]＝＝a[cur][0]：
　　　　 a[q][1]＝a[p][1]
else：
　　　　 q＝p
p＝a[p][1]
a＝[[1，3]，[1，2]，[2，4]，[2，5]，[4，－1]，[3，1]]
head＝0；cur＝head
while cur?。剑?：
print(a[cur][0]，end＝″″)
if a[cur][1]?。剑?：
guess(cur)
cur＝a[cur][1]
運行后，則輸出的結果是(　　)
A.1234 B.1122 C.11223 D.11224
解析　本題考查鏈表節點的刪除。在自定義函數guess中，當前節點p從cur節點的后繼開始，如果后面的元素與cur節點元素值相等，則刪除節點p，因此是從當前節點鏈表中刪除重復的元素。
A
例4 有兩個降序序列的鏈表 a，b?，F將鏈表 b 中的數據合并到鏈表 a，形成一個新的降序序列存于鏈表 a，實現數據合并的代碼段如下，
a＝[[98，1]，[96，2]，[95，3]，[93，4]，[90，－1]]
b＝[[99，1]，[97，2]，[94，3]，[93，4]，[92，－1]]
head_a＝head_b＝0
pre＝p＝head_a；q＝head_b
while q?。剑?：
上述程序段中可選填的語句為：
①a[p][0]>＝b[q][0]　② a[p][0]<＝b[q][0]
③q?、躭en(a)－1?、輀b[p][0]，q]
⑥[b[q][0]，p]
則加框處填寫的語句依次為(　　)
A.①⑥④ B.①⑤④ C.①⑥③ D.②⑥③
解析　本題考查鏈表元素的遍歷和插入操作。程序的功能將鏈表 b 中的數據合并到鏈表 a，形成一個新的降序序列存于鏈表 a。分別遍歷兩個鏈表，若鏈表a當前元素值a[p][0]大于等于鏈表 b當前元素值b[q][0]，則鏈表a向后遍歷，否則把鏈表 b當前元素值b[q][0]插入到鏈表a當前元素前面。由于是要把鏈表 b 中的數據合并到鏈表 a，因此鏈表b遍歷完成后，結束程序。
A
變式訓練　有如下 Python 程序：
def lnkid(n，head):
p＝head
while head?。剑? and _______________：
p＝head
head＝a[head][1]
return p
a＝[[2，2]，[5，3]，[1，－1]，[3，0]，[7，1]]
head＝4
n＝int(input())
p＝lnkid(n，head)
if n>a[head][0]：
a.append([n，head])
head＝len(a)－1
else：
a.append([n，a[p][1]])
_________________
用列表 a 模擬一個降序鏈表，運行程序，輸入自然數 n，則鏈表增加一個新的節點，要使鏈表保持降序，則劃線①②處代碼分別為(　　)
A.①nB.①nC.①nD.①n>a[head][0] ②a[p][1]＝len(a)
B
解析　本題考查鏈表的插入。①自定義函數lnkid的功能是查找n在鏈表中插入位置，head在不斷地向后移動，因此n將和a[head][0]進行比較，當比a[head][0]小時，不斷地向后查找位置。②語句p＝lnkid(n，head)將返回在節點p的后面插入新的數n，因此將修改a[p]節點指針區域值為當前插入點索引。
例5 某編程興趣小組設計了一個點歌模擬程序，功能如下：
運行程序后，從鍵盤輸入“A”，則顯示已點的歌曲列表(歌單)；輸入“B”則可以自行輸入歌曲并添加到歌單以完成點歌；輸入“C”則可以將指定的歌曲置頂等待播放；輸入“D” 則播放當前第一首歌曲，并將該歌曲從列表中刪除；輸入“E”則關閉程序并退出。程序運行界面如下圖所示。
請輸入指令A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：A
God Is a Girl　十年　年少有為　七里香　淡季動物園
請輸入指令A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：B
請輸入歌曲：蘭亭序
請輸入指令A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：B
請輸入歌曲：想自由
請輸入指令A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：A
God Is a Girl　十年　年少有為　七里香　淡季動物園　蘭亭序　想自由
請輸入指令A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：C
請輸入歌曲：七里香
請輸入指令A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：A
七里香　God Is a Girl　十年　年少有為　淡季動物園　蘭亭序　想自由
請輸入指令A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：C
請輸入歌曲：想自由
請輸入指令A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：A
想自由　七里香　God Is a Girl　十年　年少有為　淡季動物園　蘭亭序
請輸入指令A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：D
請輸入指令A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：A
七里香　God Is a Girl　十年　年少有為　淡季動物園　蘭亭序
請輸入指令A—顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：E
Python 代碼如下所示，請在劃線處填入合適的代碼。
data＝[[″十年″，4]，[″淡季動物園″，－1]，[″God Is a Girl″，0]，[″七里香″，1]，[″年少有為″，3]]
head＝2
tail＝1
while True：
cmd＝input(″請輸入指令 A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：″)
if cmd＝＝″A″：
cur＝head
while cur?。剑?:
print(data[cur][0]，end＝″″)
　　　 cur＝data[cur][1]
print()
elif cmd＝＝″B″：
song＝input(″請輸入歌曲：″)
data.append([song，－1])
if head＝＝－1：
　　　head＝tail＝len(data)－1
else：
　　　_______________
　　　tail＝len(data)－1
elif cmd＝＝″C″：
song＝input(″請輸入歌曲：″)
cur＝head
while cur?。剑? and data[cur][0]！＝song:
　　　　pre＝cur
　　　　cur＝data[cur][1]
if cur?。剑? and cur?。絟ead：
　　　_______________
　　　data[cur][1]＝head
　　　head＝cur
　　　if cur＝＝tail：
　　　　_______________
elif cmd＝＝″D″：
if head＝＝tail:
　　　　head＝tail＝－1
else：
　　　_____________
elif cmd＝＝″E″：
break
答案?、賒ata[tail][1]＝len(data)－1 ②data[pre][1]＝data[cur][1]
③tail＝pre ④head＝data[head][1]
解析　本題考查鏈表的操作。①輸入“B”則可以自行輸入歌曲并添加到歌單，新節點插入在尾節點的后面，因此原尾節點應指向新插入的節點，同時更新尾節點。②輸入“C”則可以將指定的歌曲置頂，data[cur][0]值為song表示找到節點cur，pre為cur節點的前驅，將cur移動到頭節點前面，因此需要3步，第1步是將cur的前驅pre指向cur的后繼，第2步是將cur指前原頭節點，第3步是設置新的頭節點為cur。③若cur是原尾節點tail，將cur修改為頭節點后，新的尾節點為cur的前驅。④輸入“D” 則播放當前第一首歌曲，并將該歌曲從列表中刪除，條件head＝＝tail成立表示鏈表中只有一個節點，否則將頭指針向后移動，刪除頭節點。
變式訓練　已知一個有7個節點的單向鏈表，設有頭指針head和尾指針tail，如圖所示，下列操作需要遍歷多個節點的是(　　)
A
A.刪除該鏈表中的最后一個節點
B.刪除該鏈表中的第一個節點
C.在該鏈表第一個節點前插入一個新節點
D.在該鏈表最后一個節點后插入一個新節點
解析　本題考查鏈表的遍歷、插入和刪除操作。A選項刪除該鏈表中的最后一個節點，需修改最后一個節點的前驅節點指針域，因此需遍歷多個節點。B選項只需修改頭指針。C選項修改當前節點的指針值指向原頭節點，并修改頭指針為當前節點。D選項讓原尾節點指向當前節點，并修改尾節點為當前節點。
隨堂檢測
3
1.在單向鏈表中，增加頭指針的目的是(　　)
B
解析　在單向鏈表中，一定有一個頭指針，以實現對鏈表的引用和邊界處理，因此，增加頭指針的目的是算法實現上的方便，因此，答案為B。
A.標識表節點中首節點的位置
B.算法實現上的方便
C.使單向鏈表至少有一個節點
D.說明單向鏈表是線性表的鏈式存儲實現
2.下列關于鏈表的敘述中，正確的是(　　)
D
解析　單鏈表存儲方式地址不連續，元素順序是任意的。因此，答案為D。
A.線性鏈表中的各元素在存儲空間中的位置必須是連續的
B.線性鏈表中的表頭元素一定存儲在其他元素的前面
C.線性鏈表中的各元素在存儲空間中的位置不一定是連續的，但表頭元素一定存儲在其他元素的前面
D.線性鏈表中的各元素在存儲空間中的位置不一定是連續的，且各元素的存儲順序也是任意的
3.某單向鏈表如下圖所示，若要將數據 data3 和data4 同時從鏈表中移除，至少需要修改節點指針的數量是(　　)
A
解析　只需修改data2的指針區域值修改為data4的指針區域值。
A.1 B.2 C.3 D.4
4.某 Python 程序段如下：
C
b＝[[92，2]，[98，4]，[91，1]，[88，0]，[95，3]]
h＝p＝0
while b[p][1]?。絟：
print(b[p][0]，end＝″，″)
p＝b[p][1]
print(b[p][0])
運行該程序段，輸出的內容為 (　　)
A.88，91，92，95，98 B.98，95，92，91，88
C.92，91，98，95，88 D.98，95，88，92，91
解析　本題考查循環鏈表的遍歷。h表示頭節點，值為0，在鏈表中有一個節點指向0，因此判定該鏈表為循環鏈表。當前節點p從頭節點開始遍歷，若當前節點指針區域值為頭節點，結束遍歷，即遍歷到尾節點終止循環，沒有輸出尾節點的值，循環結束后，再次輸出尾節點的值。
5.下列Python程序段的功能是在鏈表link1中刪除數據為key的所有節點，link1鏈表中的每個節點由一個數據域和一個指針域組成。
#建立鏈表 link1，代碼略
key＝int(input(″輸入要刪除的數據：″))
head＝0
while link1[head][0]＝＝key and head?。剑?:
　head＝link1[head][1]
p＝q＝head
if head＝＝－1：
　 print(″全部數據刪除″)
else：
　　q＝link1[q][1]
　　while _______________：
　　 　if link1[q][0]＝＝key：
　　　　 　_______________
　　　else：
　 　　　　p＝link1[p][1]
　　 　q＝link1[q][1]
則劃線①②處的代碼分別為(　　)
A.①link1[q][1]?。剑? ②link1[p][1]＝link1[q][1]
B.①link1[q][1]?。剑? ②link1[q][1]＝link1[p][1]
C.①q！＝－1 ②link1[q][1]＝link1[p][1]
D.①q?。剑? ②link1[p][1]＝link1[q][1]
D
解析　本題考查鏈表節點刪除的算法實現。先判斷當前節點的數據域是否為 key，如果是，則刪除當前節點，即將 p節點的指針域指向 q 節點的指針域，如果不是，則將 p 指向下一個節點，q 也指向下一個節點。最后，程序通過 while 循環遍歷鏈表并輸出每個節點的數據域。
6.小張準備去多個城市旅游，他設計的行程若采用鏈表結構表示，如圖a所示。
若行程有變，需在“上海”與“成都”之間增加一站“杭州”，鏈表修改為如圖b所示，有以下可選操作：
①“上?！彼诠濣c的next值賦為“杭州”節點的next值
②“上海”所在節點的next值賦為5
③“杭州”所在節點的next值賦為“上?！彼诠濣c的next值
④“杭州”所在節點的next值賦為－1
鏈表更新順序正確的是(　　)
A.③① B.③② C.①④ D.②④
B
解析　本題考查的知識點是鏈表元素的插入。鏈表中插入新元素并不需要進行元素位置移動，只需要進行節點指針域的更改即可。在“上海”與“成都”之間增加一站“杭州”，需要先將新元素“杭州”的指針域設置為“成都”所在位置，再更改節點“上?！钡闹羔樣蛑凉濣c“杭州”所在位置。
7.在一個單向鏈表(如圖)中，若在尾指針tail所指節點之后插入新節點(r所指節點)，則執行的操作是(　　)
D
A.tail所指節點的data3值賦為r所指節點的data4值
B.r所指節點的next值賦為tail
C.r所指節點的next值賦為－l
D.tail所指節點的next賦為r，r所指節點的next值賦為－l
解析　本題主要考查鏈表的操作。鏈表中尾節點的next指針為－1，若在尾指針tail所指節點之后插入新節點(r所指節點)，則執行的操作是：tail所指節點的next賦為r，r所指節點的next值賦為－1。
8.有如下Python程序段：
n＝int(input(″輸入一個數：″))
a＝[]；head＝－1
while n>0：
r＝1－n%2
n∥＝2
a.append([r，head])
head＝len(a)－1
解析　本題考查鏈表的插入和進制轉換。程序的功能是十進制數轉成二進制數，并把結果取反。代碼a.append([r，head]); head＝len(a)－1的功能利用頭插法生成鏈表。
p＝head
while p！＝－1：
print(a[p][0]，end＝″″)
p＝a[p][1]
運行上述程序段后，如果輸入11，則輸出結果是(　　)
A.1101 B.1011 C.0010 D.0100
D
9.找出序列中的最大數，并將其放到序列的最后面。實現上述功能的代碼如下：
#鏈表a中存儲了序列數據，head為其頭指針，代碼略
pre＝p＝head
maxpre＝maxp＝head
while p！＝－1：
if a[p][0]>a[maxp][0]:
maxp＝p; maxpre＝pre
pre＝p
p＝a[p][1]
if maxp＝＝head:
head＝a[head][1]
elif maxp！＝pre：
　?、賍_____
a[pre][1]＝maxp
②______
#遍歷輸出鏈表 a
劃線處的代碼應為(　　)
A.①a[maxp][1]＝a[maxpre][1] ②a[maxp][1]＝a[p][1]
B.①a[maxp][1]＝a[maxpre][1] ②a[maxp][1]＝p
C.①a[maxpre][1]＝a[maxp][1] ②a[maxp][1]＝a[p][1]
D.①a[maxpre][1]＝a[maxp][1] ②a[maxp][1]＝p
D
解析　本題考查鏈表。先查找序列中最大數的位置maxp和該節點的前驅節點maxpre，pre 為最后一個節點位置。再刪除最大數節點，分兩種情況，最大數節點為第一個節點或其他位置節點。如果是其他位置節點，需將該最大數節點的前驅節點指針區域指向該最大數節點的后繼節點位置，即a[maxpre][1]＝a[maxp][1]。最后將最大數節點插入鏈尾，原最后一個節點指針區域需指向最大數節點，最大數節點為新的最后一個節點，其 指針區域為－1，即 p，所以②a[maxp][1]＝p。
10.某醫院每天提前發放100個預約號，考慮到老年人身體原因，預約病人按照以下規則進行就診：
①老年人(年齡>＝60歲)比非老年人優先就診。
②老年人按年齡從大到小的順序就診，年齡相同的按預約順序就診。
③非老年人按預約順序就診。
小王根據以上規則編寫了一個Python程序，程序運行時，實時讀取病人預約數據，并根據以上規則，實時調整并顯示當前診順序，程序運行界面如圖所示。
(1)如圖所示，若當前就診順序為“75 67 40 15 30”，下一位預約病人年齡為60，則就診順序變為__________________。
請輸入病人的信息：40
當前就診順序為：40
請輸入病人的信息：15
當前就診順序為：40　15
請輸入病人的信息：67
當前就診順序為：67　40　15
請輸入病人的信息：75
當前就診順序為：75　67　40　15
請輸入病人的信息：30
當前就診順序為：75　67　40　15　30
(2)實現上述功能的代碼如下，請在劃線處填入合適的代碼。
#遍歷鏈表data，頭指針為head
def visit(data，head)：
　 cur＝head
　 while cur！＝－1：
　　　print(data[cur][0]，end＝″ ″)
　　　cur＝data[cur][1]
　　print(″\\n″)
data＝[]
head＝tail＝－1　#head、tail分別表示鏈表頭節點和尾節點所在位置
for i in range(100)：
#為了簡潔，本程序只輸入、存儲病人的年齡信息
age＝int(input(″請輸入病人的信息：″))　
cur＝head
if age>＝60：
while cur?。剑? and data[cur][0]>＝age: #查找第一個數據域小于age的節點
　　　pre＝cur
　　　
　if cur＝＝head：　#在頭節點插入新節點
　　　data.append([age，cur])
　　　head＝len(data)－1
　else：# 在鏈表中間插入新節點
　　　data.append([age，cur])
　　?、赺_____
　　if cur＝＝－1：　# 更新尾指針位置
　　　　tail＝len(data)－1
　else： #直接插在鏈表尾節點后
　　data.append([age，－1])
　　if head＝＝－1：　# 添加第一個節點
　　　　head＝tail＝0
答案　(1)75 67 60 40 15 30
(2)①cur＝data[cur][1]
②data[pre][1]＝len(data)－1
③data[tail][1]＝len(data)－1
解析　本題考查鏈表的遍歷和插入操作。(1)老年人(年齡>＝60歲)比非老年人優先就診，老年人按年齡從大到小的順序就診，因此將60插入到40前，結果是75 67 60 40 15 30。(2)當年齡大于等于 60歲時，按年齡降序插入到鏈表，當年齡小于60歲時，按預約順序插入鏈表。①從頭節點開始依次遍歷，根據數據值找到第一個比當前數據小的節點cur，pre為前驅節點。②在鏈表中間插入新節點時，需要在插入節點后，更改前驅節點的指針區域。③直接插在鏈表尾節點后，尾節點變成了前驅節點，更改前驅節點的指針區域。
4
鞏固與提升
基礎鞏固
能力提升
1.下列有關鏈表的說法中，正確的是(　　)
A
解析　本題主要考查是鏈表的特性。鏈表的頭指針指向第一個節點，要刪除第一個節點，只需將頭指針移動到第一個節點指針的指向即可，因此可以刪除第一個節點，故答案為A。
A.每個鏈表的表頭一定有一個頭指針，以實現對鏈表的引用和邊界處理
B.在單向鏈表中，最后一個節點的指針指向第一個節點
C.鏈表一旦創建好后，它占用的空間將固定
D.鏈表的頭指針指向第一個節點，因此不能刪除第一個節點
2.設指針變量p指向單向鏈表lst的某中間節點，如圖所示，則刪除該節點的后繼節點的正確操作是(　　)
C
解析　本題主要考查鏈表的刪除操作。刪除該節點的后繼節點，需將后繼節點的指針域賦值為當前節點的指針域值，實現當前節點連接后繼節點的后面節點。lst[p][next]表示后繼節點的指針，lst[lst[p][next]]表示后繼節點。
A.lst[p][next]＝lst[p][next] [next]
B.p＝lst[p][next][next]
C.lst[p][next]＝lst[lst[p][next]][next]
D.t＝lst[p][next]；p＝lst[t][next]
3.某公交路線的站點名稱、經度、緯度和下一個站點序號(經緯度已轉換為平面坐標 數據)存儲在數組 a 中，現計算相鄰兩個站點距離的總和。
import math
a＝[[″廊橋″，3，2，3]，[″徐岙″，6，11，2]，[″北門″，13，8，－1]，[″上通″，3，7，1]]
head＝0 ; s＝0 p＝a[head][3]
while (1)_________________：
s＋＝math.sqrt((a[p][1]－a[head][1])**2＋(a[p][2]－a[head][2])**2)
(2)_________________
(3)_________________
print(s)
解析　本題考查鏈表的遍歷。從當前鏈表的頭節點開始遍歷，與他下一個節點p的距離，因此head要不斷地后移，head＝p，而p為新節點的后繼節點。當頭指針節點的后繼為－1時，表示遍歷完了。
上述程序段劃線處可選的代碼為：
①a[head][3]?。剑?　②head＝p　③p＝a[head][3] ④head?。剑?
則(1)、(2)、(3)處的代碼依次為(　　)
A.①②③ B.④②③ C.④③② D.①③②
A
4.已知鏈表 a 中的每個節點包含數據區域和指針區域兩部分，下列 Python 程序段的功能是在鏈表 a 中刪除數據值為 key 的所有節點。
key＝int(input(″輸入要刪除的數據：″))
head＝0
while head?。剑? and a[head][0]＝＝key ：
　　head＝a[head][1]
p＝q＝head
if head?。剑?:
　　q＝a[q][1]
　　while ①______：
if a[q][0]＝＝key：
　　　　　②______
else：
　　　 p＝a[p][1]
　　　q＝a[q][1]
則劃線①②處的代碼分別為(　　)
A.①a[q][1]?。剑?　 ②a[p][1]＝a[q][1]
B.①a[q][1]?。剑? ②a[q][1]＝a[p][1]
C.①q?。剑? ②a[q][1]＝a[p][1]
D.①q?。剑? ②a[p][1]＝a[q][1]
D
解析　本題考查鏈表節點的刪除。①循環遍歷整個鏈表 。②q 為當前元素指針，p是當前節點q的前驅，要刪除 q 節點，只需要修改 p 的指針為 q 的后繼。
5.使用Python的二維列表來模擬單向鏈表，每個節點都是一個列表，其第一個元素存儲數據，第二個元素存儲指向后繼節點的指針。若要刪除節點a[p]的后繼節點，則需執行語句(　　)
A.p＝a[p][1] B.a[a[p][1]][1]＝a[p][1]
C.a[p][0]＝a[a[p][1]][0] D.a[p][1]＝a[a[p][1]][1]
D
解析　語句a[p][1]＝a[a[p][1]][1]是修改節點p的后繼指針，使其指向后繼節點的后繼，以實現刪除節點p后繼節點的功能。
6.用Python程序實現刪除鏈表的倒數第n(n不大于鏈表長度)個節點，如n＝2時，鏈表
更新為
部分代碼如下：
#讀入鏈表存儲在列表s中，head存儲鏈表的頭節點，代碼略
n＝int(input())
p1＝p2＝head
while p2?。剑?：
　　if n>＝0：
(1)_____________
n－＝1
　　else：
(2)_____________
p2＝s[p2][1]
if p1＝＝head and n>＝0：
　head＝s[head][1]
else：
　　(3)_____________
上述程序段中劃線處可選的語句為：
D
①p1＝s[p1][1]?、趐2＝s[p2][1]
③s[p1][1]＝s[s[p1][1]][1]
④s[p2][1]＝s[s[p2][1]][1]
則(1)～(3)劃線處語句依次為(　　)
A.①③④ B.①④③ C.②①④ D.②①③
解析　本題考查鏈表的刪除。while循環查找待刪除節點的前驅節點位置。通過p1和p2遍歷鏈表，前n次只遍歷p2，后續同時遍歷p1和p2，當p2遍歷結束時，p1剛好指向倒數第n＋1個節點。所以(1)處選p2＝s[p2][1]，(2)處選p1＝s[p1][1]。確定p1位置后，執行刪除操作。如果p1指向頭節點head，要刪除頭節點，即更新head指向原頭節點指針區域對應的節點；否則刪除p1的后繼節點，即p1的指針區域更新為p1后繼節點的指針區域，(3)處應選s[p1][1]＝s[s[p1][1]][1]。
7.在升序鏈表 a 中插入一個不重復數據 data，仍保持鏈表的升序狀態。使用 python 程序實現插入操作，代碼如下：
data＝[[20，4]，[6，3]，[35，5]，[18，0]，[27，2]，[59，－1]]
p＝head＝1
data＝int(input())
if data<＝a[head][0]:
　a.append([data，head])
　head＝len(a)－1
else：
B
　　while ①______and data>a[q][0]：
　p＝q
　q＝a[p][1]
　?、赺_____
a.append([data，q])
則劃線處的代碼為(　　)
A.①p?。剑?　②a[p][1]＝len(a)－1
B.①q?。剑? ②a[p][1]＝len(a)
C.①q?。剑? ②a[q][1]＝len(a)－1
D.①p！＝－1 ②a[q][1]＝len(a)
解析　本題考查鏈表中數據查找和插入操作。p、q 是兩個前后相鄰的節點。根據 data>a[q][0]，可以推測出①為q！＝－1。循環結束后，應該在p節點之后插入節點，所以②處代碼是：a[p][1]＝len(a)。
8.實現在鏈表 c 中找出最小值 m 的 Python 程序如下：
D
解析　本題考查鏈表遍歷和最值查找。當前節點從頭節點開始遍歷，最小值的初值為頭節點大小，因此需先移動到下一節點，再與最值進行比較，同時終止遍歷的條件是遍歷到尾節點馬上結束。
head＝3；p＝head；m＝c[head][0]
while (1)_____________：
(2)_____________
if c[p][0]m＝c[p][0]
上述程序段中方框處可選代碼為：①p?。剑?
②c[p][1]?。剑?　 ③p＝p＋1　④p＝c[p][1]
則程序段中(1)、(2)處代碼依次為(　　)
A.①③ B.②③ C.①④ D.②④
9.將兩個鏈表a(A→B→C)和b(D→E)按照間隔次序合并為一個鏈表，并將結果保存到鏈表a(A→D→B→E→C)中，部分程序如下：
解析　本題考查鏈表節點的插入操作。程序將節點q插入到節點p的后面，因此q的指針域的值將發生變化，為了鏈表b正常遍歷，應先保存q的后繼。插入過程中，由于已經保存了q的后繼，因此可以先修改q的指向，再修改p的指向，最后將p移動到原插入節點q的后繼。
B
填入方框處的可選代碼有：①data[p][1]＝data[q][1]
②data[q][1]＝data[p][1]?、踕ata[p][1]＝q
④data[q][1]＝p?、輕＝data[p][1]　⑥p＝data[q][1] 已知鏈表 b 的長度不超過鏈表 a，則下列選項中，代碼順序正確的是(　　)
A.①④⑤ B.②③⑥ C.①④⑥ D.②③⑤
10.使用鏈表結構模擬某景區游玩路線，鏈表a中每一個節點包含3個數據，第1個為景點名稱，第2個為預計游玩時間(單位：分鐘)，第3個為下一個景點指針。景區可以從多個景點的大門進入，但只能從″天梯″離開，輸出顯示各大門進入路線及預計總時間的代碼如下。
a＝[[″迎客松″，21，2]，[″激流勇進″，40，2]，[″天空棧道″，50，5]，
[″一線天″，30，4]，[″飛來峰″，60，5]，[″天梯″，20，－1]]
head＝[0，1，3]
for i in range(len(head))：
(1)___________________
s＝a[p][1]
while a[p][2]?。剑?：
　　　　print(a[p][0]，end＝″→″)
(2)_________________
(3)_________________
print(a[p][0])
print(″預計時間：″，s，″分鐘″)
解析　本題考查多條鏈表的遍歷。3條鏈表構建在數組a中，頭指針存儲在數組head中，需遍歷頭指針數組，從而來遍歷3條鏈表。(1)處為當前節點賦值為頭指針head[i]，變量s存儲所有節點游覽總時間。(2)(3)遍歷鏈表，并統計各個節點游覽時間和，由于當前節點已經計入總時間，因此先要跳轉到下一點，將下一節點的時間加入到總時間，注意遍歷結束的條件是當遍歷到尾節點時，終止遍歷。
D
上述程序劃線處的可選代碼有： ①p＝head
②p＝head[i]　 ③s＋＝a[p][1]　 ④ p＝a[p][2]
則(1)(2)(3)處代碼依次為(　　)
A.①③④ B.①④③ C.②③④ D.②④③
11.有如下Python程序：
from random import *
a＝[[″e″，4]，[″g″，8]，[″h″，5]，[″h″，0]，[″n″，1]，[″o″，7]，[″S″，3]，[″u″，6]，[″Z″，2]]
k＝randint(1，4)*2＋1
p＝q＝6
while k>0：
　　p＝a[p][1]
　　k－＝1
D
while p?。?：
　q＝a[q][1]
　p＝a[p][1]
print(a[q][0])
解析　本題考查循環鏈表的操作，根據p＝q＝6可以得出鏈表為S－h－e－n－g－Z－h－o－u，k的范圍為[3，5，7，9]，p和q相差k個節點，p為1時輸出a[q][0]，即p指向g，q的可能有h、u、g。
12.使用列表d模擬鏈表結構(節點數大于0)，每個節點包含數據區域和指針區域，h為頭指針。鏈表中各節點已按數據區域中數值的絕對值由小到大排列，如圖a所示?，F要修改該鏈表各節點的鏈接關系，使鏈表各節點按數據區域中的數值由小到大排列，結果如圖b所示。實現該功能的程序段如下，方框中應填入的正確代碼為(　　)
C
解析　題圖a按絕對值升序排序數據，鏈表中數據依次為－11，14，16，17，－18，要求改變鏈接關系，使鏈表各節點按數據區域中的數值由小到大排列。若鏈表中只有1個節點，其值無論是正數還是負數，均是最小的數。同時他既是頭節點h，也是尾節點t。因此變量p從鏈表第2個節點開始遍歷各個節點，若遍歷到負數，則該數絕對值越大，其值就越小，需將該節點從原鏈表中刪除，并移動到頭節點的前面，進行的操作是將該前節點p指向原頭節點h，同時修改當前位置為頭指針。若為正數，將該節點鏈接到尾節點t的后面。
13.有如下 Python 程序段，為實現在鏈表中插入一個[6，50]區間內的隨機數后，鏈表 data 中的數據仍然有序。
import random
x＝random.randint(6，50)
print(″在鏈表 data 中插入一個值為″，x，″的數″)
data＝[[14，1]，[26，4]，[5，0]，[49，－1]，[37，3]]
head＝2; q＝head
while q！＝－1：
if x>data[q][0]：
p＝①______
q＝data[q][1]
else：
break
data.append(②________)
data[p][1]＝len(data)－1
q＝head
while q?。剑?：
print(data[q][0]，end＝'')
q＝data[q][1]
D
解析　本題考查鏈表的插入。在有序鏈表中插入一個節點x，x 的范圍在6到50之間，故只需要考慮中間插入或者尾插，q 指向的就是小于 x 的最大節點，讓插入的節點 x 指向 p 節點的后繼節點 q，語句 data[p][1]＝len(data)－1實現讓p節點指向新插入的節點 x。
請為①②兩處選擇正確的程序代碼(　　)
A.①data[q][1]　?、赱x，p]
B.①data[q][1] ②[x，data[p][1]]
C.① q ②[x，p]
D.①q ②[x，data[p][1]]
14.報數游戲。已知班上有n名學生(用編號1，2，3，……n分別表示)，學生按照編號由小到大順時針圍成一個圓圈，從編號為1的學生開始順時針報數，報到m的同學出列；下一名同學又從1開始報數，報數為m的同學繼續出列；以此規律重復下去，直到剩下最后一位同學為止。
(1)當n＝12，m＝3時，最后留下的同學的編號是______。
(2)下列代碼通過構造一個循環單向鏈表，模擬報數的過程，逐一刪除報數為m的節點，直到剩下一個節點為止。請在劃線處填入合適的代碼。
n＝int(input(″n＝″))
m＝int(input(″m＝″))
lst＝[]
for i in range(n－1):
　 lst.append([i＋1，i＋1])
lst.append(①_____________) #將尾節點的指針指向頭節點，構成循環單向鏈表
p＝len(lst)－1
while n>1：
　 for i in range(1，m): #從 1～(m－1)依次報數
p＝lst[p][1]
out＝lst[p][1]
②____________
n＝n－1
print(″最后留下的同學的編號是： ″，lst[p][0])
答案　(1)10　(2)①[n，0]?、趌st[p][1]＝lst[out][1]
解析　(1)依次出隊的序號為3，6，9，12，4，8，1，7，2，11，5，最后留下10號。
(2)①循環隊列的特點是隊尾指向隊首，因此最后一個學生的編號為n，指針指向0。 ②節點p從最后一個節點開始，range(1，m)循環了m－1次，因此向后遍歷了m－1個節點，下一個節點lst[p][1]就是要刪除的節點，因此將當前節點的指針指向下一節點的后繼，就刪除了下一節點。
15.張三是一名計算機專業的大學生，為了幫助同學們學習專業相關的英語詞匯，編寫一個簡易字典程序。該程序中存放詞匯數據庫，在學習中輸入英文單詞，可以獲得中文翻譯結果。程序中的詞匯數據庫采用鏈表方式存儲，首字母相同時按升序排序。查找單詞時，首先根據首字母找到同首字母最小單詞所在鏈表，再按照鏈表順序查找該單詞。
(1)根據題意，部分的單詞庫數據邏輯結構如圖所示，查找單詞”byte”的過程是”binary”→”bit”→”byte”，補充圖中空白單元格的值為__________。
列表索引 數據區域 指針區域
0 audio 音頻 －1
1 binary 二進制數 6
2 byte 字節 －1
3 cursor 光標 －1
4 access 存取 1
5 cache 高速緩存 3
6 bit 比特 ____▲____
(2)wordlist(data，info)函數實現將詞匯數據庫 data 以鏈表的方式按字母序升序排列。info表示詞匯數據庫中各字母開頭的最小單詞位置，如 info[0]表示字母 a 開頭的最小單詞在詞匯數據庫 data 中的位置。實現該功能的程序如下，請在劃線處填入合適的代碼。
info＝[]
def wordlist(data，info):
　 n＝len(data)
　　for i in range(n)：
data[i].append(－1)
　#data[i]追加一個元素－1
for i in range(n):
　　 　d＝data[i][0]
　　　 ①______________
　　　 if info[k]＝＝－1:
　　　 info[k]＝i
　　　else：
　 　　head＝info[k]
　　　q＝head
　　　while ②____________ ：
　　 　　　p＝q
　　　　　q＝data[q][2]
　　　if q?。絟ead：
　　 　　　data[p][2]＝i
　　　　　data[i][2]＝q
　　　else：
　　　　　data[i][2]＝head
　　　　?、踎___________
return data，info
(3)searchword(data，info，key)函數實現單詞的查找。程序如下，請在劃線處填入合適的代碼。
def searchword(data，info，key):
　 k＝ord(key[0])－ord(″a″)
　　head＝info[k]
　　p＝head
　　while p?。剑?：
　 if data[p][0]＝＝key:
　　　　 return ________
　p＝data[p][2]
　　return ″沒有找到該單詞″
讀取詞匯數據庫，存入列表 data 中，列表的每個元素包含 2 個數據項，分別為英文單詞和中文翻譯，如 data＝[['audio'，'音頻']，['binary'，'二進制數'] …], 數據讀取存入的代碼略。
info＝[－1] * 26
data，info＝wordlist(data，info)
key＝input(″請輸入查找單詞：″).lower()
#轉化為小寫字母
res＝searchword(data，info，key)
print(key，″查找結果是：″，res)
答案　(1)2　(2)①k＝ord(d[0])－ord(″a″)
②q?。剑? and d>data[q][0]　③info[k]＝i
(3)data[p][1]
解析　本題考查鏈表的構建、遍歷和節點的插入。
(1)采用鏈表方式存儲字母，首字母相同時按升序排序。單詞bit的下一個單詞為byte，因此其指針區域值為索引2。(2)①將單詞d首字母轉換為字母表中對應數字，info[0]表示字母 a 開頭的最小單詞，因此k為字母a－z對應0－25的索引號。②遍歷data鏈表，找到單詞d位置。當前節點q從頭節點開始，當q值不為－1，且滿足d比當前節點數據區域值大。(3)返回單詞key對應的中文。每個元素包含英文單詞和中文翻譯。課時2　鏈　表
課時目標
1.理解數組和鏈表的概念和特性。2.掌握數組和鏈表的基本操作。3.能運用數組和鏈表編程解決實際問題。
1.鏈表的概念
(1)鏈表指的是將需要處理的數據對象以________的形式，通過________串聯在一起的一種數據結構。
(2)每個節點一般包括兩個區域：____________和____________。
(3)每個鏈表有個________——head(也稱頭指針)，是鏈表的入口，也便于循環鏈表在數據處理時的邊界判斷和處理。
(4)鏈表的形式
鏈表的形式主要有：____________、____________、____________。
①單向鏈表：只有一個指針用來指向其________節點。單向鏈表如下圖所示。
②雙向鏈表：有兩個指針分別用于指向其__________節點和__________節點。雙向鏈表如下圖所示。
③循環鏈表：________節點和____________節點使用指針鏈接。循環鏈表如下圖所示。
2.鏈表的特性
(1)同一鏈表中每個節點的________均相同，有數據區域和指針區域組成。
(2)每個鏈表必定有一個________，以實現對鏈表的引用和邊界處理。
(3)鏈表占用的空間________。
可根據需求增刪節點，提高了存儲空間的利用率。
3.鏈表的基本操作
(1)鏈表的創建
(2)鏈表節點的訪問
鏈表只能通過頭指針進行訪問，其他節點通過節點間的指針依次訪問。
(3)鏈表節點的插入與刪除
插入操作：
插入datax節點
刪除data2節點
(4)鏈表節點的訪問與遍歷
訪問鏈表中的節點時，只能通過頭指針進入鏈表并通過指針鏈接依次訪問，直到找到目標位置上的節點。
4.鏈表的類實現
在Python中，鏈表除了可以使用列表來實現，還可以使用“類”實現?！邦悺笔且环N抽象的數據結構，它將數據及其操作封裝在一起。構造單向鏈表類的具體實現過程如下：
(1)自定義單向鏈表的節點類：
class Node：　　　#定義單鏈表節點類
def__init__(self，data，next＝None)：#初始
化節點包含兩個域self.data、self.next
　 self.data＝data #self.data域保存數據
　self.next＝next #self.next域保存指針，缺省值為None
(2)構造單向鏈表類：
class Link：　　　#定義單向鏈表類Link
　 def __init__(self)：　#初始化空鏈表
　 self.head＝None #空鏈表頭指針指向為空
例1 對于鏈表的描述，下列說法不正確的是(　　)
A.同一鏈表中每個節點的結構均相同
B.每個鏈表必定有一個頭指針
C.鏈表占用的空間不固定
D.創建的新鏈表中至少要有一個節點
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　鏈表不具備的特點是(　　)
A.可隨機訪問任一節點
B.插入、刪除操作時不需要移動元素
C.不必事先估計存儲空間
D.所需空間與其長度成正比
例2 使用列表模擬單鏈表，其存儲結構如圖所示，遍歷該鏈表，將訪問到的節點的數據域的字符依次連接，得到字符串‘LOVE’，則指針域中的索引值依次為(　　)
A.0　1　2　3 B.3　1　0　2
C.2　0?。?　1 D.2　0　1?。?
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　利用列表模擬非循環鏈表a(可能存在已被刪除的節點)，下列程序運行完畢后，變量p表示尾節點的節點位置是(　　)
例3 有如下 Python 程序段：
a＝[[3，1]，[2，2]，[3，3]，[3，4]，[17，5]，[2，6]，[3，－1]]
p＝head＝0
while p?。剑?:
q＝p
while q?。剑?:
t＝q
q＝a[q][1]
if q！＝－1 and a[q][0]＝＝a[p][0]：
　　　　　a[t][1]＝a[q][1]
　　　　　q＝t
p＝a[p][1]
p＝head
while p?。剑?：
print(a[p][0]，end＝' ')
p＝a[p][1]
運行后程序的輸出結果是(　　)
A.3　2　17 B.3　2　17　2
C.3　2　17　2　3 D.17
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　有如下 Python 程序段：
def guess(cur)：
q＝cur
p＝a[cur][1]
while p?。剑?：
if a[p][0]＝＝a[cur][0]：
　　　　 a[q][1]＝a[p][1]
else：
　　　　 q＝p
p＝a[p][1]
a＝[[1，3]，[1，2]，[2，4]，[2，5]，[4，－1]，[3，1]]
head＝0；cur＝head
while cur！＝－1：
print(a[cur][0]，end＝″″)
if a[cur][1]?。剑?：
guess(cur)
cur＝a[cur][1]
運行后，則輸出的結果是(　　)
A.1234 B.1122 C.11223 D.11224
例4 有兩個降序序列的鏈表 a，b?，F將鏈表 b 中的數據合并到鏈表 a，形成一個新的降序序列存于鏈表 a，實現數據合并的代碼段如下，
a＝[[98，1]，[96，2]，[95，3]，[93，4]，[90，－1]]
b＝[[99，1]，[97，2]，[94，3]，[93，4]，[92，－1]]
head_a＝head_b＝0
pre＝p＝head_a；q＝head_b
while q?。剑?：
if p?。剑? and :
pre＝p
p＝a[p][1]
else：
a.append( )
if p＝＝head_a：
　　　　pre＝head_a＝len(a)－1
else：
　　　　a[pre][1]＝
　　　　pre＝len(a)－1
q＝b[q][1]
上述程序段中可選填的語句為：
①a[p][0]>＝b[q][0]　② a[p][0]<＝b[q][0]
③q　④len(a)－1　⑤[b[p][0]，q]
⑥[b[q][0]，p]
則加框處填寫的語句依次為(　　)
A.①⑥④ B.①⑤④ C.①⑥③ D.②⑥③
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　有如下 Python 程序：
def lnkid(n，head):
p＝head
while head！＝－1 and ①____________：
p＝head
head＝a[head][1]
return p
a＝[[2，2]，[5，3]，[1，－1]，[3，0]，[7，1]]
head＝4
n＝int(input())
p＝lnkid(n，head)
if n>a[head][0]：
a.append([n，head])
head＝len(a)－1
else：
a.append([n，a[p][1]])
②______________
用列表 a 模擬一個降序鏈表，運行程序，輸入自然數 n，則鏈表增加一個新的節點，要使鏈表保持降序，則劃線①②處代碼分別為(　　)
A.①nB.①nC.①nD.①n>a[head][0] ②a[p][1]＝len(a)
例5 某編程興趣小組設計了一個點歌模擬程序，功能如下：
運行程序后，從鍵盤輸入“A”，則顯示已點的歌曲列表(歌單)；輸入“B”則可以自行輸入歌曲并添加到歌單以完成點歌；輸入“C”則可以將指定的歌曲置頂等待播放；輸入“D” 則播放當前第一首歌曲，并將該歌曲從列表中刪除；輸入“E”則關閉程序并退出。程序運行界面如下圖所示。
請輸入指令A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：A God Is a Girl　十年　年少有為　七里香　淡季動物園 請輸入指令A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：B 請輸入歌曲：蘭亭序 請輸入指令A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：B 請輸入歌曲：想自由 請輸入指令A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：A God Is a Girl　十年　年少有為　七里香　淡季動物園　蘭亭序　想自由 請輸入指令A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：C 請輸入歌曲：七里香 請輸入指令A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：A 七里香　God Is a Girl　十年　年少有為　淡季動物園　蘭亭序　想自由 請輸入指令A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：C 請輸入歌曲：想自由 請輸入指令A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：A 想自由　七里香　God Is a Girl　十年　年少有為　淡季動物園　蘭亭序 請輸入指令A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：D 請輸入指令A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：A 七里香　God Is a Girl　十年　年少有為　淡季動物園　蘭亭序 請輸入指令A—顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：E
Python 代碼如下所示，請在劃線處填入合適的代碼。
data＝[[″十年″，4]，[″淡季動物園″，－1]，[″God Is a Girl″，0]，[″七里香″，1]，[″年少有為″，3]]
head＝2
tail＝1
while True：
cmd＝input(″請輸入指令 A－顯示歌單/B－點歌/C－置頂/D－唱歌/E－退出：″)
if cmd＝＝″A″：
cur＝head
while cur?。剑?:
　　　print(data[cur][0]，end＝″″)
　　　 cur＝data[cur][1]
print()
elif cmd＝＝″B″：
song＝input(″請輸入歌曲：″)
data.append([song，－1])
if head＝＝－1：
　　　head＝tail＝len(data)－1
else：
　　?、賍___________
　　　tail＝len(data)－1
elif cmd＝＝″C″：
song＝input(″請輸入歌曲：″)
cur＝head
while cur?。剑? and data[cur][0]！＝song:
　　　　pre＝cur
　　　　cur＝data[cur][1]
if cur?。剑? and cur?。絟ead：
　　?、赺___________
　　　data[cur][1]＝head
　　　head＝cur
　　　if cur＝＝tail：
　　　　③____________
elif cmd＝＝″D″：
if head＝＝tail:
　　　　head＝tail＝－1
else：
　　?、躝_________
elif cmd＝＝″E″：
break
聽課筆記　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　已知一個有7個節點的單向鏈表，設有頭指針head和尾指針tail，如圖所示，下列操作需要遍歷多個節點的是(　　)
A.刪除該鏈表中的最后一個節點
B.刪除該鏈表中的第一個節點
C.在該鏈表第一個節點前插入一個新節點
D.在該鏈表最后一個節點后插入一個新節點
1.在單向鏈表中，增加頭指針的目的是(　　)
A.標識表節點中首節點的位置
B.算法實現上的方便
C.使單向鏈表至少有一個節點
D.說明單向鏈表是線性表的鏈式存儲實現
2.下列關于鏈表的敘述中，正確的是(　　)
A.線性鏈表中的各元素在存儲空間中的位置必須是連續的
B.線性鏈表中的表頭元素一定存儲在其他元素的前面
C.線性鏈表中的各元素在存儲空間中的位置不一定是連續的，但表頭元素一定存儲在其他元素的前面
D.線性鏈表中的各元素在存儲空間中的位置不一定是連續的，且各元素的存儲順序也是任意的
3.某單向鏈表如下圖所示，若要將數據 data3 和data4 同時從鏈表中移除，至少需要修改節點指針的數量是(　　)
A.1 B.2 C.3 D.4
4.某 Python 程序段如下：
b＝[[92，2]，[98，4]，[91，1]，[88，0]，[95，3]]
h＝p＝0
while b[p][1]?。絟：
print(b[p][0]，end＝″，″)
p＝b[p][1]
print(b[p][0])
運行該程序段，輸出的內容為 (　　)
A.88，91，92，95，98 B.98，95，92，91，88
C.92，91，98，95，88 D.98，95，88，92，91
5.下列Python程序段的功能是在鏈表link1中刪除數據為key的所有節點，link1鏈表中的每個節點由一個數據域和一個指針域組成。
#建立鏈表 link1，代碼略
key＝int(input(″輸入要刪除的數據：″))
head＝0
while link1[head][0]＝＝key and head?。剑?:
　head＝link1[head][1]
p＝q＝head
if head＝＝－1：
　 print(″全部數據刪除″)
else：
　　q＝link1[q][1]
　　while ①____________：
　　 　if link1[q][0]＝＝key：
　　　　 ?、赺___________
　　　else：
　 　　　　p＝link1[p][1]
　　 　q＝link1[q][1]
則劃線①②處的代碼分別為(　　)
A.①link1[q][1]?。剑? ②link1[p][1]＝link1[q][1]
B.①link1[q][1]?。剑? ②link1[q][1]＝link1[p][1]
C.①q！＝－1 ②link1[q][1]＝link1[p][1]
D.①q?。剑? ②link1[p][1]＝link1[q][1]
6.小張準備去多個城市旅游，他設計的行程若采用鏈表結構表示，如圖a所示。
若行程有變，需在“上海”與“成都”之間增加一站“杭州”，鏈表修改為如圖b所示，有以下可選操作：
①“上?！彼诠濣c的next值賦為“杭州”節點的next值
②“上?！彼诠濣c的next值賦為5
③“杭州”所在節點的next值賦為“上?！彼诠濣c的next值
④“杭州”所在節點的next值賦為－1
鏈表更新順序正確的是(　　)
A.③① B.③② C.①④ D.②④
7.在一個單向鏈表(如圖)中，若在尾指針tail所指節點之后插入新節點(r所指節點)，則執行的操作是(　　)
A.tail所指節點的data3值賦為r所指節點的data4值
B.r所指節點的next值賦為tail
C.r所指節點的next值賦為－l
D.tail所指節點的next賦為r，r所指節點的next值賦為－l
8.有如下Python程序段：
n＝int(input(″輸入一個數：″))
a＝[]；head＝－1
while n>0：
r＝1－n%2
n∥＝2
a.append([r，head])
head＝len(a)－1
p＝head
while p！＝－1：
print(a[p][0]，end＝″″)
p＝a[p][1]
運行上述程序段后，如果輸入11，則輸出結果是(　　)
A.1101 B.1011 C.0010 D.0100
9.找出序列中的最大數，并將其放到序列的最后面。實現上述功能的代碼如下：
#鏈表a中存儲了序列數據，head為其頭指針，代碼略
pre＝p＝head
maxpre＝maxp＝head
while p！＝－1：
if a[p][0]>a[maxp][0]:
maxp＝p; maxpre＝pre
pre＝p
p＝a[p][1]
if maxp＝＝head:
head＝a[head][1]
elif maxp?。絧re：
　?、賍___
a[pre][1]＝maxp
②____
#遍歷輸出鏈表 a
劃線處的代碼應為(　　)
A.①a[maxp][1]＝a[maxpre][1]
②a[maxp][1]＝a[p][1]
B.①a[maxp][1]＝a[maxpre][1]
②a[maxp][1]＝p
C.①a[maxpre][1]＝a[maxp][1]
②a[maxp][1]＝a[p][1]
D.①a[maxpre][1]＝a[maxp][1]
②a[maxp][1]＝p
10.某醫院每天提前發放100個預約號，考慮到老年人身體原因，預約病人按照以下規則進行就診：
①老年人(年齡>＝60歲)比非老年人優先就診。
②老年人按年齡從大到小的順序就診，年齡相同的按預約順序就診。
③非老年人按預約順序就診。
小王根據以上規則編寫了一個Python程序，程序運行時，實時讀取病人預約數據，并根據以上規則，實時調整并顯示當前診順序，程序運行界面如圖所示。
請輸入病人的信息：40 當前就診順序為：40 請輸入病人的信息：15 當前就診順序為：40　15 請輸入病人的信息：67 當前就診順序為：67　40　15 請輸入病人的信息：75 當前就診順序為：75　67　40　15 請輸入病人的信息：30 當前就診順序為：75　67　40　15　30
(1)如圖所示，若當前就診順序為“75 67 40 15 30”，下一位預約病人年齡為60，則就診順序變為__________________。
(2)實現上述功能的代碼如下，請在劃線處填入合適的代碼。
#遍歷鏈表data，頭指針為head
def visit(data，head)：
　 cur＝head
　 while cur！＝－1：
　　　print(data[cur][0]，end＝″ ″)
　　　cur＝data[cur][1]
　　print(″\\n″)
data＝[]
head＝tail＝－1　#head、tail分別表示鏈表頭節點和尾節點所在位置
for i in range(100)：
#為了簡潔，本程序只輸入、存儲病人的年齡信息
age＝int(input(″請輸入病人的信息：″))　
cur＝head
if age>＝60：
while cur?。剑? and data[cur][0]>＝age: #查找第一個數據域小于age的節點
　　　pre＝cur
　　?、賍_____________
　if cur＝＝head：　#在頭節點插入新節點
　　　data.append([age，cur])
　　　head＝len(data)－1
　else：# 在鏈表中間插入新節點
　　　data.append([age，cur])
　　?、赺_____________
　　if cur＝＝－1：　# 更新尾指針位置
　　　　tail＝len(data)－1
　else： #直接插在鏈表尾節點后
　　data.append([age，－1])
　　if head＝＝－1：　# 添加第一個節點
　　　　head＝tail＝0
　　else：
　　　　
　　　　tail＝len(data)－1
　print(″當前就診順序為：″)
visit(data，head)
課時2　鏈　表
知識梳理
1.(1)節點　指針　(2)數據區域　指針區域　(3)表頭　(4)單向鏈表　雙向鏈表　循環鏈表?、俸罄^　②前驅　后繼?、鄣谝粋€　最后一個
2.(1)結構　(2)頭指針　(3)不固定
例題精析
例1　D　[本題考查鏈表的基本性質。A選項鏈表節點包含數據區域和指針區域，每個節點中的數據區域中數據類型是相同的。B選項訪問鏈表的某一節點，只能從頭指針開始，依次訪問。C選項鏈表通過指針相連，相信節點存儲時不需要連續空間，因此鏈表空間是不固定的。D選項可以空鏈表，數據區域為空，頭指針為－1。]
變式訓練　A　[本題主要考查的是鏈表的特點。訪問鏈表中的某一節點時，只能從頭指針開始，通過指針鏈接依次訪問。因此答案為A。]
例2　C　[本題考查鏈表的構建和遍歷。L的后繼節點為O，因此其指針區域值為1；O的后續為V，指針區域值為0; V的后續為E，指針區域值為2；E為尾節點，因此指針區域值為－1。 ]
變式訓練　B　[本題考查鏈表的遍歷。A選項當前節點為p，當遍歷到節點為空時停止遍歷，因此遍歷結束后，p節點為空，其前驅t為尾節點。B選項當前節點為p，若當前節點的指針區域值為－1，結束遍歷，那么當前節點p為尾節點。C選項當前節點從頭節點開始遍歷，a[a[p][1]]指當前節點的后繼節點，若該節點的指針區域值為－1，表示該節點為尾節點，當前節點為尾節點的前驅。D選項鏈表a可能存在已被刪除的節點，因此len(a)的值可能大于節點總數。]
例3　A　[本題考查鏈表的操作。當a[q]節點上的值與a[p]節點上的值相同時，q指針往后移一位。程序的功能是將與p指針所指示的節點值相同的a[q]節點刪除。指針t的作用是維護了去重后鏈表最后一個節點的位置。輸出鏈表的所有非重復節點。]
變式訓練　A　[本題考查鏈表節點的刪除。在自定義函數guess中，當前節點p從cur節點的后繼開始，如果后面的元素與cur節點元素值相等，則刪除節點p，因此是從當前節點鏈表中刪除重復的元素。]
例4　A　[本題考查鏈表元素的遍歷和插入操作。程序的功能將鏈表 b 中的數據合并到鏈表 a，形成一個新的降序序列存于鏈表 a。分別遍歷兩個鏈表，若鏈表a當前元素值a[p][0]大于等于鏈表 b當前元素值b[q][0]，則鏈表a向后遍歷，否則把鏈表 b當前元素值b[q][0]插入到鏈表a當前元素前面。由于是要把鏈表 b 中的數據合并到鏈表 a，因此鏈表b遍歷完成后，結束程序。]
變式訓練　B　[本題考查鏈表的插入。①自定義函數lnkid的功能是查找n在鏈表中插入位置，head在不斷地向后移動，因此n將和a[head][0]進行比較，當比a[head][0]小時，不斷地向后查找位置。②語句p＝lnkid(n，head)將返回在節點p的后面插入新的數n，因此將修改a[p]節點指針區域值為當前插入點索引。]
例5?、賒ata[tail][1]＝len(data)－1
②data[pre][1]＝data[cur][1]
③tail＝pre
④head＝data[head][1]
解析　本題考查鏈表的操作。①輸入“B”則可以自行輸入歌曲并添加到歌單，新節點插入在尾節點的后面，因此原尾節點應指向新插入的節點，同時更新尾節點。②輸入“C”則可以將指定的歌曲置頂，data[cur][0]值為song表示找到節點cur，pre為cur節點的前驅，將cur移動到頭節點前面，因此需要3步，第1步是將cur的前驅pre指向cur的后繼，第2步是將cur指前原頭節點，第3步是設置新的頭節點為cur。③若cur是原尾節點tail，將cur修改為頭節點后，新的尾節點為cur的前驅。④輸入“D” 則播放當前第一首歌曲，并將該歌曲從列表中刪除，條件head＝＝tail成立表示鏈表中只有一個節點，否則將頭指針向后移動，刪除頭節點。
變式訓練　A　[本題考查鏈表的遍歷、插入和刪除操作。A選項刪除該鏈表中的最后一個節點，需修改最后一個節點的前驅節點指針域，因此需遍歷多個節點。B選項只需修改頭指針。C選項修改當前節點的指針值指向原頭節點，并修改頭指針為當前節點。D選項讓原尾節點指向當前節點，并修改尾節點為當前節點。 ]
隨堂檢測
1.B　[在單向鏈表中，一定有一個頭指針，以實現對鏈表的引用和邊界處理，因此，增加頭指針的目的是算法實現上的方便，因此，答案為B。]
2.D　[單鏈表存儲方式地址不連續，元素順序是任意的。因此，答案為D。]
3.A　[只需修改data2的指針區域值修改為data4的指針區域值。]
4.C　[本題考查循環鏈表的遍歷。h表示頭節點，值為0，在鏈表中有一個節點指向0，因此判定該鏈表為循環鏈表。當前節點p從頭節點開始遍歷，若當前節點指針區域值為頭節點，結束遍歷，即遍歷到尾節點終止循環，沒有輸出尾節點的值，循環結束后，再次輸出尾節點的值。]
5.D　[本題考查鏈表節點刪除的算法實現。先判斷當前節點的數據域是否為 key，如果是，則刪除當前節點，即將 p節點的指針域指向 q 節點的指針域，如果不是，則將 p 指向下一個節點，q 也指向下一個節點。最后，程序通過 while 循環遍歷鏈表并輸出每個節點的數據域。]
6.B　[本題考查的知識點是鏈表元素的插入。鏈表中插入新元素并不需要進行元素位置移動，只需要進行節點指針域的更改即可。在“上?！迸c“成都”之間增加一站“杭州”，需要先將新元素“杭州”的指針域設置為“成都”所在位置，再更改節點“上?！钡闹羔樣蛑凉濣c“杭州”所在位置。]
7.D　[本題主要考查鏈表的操作。鏈表中尾節點的next指針為－1，若在尾指針tail所指節點之后插入新節點(r所指節點)，則執行的操作是：tail所指節點的next賦為r，r所指節點的next值賦為－1。]
8.D　[本題考查鏈表的插入和進制轉換。程序的功能是十進制數轉成二進制數，并把結果取反。代碼a.append([r，head]); head＝len(a)－1的功能利用頭插法生成鏈表。]
9.D　[本題考查鏈表。先查找序列中最大數的位置maxp和該節點的前驅節點maxpre，pre 為最后一個節點位置。再刪除最大數節點，分兩種情況，最大數節點為第一個節點或其他位置節點。如果是其他位置節點，需將該最大數節點的前驅節點指針區域指向該最大數節點的后繼節點位置，即a[maxpre][1]＝a[maxp][1]。最后將最大數節點插入鏈尾，原最后一個節點指針區域需指向最大數節點，最大數節點為新的最后一個節點，其 指針區域為－1，即 p，所以②a[maxp][1]＝p。]
10.(1)75 67 60 40 15 30
(2)①cur＝data[cur][1]
②data[pre][1]＝len(data)－1
③data[tail][1]＝len(data)－1
解析　本題考查鏈表的遍歷和插入操作。(1)老年人(年齡>＝60歲)比非老年人優先就診，老年人按年齡從大到小的順序就診，因此將60插入到40前，結果是75 67 60 40 15 30。(2)當年齡大于等于 60歲時，按年齡降序插入到鏈表，當年齡小于60歲時，按預約順序插入鏈表。①從頭節點開始依次遍歷，根據數據值找到第一個比當前數據小的節點cur，pre為前驅節點。②在鏈表中間插入新節點時，需要在插入節點后，更改前驅節點的指針區域。③直接插在鏈表尾節點后，尾節點變成了前驅節點，更改前驅節點的指針區域。

展開更多......

收起↑