“基于鏈表實(shí)現(xiàn)數(shù)據(jù)合并功能”教學(xué)思路
說(shuō)在前面
在掌握了創(chuàng)建鏈表，和對(duì)鏈表進(jìn)行查、改、增、刪基本操作后，有必要解決一些綜合性問(wèn)題來(lái)加深對(duì)鏈表概念和算法原理的理解。教材2.2.1例1“基于鏈表實(shí)現(xiàn)數(shù)據(jù)合并功能”是對(duì)第一章中使用鏈表合并數(shù)據(jù)的算法細(xì)化和編程實(shí)現(xiàn)，需要結(jié)合示意圖動(dòng)畫演示來(lái)理解代碼，并進(jìn)一步思考代碼優(yōu)化方法。
教材文本
為了降低教學(xué)難度，我們可以先創(chuàng)建好鏈表a和b，把教學(xué)重點(diǎn)放在合并鏈表上。然后單獨(dú)來(lái)分析尾插法和頭插法的區(qū)別。
學(xué)生任務(wù)單
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ù)；本來(lái)使用尾插法是需要定位尾節(jié)點(diǎn)的，因?yàn)槊看味际菑奈膊坎迦?，故程序默認(rèn)尾節(jié)點(diǎn)的下標(biāo)為(i-1)，其中i表示當(dāng)前列表長(zhǎng)度。
（2）若從鏈表頭部插入新節(jié)點(diǎn)來(lái)生成降序序列，則需要更新頭指針，并按照升序序列來(lái)插入新節(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 # 更新頭指針
完整代碼詳見(jiàn)“Python算法之旅”知識(shí)星球。
（3）程序輸出效果圖如下，完整代碼詳見(jiàn)“Python算法之旅”知識(shí)星球。
課后作業(yè)
教材第一章的合并鏈表案例中，為鏈表生成了一個(gè)空的頭節(jié)點(diǎn)，但本例中的程序并沒(méi)有創(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算法，感興趣就一起來(lái)！
相關(guān)優(yōu)秀文章：