环球实时：“数据合并”教学思路

说在前面

浙教版《选择性必修一数据和数据结构》第一章是全书的导论，起到了提纲挈领的作用。其中“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]需要本文word文档、源代码和课后思考答案的，可以加入“Python算法之旅”知识星球参与讨论和下载文件，“Python算法之旅”知识星球汇集了数量众多的同好，更多有趣的话题在这里讨论，更多有用的资料在这里分享。

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

相关优秀文章：

阅读代码和写更好的代码

最有效的学习方式

Python算法之旅文章分类

关键词： 存储数据 如下图所示 数据结构