《数据结构》第9章 查找

《数据结构》

第9章

查找

数据的组织和查找是大多数应用程序的核心，而查 找是所有数据处理中最基本、最常用的操作。特别当 查找的对象是一个庞大数量的数据集合中的元素时， 查找的方法和效率就显得格外重要。本章主要讨论顺序表、有序表、树表和哈希表查找 的各种实现方法，以及相应查找方法在等概率情况下 的平均查找长度。

《数据结构》

9.1 查找的概念查找表(Search Table):相同类型的数据元素(对象)组成的集合，每个元素通常由若干数据项构成。

关键字(Key,码):数据元素中某个(或几个)数据项的值，它可以标识一个数据元素。若关键字能唯一标 识一个数据元素，则关键字称为主关键字；将能标识若 干个数据元素的关键字称为次关键字。

查找/检索(Searching):根据给定的K值，在查找表中确定一个关键字等于给定值的记录或数据元素。 ◆ 查找表中存在满足条件的记录：查找成功；结果： 所查到的记录信息或记录在查找表中的位置。 ◆ 查找表中不存在满足条件的记录：查找失败。

《数据结构》

查找有两种基本形式：静态查找和动态查找。

静态查找(Static Search):在查找时只对数据元素进行查询或检索，查找表称为静态查找表。

动态查找(Dynamic Search):在实施查找的同时，插入查找表中不存在的记录，或从查找表中删除 已存在的某个记录，查找表称为动态查找表。

查找的对象是查找表，采用何种查找方法，首先取 决于查找表的组织。查找表是记录的集合，而集合中的 元素之间是一种完全松散的关系，因此，查找表是一种 非常灵活的数据结构，可以用多种方式来存储。根据存储结构的不同，查找方法可分为三大类：

《数据结构》

① 顺序表和链表的查找：将给定的K值与查找表中 记录的关键字逐个进行比较， 找到要查找的记录； ② 散列表的查找：根据给定的K值直接访问查找表， 从而找到要查找的记录； ③ 索引查找表的查找：首先根据索引确定待查找记 录所在的块 ，然后再从块中找到要查找的记录。

查找方法评价指标查找过程中主要操作是关键字的比较，查找过程中 关键字的平均比较次数(平均查找长度ASL:Average Search Length)作为衡量一个查找算法效率高低的标准。 ASL定义为：

ASL=∑ Pi Ci n为查找表中记录个数i=1

n

∑ Pi=1i=1

n

《数据结构》

其中： Pi :查找第i个记录的概率，不失一般性，认为查 找每个记录的概率相等，即P1=P2=…=Pn=1/n ;

Ci:查找第i个记录需要进行比较的次数。一般地，认为记录的关键字是一些可以进行比较运 算的类型，如整型、字符型、实型等，本章以后各节中 讨论所涉及的关键字、数据元素等的类型描述如下： 典型的关键字类型说明是：

typedef float KeyType ; typedef int KeyType ; typedef char KeyType ;/* 实型 */ /* 整型 */ /* 字符串型 */

数据元素类型的定义是：

《数据结构》

typedef struct RecType { KeyType key ; /* 关键字码 */

┇ /* 其他域

*/

}RecType ; 对两个关键字的比较约定为如下带参数的宏定义：/* 对数值型关键字 */

#define EQ(a, b) ((a)==(b)) #define LT(a, b) ((a)<(b)) #define LQ(a, b) ((a)<=(b))/* 对字符串型关键字 */

#define EQ(a, b) (!strcmp((a), (b)) ) #define LT(a, b) (strcmp((a), (b))<0 ) #define LQ(a, b) (strcmp((a), (b))<=0 )

《数据结构》

9. 2 静态查找静态查找表的抽象数据类型定义如下：

ADT Static_SearchTable{数据对象D:D是具有相同特性的数据元素的集合，

各个数据元素有唯一标识的关键字。数据关系R:数据元素同属于一个集合。 基本操作P:

┇} ADT Static_SearchTable 详见p216 。

线性表是查找表最简单的一种组织方式，本节介绍 几种主要的关于顺序存储结构的查找方法。

《数据结构》

9.2.1 顺序查找(Sequential Search)1 查找思想

从表的一端开始逐个将记录的关键字和给定K值进 行比较，若某个记录的关键字和给定K值相等，查找成 功；否则，若扫描完整个表，仍然没有找到相应的记录， 则查找失败。顺序表的类型定义如下： #define MAX_SIZE 100 typedef struct SSTable

{ RecType elem[MAX_SIZE] ; /* 顺序表 */int length ; }SSTable ;/* 实际元素个数 */

《数据结构》

int Seq_Search(SSTable ST , KeyType key) { int p ; ST. elem[0].key=key ; return(p) ; } 比较次数： 查找第n个元素： 1/* 设置监视哨兵,失败返回0 */

for (p=ST.length; !EQ(ST. elem[p].key, key); p--)

……….查找第i个元素： n-i+1 查找第1个元素： n 查找失败： n+1

《数据结构》

查找640 64 1 5 2 3 4 5 6 7 64 8 9 10 11 13 19 21 37 56 75 80 88 92

p

p

p

p

p

监视哨

比较次数=5 图9-1 顺序查找示例

2 算法分析不失一般性，设查找每个记录成功的概率相等，即 Pi=1/n;查找第i个元素成功的比较次数Ci=n-i+1 ; ◆ 查找成功时的平均查找长度ASL: ASL=∑ Pi Ci=i=1 n 1 ― n n

∑ (n-i+1)=i=1

n+1 2

《数据结构》

◆ 包含查找不成功时：查找失败的比较次数为n+1, 若成功与不成功的概率相等，对每个记录的查找概 率为Pi=1/(2n),则平均查找长度ASL: ASL=∑ Pi Ci=i=1n 1 2n

∑ (n-i+1)+i=1

n

n+12

=3(n+1)/4

《数据结构》

9.2.2 折半查找(Binary Search)折半查找又称为二分查找，是一种效率较高的查找 方法。

前提条件：查找表中的所有记录是按关键字有序(升序或降序) 。 查找过程中，先确定待查找记录在表中的范围，然 后逐步缩小范围(每次将待查记录所在区间缩小一半), 直到找到或找不到记录为止。

1 查找思想用Low、High和Mid表示待查找区间的下界、上界和 中间位置指针，初值为Low=1,High=n。

《数据结构》

⑴ 取中间位置Mid:Mid= (Low+High)/2 ;

⑵ 比较

中间位置记录的关键字与给定的K值：① 相等： 查找成功； ② 大于：待查记录在区间的前半段，修改上界指 针： High=Mid-1,转⑴ ; ③ 小于：待查记录在区间的后半段，修改下界指 针：Low=Mid+1,转⑴ ; 直到越界(Low>High),查找失败。

2 算法实现

《数据结构》

int Bin_Search(SSTable ST , KeyType key)

{ int Low=1,High=ST.length, Mid ;while (Low<High)

{

Mid=(Low+High)/2 ;if (EQ(ST. elem[Mid].key, key)) return(Mid) ; else if (LT(ST. elem[Mid].key, key)) Low=Mid+1 ;

else High=Mid-1 ;} return(0) ; }/* 查找失败 */

《数据结构》

3 算法示例 如图9-2(a),(b)所示。查找2115 Low 1 5 Low 1 5 2 3 2 3 4 5 6 7 64

2

3

4

5

6

764

8

9

10

11

13 19 21 37 56

75 80 88 92 Mid 8 9 10 11 High

13 19 21 37 56

75 80 88 92

Mid4 5 6

High 7 64 8 9 10 11

13 19 21 37 56

75 80 88 92

Low Mid High (a) 查找成功示例

《数据结构》