数据结构与控制算法分析 专题三 查找与排序
查找与排序 专题三 数据结构与控制算法分析
学习内容与要求 学习和掌握顺序査找和折半查找算法的原理 和实现; 学习和掌握二叉排序树的概念及其构造方法、 二叉排序树的查找算法原理 学习和掌握选择排序、交换排序、插入排序、 归并排序和快速排序方法的原理。 第2页
学习内容与要求 • 学习和掌握顺序查找和折半查找算法的原理 和实现； • 学习和掌握二叉排序树的概念及其构造方法、 二叉排序树的查找算法原理。 • 学习和掌握选择排序、交换排序、插入排序、 归并排序和快速排序方法的原理。 第 2 页
1 Search (查找/搜索) 第3页
1 Search (查找/搜索) 第 3 页
所谓查找(或搜索),就是在数据 集合中寻找满足某种条件的数据对象 1查找成功即找到满足条件的数据 对象时,作为结果,可报告该对象在结构 中的位置,还可给出该对象中的具体信息 2.查找不成功或搜索失败。作为结果 应报告一些信息,如失败标志、位置等。 第4页
第 4 页 所谓查找（或搜索），就是在数据 集合中寻找满足某种条件的数据对象: 1.查找成功 即找到满足条件的数据 对象时, 作为结果, 可报告该对象在结构 中的位置, 还可给出该对象中的具体信息。 2.查找不成功 或搜索失败。作为结果, 应报告一些信息, 如失败标志、位置等
通常称用于查找的数据集合为查找 结构,它是由同一数据类型的数据 (或记录)组成。 每个对象有若干属性,其中有一个 属性,其值可唯一地标识这个对象 称为关键字。使用基于关键字的搜 索,査找结果应是唯一的。但在实 际应用时,查找条件是多方面的, 可以使用基于属性的查找方法,但 查找结果可能不唯 第5页
◼ 通常称用于查找的数据集合为查找 结构，它是由同一数据类型的数据 (或记录)组成。 ◼ 每个对象有若干属性，其中有一个 属性，其值可唯一地标识这个对象， 称为关键字。使用基于关键字的搜 索，查找结果应是唯一的。但在实 际应用时，查找条件是多方面的， 可以使用基于属性的查找方法，但 查找结果可能不唯一。 第 5 页
实施査找时有两种不同的环境 静态环境查找结构不需进行插入和 删除操作。 静态查找表 动态环境查找过程中可能要对查找 结构执行数据插入、删除或修改等操 作,并对查找结构进行调整,结构可 能发生变化。 动态查找表 动态查找表的表结构是在查找过程中动态生成 的。 第6页
实施查找时有两种不同的环境 ◼ 静态环境 查找结构不需进行插入和 删除操作。 ⎯ 静态查找表 第 6 页 ◼动态环境 查找过程中可能要对查找 结构执行数据插入、删除或修改等操 作，并对查找结构进行调整，结构可 能发生变化。 ⎯ 动态查找表 ◼动态查找表的表结构是在查找过程中动态生成 的
11顺序查找( Sequential Search >以线性结构表示静态查找表。 >基本原理:将待查找记录依 次逐个与表中记录进行比较。 第7页
第 7 页 ➢以线性结构表示静态查找表。 ➢基本原理：将待查找记录依 次逐个与表中记录进行比较。 1.1 顺序查找（Sequential Search)
顶序查找过程(从前向后查找 SLelem 213788199205645680753 01234567891011 假设给定查找值e=64, ST Length=11 要求 SL elema=e,问:k=? 第8页
第 8 页 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.Length=11 SL.elem 顺序查找过程（从前向后查找） 假设给定查找值 e=64, 要求 SL.elem[k] = e, 问: k = ? k k
顺序查找过程(从后向前查找) 0单元用于存放待查找关键字,作为“哨兵”( guard) SLelem 返回7i 642137881992056456807513 01234567891011 key=64 ST Length=ll 返回0 SL elem 602137881992056456807513 01234567891011 key=60 T Length=112页
第 9 页 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.Length=11 SL.elem i 21 37 88 19 92 05 64 56 80 75 13 0 1 2 3 4 5 6 7 8 9 10 11 ST.Length=11 SL.elem i 60 i key=64 key=60 i 64 顺序查找过程（从后向前查找） 0单元用于存放待查找关键字，作为“哨兵”(guard) 返回0 返回7
顺序查找算法实现(从后向前查找) int Search Seq( tb sl, type key SLelem[o].key=key;“哨兵” for (i=SL length; SL elem[i]. key =key );∥/从后往前找 return i;/查找成功时为有效下标否则为0 第10页
第 10 页 int Search_Seq( TB SL, TYPE key ) { SL.elem[0].key = key; // “哨兵” for (i=SL.length; SL.elem[i].key!=key; --i); // 从后往前找 return i; // 查找成功时i为有效下标,否则i为0 } 顺序查找算法实现（从后向前查找）