页数：26页文件大小：421.8 KB来源： 数据结构-C#语言描述ppt课件
本课件围绕查找这一最常用的运算展开：先界定查找表、关键字、主次关键字与静态动态查找、内外查找等概念，再逐一讲解顺序查找、二分查找、分块查找和二叉查找树四类方法，给出二分查找的 low、high、mid 追踪过程、判定树与复杂度分析，以及二叉查找树的查找、插入与删除规则，最后横向比较各算法的优劣。
本页为第七章查找封面。本章讲解查找的基本概念，以及顺序查找、二分查找、分块查找与二叉查找树四类典型查找算法。
查找是计算机应用中最常用的操作之一，也是许多程序中最耗时间的一部分。因而，查找方法的优劣对系统的运行效率影响极大。
本章讨论各种查找算法，并通过对它们的分析来比较各种查找方法的优劣。
查找是指在数据元素集合中查找满足某种条件的数据元素的过程。例如在学生成绩表中查找某一学生的成绩；在字典中查找某个字等等。
用于查找的数据元素集合就称为查找表，查找表由同一类型的数据元素组成。
本章讨论的顺序查找、二分查找、分块查找与二叉查找树查找均属于内查找。
顺序查找又称线性查找（Sequential Search），是一种最简单、最基本的静态查找方法。其基本思想是：从表的一端开始，顺序扫描整个线性表，依次将扫描到的结点关键字与给定值 K 进行比较，若当前扫描到的结点关键字与 K 相等，则查找成功；若扫描结束后，仍未找到关键字值等于 K 的结点，则查找失败。
顺序查找所用时间跟查找关键字 K 在表中的位置有关。顺序表查找的时间复杂度为 O(n)。
二分查找又称折半查找（Binary Search），是一种效率较高的静态查找方法。二分查找要求查找表用顺序存储结构存放，且各数据元素按关键字有序（升序或降序）排列，并且要求查找表使用线性表的顺序存储结构。
也就是说，二分查找只适用于对有序顺序表进行查找。
本页演示在有序表 2、8、10、13、21、36、51、57、62、69 中查找关键字 51 的过程。各轮 low、high、mid 及比较结论如下：
| 轮次 | low | high | mid | mid 处关键字 | 比较结论 |
|---|---|---|---|---|---|
| 1 | 0 | 9 | 4 | 21 | 21 小于 51，low 改为 5 |
| 2 | 5 | 9 | 7 | 57 | 57 大于 51，high 改为 6 |
| 3 | 5 | 6 | 5 | 36 | 36 小于 51，low 改为 6 |
| 4 | 6 | 6 | 6 | 51 | 相等，查找成功 |
其中 mid 的计算式为 mid = (low + high) / 2，结果取整数部分。
例 7-1 Demo7-1.cs 使用循环实现二分查找：在循环中反复计算 mid 并比较，命中则返回下标，未命中则收缩查找区间，直到 low 大于 high 时判定查找失败。
二分查找可用一棵称为判定树的二叉树来描述，判定树中的每一结点对应表中的一个元素，但结点的值不是关键字的值，而是元素在表中的位置。
二分查找的算法复杂度为 O(log2n)，也就是说在有 10000 条记录的有序查找表中，平均只需查找 14 次就可找到指定元素。
C# 的数组内置了二分查找方法——Array.BinarySearch，它是一个静态方法。
显然，在调用这个方法之前，必须确保作为参数的查找表内的关键字已经按顺序排列，否则就需要先行调用 Array.Sort() 方法给查找表排序后再调用 Array.BinarySearch() 进行查找。
在 C# 中，System.Collections.SortedList 和 System.Collections.Generic.SortedList<TKey, TValue> 类是用于存放键/值对的集合类，它们的元素存储于线性表中，并按键进行排序。
其中 SortedList 使用了两个数组分别存放 key 和 value。
分块查找又称索引查找，是针对分块有序数据的一种静态查找算法，分块有序并非指整个顺序表元素有序，而是将某一范围的数据划分在一个数据块内。
这好比将一个班级某门课成绩划分等级，成绩为 90～100 分的学生信息放在一个数据块，成绩为 80～89 分的学生信息放在一个数据块内，然后专门使用一个索引表记录每一个分数段所在数据块的起始位置。这样在查找指定成绩的学生信息时，只需在索引表中找到相应的数据块的位置，在这个数据块中进行查找即可。
本页给出索引块与顺序表索引的对应关系：
索引表中记录每块的最大关键字与该块的起始地址，查找时先在索引表中确定块，再进入该块顺序查找。
分块查找的时间复杂度为 O(n 的 1/2 次方)，它的效率介于顺序查找和二分查找之间，是顺序查找和二分查找的折衷方案。
在分块查找中，不同的数据类型有不同的划分方法，把一个顺序表划分为多少块，每块大小多少都要根据实际情况来确定。
前面讨论的几种查找法中，二分查找效率最高，但二分查找要求表中记录按关键字排序，而且它只能在顺序表上实现，从而在删除和插入元素时需要移动表中的很多记录，这种由移动记录所引起的额外时间开销会部分抵消二分查找的优点。
如果不希望表中记录按关键字排序，而又希望得到较高的插入和删除效率，就可以考虑使用几种特殊的二叉树或树作为表的组织形式，在这里将它们统称为树表。
二叉查找树（Binary Search Tree，简称 BST）又称二叉排序树（Binary Sort Tree），它是满足如下性质的二叉树：
图中 (a) 满足上述性质是二叉查找树，(b) 因右子树中出现了小于根的值而不是二叉查找树。
二叉查找树的查找过程为：首先将给定值和根结点的关键字进行比较，若相等，则查找成功；否则，若小于根结点关键字，则在左子树上继续查找，若大于根结点关键字，则在右子树上查找。
图中给出了一棵多结点二叉查找树及查找路径示意。
二叉查找树的查找过程跟二分查找的查找过程非常相似，只是二分查找的判定树是根据有序顺序表动态生成的，而二叉查找树本身就是一棵以二叉树形式进行存储的树。
但二叉查找树跟二分查找的判定树有本质的区别：由于二分查找的查找表是有序的，无论元素按什么样的顺序插入，二分查找的判定树只有一个；二叉查找树中，如果元素的插入顺序不同，它所生成的二叉查找树有可能不同。
已知一个关键字为 k 的结点，若将其插入到二叉排序树中，只要保证插入后仍符合二叉排序树的定义即可。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找中路径上访问的最后一个结点的左孩子或右孩子。结点的插入方法如下：
二叉查找树结点的删除比较麻烦，在删除结点时，不能把以该结点为根的子树都删去，只能删掉该结点，并且还要保证删除后所得的二叉树仍然满足二叉查找树的性质。
假设要删除结点 p，结点 p 的双亲结点为 f，下面分三种情况讨论：
二叉查找树结点删除的三种情况：
本页给出两篇扩展阅读资料：
二者都是在二叉查找树基础上通过自平衡机制避免退化成链表的改进结构，具体链接请对照原课件查看。
本章介绍了几种常见的查找算法，下面对这几种查找算法做一个总结：
下载地址：{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}