“数据合并”教学思路-技术圈

说在前面

浙教版《选择性必修一数据和数据结构》第一章是全书的导论，起到了提纲挈领的作用。其中“1.2.3 数据结构的作用”，通过两个案例来说明对同一问题的解决，可以依据不同数据结构来设计算法，其效率是不一样的。两个案例较为典型，且有一定难度，教师应根据学生实际，采用算法分析、代码讲解或过程演示等不同方法授课。

教材文本

教材处理

教材虽然采用了一维数组来存储数据，但其下标是从1开始的。为了便于编程，笔者把数组下标设置从0开始，并初始化i=0，p=0，tot=len(a)，如下图所示。

学生任务单

任务1. 回顾数组和链表数据结构分别有何特征，思考如下问题：

（1）如何在数组中插入单个元素？需要移动哪些元素？

（2）如何在数组中删除单个元素？需要移动哪些元素？

（3）如何在链表中插入单个节点？需要移动哪些节点或修改哪些指针？

（4）如何在链表中删除单个节点？需要移动哪些节点或修改哪些指针？

任务2. 阅读教材中“数据合并”材料，思考如下问题：

（1）基于数组的算法设计中，如何确定数组c的长度？初始化其右侧元素值为-1的目的是什么？使用下图演示依次将数组b的元素插入到数组c的过程，初始化i=0，p=0，tot=len(a)，思考整个过程中，变量i，p，tot的变化情况，以及程序结束后数组c的值为多少？

（2）基于链表的算法设计中，使用下图演示依次将链表b的节点插入到链表a的过程，变量head_a，p1和p的含义分别是什么？若节点p的值小于节点q，需要如何修改指针？（即修改哪些变量的值）；反之，若节点p的值不小于节点q，又该修改哪些变量的值呢？

例如，将值为20的节点插入到链表a时，需要如何修改指针？请使用绘图的方法，描述整个过程中，后继指针的变化情况。

问题解析

任务1. （1）在数组中插入单个元素，需要确定插入位置的下标，将该位置及其后的元素依次右移1位，以腾出插入位置，再将新元素放到该位置。插入新元素6前后数组存储数据如下图所示：

（2）在数组中删除单个元素，需要确定该元素的下标，依次将该元素右侧的元素依次左移1位，让右侧元素覆盖左侧元素，以实现删除效果。删除元素7前后数组存储数据如下图所示：

（3）在单链表中插入单个节点，需要确定前驱节点pre在链表中的位置，设置新节点的指针指向pre的后继节点，再修改pre的后继指针指向新节点。插入新节点6前后链表存储数据如下图所示：

（4）在单链表中删除单个节点，需要确定其前驱节点pre在链表中的位置，再修改pre的后继指针指向被删除节点的后继节点。删除节点7前后链表存储数据如下图所示：

任务2. （1）基于数组的算法设计中，数组c的长度等于数组a和b的长度之和；之所以初始化数组c右侧元素值为-1，是因为在插入数组b的数据之前，数组c的实际元素只包含数组a的全部元素，可以把-1作为监视哨，一旦c[p]的值为-1，则表示p已经指向数组c实际数据的尾部，可以直接令c[p]=b[i]。但这样做的前提是数组a和b中的数据均不能为-1，否则程序会出错。更好的做法是判断p与tot的值是否相等，若相等则表示p已指向数组c尾部。

使用下图演示依次将数组b的元素插入到数组c的过程，初始化i=0，p=0，tot=len(a)。思考整个过程中，变量i，p，tot的变化情况，以及程序结束后数组c的值为多少？

算法设计如下：

① 若c[p]>=b[i]，则将p右移一位；

② 若c[p]==-1，则令c[p]=b[i]，并将tot右移一位；

③ 若c[p]<b[i]，则将c[p:tot]的元素依次右移一位，然后令c[p]=b[i]，并将tot右移一位；

④ 将i右移一位。循环执行①-④，直至i越界。

程序结束后数组c，及各变量的值如下图所示：

（2）基于链表的算法设计中，使用下图演示依次将链表b的节点插入到链表a的过程，变量head_a表示链表a的头指针，p指向链表a的当前节点，p1指向p的前驱节点；同理head_b表示链表b的头指针，q指向链表b的当前节点，q1指向q的前驱节点。

将链表b的节点插入到链表a中时，若节点p的值不小于节点q，则先将p1指向p，再将p指向其后继节点；若节点p的值小于节点q，则执行如下操作：

① 将p1的后继指针指向q；

② 将q1的后继指针指向q的后继节点；

③ 将p1指向q，并将p1的后继指针指向p；

④ 将q指向q1的后继节点。

例如，将链表b中值为20的节点q插入到链表a时，先将p1的后继指针指向q，然后将q1的后继指针指向q的后继节点；再将p1指向q，并将p1的后继指针指向p；最后将q指向q1的后继节点。插入节点20后，链表示意图如下所示：

插入全部节点后，链表示意图如下所示：

课后作业

本节课的教学任务是通过示意图动态演示分别使用数组和链表存储数据和插入元素的过程，使学生掌握使用数组或链表存储数据的方法，理解插入元素时游标或指针的变化情况。重在理解算法，无需编写程序。

当然，待学生掌握更多编程知识后，我们也可以让学生回过头来编写程序实现本案例功能；或者在使用示意图动态演示插入元素过程后，让学生运行教师编写好的代码，体验程序运行过程。程序运行结果如下，请编程实现之。

需要本文word文档、源代码和课后思考答案的，可以加入“Python算法之旅”知识星球参与讨论和下载文件，“Python算法之旅”知识星球汇集了数量众多的同好，更多有趣的话题在这里讨论，更多有用的资料在这里分享。

我们专注Python算法，感兴趣就一起来！

相关优秀文章：

阅读代码和写更好的代码

最有效的学习方式

Python算法之旅文章分类