說在前面

在掌握了創(chuàng)建鏈表，和對(duì)鏈表進(jìn)行查、改、增、刪基本操作后，有必要解決一些綜合性問題來加深對(duì)鏈表概念和算法原理的理解。教材2.2.1例1“基于鏈表實(shí)現(xiàn)數(shù)據(jù)合并功能”是對(duì)第一章中使用鏈表合并數(shù)據(jù)的算法細(xì)化和編程實(shí)現(xiàn)，需要結(jié)合示意圖動(dòng)畫演示來理解代碼，并進(jìn)一步思考代碼優(yōu)化方法。

教材文本

(相關(guān)資料圖)

教材處理例1雖然是對(duì)第一章中合并鏈表a和b的算法實(shí)現(xiàn)，但并沒有與其保持完全一致。第一章中，為了方便描述算法，增設(shè)了一個(gè)空頭節(jié)點(diǎn)，而例1則沒有使用空頭節(jié)點(diǎn)；此外，例1并沒有直接創(chuàng)建具有確切值的鏈表，而是通過先創(chuàng)建空鏈表，再使用尾插法插入新節(jié)點(diǎn)的方式，生成了一個(gè)降序排列的單鏈表。

為了降低教學(xué)難度，我們可以先創(chuàng)建好鏈表a和b，把教學(xué)重點(diǎn)放在合并鏈表上。然后單獨(dú)來分析尾插法和頭插法的區(qū)別。

學(xué)生任務(wù)單

閱讀教材P47例1“基于鏈表實(shí)現(xiàn)數(shù)據(jù)合并功能”，思考如下問題：（1）書中程序是如何生成降序序列的？新節(jié)點(diǎn)是在鏈表頭部還是尾部插入的？（2）若從鏈表頭部插入新節(jié)點(diǎn)來生成降序序列，該如何編寫代碼？（3）假設(shè)我們已經(jīng)創(chuàng)建好了鏈表a和b，只需在鏈表a的基礎(chǔ)上，把鏈表b的元素插入到a中，以實(shí)現(xiàn)合并鏈表功能。試比較如下程序與教材程序的異同，并完成填空。

a = [[19,1],[16,2],[12,3],[8,4],[5,-1]]

b = [[20,1],[15,2],[14,3],[10,4],[4,-1]]

head_a = head_b = 0

#在鏈表a的基礎(chǔ)上，把鏈表b的元素插入到a，以列表a為存儲(chǔ)空間，構(gòu)造新的鏈表

pre = p = head_a

q = head_b

while q != -1:

if p != -1 and a[p][0] >= b[q][0]: # 節(jié)點(diǎn)p非空且值不小于節(jié)點(diǎn)q

pre =填空1

p =填空2

else:

a.append(填空3) # 將節(jié)點(diǎn)q插入到列表a的尾部，以p為后繼節(jié)點(diǎn)

if p == head_a: # 若節(jié)點(diǎn)p為頭節(jié)點(diǎn)，需將q作為新的頭節(jié)點(diǎn)

pre = head_a =填空4 # 更新頭指針和pre

else:

a[pre][1] =填空5 # 將pre的后繼指針指向節(jié)點(diǎn)q

pre =填空6 # 將pre指向其后繼節(jié)點(diǎn)

q =填空7 # 處理鏈表b的下一個(gè)結(jié)點(diǎn)

問題解析

（1）書中程序先創(chuàng)建一個(gè)空鏈表，然后生成第一個(gè)節(jié)點(diǎn)，并為其賦值為[95,100]范圍內(nèi)的隨機(jī)整數(shù)；然后依次從鏈表尾部插入新節(jié)點(diǎn)，每個(gè)新節(jié)點(diǎn)都比其前驅(qū)節(jié)點(diǎn)小[1,5]的隨機(jī)數(shù)；本來使用尾插法是需要定位尾節(jié)點(diǎn)的，因?yàn)槊看味际菑奈膊坎迦?，故程序默認(rèn)尾節(jié)點(diǎn)的下標(biāo)為(i-1)，其中i表示當(dāng)前列表長(zhǎng)度。

（2）若從鏈表頭部插入新節(jié)點(diǎn)來生成降序序列，則需要更新頭指針，并按照升序序列來插入新節(jié)點(diǎn)。核心代碼為：

#生成a鏈表

a = []

head_a = -1

tmp=randint(1,5) #添加頭節(jié)點(diǎn)

a.append([tmp,head_a])

head_a = 0

for i in range(1,5): #依次生成遞增數(shù)

tmp = a[head_a][0] + randint(1,5)

a.append([tmp,head_a]) # 插入到鏈表頭部

head_a = len(a) - 1 # 更新頭指針

完整代碼詳見“Python算法之旅”知識(shí)星球。

（3）程序輸出效果圖如下，完整代碼詳見“Python算法之旅”知識(shí)星球。

課后作業(yè)

教材第一章的合并鏈表案例中，為鏈表生成了一個(gè)空的頭節(jié)點(diǎn)，但本例中的程序并沒有創(chuàng)建空的頭節(jié)點(diǎn)，而是直接把第一個(gè)有效節(jié)點(diǎn)作為頭節(jié)點(diǎn)了。如果增設(shè)一個(gè)空頭節(jié)點(diǎn)（可以為其數(shù)據(jù)域取值為-1），該如何編寫代碼？

需要本文word文檔、源代碼和課后思考答案的，可以加入“Python算法之旅”知識(shí)星球參與討論和下載文件，“Python算法之旅”知識(shí)星球匯集了數(shù)量眾多的同好，更多有趣的話題在這里討論，更多有用的資料在這里分享。

我們專注Python算法，感興趣就一起來！

相關(guān)優(yōu)秀文章：

閱讀代碼和寫更好的代碼

最有效的學(xué)習(xí)方式

Python算法之旅文章分類

關(guān)鍵詞： 降序序列 的基礎(chǔ)上