数据结构-第9章静态查找

学习目标①理解查找的基本概念，包括静态查找表和动态查找表，内查找和外查找之间的差异以及平均查找长度。②重点掌握线性表上各种查找算法、包括顺序查找、二分查找和分块查找的基本思想、算法实现和查找效率方法的本③掌握哈希表查找技术以及哈希表与其他质区别④灵活运用各种查找算法解决一些综合问题。概述本章的“查找”（Searching）及第十章的“排序”(Sorting)都是建立在数据结构上的两个重要运算。查找又称为“检索”，是在给定信息集上寻找特定信息元素的过程。查找是一种十分有用的操作，例如，在学生成绩表中查找某个学生的成绩记录，在馆的书目文件中查找某的记录等。本章

查找的基本概念、不同数据结构下的查找算法及查找效率分析等问题。概述查找表（Search

Table）由同一类型的数据元素（或记录）构成的集合。示例9-1：集合A={0，1，2，3，4，5，6，7}进行两个操作：查找5和查找8查询(Searching)特定元素是否在表中。查找若表中存在特定元素，称查找成功，应输出该记录查找成功若表中不存在特定元素，称查找不成功（也应输出失败标志或失败位置）查找失败概述示例9-2：在如下学生表中查找学号为98011的学生信息。学号98011张娟女2098012赵军男19…………分析：在这个例子中，待查找的数据单位(或数据元素)是一条记录。而记录又由若干数据项(或属性)组成。若某个数据项的值能标识(或识别)一个或一组记录，称其为关键字(key)。若一个key能唯一标识一个记录，称此key为主key。若一个key能标识一组记录，称此key为次key。概述对查找表经常进行的操作有：①

查询某个“特定”数据元素是否在查找表中；②

检索某个“特定”数据元素的各种属性；③

在查找表中 一个数据元素；④

从查找表中删去某个数据元素；若只对查找表进行类似①②的“查找”操作，此类查找表称为静态查找表。若在查找过程中，同时会进行类似③④的“更新”操作，此类查找表称为动态查找表。9.1

静态查找表静态查找是指在静态查找表上进行的查找操作，在查找表中查找满足条件的数据元素的 位置或各种属性。本节将 以线性结构表示的静态查找表及相应的查找算法。针对静态查找表的查找算法主要有：顺序查找（线性查找）

折半查找（二分或对分查找）静态树表的查找分块查找（索引顺序查找）9.1.1

顺序表的查找顺序查找（线性查找）顺序查找的基本思路：从表的一端开始，顺序扫描线性表，依次将扫描到的关键字和给定值k相比较，若当前扫描到的关键字与k相等，则查找成功；若扫描结束后，仍未找到关键字等于k的记录，则查找失败。9.1.1

顺序表的查找顺序查找（线性查找）（1）顺序表的机内

结构：typedef

struct

{ElemType

*elem;//表基址，0号单元留空。表容量为全部元素int

length;//表长，即表中数据元素个数}SSTable;9.1.1

顺序表的查找顺序查找（线性查找）（2）顺序查找算法的实现int

Search_Seq(

SSTable

ST

,

KeyType key

){//在顺序表ST中，查找关键字与key相同的元素；若成功，返回其位置信息，否则返回0S em[0].key

=key;for(

i=ST.length;

S//设立哨兵em[

i

].key!=key;

-

-

i

);return

i;

//从后往前开始查找，找不到返回0.}

//

Search_Seq9.1.1

顺序表的查找顺序查找（线性查找）（3）顺序查找算法的性能分析平均查找长度（Average

Search

Length)为确定记录在查找表中的位置，将和给定值进行比较的关键字个数的期望值称为查找算法在查找成功是的平均查找长度。ASL=∑PiCi其中Pi为查找表中第i个记录的概率，Ci为找到表中关键字和给定值相等的第i个记录时，和给定值已经进行过比较的关键字的个数。9.1.1

顺序表的查找顺序查找（线性查找）（3）顺序查找算法的性能分析设Ci(1≤i≤n)为查找第i记录的key比较次数(或查找次数)：Cn=1；Cn-1=2；Ci=n-i+1；C1=n若r.data[n].key=k，若r.data[n-1].key=k，……若r.data[i].key=k，……若r.data[1].key=k，则ASL=nP1+(n-1)P2+…+2Pn-1+Pn假设每个记录的查找概率相等，Pi=1/n则ASL=∑PiCi

=(1/n)

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

顺序表的查找顺序查找（线性查找）（3）顺序查找算法的性能分析由上分析可知，ASL=O(n)而查找失败时，查找次数等于n+l，同样为O(n)。对查找算法，若ASL=O(n)，则效率是最低的，意味着查找某记录几乎要扫描整个表，当表长n很大时，会令人受。但是顺序查找的优点是：算法简单且适应面广。它对表的结构无任何要求，无论记录是否按关键字有序均可应用，而且上述结构对线性链表也适合。9.1.2

有序表的查找折半查找（二分或对分查找）折半查找的基本思路：对给定值k，逐步确定待查记录所在区间，每次将搜索空间减少一半(折半)，直到查找成功或失败为止。9.1.2

有序表的查找折半查找（二分或对分查找）Eg9-2

折半查找举例，已知有如下12个元素的有序表（3，12，18，20，32，55，60，68，80，86，90，100）请查找关键字为20的数据元素。解：①先设定3个辅助标志:low,high,mid，033232high

midmid

low0312182032556068808690100lowhigh9.1.2

有序表的查找折半查找（二分或对分查找）②算法描述int

Binsearch(sqlist

r,keytypek)

//对有序表r折半查找的算法//{

int

low,high,mid;

low=1;high=r.len;

//上下界初值//while(low<=high)

//表空间存在时//{mid=(low+high)/2;

//求当前mid//if

(k==r.data[mid].key)return(mid);

//查找成功，返回mid//if(k<r.data[mid].key)high=mid-1;

//调整上界，向左部查找//else

low=mid+1;

}return(0);

}//调整下界，向右部查找////low>high，查找失败//9.1.2

有序表的查找折半查找（二分或对分查找）③折半查找的算法分析:二分查找的效率（ASL）的元素有1个（20），即中间值；的元素有2个（21），即1/4处（或3/4）处；的元素有4个（22），即1/8处（或3/8）处…1次比较就查找成功,需要2次比较就查找成功,需要3次比较就查找成功,需要……则第m次比较时查找成功,需要 的元素会有（2m-1）个；为方便起见，假设表中全部n个元素＝

2m-1个，此时就不 第m次比较后还有剩余元素的情况了。全部比较总次数为1×20＋2×21＋3×22＋4×23…＋m×2m—1

=推导过程j1m

j

2

j1n

nmlog2

(n

1)

1

log2

n1

n

1j1平均每个数据的查找时间:

ASL

j

2

j1

9.1.2

有序表的查找折半查找（二分或对分查找）③折半查找的算法分析找到有序表中任一记录的过程就是：走了一条从根结点到与该记录相应的结点的路径。比较的关键字个数：为该结点在判定树上的层次数。查找成功时比较的关键字个数最多不超过树的深度d:d=

log2n

+1查找不成功的过程就是走了一条从根结点到外部结点的路径。6397查找过程可用二叉树描述：每个记录用一个结点表示；结点中值为该记录在表中位置，这个描述查找过程的二叉树称为判定树。n个元素的表的折半查找的判定树是唯一的，即：判定树由表中元素个数决定。9.1.2

有序表的查找折半查找（二分或对分查找）③折半查找的算法分析折半查找的效率比顺序查找高，但折半查找只适用于有序表，且限于顺序

结构，对链表无法有效地进行折半查找。课堂练习使用折半查找算法时，要求被查文件(

Ｃ)、DＡ．采用链式存贮结构

Ｂ．记录的长度≤128Ｃ．采用顺序存贮结构Ｄ．记录按关键字递增有序思考：假设在有序线性表a[20]上进行折半查找，则平均查找长度为

3.7

。9.1.4

索引顺序表的查找分块查找（索引顺序查找）分块查找(Blocking

Search)，又称索引顺序查找（IndexedSequential

Search），是顺序查找方法的一种改进，目的也是为了提高查找效率。9.1.4

索引顺序表的查找分块查找（索引顺序查找）1．分块设记录表长为n，将表的n个记录分成b=记录数可以少于s个），即：且表分块有序，即第i（1≤i≤b-1）块所有记录的key小于第i+1块中记录的key，但块内记录可以无序。2．建立索引每块对应一索引项：其中kmax为该块内记录的最大key；link为该块第一记录的序号（或指针）。n/s个

块，每块s个记录（最后一块kmaxlink9.1.4

索引顺序表的查找分块查找（索引顺序查找）Eg9-3：设表长n=19，取s=5，b=⌈19/5⌉=4，则分块索引结构序号R.key1050118412721356145590188819108Kmax序号(索引表)块1块2块3块41816算法思路分块索引查找分两步进行：(1)由索引表确定待查找记录所在的块；(2)在块内顺序查找。查找失败情况，一是给定k值超出索引表范围；二是若k落在某块内，但该块中无key=k的记录。9.1.4

索引顺序表的查找分块查找（索引顺序查找）索引顺序查找的算法分析分块查找算法的时间复杂度为：ASL=Lb+Ls其中Lb为对索引表的平均查找长度；Ls为块内查找的平均查找长度。一般索引表采