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

Python算法之旅

共 2183字,需浏览 5分钟

 ·

2022-11-17 09:33

说在前面

在掌握了创建链表,和对链表进行查、改、增、删基本操作后,有必要解决一些综合性问题来加深对链表概念和算法原理的理解。教材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算法之旅文章分类


浏览 44
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报