1、第九章查 找,何谓查找表？,查找表(Search Table)是由同一类型的数据元素(或记录)构成的集合。,由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。,对查找表经常进行的操作:,1）查询某个“特定的”数据元素是否在查找表中；2）检索某个“特定的”数据元素的各种属性；3）在查找表中插入一个数据元素；4）从查找表中删去某个数据元素。,仅作查询和检索操作的查找表。,静态查找表,有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。,动态查找表,查找表可分为两类:,所谓“查找”即
2、为在一个含有众多的数据元素（或记录）的查找表中找出某个特定的数据元素（或记录）。,是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）。,关键字(Key),若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。,若此关键字能识别若干记录，则称之谓“次关键字”。,根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。,查找(Searching),若查找表中存在这样一个记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”。查找结果给出“空记录”或“空指针”。,由于查找表中的数据元素之间不存在明显的组织
3、规律，因此不便于查找。为了提高查找的效率，需要在查找表中的元素之间人为地 附加某种确定的关系，换句话说，用另外一种结构来表示查找表。,如何进行查找？,查找的方法取决于查找表的结构。,9.1 静态查找表,9.2 动态查找表,9.3 哈希表,9.1 静 态 查 找 表,数据对象D：,数据关系R：,D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。,数据元素同属一个集合。,ADT StaticSearchTable,Create(,Destroy(,Search(ST,key);,Traverse(ST,Visit();,基本操作 P：,ADT StaticSe
4、archTable,构造一个含n个数据元素的静态查找表ST。,Create(,操作结果：,销毁表ST。,Destroy(,初始条件：操作结果：,静态查找表ST存在；,若 ST 中存在其关键字等于 key 的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。,Search(ST,key);,初始条件：操作结果：,静态查找表ST存在，key 为和查找表中元素的关键字类型相同的给定值；,按某种次序对ST的每个元素调用函数Visit()一次且仅一次，一旦Visit()失败，则操作失败。,Traverse(ST,Visit();,初始条件：操作结果：,静态查找表ST存在，Visit是对元素操作
5、的应用函数；,9.1.1 顺序表的查找,9.1.2 有序表的查找,9.1.4 索引顺序表的查找,以顺序表或线性链表表示静态查找表,9.1.1 顺序查找表,typedef struct/数据元素存储空间基址，建表时/按实际长度分配，0号单元留空 int length;/表的长度 SSTable;,假设静态查找表的顺序存储结构为,ElemType*elem;,数据元素类型的定义为:,typedef struct keyType key;/关键字域/其它属性域 ElemType;,TElemType;,ST.elem,回顾顺序表的查找过程：,假设给定值 e=64,要求 ST.elemk=e,问:k=
6、?,k,k,int location(SqList L,ElemType/location,顺序查找(Sequential Search)的查找过程为：从表中最后一个记录开始，逐个进行记录的关键字和给定值的比较，若某个记录的关键字和给定值比较相等，则查找成功，找到所查记录；反之，若直至第一个记录，其关键字和给定值比较不等，则表明表中没有所查记录，查找不成功。,int Search_Seq(SSTable ST,KeyType key)/在顺序表ST中顺序查找其关键字等于/key的数据元素。若找到，则函数值为/该元素在表中的位置，否则为0。ST.elem0.key=key;/“哨兵”for(i=
7、ST.length;ST.elemi.key!=key;-i);/从后往前找 return i;/找不到时，i为0/Search_Seq,ST.elem,i,ST.elem,i,60,i,key=64,key=60,i,64,在函数Search_Seq中，若返回的值为表示查找不成功，否则查找成功。函数中查找的范围从ST.elemST.length到ST.elem，ST.elem为监视哨，在查找之前将ST.elem 的关键字赋值为key,目的在于免去查找过程中每一步都要检查整个表是否查找完毕。若算法中不设立监视哨ST.elem，程序花费的时间将会增加。,定义：查找算法的平均查找长度(Averag
8、e Search Length)为确定记录在查找表中的位置，需和给定值 进行比较的关键字个数的期望值 其中:n 为表长，Pi 为查找表中第i个记录的概率，且，Ci为找到该记录时，和给定值比较过的关键字的个数。,分析顺序查找的时间性能,在等概率查找的情况下，顺序表查找的平均查找长度为：,对顺序表而言，Ci=n-i+1,ASL=nP1+(n-1)P2+2Pn-1+Pn,若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。,在不等概率查找的情况下，ASLss 在 PnPn-1P2P1时取极小值,上述顺序查找表的查找算法简单，但平均查找长度较大，
9、特别不适用于表长较大的查找表。,9.1.2 有序查找表,若以有序表表示静态查找表，则查找过程可以基于“折半”进行。,折半查找(Binary Search)的查找过程为：先确定待查记录所在的范围（区间），然后逐步缩小范围直到找到或找不到该记录为止。,ST.elem,ST.length,例如:key=64 的查找过程如下：,low,high,mid,low,mid,high,mid,low 指示查找区间的下界high 指示查找区间的上界mid=(low+high)/2,由此可见，折半查找过程是以处于区间中间位置记录的关键字和给定值比较，若相等，则查找成功，若不等，则缩小范围，直至新的区间中间位置记
10、录的关键字等于给定值或者查找区间的大小小于0时（表明查找不成功）为止。,int Search_Bin(SSTable ST,KeyType key)low=1;high=ST.length;/置区间初值 while(low=high)mid=(low+high)/2;if（EQ(key,ST.elemmid.key)return mid;/找到待查元素 else if(LT(key,ST.elemmid.key)high=mid-1;/继续在前半区间进行查找 else low=mid+1;/继续在后半区间进行查找 return 0;/顺序表中不存在待查元素/Search_Bin,先看一个具体的
11、情况，假设：n=11,分析折半查找的平均查找长度,6,3,9,1,4,2,5,7,8,10,11,判定树,1,2,2,3,3,3,3,4,4,4,4,假设 n=2h-1 并且查找概率相等则 在n50时，可得近似结果,一般情况下，表长为 n 的折半查找的判定树的深度和含有 n 个结点的完全二叉树的深度相同。,9.1.4 索引顺序表的查找,若以索引顺序表表示静态查找表，则Search函数可用分块查找来实现。,分块查找(Blocking Search)又称索引顺序查找。它是一种性能介于顺序查找和二分查找之间的查找方法。,1、查找表存储结构 查找表由“分块有序”的线性表和索引表组成。（1）“分块有序”
12、的线性表 线性表被均分为若干子表（块），每一块中的关键字不一定有序，但前一块中的最大关键字必须小于后一块中的最小关键字，即表是分块有序的。,（2）索引表抽取各块中的最大关键字及其起始位置构成一个索引表IDl.b，即：索引表中的每个元素含有两项内容：关键字项（其值为该块内的最大关键字）和指针项（其值为该块中第一个元素的在表中位置）由于查找表是分块有序的，所以索引表是一个递增有序表。,【例】下图就是一个带索引的分块有序的线性表。其中线性表L共有20个结点，被分成3块，第一块中最大关键字25小于第二块中的最小关键字27，第二块中最大关键字55小于第三块中的最小关键字60。,分块查找的基本思想分块查找
13、的基本思想是：（1）首先查找索引表索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。（2）然后在已确定的块中进行顺序查找 由于块内无序，只能用顺序查找。,可见，索引顺序查找的过程也是一个“缩小区间”的查找过程。,分块查找的平均查找长度=查找“索引表”确定所在块的平均查找长度+在块中查找元素的平均查找长度,即 ASLbs=Lb+Lw,一般情况下，为进行分块查找，可以将长度为n 的表均匀地分成b块，每块含有s个记录，即b=n/s 若以顺序检索来确定块，则分块查找成功时的平均查找长度为：,ASLbs=Lb+LW=,当 时，ASLbs取最小值+1,若以折半查找来确定块，则分块查找查找
14、成功时的平均查找长度为：ASLbs=Lb+Lwlog2（b+1）-1+（s+1）/2log2（n/s+1）+s/2,9.2 动 态 查 找 表,ADT DynamicSearchTable,抽象数据类型动态查找表的定义如下：,数据对象D：数据关系R：,数据元素同属一个集合。,D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。,InitDSTable(&DT),基本操作P：,DestroyDSTable(&DT),SearchDSTable(DT,key);,InsertDSTable(,DeleteDSTable(,TraverseDSTable(DT,Visit();,ADT DynamicSearchTable,操作结果：,构造一个空的动态查找表DT。,InitDSTable(,销毁动态查找表DT。,DestroyDSTable(,初始条件：操作结果：,动态查找表DT存在；,若DT中存在其关键字等于 key的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”。,SearchDSTable(DT,key);,初始条件：操作结果：,动态查找表DT存在，key为和关键字类型相同的给定值；,动态查找表DT存在，e 为待插入的数据元素；,
