数据结构第五章查找

查找是为了得到某个信息而进行的工作，也称检索基本概念与术语静态查找表动态查找表哈希表查找基本概念关键码关键码是数据元素(或记录)中某个数据项的值，用它

可以标识一个数据元素。

主关键码：能唯一确定一个数据元素的关键码。次关键码：不能唯一确定一个数据元素的关键码。查找表查找表是一种以集合为逻辑结构、以查找为核心的数据结构。查找表的基本操作：建表、查找、读表元、插入与删除静态查找表：指一经建立就基本保持不变的查找表，

主要操作是检索。动态查找表：经常需要改动的查找表，常进行插入删除操作。平均查找长度查找是给定一个值key，在查找表中找出关键码

等于key的元素，如果找到，则查找成功；

否则查找失败（主关键字）。查找效率的标准是指查找过程中和关键码的平均比较次数，即平均查找长度ASL，定义为：5-1线性表查找表结构将数据元素组织为一个线性表，可以是基于数组的

顺序存储或以线性链表存储TypedefintKeyType;typedefstruct{KeyTypekey;DataTypeother;}ElemType;首先，关键码类型和数据元素类型约定如下描述：typedefstruct{ElemType*data;intlength;}SeqTable;静态查找表的顺序存储结构描述如下：静态查找表的链式存储结构及其结点类型描述如下：typedefstructnode{ElemTypedata;structnode*next;}NodeType;顺序查找基本思想是从查找表的一端开始顺序扫描，将查找表中

元素的关键码同给定的值比较，如果相等，则查找成功；

当扫描结束时，还未找到关键码等于给定值的元素，

则查找失败。顺序查找算法结束时，返回查找成功或失败的标志，

若查找成功，指出找到元素的位置，否则，给出失败信息。顺序查找既适合于顺序存储的静态查找表，

又适合于链式存储的静态查找。typedefintKeyType;typedefstruct{KeyTypekey;DataTypeother;}ElemType;typedefstruct{ElemType*elem;intlength;}SeqTable;顺序查找算法intS_Search(SeqTable*t,KeyTypekx){inti;t->elem[0]=kx;for(i=t->length;t->elem[i].key!=kx;i--);returni;}

intseqSearch(SeqTable*t,KeyTypekx,int*p){inti；

for(i=0；i<t->length；i++)if(t->elem[i].key==kx){*p=i；return(1)；}*p=i；

return(0)；}若找到的是第一个元素data[1]，则比较次数c1=n；若找到的是第i个元素data[i]，则比较次数ci=n-i+1；在不考虑检索失败的情况下，顺序检索的平均检索长度为

ASL=1*pn+2*pn-1+…+n*p1=(1+2+…+n)/n(pi=1/n)=(n+1)/2T（n)=O(n)优点是算法简单且适应面广，无论查找表中元素是否有序均可使用。

缺点是平均检索长度较大，特别是当n很大时，检索效率较低。有序表的查找二分查找基本思想是设查找表中的元素从小到大有序，首先将

给定值key与表中间位置上元素的关键码比较，如果相

等，则检索成功；否则，若key小，则在查找表前半部

分中继续进行二分法查找，若key大，则在查找表后半

部分中继续进行二分法查找。这样，经过一次比较就缩

小一半的查找区间，如此进行下去，直到检索成功或检

索失败。效率较高的查找方法71418212329313538424649520123456789101112lowmidhighhighmidhighmidlowmidstatusBinSearch(SeqTablet,KeyTypekx){intlow,high,mid;intflag;low=0;high=t->length-1;while(low<=high){mid=(low+high)/2;if(kx<t->elem[mid])high=mid-1;elseif(kx>t->elem[mid])low=mid+1;else{flag=mid;break;}}returnflag;}若表中元素个数n为：有则最大检索长度为j;若则最大检索长度为j+1，所以设检索每个元素的概率相同，则平均检索长度为：T(n)=O(log2n)插值查找类似于查英文字典的方法，在查找一个C开头的

英文单词时，从字典中间的一页开始，这就是

插值查找的基本思想。查找表顺序存储，数据元素的关键字在查找表中均匀分布。mid=low+kx-t.data[low].keyt.data[high].key-t.data[low].key(high-low)时间效率为T(n)=O(log2n)斐波纳契查找（黄金分割法）斐波纳契数列定义：设n个数据元素的有序表，且n正好是某个斐波纳契数。

可用此查找方法基本思想：对于表长为F(k)-1的有序表，以相对low

偏移量F(k-1)-1取中点，即mid=low+F(k-1)-1,对表进

行分割，则左子表表长为F(k-1)-1，右子表表长为

F(k)-1-F(k-1)-1＝F(k-2)-1。

一直分割到查找成功或查找失败。分块查找分块检查找（索引顺序查找），

是顺序查找的一个改进方法。索引表的整个表分成三个子表，对每个子表建立一个索引项，

其中包括两项内容：关键字项(其值为该子表内的最大关键字)

和指针项(指示该子表的第一个记录在表中的位置)。

索引表按关键字有序，表或者有序或者分块有序。

分块有序指的是后一个子表中所有记录的关键字均

大于前一个子表中的最大关键字。设n个数据元素查找表分为m个子表，

分块检索的平均检索长度为5-2哈希表查找哈希表查找法即散列法又称为杂凑法或关键码—地址转换法。

用散列法表示的查找表称为（哈希表）散列表。

散列函数使每个关键码都和结构中存储位置对应,

这样的一个对应关系称为散列(哈希Hash)函数。关键码存储地址h22113251527618412010012345678910例{18,27,1,20,22,6,10,13,41,15,25}h(key)=keymod11哈希表与哈希方法哈希表与哈希方法：选取某个函数，依该函数

按关键码计算元素的存储位置，并按此存放；

查找时，由同一个函数对给定值kx计算地址，

将kx与地址单元中元素关键码进行比较，

确定查找是否成功。若key1≠key2，有h(key1)=h(key2)，这种现象称为冲突（碰撞）。

key1和key2称为同义词。

h(key)的值域所对应的地址空间称为基本区域。

发生碰撞时，同义词可以存放在基本区域中未被占用

的单元，也可以存放到另外的区域中负载因子：

其中α>1时冲突不可避免。

(1)构造好的哈希函数哈希方法的两个问题：(2)制定解决冲突的方案所选函数尽可能简单，以便提高转换速度。转制换出来的地址要大致均匀分布，减少空间浪费。常用的哈希函数1.直接定址法取关键码的某个线性函数值为哈希函数。Hash(key)=a.key+b例：{100,300,500,700,800,900}1003005007008009000123456789Hash(key)=1/100*key2.除余法除余法是取关键码被某个不大于散列表长度m的

数P除后所得余数为散列地址。数p的选取，一般

可选P为小于基本区域长度m的最大素数比较好。22113251527618412010012345678910例{18,27,1,20,22,6,10,13,41,15,25}h(key)=keymod113.乘余取整法Hash(key)=取上式的整数部分作为哈希地址。a一般取值为：4.中平方法先求出关键码的平方，然后取中间几位作为地址。例如，关键码key=4731(4731)2=22382361h(key)=3825.数字分析法数字分析法是关键码位数比存储区的地址码的位数多,这时可以对关键码的各位进行分析,丢掉分布不均匀的位留下均匀位作为地址。例如:对下列关键码集合进行关键码到地址的转换。关键码是9位的，地址是3位的，需要经过分析丢掉6位。

Keyh(key)0003194263260007183097090006294436430007586157150009196979970003103293296.折叠法

折叠法是将关键码分割成倍数相等的几部分，最后一部分的倍数可以短点，将这几部分叠加求和，取后几位为哈希地址。例：key=25346358705移位叠加法：将各部分的最后一位对齐相加；间界叠加法：从一端向另一端沿各部分分界来回折叠，

最后一位对齐相加。分割：25346358705253463587+051308253

364

587

50+1254Hash(key)=308Hash(key)=254例如，关键码为key=582422241，要求转换为4位的地址码。

58|2422|241

移位折叠相加移位相加

855814224124222422110642721h1(key)=1064h2(key)=2721折叠法是将关键码分割成几部分，其中一部分的长度

等于地址码的长度，再加上其余部分，舍弃进位作为地址。++补充：处理冲突的方法1.开放定址法开放定址法解决碰撞的方法是在基本区域内形成

一个探查序列，沿探查序列进行检索，直到找

到该元素或碰到一个未被占用的地址为止。

插入时，直到找到一个空单元；检索时，

或检索到关健码为key的元素或检索到达一个空单元。Hi=(Hash(key)+di)MODmi=1,2,…,k(k≤m-1)其中：m为表长，di为增量序列，可有多种取法；di=1,2,3,…,m-1,di=i称线性探查序列；①线性探查法由线性探查序列,解决碰撞,称为线性探查法。关键码集：{47,7,29,11,16,92,22,8,3}哈希表长为11，

Hash(key)=keymod11477012345678910291116922283②二次探测法di=12,-12,22,-22,…,k2,-k2(k≤m/2)称为二次探查序列；801234567891016{47,7,29,11,16,92,22,8,3}477291192223③双哈希函数探测法di=i*ReHash(key),ReHash(key)是另一个散列函数，

称双散列探查序列；Hi=(Hash(key)+i*ReHash(key))MODm例如:K={18,73,10,05,68,99,27,41,51,32,25},Hash(key)=key%13，ReHash(key)=key%11+11873100123456789101112568992741513225２.拉链法设基本区域长度为m，建立m条链表，将所有关键字

为同义词的记录存储在同一条线性链表中。如果某

个基本区域地址中没有存放查找表元素，则对应的

链表为空链表；

发生冲突的同组同义词存放在同一条链表中。给定元素的关键码为key，首先计算出h(key)，

即确定是在第h(key)条链表中，

在链表中进行插入及检索操作。K={18,73,10,05,68,99,27,41,51,32,25}，h(key)=key%13{5,8,10,5,3,8,1,2,12,6,12}结点类型：typedefstructNode{keytypedey;…

structNode*next;

}NodeType;哈希表：typedefNodeType*OpenHash[m];#definem…intCreateHashT(OpenHashl_t;DataType*eptr){intI;intd,finished;for(i=0;i<m;i++)l_t[i]=NULL;for(;eptr->key!=0;eptr++){d=Hash(eptr->key);finished=MovElemToHashT(eptr,l_t,d);if(!finished)break;}returnfinished;}3.建立一个公共溢出区基本表溢出表5-4动态查找表二叉排序树查找表采用二叉排序树作为存储结构，既有较高的查找效率，

又具有链式存储时元素插入、删除操作的灵活性。二叉排序树的定义二叉排序树(BinarySortTree)或者是一棵空二叉树；或者具有下列性质的二叉树：(1).若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

(2).若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；((3).它的左右子树也分别为二叉排序树。6355425890706310456783一棵二叉排序树二叉排序树的查找过程(1)若查找树为空，查找失败。(2)查找树为非空，将给定值kx与查找树的根结点关键码比较；(3)若相等，查找成功，结束，否则有以下两种情况：①当小于根结点关键码，查找将在左子树上进行，转(1)；②当大于根结点关键码，查找将在右子树上进行，转(1)；typedefstructNode{KeyTypekey;structNode*lchild,*rchild;}BinTNode,*BiTree;intBSTSearch(BinTNode*T,BinTNode*C,BinTNode*F,

KeyTypex)

{intflag;C=T;flag=0;while(C)

if(x>C->key){F=C;C=C->rchild;}

elseif(x<C->key){F=C;C=C->lchild;}

else{flag=1;break;}returnflag;}

二叉排序树查找算法假设二叉排序树共有n个结点，高度是h()，

算法的执行时间代价最坏为O(h)。二叉排序树的插入操作和构造一棵二叉排序树在二叉排序树中插入新结点，要保证插入后仍是二叉排序树。插入新结点的方法是：(1).如果二叉排序树为空，则新结点为根结点。

(2).如果二叉排序树为非空，则将新结点的关键码与根结点的关键码比较，若相等表示该结点已在二叉排序树中；若小于根结点的关键码，则将新结点插入到根结点的左子树中；否则，插入到根结点的左子树中。(3).子树中的插入过程和树中的插入过程相同，如此进行下去，直到找到该结点，或者直到新结点成为叶子结点为止。635542589070631045678343二叉排序树插入一个结点的算法IntInsertNode(BinTNode*T,KeyTypex){BinTNode*p,*q,*s;intflag=0;p=*t;if(!BSTSearch(T,q,p,x)){s=newBinTNode;s->key=kx;s->lchild=s->rchild=NULL;flag=1;if(!p)T=s;else{if(x>p->key)p->rchild=s;elsep->lchild=s;

}

}returnflag;

}

例如：已知关键码集合K={18,73,10,05,68,99,27,41,51,32,25}，写出二叉排序树的构造过程1873100568992741513225StatusCreatBST(BinTNode*T){KeyTypex;T=NULL;cin>>x;while(x!=-1){InsertNode(T,x);cin>>x;}returnsuccess;}二叉排序树的删除操作在二叉排序树中删除一个指定结点，删除结点后的二叉树

还是一棵二叉排序树。设待删除结点为p，其双亲结点为f，分以下三种情况：(1)p是叶结点。(2)p是单分支结点，即只有左子树pl或右子树pr,

只需用子树根结点代替p结点。

(3)p有左右子树时,按中序遍历保持有序进行调整。FPfpPL两种调整方法：①直接令p结点的右孩子p1为f相应的子树，将p的

原左子树pL作为以pr为根的子树中序遍历的第一

个结点的左子树。②用p结点的直接后继pr(或直接前驱)替换p结点。

再用(2)方法删去pr。FPfpPLP1P2PJPRS1S2SJSRFPpPLP1P2PJPRS1S2SJSRfPR二叉排序树删除算法intDeleteNode(BinTNode*T,KeyTypex)

{BinTNode*p,*q,*s,*f;intflag=0;p=T;if(BSTSearch(T,q,p,x))

if(q){if(q->lchild==NULL&&q->rchild==NULL){if(p){if(p->lchild==q)p->lchild=NULL;elsep->rchild=NULL;}elseT=NULL;free(q);}elseif(q->lchild==NULL){if(p){if(p->lchild==q)p->lchild=q->rchild;elsep->rchild=q->rchild;}elseT=q->rchild;free(q);}elseif(q->rchild==NULL){if(p){if(p->lchild==q)p->lchild=q->lchild;elsep->rchild=q->lchild;}

elseT=q->lchild;free(q);}else{child=q->rchild;while(child->lchild)child=child->lchild;child->lchild=q->lchild;if(p){if(p->lchild==q)p->lchild=q->rchild;elsep->rchild=q->rchild;}elseT=q->rchild;free(q);}returnsuccess;}returnfailure;}在二叉排序树上查找关键字实际上是走了一条从根结点

到某个结点的路径的过程，比较的次数等于路径长度加1。

因此，比较的次数不超过树的深度。但是具有n个结点的

二叉树可以有不同的形态，因此，对于不同形态的二叉

排序树，其平均查找长度也是不同的。

最坏的情况下蜕变为单支树，此时的平均查找长度为（n+1)/2。平衡二叉树（AVL树）平衡二叉树的定义是一棵空树或是具有下列性质的二叉排序树：

它的左子树和右子树都是平衡二叉树，且左子树和

右子树高度之差的绝对值不超过1.72418530607891426550477241853060789142非平衡二叉树平衡二叉树3-30000000002-2011-101平衡因子：结点左右子树高度之差的数字称为结点的平衡因子在平衡二叉树上插入或删除结点后，得进行平衡调整左单旋转（RR型）aBhDhEhcxaBhDhEhcx27510-1BA27510-1BA73-2735100BA27051270-1BA1007341099730BA510274101000-10990-1-1-2acDhEhBhxacDhEhBhx右单旋转（LL型）271001BA271001BA052271000BA050512701BA10005180003011251270BA1000518003010先左后右双向旋转（LR型）先右后左双向旋转（RL型）B树和B＋树B树和B＋树用于外存文件的索引。

一棵m阶的B树，或为空树，或是满足下列特性的m叉树：（1）树中每个结点至多有m棵子树；（2）除根之外的所有分支结点至少有m/2棵子树；（3）若根结点不是叶子结点，则至少有两棵子树；（4）有j个子女的非叶结点中恰好有j-1个关键码，且按递增顺序排列，结点中包含的信息为

(p0,k1,p1,k2,…,kj-1,pj)B树的定义其中ki(i=1,..,j-1)为关键码，且ki<ki+1(i=1,…,j-2);pi(i=0,…,j-1)为指向子树根结点的指针，且pi-1所指子树中所有结点的关键码均小于ki(i=1,…,j-1),pj-1所指子树中所有结点的关键码均大于kj-1,j（m/2<=j<=m-1）为关键码的个数。（5）所有叶子结点都在同一层上，实际上这些结点不存在。当m=2时，m阶B树实际上就是二叉排序树。所以m阶B树是二叉排序树的推广。其查找过程和二叉排序树类似，它是一个沿指针查找结点和在结点的关键码中进行顺序查找交叉进行的过程。实际应用中，m和内外存交换的单位有关，一般，m=1024B树主要用于文件的索引。结点类型可以如下说明：#definem 3typedefstructBTNode{int keyNum; /*关键字个数*/structBTNode*parent; /*指向父结点*/KeyType key[m+1];/*关键字向量*/structBTNode*ptr[m+1];/*子树指针向量*/Record *recPtr[m+1]/*指向文件中的记录号*/}NodeType;1、B树的检索keykiki+1pi

首先在根结点的关键码集合中进行检索，若key==ki

，则检索成功；否则，key一定在ki

和ki+1

之间（存在某个i），沿pi继续查找，重复上述过程，直到检索成功，或pi为空，检索失败。B树的运算性能分析在B树是进行查找包含两种基本操作：（1）在B树中找结点；（2）在结点中找关键字。由于B树通常存储在磁盘上，因此前一操作是在磁盘上进行的，而后一操作是在内存中进行的，即在磁盘上找到指针p所指结点后，先将结点中信息读入内存，然后查询。而在磁盘上进行操作比在内存中操作慢得多，因此在磁盘上进行查找的次数，即待查关键字所在结点在B树是的层次数，是决定B树查找效率的关键因素。现在考虑最坏的情况：含n个关键字的m阶B树的最大深度 为logm/2(n+1)/2+12.B树的插入深度为h的m阶B树，新结点一般插入到h层，首先检索到第h层，确定插入结点位置。（1）若被插入结点中关键码个数小于m-1，则插入。（2）若被插入结点中关键码个数等于m-1，则引起结点“分裂”。可如下实现“分裂”：假设*p结点中含有信息为：

m,p0,(k1,p1),…,(km,pm)将*p分裂为*p和*p’两个结点，分别含有信息为：*p：m/2－1,p0,(k1,p1),…(km/2－1,pm/2－1)*p’：(m-m/2,pm/2,(km/2+1,pm/2+1),…(km,pm)把关键字km/2和指针*p’一起插入到*p的双亲结点中。3.B树的删除在深度为h的m阶B树中删除一个关键码，首先检索到该关键码所在的结点,然后根据不同情况进行删除。（1)若结点在第h层，且关键码数目大于m/2-1，则只需从该结点中删去该关键码ki。（2）若结点在第h层，且关键码数目等于m/2-1，该结点左兄弟（或右兄弟）结点中的关键码数目大于m/2－1，则需调整被删除关键码的结点，兄弟结点，以及父结点中的信息。方法：设父结点中的信息为：（p0,k1,p1,k2,p2,…,kxpx),由pi指向被删除关键码的结点，其的信息为：（p0,k

1,p

1,k2,p

2,…,k