次课-链接存储结构上的排序和查找

《次课-链接存储结构上的排序和查找》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、首页本章挺难的吧。加油哦！教学主题链接存储结构上的排序和查找教学目标通过本次课的学习，使学生掌握直接插入排序算法的基本思想、链接存储结构线性表（单链表）的排序和查找方法。教学重点1．直接插入排序算法2．链接存储结构线性表上的排序方法3．链接存储结构线性表上的查找方法教学难点链接存储结构线性表上排序算法的实现教案主要内容直接插入排序链接存储结构上的直接插入排序链接存储结构上的查找排序回顾在第5章中已介绍了冒泡排序和简单选择排序。本章介绍另外一种常用的排序方法——直接插入排序。直接插入排序直接插入排序：通过顺序地把待排序的对象

2、按其关键字值的大小插入到已排序对象集合的适当位置来实现排序的。直接插入排序举例假定将数据按从小到大进行排序。对一组关键字（42，38，64，91，14，25）进行排序。直接插入排序的基本思想基本思路（对n个数据进行排序）假设待排序的对象为R0、R1、R2、……、Rn-1。（1）开始时，已排序对象集合只有一个对象R0。（2）寻找合适的位置，把对象R1插入到已排好序的对象集合中去，使对象R0、R1排好序。（3）依次类推，分别将对象R2、R3、……、Rn-1插入到已排好序的对象集合中去。直接插入排序举例运行程序(9_1)看源程序

3、(9_1)【补例】将一组数据（42，38，64，91，14，25）按从小到大进行排序。流程图源程序返回链接存储结构上的直接插入排序链表插入排序的最终排序结果是把对象集合按关键码大小依次链接地存储在一个链表中。具体做法（单链表）（1）首先将第一个记录看作只有一个记录的有序子序列。（2）然后将第二个记录插入到该有序子序列中，再插入第三个记录、……，直到插入最后一个记录为止。每趟插入，总是从链表的表头开始搜索适当的插入位置。在黑板上用示例图进行讲解单链表的直接插入排序举例【例7-6】在【例7-5】的基础上修改程序，使输出的数据从

4、小到大排序。流程图源程序思考：不用附加头结点，任何修改？(9_3)运行程序(9_2)看源程序(9_2)任务相关部分（1）在任务程序中，要求按照不同的要求对数据进行排序。所以，我们可以设计成子菜单的形式，让用户根据菜单选择，并按选定的功能号分别实现不同的排序。（2）对链接存储结构的数据，可以采用前面讲解的直接插入排序算法来实现。（3）为避免编写多个排序子函数，我们可以参考第6章中介绍的通用排序的思想来实现。返回查找回顾在第5章中已介绍了顺序查找法和折半查找法。对于顺序存储线性表，两种查找法都可以用。对于用链表存储的线性表而言

5、，适合用哪种查找法呢？链接存储结构上的查找链接存储结构（单链表）上的查找只能从链表的首结点开始顺序查找。（1）若链表无序，则从链表的首结点开始，逐一检查链表中每个结点的值，直至所找的结点找到或者直至考察到了链表的末结点后仍未找到。（2）若链表有序，则顺序查找时，发现结点的值比要查找的值大（或小）时，就可提早得出结论了。单链表的顺序查找举例【例7-7】改写【例7-5】的create函数，使线性表中没有相同的数据。分析（1）要使线性表中没有相同的数据，则在输入数据后要判断该数据在链表中存在不存在，如不存在，才进行插入操作。（2

6、）“判断该数据在链表中存在不存在”就涉及到查找。编写一个函数，其功能是查找某个数据在链表中存在不存在。修改create函数单链表的顺序查找举例【例7-7】改写【例7-5】的create函数，使线性表中没有相同的数据。查找子函数流程图运行程序(9_4)看源程序(9_4)源程序单链表的顺序查找举例【例7-7】改写【例7-5】的create函数，使线性表中没有相同的数据。create函数流程图运行程序(9_4)看源程序(9_4)思考：不用附加头结点，任何修改？(9_5)源程序任务相关部分在任务程序中，要求按照不同的要求对数据进行

7、查找。所以，我们可以设计成子菜单的形式，让用户根据菜单选择，并按选定的功能号分别实现不同的查找。（1）查找指定学号的学生：可以先对学生数据按学号进行排序，然后查找时就不需要搜索整个链表，只要搜索到某个结点的学号等于或大于待查找的学号就可以提前结束了。（2）查找符合三好生标准的学生（平均分>=85分）：先对链表按照总分递减排序，然后只要搜索到某个结点的平均分<85分就可以提前结束。（3）查找成绩不及格的学生：只能采用搜索整个链表的方法。本次课总结排序回顾直接插入排序单链表中直接插入排序的实现查找回顾单链表中的查找方法冒泡排序

8、、简单选择排序学习过：顺序查找法、折半查找法学习过：适合采用顺序查找法下课ThankYou！TheEnd.