數(shù)據結構課件25講第九章查找

第九章查找本章內容與要點本章內容討論基于比較的各種查找的實現(xiàn)方法：順序表查找、有序表查找、樹表查找、哈希表查找以及相應的衡量查找效率的平均查找長度的分析。本章要點熟練掌握順序表和有序表的查找方法，并能靈活應用；熟練掌握二叉排序樹的構造和查找方法；掌握哈希表的構造方法。各種查找方法的查找效率分析；基本概念查找:就是在一組數(shù)據集合中找到滿足某種條件的數(shù)據。查找表由同一類型的數(shù)據元素構成的集合；靜態(tài)查找表對查找表的查找僅是以查詢?yōu)槟康?，不改動查找表中的?shù)據。動態(tài)查找表在查找的過程中同時插入不存在的記錄，或刪除某個已存在的記錄。關鍵字數(shù)據元素（或記錄）的某個數(shù)據項，能用來標識一個數(shù)據元素。若能唯一的標識一個數(shù)據元素，則稱為主關鍵字（primarykey），反之則為次關鍵字（secondarykey）。基本概念（續(xù)）查找成功查找表中存在滿足查找條件的記錄。查找不成功查找表中不存在滿足查找條件的記錄。內查找整個查找過程都在內存中進行。外查找在查找過程中需要訪問外存。平均查找長度ASL——查找方法時效的度量為確定記錄在查找表中的位置，需將關鍵字和給定值比較次數(shù)的期望值。查找成功時的ASL計算方法：n：記錄的個數(shù)pi：查找第i個記錄的概率，(不特別聲明時認為等概率pi=1/n)ci：找到第i個記錄所需的比較次數(shù)9.1靜態(tài)查找表順序表的查找通常查找表中的各元素（或記錄）的關鍵字的值是無序的。實際查找時，通常將給定值放在第0個記錄處，然后從后向前查找，直到找到所查記錄為止，找不到則返回結果0。因為記錄0像哨兵一樣看守著查找表下界，所以不會越界。typedefintKeytype; /*定義關鍵字類型為整型*/typedefstruct{Keytypekey; /*關鍵字*/ /*此處為其它數(shù)據項*/}Rcdtype; /*記錄類型*/順序表算法及性能分析intsequelsearch(Rcdtypes[],Keytypekey,intn){/*在s[1]~s[n]中順序查找關鍵字為key的記錄*/ for(i=n;i>0&&s[i].key!=key;i--); returni;}性能分析查找成功時ASLs(n)==(1+2+...+n)/n=(n+1)/2查找失敗時ASLf=n+1s[0]=key;for(i=n;s[i].key!=key;i--); returni;靜態(tài)查找表有序表的查找有序表查找表中的各元素（或記錄）的關鍵字的值是有序的。仍可用順序查找，但在找不到時不需比較到表尾，只需比較到比給定值大的記錄就可終止。在等概率情況下，順序查找有序表的平均查找長度為：ASL成功

=（n+1)/2ASL不成功

=（n+2)/2。有序表的查找比較好的方法是折半查找。二分法查找－－－折半查找將給定值與中間的記錄進行比較；若找到則查找成功；否則若給定值比中間記錄小，則對前一半子表進行折半查找，反之則對后一半子表進行折半查找。若在查找過程中，遇到查找子表的上界小于下界，則表示查找失敗。

設順序表中有11個記錄，它們的關鍵字依次為{7,15,19,21,38,40,66,78,83,102,110}，用二分查找法在該順序表中查找關鍵字為21和63的記錄。7 15 19213840667883102110lowhighmid7 15 19213840667883102110lowmidhigh查找關鍵字21查找關鍵字63折半查找算法的非遞歸算法intbinarysearch(Rcdtypes[],Keytypekey,intn){low=1;high=n;while(low<=high) { mid=(low+high)/2; if(key==s[mid].key)returnmid; elseif(key<s[mid].key)high=mid-1; elselow=mid+1; } return0;}折半查找算法的遞歸算法intbinarysearch2(Rcdtypes[],Keytypekey,intlow,inthigh){ if(low>high)return0; else { mid=(low+high)/2; if(s[mid].key==key)returnmid; elseif(s[mid].key>key) returnbinarysearch2(s,key,low,mid-1); else returnbinarysearch2(s,key,mid+1,high); }}折半查找的性能分析折半查找每次只查表的一半，其所有記錄的查找路徑構成一棵二叉樹，稱為折半查找樹（或判定樹），每次查找只走了該樹的一條分支，故平均查找長度不超過log2n+1折半查找舉例有一組記錄的關鍵字為{1，2，3，4，5，6，7，8}，求其在等概率情況下查找成功的平均查找長度：42516378其查找樹如左圖所示：ASL成功

==21/8。1*1+2*2+3*4+4*189.1.3分塊查找－－索引順序表的查找索引順序表帶索引表的順序表索引部分一定是有序的，這部分可用折半查找等方法；順序表本身不一定有序，要根據順序表是否有序而選用相應的查找方法。分塊查找（blockingsearch）將索引部分和表體部分分開查找的方法。索引表的平均查找長度為兩部分查找之和。35689311013最大關鍵字起始地址索引表231611356283125194157689375886913245678910111213141516順序表9.2樹表的動態(tài)查找二叉排序樹9.2.1二叉排序樹空或有一個根；根的左子樹若非空，則左子樹上的所有結點的關鍵字值均小于根結點的值；根的右子樹若非空，則右子樹上的所有結點的關鍵字值均大于根結點的值；根結點的左、右子樹也分別為二叉排序樹；12225030011020099LNPEMCY105230216二叉排序樹查找算法思路：btreebssearch(btreebt,Keytypekey)/*在二叉排序樹查找關鍵字之值為key的結點，找到返回該結

點的地址，否則返回空。bt為二叉排序樹的根結點的地址。*/{if((!bt)||key==bt->key))return(bt);elseif(key<bt->key) return(bssearch(bt->lchild,key));elsereturn(bssearch(bt->rchild,key));}若根結點的關鍵字值等于查找的關鍵字,成功;否則，若小于根結點的關鍵字值，查其左子樹;若大于根結點的關鍵字值，查其右子樹;在左右子樹上的操作類似。122250300110200991052302161222503001102009910523021628030011099eg：將數(shù)的序列：122、99、250、110、300、280作為二叉排序樹的結點的關鍵字值，生成二叉排序樹。二叉排序樹的插入首先執(zhí)行查找算法，找出被插結點的父親結點。判斷被插結點是其父親結點的左、右孩子。將被插結點作為葉子結點插入。若二叉樹為空,則首先單獨生成根結點。注意：新插入的結點總是葉子結點。122250二叉排序樹的插入算法12225030011099f:bt的父親結點p:指向最后一個結點，TRUE找到；FALSE葉子的父親結點。如：插入280的過程。280voidinsert(btree*bt,Keytypex){ p=*bt; while(p) { if(x==p->key)return; f=p; p=(x<p->key)?p->lchild:p->rchild;} p=(btree)malloc(sizeof(bsnodetype)); p->key=x;p->lchild=p->rchild=NULL; if(*bt==NULL)*bt=p; else if(x<f->key)f->lchild=p; elsef->rchild=p;}}pbtf二叉排序樹的查找分析

平均情況分析（在成功查找兩種的情況下）e.g:下述兩種情況下的成功的平均查找長度ASL156070302050ASL=(1+2+2+3+3+3)/6=14/6156070302050ASL=(1+2+3+4+5+6)/6=21/6二叉排序樹的刪除葉子結點：直接刪除，更改它的父親結點的相應指針域為空。如：刪除數(shù)據域為15、70的結點。15607030205060302050刪除子樹的根結點：通常的做法：選取“替身”取代被刪結點。有資格充當該替身的是誰哪？左子樹中最大的結點或右子樹中最小的結點。要點：維持二叉排序樹的特性不變。在中序遍歷中緊靠著被刪結點的結點才有資格作為“替身”。二叉排序樹的刪除（續(xù)）12225030020099110105230216400450500子樹的根結點：若被刪結點的左孩子為空或者右孩子為空。如下圖所示，刪除結點的數(shù)據域為99的結點。被刪結點122250300200230216400450500110105刪除99二叉排序樹的刪除（續(xù)）12225030011099105200230216400450500被刪結點子樹的根結點：若被刪結點的左孩子為空或者右孩子為空。如下圖所示，刪除結點的數(shù)據域為200的結點。刪除20012225030023021640045050011099105二叉排序樹的刪除（續(xù)）

12225030099110105200230216400450500被刪結點子樹的根結點：若被刪結點的左孩子為空或者右孩子為空。如下圖所示，刪除結點的數(shù)據域為99、200的結點。結論:

將被刪結點的另一孩子作為它的父親結點的孩子，究竟是作為左孩子還是右孩子依被刪結點和其父親結點的關系而定。釋放被刪結點的空間。被刪結點

子樹的根結點：若被刪結點的左、右子樹皆不空，則：通常的做法：選取“替身”取代被刪結點。有資格充當該替身的是誰哪？左子樹中最大的結點(被刪結點的左子樹中的最右的結點，其右孩子指針域為空)或右子樹中最小的結點(被刪結點的右子樹中的最左的結點，其左孩子指針域為空)，參看下圖。要點：維持二叉排序樹的特性不變。在中序遍歷中緊靠著被刪結點的結點才有資格作為“替身”。12225030011020099105230216400450500被刪結點替身替身11025030010520099230216400450500做法：將替身的數(shù)據域復制到被刪結點的數(shù)據域。將結點的左孩子作為的父結點的右孩子。11011099注意：結點右孩子必為空結點的父結點為11011099

12225030011020099105230216400450500被刪結點替身替身20025030011099105230216400450500做法：將替身的數(shù)據域復制到被刪結點的數(shù)據域。將結點的右孩子作為的父結點的左孩子。注意：結點左孩子必為空結點的父結點為200200200200250子樹的根結點：若被刪結點的左、右子樹皆不空，則：通常的做法：選取“替身”取代被刪結點。有資格充當該替身的是誰哪？左子樹中最大的結點(被刪結點的左子樹中的最右的結點，其右孩子指針域為空)或右子樹中最小的結點(被刪結點的右子樹中的最左的結點，其左孩子指針域為空)，參看下圖。要點：維持二叉排序樹的特性不變。在中序遍歷中緊靠著被刪結點的結點才有資格作為“替身”。二叉排序樹的操作二叉排序樹的查找若當前結點指針為空或當前結點為所找結點則返回當前指針；若當前結點關鍵字值比給定值大則繼續(xù)查找當前結點的左子樹；否則就繼續(xù)查找當前結點的右子樹。二叉排序樹的插入先用給定值查找二叉排序樹，查找成功則返回所找結點指針；否則在找不到時的葉結點的左