“基于链表实现数据合并功能”教学思路

说在前面

在掌握了创建链表，和对链表进行查、改、增、删基本操作后，有必要解决一些综合性问题来加深对链表概念和算法原理的理解。教材2.2.1例1“基于链表实现数据合并功能”是对第一章中使用链表合并数据的算法细化和编程实现，需要结合示意图动画演示来理解代码，并进一步思考代码优化方法。

教材文本

(相关资料图)

教材处理例1虽然是对第一章中合并链表a和b的算法实现，但并没有与其保持完全一致。第一章中，为了方便描述算法，增设了一个空头节点，而例1则没有使用空头节点；此外，例1并没有直接创建具有确切值的链表，而是通过先创建空链表，再使用尾插法插入新节点的方式，生成了一个降序排列的单链表。

为了降低教学难度，我们可以先创建好链表a和b，把教学重点放在合并链表上。然后单独来分析尾插法和头插法的区别。

学生任务单

阅读教材P47例1“基于链表实现数据合并功能”，思考如下问题：（1）书中程序是如何生成降序序列的？新节点是在链表头部还是尾部插入的？（2）若从链表头部插入新节点来生成降序序列，该如何编写代码？（3）假设我们已经创建好了链表a和b，只需在链表a的基础上，把链表b的元素插入到a中，以实现合并链表功能。试比较如下程序与教材程序的异同，并完成填空。

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算法，感兴趣就一起来！

相关优秀文章：

阅读代码和写更好的代码

最有效的学习方式

Python算法之旅文章分类

关键词： 降序序列 的基础上