软件应用技术基础：查找算法.doc

2.7查找
2.7.1 查找的基本概念
查找的定义：给定一个值K，在含有n个记录的文件中进行搜索，寻找一个关键字值等于K的记录，如找到则输出该记录；否则输出查找不成功信息。
2.7.2 线性查找
线性查找又称顺序查找，是一种最简单的查找方法，它的基本思想是从第一个记录开始，逐个比较记录的关键字，直到和给定的K值相等，则查找成功；若比较结果与文件中n个记录的关键字都不等，则查找失败。如图2.68和图2.69

2.7.3 对分查找
又称为跳跃式查找，假设记录是按关键字递增有序排列的，对分查找的基本思想是：先找到“中间记录”，比较其关键字与给定值K相等，则查找成功；如果关键字小于给定值K则说明被查找记录必在前半区间中；反之则在后半区间中。这样把搜索区间缩小了一半，继续进行查找。
在算法中，设置一个下界指示器low和一个上界指示器high，它们分别指向待查文件搜索区间的头、尾。由low和high的值可以计算出“中间记录”位置，由mid表示。

设顺序表r[1:n]的关键字项为r[i].key (1≤i≤n)将K值r[mid].key比较： 若r[mid].key=K 查找成功
若r[mid].key＞K 令high=mid-1，继续查找
若r[mid].key＜K 令low=mid+1，继续查找
若low＞high 查找不成功
假设记录的关键字为（5，13，17，42，46，55，70，94），现分别用K为55和12进行查找，查找过程如图2.70所示，其中(a)为K=55，查找成功；(b)为K=12，查找失败。

对分查找算法如下：
BINSERRCH(r,n,K)
1.low←1;high←n //上下界指示器赋初值//
2.while (low<high) do
3.mid←(low+high) div 2 // div为整除//
4.case
5.K=r[mid].key: {查找成功;return}
6.K>r[mid].key: low←mid+1
7.K<r[mid].key: high←mid-1
8.end(case)
9.end(while)
10. return

2.7.4 分块查找
分块查找又称索引顺序查找，它要求文件中的记录关键字“分块有序”，即文件可按关键字分为若干块，且前一块中最大的关键字小于后一块中最小的关键字，而每一块内的关键字则不一定有序。基本思想为：先将各块中的最大关键字构成一个索引表，由于文件是分块有序的因此索引表是递增有序的。查找过程分两步进行，第一步先对索引表进行对分或顺序查找，以确定记录在哪一块；第二步在所在块中进行顺序查找。如图2.72所示

2.7.5 二叉排序树查找
BSTSEARCH(K,t) //K为查找给定值,t为根结点指针//
1.p←t //p为查找过程中进行扫描的指针//
2.while (p<>nil) do
3.case
4.K=data(p): {查找成功;return}
5.K<data(p): {q←p;p←L child(p)} //继续向左搜索//
6.K>data(p): {q←p;p←R child(p)} //继续向右搜索//
7.end(case)
8.end(while)
9.GET(s); data(s)←K; L child(s)←nil; R child(s)←nil;
//查找不成功,生成一个新结点s,插入到二叉排序中//
10.case
11.t=nil:p←s; //插入结点为根结点//
12.K<data(q): L child(q)←s
13. K>data(q): R child(q)←s
14.end(case)
15.return

2.7.4 哈希表技术及其查找
1.哈希表
哈希查找的基本思想是：通过对给定值作某种运算，直接求得关键字等于给定值的记录在文件中的位置。这就要求在建立文件时，对记录的关键字和她的存储位置之间建立一个确定的对应关系。设关键字key与存储位置见的对应关系为H(key)，若用一维数组来存放文件，则H(key)即为数组的下标。称函数H为哈希（hash）函数，H（key）为哈希地址，这个一维数组称为哈希表。例如以学生姓名为关键字的记录集合{Wang, Li, Zhao, Shen, Gao, Fung, Bai, Chang, Ren, Ma}，若采用关键字中第一个字母表中的序号作为哈希函数，则可以构成一个哈希表如图2.74所示

2.构造哈希函数的集中方法
(1) 数字分析法
将不均匀的数字删除，然后根据存储空间的大小来决定数字的数目。例如有7个学生的学号为
542 42 2241
542 81 3678
542 22 8171
542 38 9671
542 54 1577
542 88 5376
542 19 3552
第1，2，3位的数值太不均匀，删去；第8位中数值7出现次数太多，删去；假设存储空间为1000，则可选取第4，6，7位作为起存储地址，分别为422，836，281，396，515，853，135。
(2) 平方取中法
如果一组关键字在每一位上对某些数字的重复频率都很高，用数字分析法很难得到均匀的哈希函数。平方取中法首先求关键字的平方值，通过平方扩大差别，然后再选取其中几位作为哈希地址。例如一组关键字（0100，1100，1200，1160，2060，2061，2163，2261，2262），设 存储空间为1000，将关键字平方后取第2，3，4位构成哈希地址为（010，210，440，345，243，247，678，112，116）。
(3) 除留余数法
除留余数法是对关键字取模作为哈希函数，即
H(key)=key mod p
其中p必须是小于或等于表长的质数。
(4) 折叠法
折叠法是将关键字值分为几段，除了最后一段外，其余各段都须等长，然后将各段相加作为哈希地址。在相加时有两种方法：
·移位折叠：将各段想左边靠齐后相加。
·边界折叠：将奇数字段或偶数字段倒排后相加。
例如关键字值为12320324111220，分为5段：P1=123, P2=241, P3=241, P4=112, P5=20，其移位折叠和边界折叠分别如图2.75(a)和(b)所示。

3.解决冲突的方法
为同义词寻找“另一个”地址。
(1) 线性探测再散列
设哈希表的空间为T[0:m-1]，哈希函数为H(key)。线性探测再散列求“另一个”地址的公式为
dj+1=(d1+j) mod m (j=1,2,…,s s≥1)
其中d1=H(key)。
查找算法如下：
LINSRCH(K,T,m) //T[0:m-1]为哈希表,K为给定值//
1.i←H(K); j←i //H为哈希函数,j为哈希地址//
2.while (T[j].key<>k) and (T[j].key<>0) do
3.j←(j+1) mod m //环形地址//
4.if (j=i) then {‘表满’ return}
5.end(while)
6.return(j)
返回值为查到的哈希地址，如果T[j].key=0表示此地址为空，可将关键字为K的记录插入该地址中。
利用线性探测解决冲突极易造成关键字值聚集在一块（见图2.76(a)），从而增加查找时间。
(2) 平方探测再散列
本办法用来改善线性探测的缺点，避免相近的关键字值聚集在一块。当发生冲突时，求“另一个”地址的公式是

(3) 随机探测再散列
随机探测再散列是用一组预先给定的随机数来求发生冲突时的“另一个”地址，公式为
dj+1=(d1+Rj) mod m (j=1,2,…,s s≥1)
其中Rj为一组随机数列。-
设有一组关键字为（13，29，01，23，44，55，20，84，27，68，11，10，79，14）的记录，n=14，选择α=0.75，则哈希表长

哈希表为T[0:18]。用除留余数法构造哈希函数，选p=17，分别用线性探测、平方探测和随机探测方法解决冲突，而建成的哈希表分别如图2.76(a)、(b)、(c)所示。其中随机探测所用的随机数列为3，16，55，44，…。
(4) 链地址法
链地址法解决冲突的做法是：若哈希表为T[0,m-1]，设置一个有m个指针分量组成的一维数组ST[0:m-1],凡哈希地址为i的记录都插入到头指针为ST[i]的链表中。上例中的一组关键字用链地址法构造哈希表如图2.77所示。

用链地址法解决冲突的哈希表查找算法如下：
CHNSRCH(ST,m,k) //ST[0:m-1],每个分量ST[i]或为nil,或为链表的头指针。链表中每个结点由两个域组成data存放关键字,next存放指向下一结点的指针//
1.i←H(K) //H为哈希函数.K为给定查找值//
2.p←ST[i] //链表的头结点//
3.while (p<>nil) and (data[p]<>k) do
4.p←next(p)
5.end(do)
6.return
返回时p的指向即为查找元素地址，若p=nil说明表中无此元素，则可将关键字为K的记录插入哈希表中。

设有一组关键字为（13，29，01，23，44，55，20，84，27，68，11，10，79，14）的记录，n=14，选择α=0.75，则哈希表长
27/17=10, （10+3）/19=13, （10+16）=26/19=7
10/17=10, （10+3）/19=13, （10+16）=26/19=7 （10+55）/19=8
哈希表为T[0:18]。用除留余数法构造哈希函数，选p=3，16，55，44，…。
8 / 8