数据结构与算法_第九章

第9章查找查找的基本概念静态查找表动态查找表哈希表主要知识点查找的基本概念查找表：同一类型数据元素构成的集合。(集合则无相同元素)查找:查询关键字是否在(数据元素集合）表中的过程。也称作检索。主关键字:能够惟一区分各个不同数据元素的关键字次关键字:通常不能惟一区分各个不同数据元素的关键字查找成功:在数据元素集合中找到了要查找的数据元素查找不成功:在数据元素集合中没有找到要查找的数据元素静态查找:只查找，不改变数据元素集合内的数据元素动态查找:既查找，又改变（增减）集合内的数据元素静态查找表:静态查找时构造的查找表动态查找表:动态查找时构造的查找表平均查找长度:查找过程所需进行的关键字比较次数的平均值,是衡量查找算法效率的最主要标准,其数学定义为：其中，Pi是要查找数据元素出现的概率，Ci是查找相应数据元素的比较次数。niiiCPASL19.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大，则缩小至后半部内查找。查找215131921375664758088921234567891011MidHighLow5131921375664758088921234567891011MidHighLow5131921375664758088921234567891011MidHighLow(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/nASL=iPiCi=(jj*2j-1)/n=(n+1)/n*Log2(n+1)-1(推导过程略去)其它有序表查找算法:取区间某分割点与x比较,类似折半。9.1.4索引顺序表的查找当顺序表中的数据元素个数非常大时，采用在顺序表上建立索引表的办法提高查找速度。把要在其上建立索引表的顺序表称作主表。主表中存放着数据元素的全部信息，索引表中只存放主表中要查找数据元素的主关键字和索引信息。主表按块有序8146910223418193140385466467178688085140034516610285153keylink下标索引表012345678910111213141516171819key其它域位置主表索引表结构图索引表中的数据元素由两个域构成，key域为被索引的若干个数据元素中关键字的最大值，link域为被索引的若干个数据元素中第一个数据元素的位置编号。算法示例索引表1234567891011121314151617182212138920334244382448605874578653查382248861713分块查找示例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-l