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

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

2、现排序的。5直接插入排序举例 假定将数据按从小到大进行排序。对一组关键字（42，38，64，91，14，25） 进行排序。6直接插入排序的基本思想 基本思路（对n个数据进行排序）假设待排序的对象为R0、R1、R2、Rn-1。（1）开始时，已排序对象集合只有一个对象R0。（2）寻找合适的位置，把对象R1插入到已排好序的对象集合中去，使对象R0、R1排好序。（3）依次类推，分别将对象R2、R3、Rn-1插入到已排好序的对象集合中去。7直接插入排序举例运行程序(9_1)看源程序(9_1)【补例】将一组数据（42，38，64，91，14，25）按从小到大进行排序。 流程图 源程序返回8链接存储结构上的

3、直接插入排序 链表插入排序的最终排序结果是把对象集合按关键码大小依次链接地存储在一个链表中。 具体做法（单链表）（1）首先将第一个记录看作只有一个记录的有序子序列。（2）然后将第二个记录插入到该有序子序列中，再插入第三个记录、，直到插入最后一个记录为止。每趟插入，总是从链表的表头开始搜索适当的插入位置。在黑板上用示例图进行讲解9单链表的直接插入排序举例【例7-6】在【例7-5】的基础上修改程序，使输出的数据从小到大排序。 流程图 源程序思考：不用附加头结点，任何修改？(9_3)运行程序(9_2)看源程序(9_2)10任务相关部分（1）在任务程序中，要求按照不同的要求对数据进行排序。所以，我们可

4、以设计成子菜单的形式，让用户根据菜单选择，并按选定的功能号分别实现不同的排序。（2）对链接存储结构的数据，可以采用前面讲解的直接插入排序算法来实现。（3）为避免编写多个排序子函数，我们可以参考第6章中介绍的通用排序的思想来实现。返回11查找回顾 在第5章中已介绍了顺序查找法和折半查找法。 对于顺序存储线性表，两种查找法都可以用。 对于用链表存储的线性表而言，适合用哪种查找法呢？12链接存储结构上的查找 链接存储结构（单链表）上的查找只能从链表的首结点开始顺序查找。 （1）若链表无序，则从链表的首结点开始，逐一检查链表中每个结点的值，直至所找的结点找到或者直至考察到了链表的末结点后仍未找到。 （

5、2）若链表有序，则顺序查找时，发现结点的值比要查找的值大（或小）时，就可提早得出结论了。13单链表的顺序查找举例【例7-7】改写【例7-5】的create函数，使线性表中没有相同的数据。 分析（1）要使线性表中没有相同的数据，则在输入数据后要判断该数据在链表中存在不存在，如不存在，才进行插入操作。（2）“判断该数据在链表中存在不存在”就涉及到查找。 编写一个函数，其功能是查找某个数据在链表中存在不存在。修改create函数14单链表的顺序查找举例【例7-7】改写【例7-5】的create函数，使线性表中没有相同的数据。 查找子函数 流程图运行程序(9_4)看源程序(9_4) 源程序15单链表的

6、顺序查找举例【例7-7】改写【例7-5】的create函数，使线性表中没有相同的数据。 create函数流程图运行程序(9_4)看源程序(9_4)思考：不用附加头结点，任何修改？(9_5) 源程序16任务相关部分 在任务程序中，要求按照不同的要求对数据进行查找。所以，我们可以设计成子菜单的形式，让用户根据菜单选择，并按选定的功能号分别实现不同的查找。（1）查找指定学号的学生：可以先对学生数据按学号进行排序，然后查找时就不需要搜索整个链表，只要搜索到某个结点的学号等于或大于待查找的学号就可以提前结束了。（2）查找符合三好生标准的学生（平均分=85分）：先对链表按照总分递减排序，然后只要搜索到某个结点的平均分85分就可以提前结束。（3）查找成绩不及格的学生：只能采用搜索整个链表的方法。17本次课总结 排序回顾 直