数据结构与算法-第九章

第9章查找查找的基本概念静态查找表动态查找表哈希表主要知识点查找的基本概念查找表：

同一类型数据元素构成的集合。(集合则无相同元素)

查找:查询关键字是否在(数据元素集合）表中的过程。也称作检索。主关键字:能够惟一区分各个不同数据元素的关键字次关键字:通常不能惟一区分各个不同数据元素的关键字查找成功:在数据元素集合中找到了要查找的数据元素查找不成功:在数据元素集合中没有找到要查找的数据元素静态查找:只查找，不改变数据元素集合内的数据元素动态查找:既查找，又改变（增减）集合内的数据元素静态查找表:静态查找时构造的查找表动态查找表:动态查找时构造的查找表平均查找长度:查找过程所需进行的关键字比较次数的平均值,是衡量查找算法效率的最主要标准,其数学定义为：其中，Pi是要查找数据元素出现的概率，Ci是查找相应数据元素的比较次数。9.1静态查找表

静态查找表主要有三种结构：

顺序表有序顺序表索引顺序表静态查找表的顺序存储结构：typedefstruct{ElemType*elem;//数据元素存储空间基址，0号单元留空

intlength/*表长度*/}SSTable;typedefintKeyType;typedefchar*InfoType;定义要查找数据元素的结构体为：typedefstruct{KeyTypekey;/*关键字域*/InfoTypeotherinfo;/*其他域*/}ElemType;9.1.1顺序表顺序查找的基本思想是：从顺序表的一端开始，用给定数据元素的关键字逐个和顺序表中各数据元素的关键字比较，若在顺序表中查找到要查找的数据元素，则查找成功，函数返回该数据元素在顺序表中的位置；否则查找失败，函数返回0。查找函数设计如下：intSearch_Seq(SSTableST,KeyTypekey){//算法9.1//在顺序表ST中顺序查找其关键字等于key的数据元素。//若找到，则函数值为该元素在表中的位置，否则为0。

inti=0;ST.elem[0].key=key;//"哨兵"for(i=ST.length;ST.elem[i].key!=key;--i);//从后往前找returni;//找不到时，i为0}//Search_Seq利用监视哨的算法。思考：监视哨作用？算法分析(顺序表)查找成功时的平均查找长度ASL成功为：

ASL=PiCi=1/n*(n-i+1)=(n+1)/2(约表长的一半)查找失败时的平均查找长度ASL失败显然为n+19.1.2有序表的查找有序顺序表上的查找算法主要有顺序查找和折半查找两种方法。一、有序表的顺序查找有序顺序表上的顺序查找算法和顺序表上的查找算法方法类同二、二分查找（又称折半查找）算法的基本思想：先给数据排序（一般按升序排好），形成有序表，然后再将key与正中元素相比，若key小，则缩小至前半部内查找；再取其中值比较，每次缩小1/2的范围，直到查找成功或失败为止。反之，如果key大，则缩小至后半部内查找。查找21

5131921375664758088921234567891011MidHighLow

5131921375664758088921234567891011MidHighLow

5131921375664758088921234567891011MidHighLow(a)查找成功示例算法示例

如图(a)，(b)所示。查找71

-5131723384656657881921234567891011MidHighLow

-5131723384656657881921234567891011MidHighLow

-5131723384656657881921234567891011MidHighLow

-5131723384656657881921234567891011MidHighLow(b)查找不成功示例二分查找算法如下：intSearch_Bin(SSTableST,KeyTypekey){//算法9.2//在有序表ST中折半查找其关键字等于key的数据元素。//若找到，则函数值为该元素在表中的位置，否则为0。intlow,high,mid;low=1;high=ST.length;//置区间初值while(low<=high){mid=(low+high)/2;if(EQ(key,ST.elem[mid].key))returnmid;//找到待查元素elseif(LT(key,ST.elem[mid].key))high=mid-1;//继续在前半区间进行查找elselow=mid+1;//继续在后半区间进行查找}return0;//顺序表中不存在待查元素}//Search_Bin

算法分析查找时每经过一次比较，查找范围就缩小一半，该过程可用一棵二叉树表示：

◆

根结点就是第一次进行比较的中间位置的记录；◆排在中间位置前面的作为左子树的结点；◆排在中间位置后面的作为右子树的结点；对各子树来说都是相同的。这样所得到的二叉树称为判定树(DecisionTree)。②将二叉判定树的第㏒2n+1层上的结点补齐就成为一棵满二叉树，深度不变。折半查找的性能分析6391410275811可用判定树描述折半查找(其它查找也可)过程:

判定树的各层结点由查找过程中从大到小可

能出现的各区间中点(分割点)构成。包括

外部结点(方,对应不成功查找)和内部结点。

该树接近满二叉树(叶子未在左边排紧),

树高与结点数的关系相同(倒2层缺左孩,因整除2造成)

求平均查找长度,为方便,假设表长n=2h-1对应满二叉树。按等概率Pi=1/n

ASL=iPiCi=(j

j*2j-1)/n=(n+1)/n*Log2(n+1)-1(推导过程略去)其它有序表查找算法:取区间某分割点与x比较,类似折半。9.1.4索引顺序表的查找

当顺序表中的数据元素个数非常大时，采用在顺序表上建立索引表的办法提高查找速度。把要在其上建立索引表的顺序表称作主表。主表中存放着数据元素的全部信息，索引表中只存放主表中要查找数据元素的主关键字和索引信息。主表按块有序8146910223418193140385466467178688085140034516610285153keylink下标索引表012345678910111213141516171819key其它域位置主表索引表结构图

索引表中的数据元素由两个域构成，key域为被索引的若干个数据元素中关键字的最大值，link域为被索引的若干个数据元素中第一个数据元素的位置编号。算法示例索引表1234567891011121314151617182212138920334244382448605874578653查38224886

1713分块查找示例9.2动态查找表动态查找表主要有二叉树结构和树结构两种类型。二叉树结构有二叉排序树、平衡二叉树等。树结构有B-树、B+树等。1.二叉排序树一、基本概念----或是一棵空树；或者是具有如下性质的非空二叉树：

（1）左子树的所有结点均小于根的值；（2）右子树的所有结点均大于根的值；（3）它的左右子树也分别为二叉排序树。二叉排序树中结点的结构体定义如下：typedefstructBiTNode{ElemTypedata;structnode*lchild;structnode*rchild;}BiTNode,*BiTree3811241094039454035190146476760445600800下图所示就是一棵二叉排序树二、二叉排序树的查找算法StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p){/*在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，若查找成功，则指针p指向该数据元素结点，并返回TRUE，否则指针p指向查找路径上访问的最后一个结点并返回FALSE，指针f指向T的双亲，其初始调用值为NULL*/if(!T){p=f;returnFALSE;}//查找不成功elseif(EQ(key,T->data.key)){p=T;returnTRUE;}//查找成功elseif(LT(key,T->data.key))returnSearchBST(T->lchild,key,T,p);//在左子树中继续查找elsereturnSearchBST(T->rchild,key,T,p);//在右子树中继续查找}//SearchBST与判定树相类似，但有本质区别，判定树顺序存储，二叉排序树链式存储。插入操作要求首先查找数据元素是否在二叉排序树中存在，若存在则返回；若不存在，插入查找失败时结点的左指针或右指针上。插入算法设计如后:三、二叉排序树的插入算法StatusInsertBST(BiTree&T,ElemTypee){//算法9.6//当二叉排序树T中不存在关键字等于e.key的数据元素时，//插入e并返回TRUE，否则返回FALSEBiTreep,s;if(!SearchBST(T,e.key,NULL,p)){//查找不成功s=(BiTree)malloc(sizeof(BiTNode));s->data=e;s->lchild=s->rchild=NULL;if(!p)T=s;//插入s为新的根结点elseif(LT(e.key,p->data.key))p->lchild=s;//插入s为左孩子elsep->rchild=s;//插入s为右孩子returnTRUE;}elsereturnFALSE;//树中已有关键字相同的结点，不再插入}//InsertBST下图是调用上述插入函数依次插入数据元素4,5,7,2,1,9,8,11,3的过程。41152791384115279184527918452791452714527457454(d)(c)(b)(a)(g)(f)(e)(i)(h)删除二叉排序树的结点删除方案:

要求删除二叉排序树中结点

P后,不破坏二叉排序树特性.

F为其双亲.若P只有左(右)子

树,将子树接到F的左指针即

可,若同时有左右子树,有两

种方案:FPCfpPrQS...Sl.FfpPrCQS..Sl方案1:将P的右子树接到P的左子树方案1方案2

中序序列最后结点的右指针处,将P的左子树接到F的左指针

处,结果树可能增高.FSCfpPrQ...Sl方案2:删除P的左子树中序序列最后结点S,来顶替P结点,原S的左

子树接到原S的双亲的右指针处,结果树可能降低。删除二叉排序树结点的算法StatusDeleteBST(BiTree&T,KeyTypekey){//算法9.7//若二叉排序树T中存在关键字等于key的数据元素时，//则删除该数据元素结点p，并返回TRUE；否则返回FALSEif(!T)returnFALSE;//不存在关键字等于key的数据元素else{if(EQ(key,T->data.key))//找到关键字等于key的数据元素returnDelete(T);elseif(LT(key,T->data.key))returnDeleteBST(T->lchild,key);elsereturnDeleteBST(T->rchild,key);}}//DeleteBST二叉排序树删除算法(方案2)StatusDelete(BiTree&p){//算法9.8//从二叉排序树中删除结点p，并重接它的左或右子树BiTreeq,s;if(!p->rchild){//右子树空则只需重接它的左子树q=p;p=p->lchild;free(q);}elseif(!p->lchild){//只需重接它的右子树q=p;p=p->rchild;free(q);}else{//左右子树均不空q=p;s=p->lchild;while(s->rchild)//转左，然后向右到尽头{q=s;s=s->rchild;}p->data=s->data;//s指向被删结点的“后继”if(q!=p)q->rchild=s->lchild;//重接*q的右子树elseq->lchild=s->lchild;//重接*q的左子树free(s);}returnTRUE;}//Delete2.平衡二叉树的定义平衡二叉树或者是空树，或者是满足下列性质的二叉树。⑴：左子树和右子树深度之差的绝对值不大于1；⑵：左子树和右子树也都是平衡二叉树。

平衡因子(BalanceFactor)：二叉树上结点的左子树的深度减去其右子树深度称为该结点的平衡因子。因此，平衡二叉树上每个结点的平衡因子只可能是-1、0和1，否则，只要有一个结点的平衡因子的绝对值大于1，该二叉树就不是平衡二叉树。如果一棵二叉树既是二叉排序树又是平衡二叉树，称为平衡二叉排序树(BalancedBinarySortTree)。平衡化旋转

一般的二叉排序树是不平衡的，若能通过某种方法使其既保持有序性，又具有平衡性，就找到了构造平衡二叉排序树的方法，该方法称为平衡化旋转。在对AVL树进行插入或删除一个结点后，通常会影响到从根结点到插入(或删除)结点的路径上的某些结点，这些结点的子树可能发生变化。以插入结点为例，影响有以下几种可能性◆

以某些结点为根的子树的深度发生了变化；◆

某些结点的平衡因子发生了变化；◆

某些结点失去平衡。一、LL型平衡化旋转⑴失衡原因在结点a的左孩子的左子树上进行插入，插入使结点a失去平衡。a插入前的平衡因子是1，插入后的平衡因子是2。设b是a的左孩子，b在插入前的平衡因子只能是0，插入后的平衡因子是1(否则b就失衡)。⑵平衡化旋转方法通过顺时针旋转操作实现，如图所示。用b取代a的位置，a成为b的右子树的根结点，b原来的右子树作为a的左子树。⑶插入后各结点的平衡因子分析①旋转前的平衡因子设插入后b的左子树的深度为HbL，则其右子树的深度为HbL-1；a的左子树的深度为HbL+1。abbRaRbLxabbRaRbLx图9-7LL型平衡化旋转示意图a的平衡因子为2，则a的右子树的深度为：HaR=HbL+1-2=HbL-1。②旋转后的平衡因子

a的右子树没有变，而左子树是b的右子树，则平衡因子是：HaL-HaR=(HbL-1)-(HbL-1)=0

即a是平衡的，以a为根的子树的深度是HbL。

b的左子树没有变化，右子树是以a为根的子树，则平衡因子是：HbL-HbL=0

即b也是平衡的，以b为根的子树的深度是HbL+1，与插入前a的子树的深度相同，则该子树的上层各结点的平衡因子没有变化，即整棵树旋转后是平衡的。二、LR型平衡化旋转⑴失衡原因

在结点a的左孩子的右子树上进行插入，插入使结点a失去平衡。a插入前的平衡因子是1，插入后a的平衡因子是2。设b是a的左孩子，c为b的右孩子，b在插入前的平衡因子只能是0，插入后的平衡因子是-1；c在插入前的平衡因子只能是0，否则，c就是失衡结点。（2）平衡化旋转方法

先以b进行一次逆时针旋转(将以b为根的子树旋转为以c为根)，再以a进行一次顺时针旋转，如图9-8所示。将整棵子树旋转为以c为根，b是c的左子树，a是c的右子树；c的右子树移到a的左子树位置，c的左子树移到b的右子树位置。图9-8LR型平衡化旋转示意图abbLaRcLxcRxcacbLaRcLxcRxb(3)

插入后结点c的平衡因子的变化分析①插入后c的平衡因子是1：即在c的左子树上插入。设c的左子树的深度为HcL，则右子树的深度为HcL-1；b插入后的平衡因子是-1，则b的左子树的深度为HcL，以b为根的子树的深度是HcL+2。因插入后a的平衡因子是2，则a的右子树的深度是HcL。②插入后c的平衡因子是0：c本身是插入结点。设c的左子树的深度为HcL，则右子树的深度也是HcL；因b插入后的平衡因子是-1，则b的左子树的深度为HcL，以b为根的子树的深度是HcL+2；插入后a的平衡因子是2，则a的右子树的深度是HcL。③插入后c的平衡因子是-1：即在c的右子树上插入。设c的左子树的深度为HcL，则右子树的深度为HcL+1，以c为根的子树的深度是HcL+2；因b插入后的平衡因子是-1，则b的左子树的深度为HcL+1，以b为根的子树的深度是HcL+3；则a的右子树的深度是HcL+1。⑷旋转后各结点(a,b,c)平衡因子分析

①

旋转前(插入后)c的平衡因子是1：

a的左子树深度为HcL-1，其右子树没有变化，深度是HcL，则a的平衡因子是-1；b的左子树没有变化，深度为HcL，右子树是c旋转前的左子树，深度为HcL，则b的平衡因子是0；c的左、右子树分别是以b和a为根的子树，则c的平衡因子是0。②

旋转前

(插入后)c的平衡因子是0：旋转后a，b，c的平衡因子都是0。

③

旋转前

(插入后)c的平衡因子是-1：旋转后a，b，c的平衡因子分别是0，-1，0。综上所述，即整棵树旋转后是平衡的。三、RL型平衡化旋转⑴失衡原因

在结点a的右孩子的左子树上进行插入，插入使结点a失去平衡，与LR型正好对称。对于结点a，插入前的平衡因子是-1，插入后a的平衡因子是-2。设b是a的右孩子，c为b的左孩子，b在插入前的平衡因子只能是0，插入后的平衡因子是1；同样，c在插入前的平衡因子只能是0，否则，c就是失衡结点。(2)平衡化旋转方法

先以b进行一次顺时针旋转，再以a进行一次逆时针旋转，如图9-9所示。即将整棵子树(以a为根)旋转为以c为根，a是c的左子树，b是c的右子树；c的右子树移到b的左子树位置，c的左子树移到a的右子树位置。图9-9RL型平衡化旋转示意图abbRaLcLxcRxcbcbRaLcLxcRxa(3)

插入后结点c的平衡因子的变化分析

①插入后c的平衡因子是1：在c的左子树上插入。设c的左子树的深度为HcL，则右子树的深度为HcL-1。因b插入后的平衡因子是1，则其右子树的深度为HcL，以b为根的子树的深度是HcL+2；因插入后a的平衡因子是-2，则a的左子树的深度是HcL。②插入后c的平衡因子是0：c本身是插入结点。设c的左子树的深度为HcL，则右子树的深度也是HcL；因b插入后的平衡因子是1，则b的右子树的深度为HcL，以b为根的子树的深度是HcL+2；因插入后a的平衡因子是-2，则a的左子树的深度是HcL。③插入后c的平衡因子是-1：在c的右子树上插入。设c的左子树的深度为HcL，则右子树的深度为HcL+1，以c为根的子树的深度是HcL+2；因b插入后的平衡因子是1，则b的右子树的深度为HcL+1，以b为根的子树的深度是HcL+3；则a的右子树的深度是HcL+1。⑷旋转后各结点(a,b,c)的平衡因子分析①

旋转前

(插入后)c的平衡因子是1：

a的左子树没有变化，深度是HcL，右子树是c旋转前的左子树，深度为HcL，则a的平衡因子是0；b的右子树没有变化，深度为HcL，左子树是c旋转前的右子树，深度为HcL-1

，则b的平衡因子是-1；c的左、右子树分别是以a和b为根的子树，则c的平衡因子是0。

②

旋转前

(插入后)c的平衡因子是0：旋转后a，b，c的平衡因子都是0。

③

旋转前

(插入后)c的平衡因子是-1：旋转后a，b，c的平衡因子分别是1，0，0。综上所述，即整棵树旋转后是平衡的。四、RR型平衡化旋转⑴失衡原因在结点a的右孩子的右子树上进行插入，插入使结点a失去平衡。要进行一次逆时针旋转，和LL型平衡化旋转正好对称。⑵平衡化旋转方法

设b是a的右孩子，通过逆时针旋转实现，如图9-10所示。用b取代a的位置，a作为b的左子树的根结点，b原来的左子树作为a的右子树。图9-10RR型平衡化旋转示意图babLaLbRxabbLaLbRx哈希表概念：哈希表设计思想不基于比较(不依赖n),关键字地址的映射。

Hash函数--杂凑。冲突,同义词,二次聚集,散列,哈希(散列)地址。哈希函数构造：

1.直接定址2.数字分析3.平方取中4.折叠5.伪随机数法

6.除留余数(模取质数或不包含质因数小于20的合数)

考虑因素：1.计算哈希函数耗时2.关键字长度3.哈希表尺寸

4.关键字分布情况5.记录查找频率冲突处理：

1.开放定址法Hi=(H(key)+di)MODm

线性探测(易聚集)/二次探测/伪随机数探测再散列

2.再哈希法

3.链地址法

4建公共溢出区哈希表查找与分析查找类似于构造过程,要能区分出空位(NULLKEY)。存储结构:

inthashsize[]={997,…};//哈希表容量递增表,合适的素数序列

typedefstruct{

elemtype*elem;//元素存储基址

intcount,sizeindex;//当前元素数,hashsize[sizeindex]当前容量

}hashtable;//哈希表结构

#defineSUCCESS1

#defineUNSUCCESS0

#defineDUPLICATE-1

statussearchhash(hashtableh,keytypek,int*p,int*c){

p0=*p=hash(k);q=-1;//*c为冲突计数，实参初值取0

while(h.elem[*p].key!=NULLKEY&&h.elem[*p].key!=k){

if(h.elem[*p].key==DELKEY&&q==-1)q=*p;/*记第一个删标记位置*/

collision(*p,++*c);/*求探查地址*p*/if(*p==p0){*p=-1;returnUNSUCCESS;}/*防循环探测,用改表长来处理*/

}if(k==h.elem[*p].key)returnSUCCESS;

else{if(q!=-1)*p=q;returnUNSUCCESS;}

}//查找算法增加了对删除标记DELKEY的处理(绿色部