“基于链表实现数据合并功能”教学思路
共 2183字,需浏览 5分钟
·
2022-11-17 09:33
说在前面
在掌握了创建链表,和对链表进行查、改、增、删基本操作后,有必要解决一些综合性问题来加深对链表概念和算法原理的理解。教材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算法,感兴趣就一起来!
相关优秀文章: