“基于链表实现数据合并功能”教学思路
共 2183字，需浏览 5分钟
· 2022-11-17
说在前面
在掌握了创建链表，和对链表进行查、改、增、删基本操作后，有必要解决一些综合性问题来加深对链表概念和算法原理的理解。教材2.2.1例1“基于链表实现数据合并功能”是对第一章中使用链表合并数据的算法细化和编程实现，需要结合示意图动画演示来理解代码，并进一步思考代码优化方法。
教材文本
为了降低教学难度，我们可以先创建好链表a和b，把教学重点放在合并链表上。然后单独来分析尾插法和头插法的区别。
学生任务单
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的基础上，把链表b的元素插入到a，以列表a为存储空间，构造新的链表
pre = p = head_a
q = head_b
while q != -1:
if p != -1 and a[p][0] >= b[q][0]: # 节点p非空且值不小于节点q
pre =填空1
p =填空2
else:
a.append(填空3) # 将节点q插入到列表a的尾部，以p为后继节点
if p == head_a: # 若节点p为头节点，需将q作为新的头节点
pre = head_a =填空4 # 更新头指针和pre
else:
a[pre][1] =填空5 # 将pre的后继指针指向节点q
pre =填空6 # 将pre指向其后继节点
q =填空7 # 处理链表b的下一个结点
（1）书中程序先创建一个空链表，然后生成第一个节点，并为其赋值为[95,100]范围内的随机整数；然后依次从链表尾部插入新节点，每个新节点都比其前驱节点小[1,5]的随机数；本来使用尾插法是需要定位尾节点的，因为每次都是从尾部插入，故程序默认尾节点的下标为(i-1)，其中i表示当前列表长度。
（2）若从链表头部插入新节点来生成降序序列，则需要更新头指针，并按照升序序列来插入新节点。核心代码为：
#生成a链表
a = []
head_a = -1
tmp=randint(1,5) #添加头节点
a.append([tmp,head_a])
head_a = 0
for i in range(1,5): #依次生成递增数
tmp = a[head_a][0] + randint(1,5)
a.append([tmp,head_a]) # 插入到链表头部
head_a = len(a) - 1 # 更新头指针
完整代码详见“Python算法之旅”知识星球。
（3）程序输出效果图如下，完整代码详见“Python算法之旅”知识星球。
课后作业
教材第一章的合并链表案例中，为链表生成了一个空的头节点，但本例中的程序并没有创建空的头节点，而是直接把第一个有效节点作为头节点了。如果增设一个空头节点（可以为其数据域取值为-1），该如何编写代码？
需要本文word文档、源代码和课后思考答案的，可以加入“Python算法之旅”知识星球参与讨论和下载文件，“Python算法之旅”知识星球汇集了数量众多的同好，更多有趣的话题在这里讨论，更多有用的资料在这里分享。
我们专注Python算法，感兴趣就一起来！
相关优秀文章：