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

1、2.7查找查找的基本概念查找的定义：给定一个值K,在含有n个记录的文件中进行搜索，寻找一个关键字值等于K 的记录，如找到则输出该记录；否则输出查找不成功信息。线性查找线性查找又称顺序查找，是一种最简单的查找方法，它的基本思想是从第一个记录开始，逐 个比较记录的关键字，直到和给定的K值相等，则查找成功；若比较结果与文件中n个记录 的关键字都不等，则查找失败。如图268和图2.69图2.69城性査捉流准图二对分查找又称为跳跃式查找，假设记录是按关键字递增有序排列的，对分查找的基本思想是：先找到“中间记录”，比较其关键字与给定值K相等，则查找成功；如果关键字小于给定值K则说 明被查找记录必在前半区间

2、中；反之则在后半区间中。这样把搜索区间缩小了一半，继续进 行查找。在算法中，设置一个下界指示器low和一个上界指示器high它们分别指向待查文件搜索区 间的头、尾。由low和high的值可以计算出冲间记录”位置，由mid表示。niid=|jlow+high)/2j设顺序表 r1:n的关键字项为 ri.key (iwiwn将 K 值 rmid.key比较：若 rmid.key=K查找成功若 rmidkey>K 若 rmidkeyK 若 lowz>high令high=mid-1继续查找 令low=mid+1继续查找 查找不成功假设记录的关键字为(5, 13, 17, 42, 46, 5

3、5, 70, 94),现分别用K为55和12进行查找,K=12(to)513174246557094lowmidhigh513 "142 46 55 70 94K=55low mid查找成功何查找过程如图2.70所示，其中(a)为K=55, 查找成功；b)为K=12, 查找失败。图2E对分查找对分查找算法如下：BINSERRCH(r,n,K)1. low-1;high-n /上下界指示器赋初值/2. while (lowvhigh) do3. mic(low+high) div 2 / d为整除/4. case5. K=rmid .key:查找成功;return6. K>rmi

4、d .key: lomid+17. K<rmid .key: higmid-18. end(case)9. end(while)10. returnfi3)霓比曲次(Q) 丈比較3次(94)比较H決12.71对分査找和斯树分块查找分块查找又称索引顺序查找，它要求文件中的记录关键字 分块有序”即文件可按关键字 分为若干块，且前一块中最大的关键字小于后一块中最小的关键字，而每一块内的关键字则 不一定有序。基本思想为：先将各块中的最大关键字构成一个索引表，由于文件是分块有序 的因此索引表是递增有序的。查找过程分两步进行,第一步先对索引表进行对分或顺序查找， 以确定记录在哪一块；第二步在所在块中

5、进行顺序查找。如图72所示第1块第2決第3块圏2J2分块査找二叉排序树查找BSTSEARCH(K,t) /K为查找给定值t为根结点指针/1t /p为查找过程中进行扫描的指针/2. while (pv>nil) do3. case4. K=data(p):查找成功;return5. Kvdata(p): q-p;pL child(p)继续向左搜索/6. K>data(p): q-p；pR child(p)继续向右搜索/7. end(case)8. end(while)9. GET(s); data(s)K; L child(s-nil; R child(s)nil;/查找不成功，生成

6、一个新结点s插入到二叉排序中/10. case11. t=nil:p- s;插入结点为根结点/12. Kvdata(q): L child(q)s13. K>data(q): R child(q)s14. end(case)15. return图匕73不同插入次序的二叉排序树哈希表技术及其查找1哈希表哈希查找的基本思想是：通过对给定值作某种运算，直接求得关键字等于给定值的记录在文 件中的位置。这就要求在建立文件时，对记录的关键字和她的存储位置之间建立一个确定的 对应关系。设关键字key与存储位置见的对应关系为H(key),若用一维数组来存放文件，则 H(key即为数组的下标。称函数H为哈

7、希(hash函数，H (key)为哈希地址，这个一维 数组称为哈希表。例如以学生姓名为关键字的记录集合Wang, Li, Zhao, Shen, Gao, Fung, Bai, Chang, Ren, Ma若采用关键字中第一个字母表中的序号作为哈希函数则可以构成一个哈 希表如图2.74所示1-23鼻5歩7901-|234£歩7&90 丄壬345衣眾 工工11111工122.22226|1(1) 数字分析法将不均匀的数字删除，然后根据存储空间的大小来决定数字的数目。例如有个学生的学号 为542 42 2241542 81 3678542 22 8171542 38 967154

8、2 54 1577542 88 5376542 佃 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将关键字

9、平方后取第2, 3, 4位构成哈希地址为(010, 210, 440, 345,243, 247, 678, 112 116。(3) 除留余数法除留余数法是对关键字取模作为哈希函数，即H(key)=key mod p其中p必须是小于或等于表长的质数。(4) 折叠法折叠法是将关键字值分为几段，除了最后一段外，其余各段都须等长，然后将各段相加作为 哈希地址。在相加时有两种方法：移位折叠：将各段想左边靠齐后相加。边界折叠：将奇数字段或偶数字段倒排后相加。例如关键字值为 分为 5 段：P“=123, P=241, P=241, P=112, P=20,其移位 折叠和边界折叠分别如图2.75(a和(b所

10、示。Pl123123巧203P302p3241P241P斗112Pq21120P520879897(a)(b)图2-75折叠法3解决冲突的方法为同义词寻找“另一个”地址。(1)线性探测再散列设哈希表的空间为T0:m-1哈希函数为H(keyK线性探测再散列求 另一个”地址的公式 为dj+1=(di+j) mod m (j=1,2,s；ls)其中 d1=H(key。查找算法如下：LINSRCH(K,T,m) T0:m-1 为哈希表,K 为给定值/1. LH(K); jT /H为哈希函数J为哈希地址/2. while (Tj keyv>k) and (Tj keyv>0) do3片(j+

11、1) mod m环形地址/4if (j=i) then 表满'etUrn5. end(while)6. return(j)返回值为查到的哈希地址，如果Tj.key=0表示此地址为空，可将关键字为K的记录插入该 地址中。利用线性探测解决冲突极易造成关键字值聚集在一块(见2.76(a)，从而增加查找时间。 (2)平方探测再散列本办法用来改善线性探测的缺点，避免相近的关键字值聚集在一块。当发生冲突时，求“ 一个”地址的公式是s >1)rd2p (di+J 2) mod md 2j+r Wrjmod m(3) 随机探测再散列随机探测再散列是用一组预先给定的随机数来求发生冲突时的另一个”地

12、址，公式为dj+i=(d1+Rj) mod m (j=1,2, 寺 1) 其中Rj为一组随机数列。-设有一组关键字为(13, 29, 01, 23, 44, 55, 20, 84, 27, 68, 11, 10 79, 14)的记录， n=14,选择0=0.75则哈希表长m=n/ J T9哈希表为T0:18J用除留余数法构造哈希函数，选p=17,分别用线性探测、平方探测 和随机探测方法解决冲突，而建成的哈希表分别如图2.76(a) (b)、(c所示。其中随机探测所 用的随机数列为3, 16, 55, 44,。(4) 链地址法链地址法解决冲突的做法是:若哈希表为T0,m-1设置一个有m个指针分量

13、组成的一维数 组ST0:m-1讥哈希地址为i的记录都插入到头指针为STi的链表中。上例中的一组关键字 用链地址法构造哈希表如图2.77所示。图 2.77法用链地址法解决冲突的哈希表查找算法如下:CHNSRCH(ST,m,k) ST0:m-1每个分量STi或为nil或为链表的头指针。链表中每个结点 由两个域组成data存放关键字,next存放指向下一结点的指针71. LH(K) /H为哈希函数K为给定查找值/2. pSTi /链表的头结点/3. while (pv>nil) and (datap<>k) do4. pnext(p)5. end(do)6. return返回时p的

14、指向即为查找元素地址，若p=nil说明表中无此元素，则可将关键字为K的记录 插入哈希表中。哈痢地 ht 0123456789 10 11 12 13 14 15 16 17 18哈布表 比较冼数68014>20554>23中4>4-127291311108479141111112114617527：:1:旨"V11IZ%Z%IIIJ i! I冲突处理 （线性探卿79；:14012345 67 89 10111213141516171S014*205S4>2379*104427291314US44>11111531211141晤布地址比较冼数V X冲笑处疥 （普方探测110123456789 10 11 12 13 14 15 16 17 186801*2055*23271004411工9137984144>11111341111212JXXX哈布地址 哈希表 比较次数冲突虻理 （随机探测X X 10/S(c)图2/