查找的基本概念.ppt

度可表示为：
2020-6-17
n
ASL n pici i 1
谢谢阅读
8.2静态表的查找
静态查找表可分为顺序表、有序表和索 引顺序表三种。
2020-6-17
谢谢阅读
8.2.1顺序表的查找
顺序表的查找基本思想是：从顺序表的 一端开始，逐个比较结点的关键字和给 定值，若某个结点的关键字与给定值相 等，则查找成功；若找遍整个顺序表都 不相等，则查找失败。查找成功时，查 找算法返回找到结点在顺序表中的位置， 失败时返回－1。
图8.2 表及索引表结构图
谢谢阅读
分块查找的平均查找长度：
ASL =ASL +ASL
bs
b
w
ASL 表示分块查找的平均查找长度，ASL 表
bs
b
示查找索引表以确定所在块的平均查找长度，
ASL 表示在块中查找关键字的平均查找长度。 w
2020-6-17
谢谢阅读
8.3动态表的查找
动态查找表的特点是：表结构本身是在查 找过程中动态生成的，即对于给定值key， 若表中存在关键字等于key的结点，则查找 成功；否则插入关键字为key的结点。
2020-6-17
谢谢阅读
例：已知有11个关键字的有序表序列如下所示：
02，08，15，23，31，37，42，49，67，83， 91
当给定的k值为23和83时，折半查找的过程如图
所示。图中用方括号表示当前的查找区间，用 “↑”指向中间位置。
2020-6-17
谢谢阅读
【算法8.2】二分法查找非递归算法
2020-6-17
谢谢阅读
例8.2 设有一个顺序表共有20个结点，现将它分 成四块，每块5个结点。以每块最大关键字值建立 索引表，索引表包含最大关键字值和对应块的起 始地址两个域，如图8.2所示。试查找关键字值为 58的结点。
23 54 76 99 0 5 10 15
2020-6-17
3 23 12 9 21 54 25 45 33 30 60 58 76 70 65 89 80 77 93 99
2020-6-17
谢谢阅读
8.3.1二叉排序树
二叉排序树又称二叉查找树，它或者是一棵空 树，或者是具有以下性质的二叉树：
若任一结点的左子树非空，则左子树中的所有 结点的值都不大于根结点的值；
若任一结点的右子树非空，则右子树中的所有 结点的值都不小于根结点的值。
2020-6-17
谢谢阅读
例如：图8.3所示为一棵二叉排序树（结点内的数 为数据元素的关键字）。其中序遍历序列为：15， 55，65，75，79，95，100，120，200，230， 240。
第8章 查 找
查找是数据处理中经常使用的一种重要运算， 查找算法的优劣对系统运行效率的影响非常 大。静态查找表、动态查找表和哈希表是主 要的查找技术。
本章要点
❖查找的基本概念；
❖几种常见的静态查找表的查找算法；
❖二叉排序树的创建、查找和删除算法；
❖平衡二叉树的基本操作；
❖哈希函数的构造方法和哈希表的查找算法。
2020-6-17
2020-6-17
谢谢阅读
下面的算法描述了顺序查找过程。
❖ 顺序表的存储结构定义如下：
typedef struct {
…
KeyType key；
/*关键字的数据类型*/
…
} DataType；
/*数据元素的类型*/
typedef struct {
DataType *data；/*顺序表data*/
i=S.len;
/*设置初始查找位置*/
while (S.data[i].key!=key) i--； /*从后往
前找*/
if (i==0) return –1；
/*查找失败*/
else return i；
/* 查找成功*/
}
❖ 顺序查找的平均查找长度为： ASL n 1(n i 1) n 1
low=mid+1； else return mid ；}
return –1；}
2020-6-17
谢谢阅读
8.2.3索引顺序表的查找
索引顺序查找又称为分块查找，是顺序查找的一 种改进方法。在索引顺序查找法中，除表本身以 外，还需要建立一个“索引表”。
分块查找的基本思想：把顺序表分成若干块，每一 块中结点的存放是任意的，但是块与块之间必须 有序。假设块间按关键字值递增排序，以每块中 的最大（小）关键字值建立一个索引表，存放每 块的最大（小）关键字值和每块的起始位置。查 找时需分两步走，首先在索引表中采用顺序查找 或折半查找算法查找给定值，确定给定值所在的 块；然后在所确定的块中顺序查找。
2020-6-17
谢谢阅读
章节安排
8.1查找的基本概念 8.2静态表的查找 8.3动态表的查找
8.4散列表
2020-6-17
谢谢阅读
8.1查找的基本概念
❖ 查找：又称检索，是指在查找表中查找满足一 定条件的结点或记录。
❖ 查找方法：静态查找、动态查找
❖ 衡量查找算法优劣指标：最大查找长度、平均
查找长度如对n个记录进行查找时，平均查找长
int len； /*顺序表的长度*/
}Stable；
2020-6-17
谢谢阅读
【算法8.1】顺序表查找算法
int Stable_Search(Stable S，KeyType key) {/*在顺序表S中查找关键字等于key的结点*/
int i;
S.data[0].key=key；
/*设置哨兵*/
2020-6-17
谢谢阅读
i1 n
2
8.2.2有序表的查找
二分法查找（Binary Search）又称为折半查 找，其基本思想是：首先取查找表中间位置上 的结点的关键字与给定值进行比较，若相等， 则查找成功；否则，如果给定值比中间位置上 的结点的关键字大，则把查找区间定为表的后 半段，反之把查找区间定为表的前半段；然后 在前半段或后半段采用同样的方法继续查找， 如此继续，直到找到关键字等于给定值的结点， 则查找成功；若出现查找区间的左右边界异常， 则查找失败。
int Binary_Search(Stable S，
KeyType key) {
int low，mid，high；
low=1；high=S.len； while(low<=high) {mid=(low+high)/2； if(key<S.data[mid].key) 1；
high=mid-
else if(key>S.data[mid].key)