【数据结构讲解】查找

《【数据结构讲解】查找》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、查找顺序查找是一种最基本和最简单的查找方法。它的思路是，从表中的第一个元素开始，将给定的值与表中逐个元素的关键字进行比较，直到两者相符，查到所要找的元素为止。否则就是表中没有要找的元素，查找不成功。对于表中记录的关键字是无序的表，只能采用这种方法。描述顺序查找的算法见框图8-1。其中n是表r的长度，k是要查的元素的关键字，i查到的元素的序号。折半查找又称二分查找，是针对有序表进行查找的简单、有效而又较常用的方法。所谓有序表，即要求表中的各元素按关键字的值有序（升序或降序）存放。折半查找不像顺序查

2、找那样，从第一个记录开始逐个顺序搜索，其基本思想是：首先选取表中间位置的记录，将其关键字与给定关键字k进行比较，若相等，则查找成功；否则，若k值比该关键字值大，则要找的元素一定在表的后半部分（或称右子表），则继续对右子表进行折半查找；若k值比该关键字值小，则要找的元素一定在表的前半部分（左子表），同样应继续对左子表进行折半查找。每进行一次比较，要么找到要查找的元素，要么将查找的范围缩小一半。如此递推，直到查找成功或把要查找的范围缩小为空（查找失败）。设表的长度为n，表的被查找部分的头为low，尾

3、为high，初始时，low=1,high=n,k为关键字的值。（2）若k=r[mid].key,成功，否则：若kr[mid].key,则low=mid+1,重复（1）；直到成功或不成功（此时low>high）。具体算法如下：Voidbinsrch(structnoder[],intn,intk){intmid,low,high,find;low=1;high=n;find=0;/*置区间初值*/while((low<=high)&

4、&(!find)){mid=(low+high)/2;/*求中点*/if(k==r[mid].key)find=1;/*已查到*/elseif(k>r[mid].key)low=mid+1;/*在后半区间查找*/elsehigh=mid-1;/*在前半区间查找*/}if(find)return(mid);/*查找成功，返回找到元素的位置*/elsereturn(0);/*查找不成功，返回0标记*/}采用折半查找，当查找成功时，最少比较次数为一次，如在上例中查找关键字值为18的结点，只需一次比较。

5、最多经过log2n次比较之后，待查找子表要么为空，要么只剩下一个结点，所以要确定查找失败需要log2n次或log2n+1次比较。可以证明，折半查找的平均查找长度是：从折半查找的平均查找长度ASL来看，当表的长度n很大时，该方法尤其能显示出其时间效率。但由于折半查找的表仍是线性表，若经常要进行插入、删除操作，则元素排列费时太多，因此折半查找比较适合于一经建立就很少改动而又需要经常查找的线性表，较少查找而又经常需要改动的线性表可以采用链接存储，使用顺序查找。分块查找在处理线性表时，如果既希望能够快速

6、查找，又要经常动态变化，则可以采用分块查找方法。分块查找又称索引顺序查找，要求将待查的元素均匀的分成块，块间按大小排序，块内不排序。因此需要建立一个块的最大（或最小）关键字表，称之为“索引表”。具体而言，假设我们按结点元素关键字升序方式组织表中各块，则要求第一块中任一结点的关键字值都小于第二块中所有结点的关键字值；第二块中任一结点的关键字值都小于第三块中所有结点的关键字值；如此类推。然后选择每块中的最大（或最小）关键字值组成索引表。换言之，索引表中的结点个数等于线性表被分割的块数。例如要找关键字

7、为k的元素，则先用折半查找法由索引表查出k所在的块，再用顺序查找法在对应的块中找出k。在图8-2中若要找关键字值为41的元素，则先由索引表查出41在第二块中（29<41<64），再在第二块中找到41。由此我们可以总结：分块查找分两步进行，第一步确定要查找结点在表中的哪一块，第二步在确定的块中找到该结点。分块查找的平均查找长度为：ASL=ASLb+ASLe其中ASLb是折半查找的平均查找长度，ASLe是用顺序查找法查块内元素的平均查找长度。设每块中有s个元素，可以近似的得到：可以看出分块查找的平均

8、查找长度位于顺序查找和折半查找之间。下面我们简单的对以上几种查找方法做出比较：（1）平均查找长度：折半查找最小，分块查找次之，顺序查找最大；（2）表的结构：顺序查找对有序表、无序表均适用；折半查找仅适用于有序表；分块查找要求表中元素是逐段有序的，就是块与块之间的记录按关键字有序；（3）存储结构：顺序查找和分块查找对向量和线性链表结构均适用；折半查找只适用于向量存储结构的表，因而要求表中元素基本不变，而在需要插入或删除运算时，要移动元素，才能保持表的有序性，所以影响了查找效率。哈希法哈希法又名散列