软件技术基础：查找算法.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表示。设顺序表r1:n的关键字项为ri.key (1in)将K值rmid.key比较： 若rmid.key=K 查找成功 若rmid.keyK 令high=mid-1，继续查找 若rmid.keyK 令low=mid+1，继续查找若lowhigh 查找不成功假设记录的关键字为（5，13，17，42，46，55，70，94），现分别用K为55和12进行查找，查找过程如图2.70所示，其中(a)为K=55，查找成功；(b)为K=12，查找失败。对分查找算法如下：BINSERRCH(r,n,K)1.low1;highn /上下界指示器赋初值/2.while (lowrmid.key: lowmid+17.Krmid.key: highmid-18.end(case)9.end(while)10. return 2.7.4 分块查找分块查找又称索引顺序查找，它要求文件中的记录关键字“分块有序”，即文件可按关键字分为若干块，且前一块中最大的关键字小于后一块中最小的关键字，而每一块内的关键字则不一定有序。基本思想为：先将各块中的最大关键字构成一个索引表，由于文件是分块有序的因此索引表是递增有序的。查找过程分两步进行，第一步先对索引表进行对分或顺序查找，以确定记录在哪一块；第二步在所在块中进行顺序查找。如图2.72所示2.7.5 二叉排序树查找BSTSEARCH(K,t) /K为查找给定值,t为根结点指针/1.pt /p为查找过程中进行扫描的指针/2.while (pnil) do 3.case4.K=data(p): 查找成功;return5.Kdata(p): qp;pR child(p) /继续向右搜索/7.end(case)8.end(while)9.GET(s); data(s)K; L child(s)nil; R child(s)nil;/查找不成功,生成一个新结点s,插入到二叉排序中/10.case11.t=nil:ps; /插入结点为根结点/12.Kdata(q): R child(q)s14.end(case)15.return2.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 2241542 81 3678542 22 8171542 38 9671542 54 1577542 88 5376542 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) 线性探测再散列设哈希表的空间为T0:m-1，哈希函数为H(key)。线性探测再散列求“另一个”地址的公式为dj+1=(d1+j) mod m (j=1,2,s s1)其中d1=H(key)。查找算法如下：LINSRCH(K,T,m) /T0:m-1为哈希表,K为给定值/1.iH(K); ji /H为哈希函数,j为哈希地址/2.while (Tj.keyk) and (Tj.key0) do 3.j(j+1) mod m /环形地址/4.if (j=i) then 表满 return5.end(while)6.return(j)返回值为查到的哈希地址，如果Tj.key=0表示此地址为空，可将关键字为K的记录插入该地址中。利用线性探测解决冲突极易造成关键字值聚集在一块（见图2.76(a)），从而增加查找时间。(2) 平方探测再散列本办法用来改善线性探测的缺点，避免相近的关键字值聚集在一块。当发生冲突时，求“另一个”地址的公式是 (3) 随机探测再散列随机探测再散列是用一组预先给定的随机数来求发生冲突时的“另一个”地址，公式为dj+1=(d1+Rj) mod m (j=1,2,s s1)其中Rj为一组随机数列。-设有一组关键字为（13，29，01，23，44，55，20，84，27，68，11，10，79，14）的记录，n=14，选择=0.75，则哈希表长哈希表为T0:18。用除留余数法构造哈希函数，选p=17，分别用线性探测、平方探测和随机探测方法解决冲突，而建成的哈希表分别如图2.76(a)、(b)、(c)所示。其中随机探测所用的随机数列为3，16，55，44，。(4) 链地址法链地址法解决冲突的做法是：若哈希表为T0,m-1，设置一个有m个指针分量组成的一维数组ST0:m-1,凡哈希地址为i的记录都插入到头指针为STi的链表中。上例中的一组关键字用链地址法构造哈希表如图2.77所示。用链地址法解决冲突的哈希表查找算法如下：CHNSRCH(ST,m,k) /ST0:m-1,每个分量STi或为nil,或为链表的头指针。链表中每个结点由两个域组成data存放关键字,next存放指向下一结点的指针/1.iH(K) /H为哈希函数.K为给定查找值/2.pSTi /链表的头结点/3.while (pnil) and (datapk) do 4.pnext(p)5.end(do)6.return返回时p的指向即为查找元素地址，若p=nil说明表中无此元素，则可将关键字为K的记录插入哈希表中。设有一组关键字为（13，29，01，23，4