数据结构c课件 第八章 查找

对查找表进行的操作
1）查询某个”特定的” 数据元素是否在查找表 中 2）检索某个”特定的”数据元素的各种属性 3）在查找表中插入一个数据元素 4）从查找表中删除数据元素
查找表可分为两类: 查找表可分为两类
静态查找表
仅作查询和检索操作的查找表。
动态查找表
有时在查询之后，还需要将“查询” 结果为“不在查找表中”的数据元素插 入到查找表中；或者，从查找表中删除 其“查询”结果为“在查找表中”的数 据元素。
8.2 基于线性表的查找法
具有顺序查找法、 具有顺序查找法、折半查找法和分块 顺序查找法 查找法三种 查找法三种 8.2.1顺序查找法 顺序查找法 顺序查找法的特点 特点是 顺序查找法的特点是：用所给关键字 与线性表中各元素的关键字逐个比较， 与线性表中各元素的关键字逐个比较， 直到成功或失败。 直到成功或失败。
平均查找长度： 平均查找长度：为确定数据元素在列表 中的位置， 中的位置，需和给定值进行比较的关键 字个数的期望值， 字个数的期望值，称为查找算法在查找 成功时的平均查找长度。 成功时的平均查找长度。 对于长度为n的列表 的列表， 对于长度为 的列表，查找成功时的平均 查找长度为： 查找长度为：
ASL=P1C1+ P2C2+…+ PnCn = ∑ni=1PiCi
21
56
45
33
55
25
17
int Locate(SeqList L，ElemType e) { i=0 ; /*i为扫描计数器，初值为0，即 从第一个元素开始比较*/ while ((i<=st)&&(L.elem[i]!=e) ) i++; /*顺序扫描表，直到找到值为e 的元素,或扫描到表尾而没找到*/ if (i<=st) return(i+1); /*若找到值为e的元素，则返回其序号*/ else return(-1); /*若没找到，则返回空序号*/ }
55
21
56
45
33
55
25
17
设置监视哨的顺序查找算法 int SeqSearch（RecordList l, KeyType k） （ ） /*在顺序表 中顺序查找其关键字等于 的元素，若找到， 在顺序表l中顺序查找其关键字等于 的元素， 在顺序表 中顺序查找其关键字等于k的元素 若找到， 则函数值为该元素在表中的位置，否则为0*/ 则函数值为该元素在表中的位置，否则为 { l.r[0].key=k; i=l.length; while (l.r[i].key!=k) i--; return（i）; （） } 其中l.r[0]为监视哨，可以起到防止越界的作用 为监视哨， 其中 为监视哨
35
46
58
60
low=10 6 12 15 18 22 25 28 35 46
mid=10 high=11 58 60
high=9 low=10
折半查找的算法如下： 折半查找的算法如下：
int BinSrch （SqList l, KeyType k）/*在有序表 中折半查找其关键 在有序表l中折半查找其关键 ） 在有序表 字等于k的元素 若找到，则函数值为该元素在表中的位置*/ 的元素， 字等于 的元素，若找到，则函数值为该元素在表中的位置 { low=1 ; high=l.length; /*置区间初值 置区间初值*/ 置区间初值 while ( low<=high) { mid=(low+high) / 2; if (k==l.r[mid]. key) return（mid）; /*找到待查元素 找到待查元素*/ （ ） 找到待查元素 else if (k<l.r[mid]. key) high=mid-1;/*未找到，则继续在前半区间进行查找 未找到， 未找到 则继续在前半区间进行查找*/ else low=mid+1; /*继续在后半区间进行查找 继续在后半区间进行查找*/ 继续在后半区间进行查找 } return (0); }
其中P 为查找列表中第i个数据元素的概 其中 i为查找列表中第 个数据元素的概 率，Ci为找到列表中第i个数据元素时， 为找到列表中第 个数据元素时， 个数据元素时 已经进行过的关键字比较次数。 已经进行过的关键字比较次数。
如何进行查找？ 如何进行查找？ 取决于查找表的结构。 取决于查找表的结构。 然而，查找表本身是一种很松散的结构，因此， 然而，查找表本身是一种很松散的结构，因此，为了 提高查找的效率， 提高查找的效率，需要在查找表中的元素之间人为地 附加某种确定的关系，换句话说， 附加某种确定的关系，换句话说，用另外一种结构来 表示查找表。 表示查找表。 讨论：查找表的表示方法和 讨论：查找表的表示方法和在该查找表下进行的各种 操作 查找的基本方法可以分为两大类，即比较式查找法 比较式查找法和 查找的基本方法 比较式查找法 计算式查找法。 计算式查找法 比较式查找法又可以分为基于线性表的查找法 基于 基于线性表的查找法和基于 比较式查找法 基于线性表的查找法 树的查找法 计算式查找法也称为hash哈希查找法 计算式查找法 哈希查找法
例如用折半查找法查找10、 的具体过程 的具体过程， 例如用折半查找法查找 、50的具体过程，其中 mid=(low+high)/2，当high<low时，表示不存在这 ， 时 样的子表空间，查找失败。 样的子表空间，查找失败。 用折半查找法查找12的过程为 的过程为： 用折半查找法查找 的过程为：
用折半查找法查找50的过程为： 用折半查找法查找 的过程为： 的过程为
1
6 low=1 6 12 15 18 22
2
12
3
15
4
18
5
22
6
25 mid=6 25
7
28
8
35
9
46
10
58
11
60 high=11
28 low=7
35
46 mid=9
58
60 high=11
6
12
15
18
22
25
28
1
6 low=1 6 low=1 6 12 12 15 mid=3 15 18 18 22
2
12
3
15
4
18
5
22
6
25 mid=6 25
7
28
8
35
9
46
10
58
11
60 high=11
28
35
46
58
60
high=5 22 25 28 35 46 58 60
low=1 high=2 low=2 mid=2 high=2 mid=1
顺序结构有关数据类型的定义： 顺序结构有关数据类型的定义： #define LIST_SIZE 20 typedef struct { KeyType key; OtherType other_data; } RecordType; typedef struct { RecordType r[LIST_SIZE+1]; /* r[0]为工作单元 */ 为工作单元 int length; } RecordList;
21
56
45
33
55
25
17
不设置监视哨的顺序查找算法 int SeqSearch（RecordList l, KeyType k） （ ）
/*不用监视哨法，在顺序表中查找关键字等于k的元素 不用监视哨法，在顺序表中查找关键字等于 的元素 的元素*/ 不用监视哨法 { i=l.length; while (i>=1&&l.r[i].key!=k) i--; if (i>=1) return（i） （） else return (0); } 循环条件i>=1判断查找是否越界。 判断查找是否越界。 循环条件 判断查找是否越界
8.1 查找的基本概念
列表：由同一类型的数据元素（或记录） 列表：由同一类型的数据元素（或记录）构成的集 可利用任意数据结构实现。 合，可利用任意数据结构实现。 关键字：数据元素的某个数据项的值，用它可以标 关键字：数据元素的某个数据项的值， 识列表中的一个或一组数据元素。 识列表中的一个或一组数据元素。 主关键字：如果一个关键字可以唯一标识列表中的 主关键字：如果一个关键字可以唯一标识列表中的 唯一标识 一个数据元素，则称其为主关键字 为主关键字， 一个数据元素，则称其为主关键字，否则为次关键 当数据元素仅有一个数据项时， 字。当数据元素仅有一个数据项时，数据元素的值 就是关键字。 就是关键字。
第八章 查 找
8.1查找的基本概念 8.2基于线性表的查找法 8.3基于树的查找法 8.4计算式查找法-----哈希法
无法显示图像。计算机可能没有足够的内存以打开该 无法显示图像。计算机可能没有足够的内存以打开该图像，也可能是该图像已损坏。请重新启动计算机，然后重新打开该文件。如果仍然显示红色 “x”，则 图像，也可能是该图像已损坏。请重新启动计算机， 可能需要删除该图像，然后重新将其插入。 然后重新打开该文件。如果仍然显示红色 “x”，则可能 需要删除该图像，然后重新将其插入。1Fra bibliotek3 4
7
10
2
5
8
11
优点：比较次数少，查找速度快，平均性能好。 优点：比较次数少，查找速度快，平均性能好。 缺点：要求待查的表为有序表，且插入、删除困难。 缺点：要求待查的表为有序表，且插入、删除困难。
8.2.3 分块查找法
分块查找法要求将列表组织成以下索引顺序结构： 分块查找法要求将列表组织成以下索引顺序结构： ★首先将列表分成若干个块（子表）。一般情况下， 首先将列表分成若干个块（ ）。一般情况下 首先将列表分成若干个块 子表）。一般情况下， 块的长度均匀，最后一块可以不满。每块中元素任 块的长度均匀，最后一块可以不满。 意排列，即块内无序，但块与块之间有序。 意排列， 块内无序， 块与块之间有序。 ★构造一个索引表。其中每个索引项对应一个块并 构造一个索引表。 构造一个索引表 记录每块的起始位置，和每块中的最大关键字（ 记录每块的起始位置，和每块中的最大关键字（或 最小关键字）。索引表按关键字有序排列。 ）。索引表按关键字有序排列 最小关键字）。索引表按关键字有序排列。