数据结构与控制算法分析 专题三 查找与排序
查找与排序 专题三 数据结构与控制算法分析
学习内容与要求 学习和掌握顺序査找和折半查找算法的原理 和实现; 学习和掌握二叉排序树的概念及其构造方法、 二叉排序树的查找算法原理 学习和掌握选择排序、交换排序、插入排序、 归并排序和快速排序方法的原理。 第2页
学习内容与要求 • 学习和掌握顺序查找和折半查找算法的原理 和实现； • 学习和掌握二叉排序树的概念及其构造方法、 二叉排序树的查找算法原理。 • 学习和掌握选择排序、交换排序、插入排序、 归并排序和快速排序方法的原理。 第 2 页
1 Search (查找/搜索) 第3页
1 Search (查找/搜索) 第 3 页
所谓查找(或搜索),就是在数据 集合中寻找满足某种条件的数据对象 1查找成功即找到满足条件的数据 对象时,作为结果,可报告该对象在结构 中的位置,还可给出该对象中的具体信息 2.查找不成功或搜索失败。作为结果 应报告一些信息,如失败标志、位置等。 第4页
第 4 页 所谓查找（或搜索），就是在数据 集合中寻找满足某种条件的数据对象: 1.查找成功 即找到满足条件的数据 对象时, 作为结果, 可报告该对象在结构 中的位置, 还可给出该对象中的具体信息。 2.查找不成功 或搜索失败。作为结果, 应报告一些信息, 如失败标志、位置等
通常称用于查找的数据集合为查找 结构,它是由同一数据类型的数据 (或记录)组成。 每个对象有若干属性,其中有一个 属性,其值可唯一地标识这个对象 称为关键字。使用基于关键字的搜 索,査找结果应是唯一的。但在实 际应用时,查找条件是多方面的, 可以使用基于属性的查找方法,但 查找结果可能不唯 第5页
◼ 通常称用于查找的数据集合为查找 结构，它是由同一数据类型的数据 (或记录)组成。 ◼ 每个对象有若干属性，其中有一个 属性，其值可唯一地标识这个对象， 称为关键字。使用基于关键字的搜 索，查找结果应是唯一的。但在实 际应用时，查找条件是多方面的， 可以使用基于属性的查找方法，但 查找结果可能不唯一。 第 5 页