数据结构第8章

第八章查找8.1概述8.3基于树的查找8.5算法总结8.2基于线性表的查找8.4散列8.1概述1、

列表(查找表):是由同一类型的数据元素(或记录)构成的集合,可由任意数据结构实现。2、关键字:数据元素中某数据项的值,用以标识(识别)一个(组)数据元素(记录)。若关键字可以唯一的识别一个记录，则称之为“主关键字”；若关键字识别的记录不唯一，则称之为“次关键字”。3、查找

根据某个给定值,在列表中确定其关键字等于给定值的数据元素(记录)的过程称为查找。

若列表中存在待查记录,则称“查找成功”。查找结果给出整个记录的信息,或指示该记录在列表中的位置；

若列表中不存在待查纪录,则称“查找不成功”.查找结果给出“空记录”或“空指针”。4、查找表的分类1)静态查找表:仅作查询和检索操作的列表。2)动态查找表:不仅作查询和检索操作，还经常进行插入和删除操作的列表。

在查找算法中要用到三类参量，即：①查找对象K（找什么）②查找范围L（在哪找）③查找的结果（K在L中的位置）其中①②为输入参量，在函数中不可缺少；③为输出参量，可用函数返回值表示。5、平均查找长度为确定数据元素在列表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法在查找成功时的平均查找长度。对于长度为n的列表，查找成功时的平均查找长度为：nASL=P1C1+P2C2+…+PnCn

=i=1PiCi其中：Pi为查找列表中第i个数据元素的概率，

Ci为找到列表中第i个数据元素时，已经进行过的关键字比较次数。6、查找的基本方法：查找方法：比较式查找法计算式查找法－HASH(哈希)查找法基于线性表的查找法基于树的查找法8.2基于线性表的查找有顺序查找、折半查找和索引查找法三种一、顺序查找法顺序查找的特点是：用所给关键字与线性表中各元素的关键字逐个比较，直到成功或失败。存储结构：顺序结构链式结构#defineMAXSIZE1000Typedef

int

KeyTypetypedef

struct{

KeyTypekey;

OtherTypeother_data; }RecordType;typedef

struct{

RecordTyper[MAXSIZE+1];

/*r[0]为工作单元*/

intlength; }SeqRList;1、顺序结构数据类型定义：顺序查找过程示例：或ii假设给定值k=64,要求r[i].key=k,问:i=?结果:i=7

2137881992

5

6456807513…

901234567891011

niiiiiii2、顺序查找算法int

SeqSearch（SeqRListL,KeyTypeK）{i=L.length;while(i>=1&&L.r[i].key!=K)i--;if(i>=1)return（i）elsereturn(0);}循环条件i>=1判断查找是否越界。设置监视哨的顺序查找算法int

SeqSearch（SeqRListL,KeyTypeK）{L.r[0].key=K;i=L.length;while(L.r[i].key!=K)i--;return（i）;}l.r[0]为监视哨，可以防止越界。例：

2137881992

5

6456807513…

901234567891011

niiK=56

2137881992

5

6456807513…

901234567891011

n56结果:i=8iiK=6060结果:i=03、顺序查找的时间复杂度分析åi=1PiCiASL=n因为：对顺序表而言：Ci=n-i+1在等概率查找的情况下：顺序表查找成功的平均查找长度为：顺序表查找不成功的平均查找长度为：

ASLSS=n+1所以，顺序表查找的时间复杂度为:O(n)二、折半查找法（二分搜索法）条件：要求待查找的列表必须是按关键字大小有序排列的顺序表。查找方法：由于列表是按关键字有序排列，所以可以基于“折半确定区间”的思想进行查找。优点：比较次数少，查找速度快;缺点：要求表为有序表，插入、删除困难。1、概念例如:nK=64

的查找过程如下：lowhighmid

mid

midlow

：指示查找区间的下界high：指示查找区间的上界mid=(low+high)/2:每次比较、划分区间的“点”lowhigh0123456789101105131921375664758088922、折半查找算法int

BinSrch

（SeqRListL,KeyTypeK）

{low=1;high=L.length;/*置区间初值*/while(low<=high){mid=(low+high)/2;

if(K==L.r[mid].key)return（mid）;

/*找到待查元素*/

elseif(K<L.r[mid].key)high=mid-1;

/*继续在前半区间查找*/

elselow=mid+1;

/*继续在后半区间查找*/}return(0);}3、折半查找时间复杂度分析先看一个具体的情况，假设：n=11折半查找判定树1223333444

46391471025811一般情况,表长为n的折半查找判定树的深度和含有n个结点的完全二叉树的深度相同。假设n=2h-1并且查找概率相等则ASLbs»log2(n+1)-1所以，折半查找的时间复杂度为:O(logn)最坏情况查找长度为二叉树的深度：log2n+1查找不成功时的比较次数最多也为：log2n+1当n>50时近似为三、索引查找分块查找要将列表组织成以下索引顺序结构：★首先将列表分成若干个块(子表),一般情况下块的长度均匀,最后一块可以不满。每块中元素任意排列(块内无序)，但块与块之间有序。★构造一个索引表,其中每个索引项对应一个块,

记录每块的起始位置及每块中的最大关键字

(或最小关键字)。索引表按关键字有序排列。

整个表由两部分组成：基本块表与索引表。例：224886

1

6

12索引表各块最大关键字

各块起始地址221213

8

9

3342382448287449…12345678910111213…分块查找过程1)由索引确定记录所在的块(折半或顺序查);2)在块内进行查找(顺序查)。索引可以根据查找表的特点来构造。可见:

索引顺序表查找的过程也是一个

“缩小区间”的查找过程。

分块查找时间复杂度分析分块查找的平均查找长度=

查找“索引”的平均查找长度

+“块内”查找的平均查找长度

若n个记录分为b块，每块含s个记录，则等概率情况下,顺序查找索引时：

ASL=(b+1)/2+(s+1)/2=(n/s+s)/2+1

可以证明：当s=√n时,ASL取最小值√n+1折半查找索引时：ASL=log2(n/s+1)+s/2.线性表的三种查找方法比较顺序查找折半查找索引查找表的结构有序、无序有序表间有序表的存储顺序、链式顺序顺序、链式ASL最大最小次之8.3基于树的查找法一、二叉排序树二、平衡二叉树三、B树和B+树四、伸展树五、红黑树

8.3.1二叉排序树（二叉查找树）一、定义二、查找三、插入四、删除五、性能分析一、定义：（1）若左子树不空，则左子树上所有结点的值均小于根结点的值；二叉排序树：或者是一棵空树，或者是具有如下特性的二叉树：（3）左、右子树也分别为二叉排序树。（2）若右子树不空，则右子树上所有结点的值均大于根结点的值；例如:是二叉排序树。不50308020901085403525238866*中序遍历一个二叉排序树,可以得到一个递增有序序列。

typedef

structNode{KeyTypekey;/*关键字的值*/

……

structnode*Lchild,*Rchild;/*左右指针*/}BSTNode,*BSTree;通常用二叉链表作为二叉排序树的存储结构二叉排序树的存储结构二、查找根据二叉排序树的特点，查找过程如下：（1）k=t：则查找成功，返回根结点地址；（2）k<t：则进一步查左子树；（3）k>t：则进一步查右子树。显然这是一个递归过程，可用递归算法实现查找。若二叉排序树为空，则查找不成功；否则将待查关键字k与根结点关键字t进行比较，如果：例如:50308020908540358832二叉排序树查找关键字==50,505035,503040355090,50809095,从上述查找过程可见：在查找过程中，生成了一条查找路径：

从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点;或者

从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。

——查找成功

——查找不成功BSTree

SearchBST(BSTree

bst,KeyType

K){if(!bst)returnNULL;else

if(bst->key==K)returnbst;else

if(K<bst->key)returnSearchBST(bst->lchild,key);else

returnSearchBST(bst->rchild,key);}二叉排序树查找的递归算法BSTree

SearchBST(BSTree

bst,KeyType

K){BSTreeq;q=bst;while(q){if(q->key==K)returnq;

if(K<q->key)q=q->lchild;

elseq=q->rchild;}returnNULL;}二叉排序树查找的非递归算法三、插入1、若二叉排序树为空树，则s成为二叉排序树的根；2、若二叉树排序树非空，则将key与二叉树排序树根结点的值t进行比较，如果:已知关键字值为Key的结点由s指示，将其插入二叉排序树的过程为：（1）key=t：不进行插入；（2）key<t：则将s插入左子树；（3）key>t：则将s插入右子树。显然，可以用递归算法实现插入。voidInsertBST(BSTree*bst,KeyType

K){BiTrees;

if(*bst==NULL){s=(BSTree)malloc(sizeof(BSTNode));s->key=K;*bst=s;s->lchild=NULL;s->rchild=NULL;}

else

if(K<(*bst)->key)

InsertBST(&((*bst)->lchild),K);else

if(K>(*bst)->key)

InsertBST(&((*bst)->rchild),K);}二叉排序树插入算法二叉排序树的生成算法给定一个元素序列，可以利用插入算法逐步创建一棵二叉排序树。将二叉排序树初始化为一棵空树，然后逐个读入元素，每读入一个元素，就调用上述插入算法将新元素插入当前已生成的二叉排序树中，直至元素序列插入完毕。voidCreateBST(BSTree*bst){KeyTypekey;*bst=NULL;

scanf("%d",&key);while(key!=ENDKEY){InsertBST(bst,key);scanf("%d",&key);}}例如：元素输入序列为：45,24,53,12,28,90,按上述算法生成的二叉排序树的过程：空树45插入454524插入24452453插入5345245312插入124524531228插入28452453122890插入90对同样一组元素值，如果输入的顺序不同，所建的二叉排序树形态也不同。241228539045如将上述关键字顺序变为:24,53,90,12,28,45,则生成的二叉排序树为：四、删除可分三种情况讨论：（1）被删除的结点是叶子；（2）被删除的结点只有左子树或只有右子树；（3）被删除的结点左、右子树都有。和插入相反，删除在查找成功之后进行,并且要求在删除二叉排序树上某个结点之后,仍然保持二叉排序树的特性。（1）被删除的结点是叶子结点50802090403588328530例如:被删关键字=2088其双亲结点中相应指针域的值改为“空”（2）被删除结点只有左子树或只有右子树其双亲结点的相应指针域的值改为“指向被删除结点的左子树或右子树”。被删关键字=408080405020908588323035（3）被删除的结点既有左子树也有右子树方法一：找被删结点p在中序序列中的直接前驱结点s(如图a所示),将p的左子树改为f(p的双亲)的左子树，将p的右子树改为s的右子树,结果如图(b)所示。

f->lchild=p->lchild；s->rchild=p->rchild；free(p)；FPCPRfpcSQQLSLqsCL(a)S为P的直接前驱CLFCSSLPRfc(b)将P的左子树改为f的左子，将P的右子树改为S的右子树。方法二：找到p结点在中序序列中的直接前驱结点s(如图a所示),用s结点的值替代p结点的值,再将s结点删除,原s结点的左子树改为s的双亲结点q的右子树,如图(b)所示。

p->data=s->data；q->rchild=s->lchild；free(s)；FPCPRfpcSQQLSLqsCL(a)S为P的直接前驱(b)将原P结点的值改为S结点的值，删除原S结点并将原S的左子树改为Q的右子树FSCPRfpcQQLSLqCL例：方法二被删关键字=5040508090858820323035以其前驱替代之，然后再删除该前驱结点4040被删结点前驱结点二叉排序树删除算法BSTNode*DelBST(BSTree

bst,KeyTypeK){BSTNode*p,*f,*s,*q;p=bst;f=NULL;

while(p){if(p->key==K)break;f=p;if（p->key>K）

p=p->lchild;elsep=p->rchild;}

if(p==NULL)returnbst;if(p->lchild==NULL)/*p没有左子树*/{if(f==NULL)bst=p->rchild;

elseif(f->lchild==p)f->lchild=p->rchild

；

elsef->rchild=p->rchild;free(p);}else/*p有左子树*/{q=p;s=p->lchild;

while(s->rchild){q=s;s=s->rchild;}

if(q==p)q->lchild=s->lchild;

elseq->rchild=s->lchild;p->key=s->key;free(s);}returnbst;}

时间复杂度为：O(LOG2N)五、二叉排序树的查找性能对于一组相同的关键字序列，关键字插入的先后次序不同，所构成的二叉排序树的形态及深度即不同。二叉排序树的平均查找长度ASL与二叉排序树的形态有关：二叉排序树的各分支越均衡,树的深度越浅，其平均查找长度ASL越小。例如：452412375393(a)输入关键字序列为{45,24,53,12,37,93}时的二叉排序树12122437455393(b)输入关键字序列为{12,24,37,45,53,93}时的二叉排序树假设每个元素的查找概率相等，则它们的平均查找长度分别是：ASL=(1+2+2+3+3+3)/6=14/6ASL=(1+2+3+4+5+6)/6=21/6由此可见，在二叉排序树上进行查找时的平均查找长度和二叉排序树的形态有关。若考虑把n个结点，按各种可能的次序插入到二叉排序树中，则有n！棵二叉排序树（其中有的形态相同）,可以证明，这些二叉排序树的平均查找长度仍然是O(log2n)。8.3.2平衡二叉树

对于二叉排序树,高度越低查找速度就越快。为此可在构造二叉排序树的过程中进行树形的优化，即平衡化处理,使其成为平衡二叉排序树。树中每个结点的左、右子树深度之差的绝对值不大于1，。1、定义：平衡二叉树(AVL树)或是一颗空树，或者是具有如下特性的二叉树：例如：5472是平衡树不是平衡树547218结点的平衡因子：结点的左子树的深度减去它的右子树的深度。

平衡二叉树上所有结点的平衡因子只可能是-1、0、1，否则不是平衡二叉树。例如:平衡二叉树不平衡的二叉树10010100-12因此，若构造的二叉树排序树是平衡二叉树，则可大大降低其查找长度。可以证明：平衡二叉树的深度与logn是同数量级2、平衡二叉排序树的构造

二叉排序树的构造过程，是不断插入新结点(叶子)的过程。插入新结点后,如果失去平衡则应立即进行平衡化调整，一般以失去平衡的最小子树为调整对象,随时的调整可确保二叉排序树的平衡。在一般二叉排序树的结点中增加一个存放平衡因子的域bf。例:输入(13,24,37,90,53),构造过程如下：13132413243713243790132437539013243790531324373790132453例：402560203010000AB(a)平衡二叉排序树402560203020101AB150(b)插入15后失去平衡25204015300010BA6000©调整后的二叉排序树(a)平衡二叉排序树2520403060-10000AB2520403060-2-10-10AB700(b)插入70后失去平衡40256030700-1000AB200©调整后的二叉排序树例：18010904020306050708595A0000C000000B(a)一棵平衡二叉排序树8010904020306050708595A0001C01000-1B4502(b)插入45后失去平衡060108040203050457090C-100100000BA859500©调整后的二叉排序树(a)一棵平衡二叉排序树-140A0508060709085950C00000B2010300000-240A1508060709085950C00-11B2010300040A508060709085950C00B201030005500(b)插入55后失去平衡0040C20608090859500B402007050551030-100000A©调整后的二叉排序树(1)LL型旋转:

左子树的左子树上插入结点而失去平衡，应进行顺时针旋转。

各种情况下，平衡化调整的规则可归纳为如下四种旋转：BAARBRBL新21ABARBRBL新00LL型失衡的特点是：A->bf=2，B->bf=1。操作：B=A->Lchild；A->Lchild=B->rchild；

B->rchild=A；A->bf=0；

B->bf=0；

(2)RR型旋转:右子树的右子树上插入结点而失去平衡，应进行逆时针旋转。BAALBLBR新-2-1ABBLALBR新00RR型失衡的特点是：A->bf=-2，B->bf=-1。操作：B=A->rchild；A->rchild=B->lchild；

B->lchild=A；A->bf=0；

B->bf=0；

(3)LR型旋转:左子树的右子树上插入结点而失去平衡,应进行先逆时针后顺时针旋转。CBAARCRCL新BL2-11CBAARCRCL新BL00-1LR型失衡的特点是：A->bf=2，B->bf=-1。操作：B=A->lchild；C=B->Rchild；B->rchild=C->lchild；

A->lchild=C->rchild；C->lchild=B；C->rchild=A；(4)RL型旋转:右子树的左子树上插入结点而失去平衡,应进行先顺时针后逆时针旋转。CBAALCRCL新BR-211CABBRCRCL新AL00-1RL型失衡的特点是：A->bf=-2，B->bf=1。操作:B=A->rchild；C=B->lchild；B->lchild=C->rchild；

A->rchild=C->lchild；C->lchild=A；C->rchild=B；8.4散列

一、哈希表的定义二、hash函数的构造方法三、处理冲突的方法四、hash表的查找五、hash法性能分析8.4.1哈希表的定义以上讨论的各种查找表的共同特点为：

记录在表中的位置和它的关键字之间不存在一个确定的关系，查找的过程是“基于”比较。查找的效率取决于和给定值进行比较的次数,这类方法的平均查找长度为O(logn)---O(n)。对频繁使用的查找表,希望ASL---〉0。能否做到？能！若以下标为000~999的顺序表表示之。如：为招收的1000名新生建立一张查找表,

其关键字为学号,其值的范围为xx000~xx999(前两位为年份)。则查找过程可以简单进行：取给定学号的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。

另例：1、各年龄人口信息统计表；

2、解放后各年国民经济信息统计表。上述几例的特点为：记录在表中的位置与其关键字之间存在一种确定的对应关系,按此对应关系可根据关键字的值寻址，从而获得待查纪录。这种查找表称为哈希表，关键字与记录地址间的对应关系称为哈希函数f(key)

。{Zi,Qi,Su,Li,Wu,Ci,He,Ye,Du}

又例：对于如下9个关键字设

哈希函数f(key)=

(Ord(第一个字母)-Ord('A')+1)/2CiZiQiSuLiWuHeYeDu问题:

若需添加关键字Zh,怎么办？此类问题称为“冲突”，如何解决？

0123

4567

8

9

10

11

12

13从上述例子可见：哈希表的构造、使用中有两个问题有待研究：1、如何根据关键字集合的特点，选择合适的哈希函数，使关键字均匀的散列到表中？2、当不同的关键字所得的哈希函数值相同时，即f(k1)=f(k2),如何有效的处理这类“冲突”现象（碰撞），使建表、查找均能有效地进行？根据选定的函数H(key)

和处理冲突的方法,将一组关键字映象到一个有限的、连续的地址集(区间)上，并以每个关键字在地址集中的“映象”作为相应记录在表中的存储位置，由此构造所得的查找表称为“哈希表”

(散列表、杂凑表),所选择的函数H(key)称为哈希函数。哈希表的定义：若是非数字关键字，则需先对其进行数字化处理。5.

基数转换法3.平方取中法1.除留余数法4.分段叠加法2.数字分析法

“好的”哈希函数应该是“均匀”的，对数字型关键字，一般有下列哈希函数的构造方法：二、构造哈希函数的方法设定哈希函数为:H(key)=keyMODp其中：p≤m(表长)

也可对2,3,4种方法的结果取模。

这是一种简单且适用范围很广的哈希函数，但要求：1、P不能取关键字基数的幂；

2、P应尽可能的取质数，或不包含小于20的质因数的合数；

3、P应尽可能的接近m。1.除留余数法此方法仅适合于：能预先估计出全体关键字的每一位上各种数字出现的频度。假设关键字集合中的每个关键字都是由s位数字组成(u1,u2,…,us)，分析关键字集中的全体,去掉数字重复出现频度很高的位,提取数字均匀分布的若干位或它们的组合作为地址。2.

数字分析法

以关键字平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”,平方值的中间几位与整个关键字中的每一位数字都相关。

此方法适合于:

关键字中的每一位都有某些数字重复出现频度很高的现象。3.平方取中法

将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加。

此方法适合于:

关键字的数字位数特别多，且每一位的数字分布大致均匀。4.分段叠加法首先将关键字看成是另一种进制的数，然后再转换成原来进制的数，再选择其中几位作为散列地址。例如：对于十进制关键字先把它看成是十三进制数，再转换为十进制数。5.

基数转换法

实际造表时,采用何种方法来构造哈希函数,考虑的因素有：建表的关键字集合的情况(包括关键字的范围和形态),哈希表的大小,哈希函数计算时间和查找频率。总的原则是:减少集聚现象,在关键字取值范围内,使哈希函数值尽量均匀散列在函数值范围内,从而使产生冲突的可能性尽量减小。为产生冲突的关键字寻找下一个哈希地址。1.开放定址法2.链地址法除了需要选择一个“好”(尽可能少产生冲突)的哈希函数之外；还需要找到一种“处理冲突”

的方法。其含义是：三、处理冲突的方法

为产生冲突的关键字H(key)求得一个探测地址序列(在其中逐个探测空哈希地址)：

H0,H1,H2,…,Hs

1≤s≤m-1其中：H0=H(key)Hi=(H(key)+

di

)MODm

di

为探测增量有三种，i=1,2,…,m-1

1.开放定址法(1)线性探测再散列

di=ci

最简单的情况

c=1(2)平方探测再散列

di=12,-12,22,-22,…,(3)随机探测再散列

di

是一组伪随机数列或者

di=i×H2(key)(又称双散列函数探测)探测增量序列

di

的三种取法：即：产生的Hi

均不相同,且m-1个Hi值能覆盖

哈希表中所有地址。则要求：

注意：增量di

应具有“完备性”※

随机探测时的m

和di

应没有公因子；※

平方探测时的表长

m

应为形如4j+3

的素数（如:7,11,19,23,…等）；※

避免二次聚集。012345678910例如哈希表长m=11，现有关键字集合：

{19,01,23,14,55,68,11,82,36}设定哈希函数H(key)=keyMOD11

190123145568(1)采用线性探测再散列处理冲突1182361121362510123456789101901231468(2)采用二次探测再散列处理冲突55118236112121412ASL=22/9ASL=15/9设：H2(key)=(3key)MOD10+1

di=i×H2(key)190123145568118236211121214ASL=15/9012345678910(3)采用双散列函数探测线性探测处理冲突时：ASL=双散列探测处理冲突时：ASL=22/915/9二次探测处理冲突时：ASL=15/9本例不同的处理冲突方法的ASL为：将所有哈希地址相同的记录都链接在同一链表中。

012345614

0136198223116855ASL=(6×1+2×2+3)/9=13/9设哈希函数为：H(key)=keyMOD7显然不会发生二次聚集2.链地址法：

哈希表的查找过程和造表过程一致。

对于给定值K，计算哈希地址i=H(K)若r[i]=NULL则查找不成功若r[i].key=K则查找成功否则“求下一地址Hi”

，直至

r[Hi]=NULL(查找不成功)

或

r[Hi].key=K(查找成功)为止。采用开放定址处理冲突，则查找过程为：四、哈希表的查找数据类型描述为#defineHASHSIZE11

typedef

struct{intkey;

otherdat