嚴蔚敏數(shù)據(jù)結構課件09查找.ppt

《嚴蔚敏數(shù)據(jù)結構課件09查找.ppt》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。

1、靜態(tài)查找表二叉排序樹平衡二叉樹（AVL樹）小結B樹哈希表第9章查找查找(Search)的概念靜態(tài)查找表查找：就是在數(shù)據(jù)集合中尋找滿足某種條件的數(shù)據(jù)對象。查找表：是由同一類型的數(shù)據(jù)元素(或記錄)組成的數(shù)據(jù)集合。查找的結果通常有兩種可能：查找成功，即找到滿足條件的數(shù)據(jù)對象。查找不成功，或查找失敗。作為結果，報告一些信息，如失敗標志、失敗位置等。關鍵字：數(shù)據(jù)元素中某個數(shù)據(jù)項的值，用以標識一個數(shù)據(jù)元素。主關鍵字：可唯一地標識一個數(shù)據(jù)元素的關鍵字。次關鍵字：用以識別若干記錄的關鍵字。使用基于主關鍵字的查找，查找結果應是唯一的。靜態(tài)查找表（p214）動態(tài)查找表9.1靜態(tài)查找表基

2、本操作：Create(&ST,n);//構造含有n個元素的靜態(tài)查找表STDestroy(&ST);//銷毀表Search(ST,key);//查找關鍵字為key的數(shù)據(jù)元素Traverse(ST,visit());//遍歷查找表關鍵字比較約定為如下宏定義#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))衡量一個查找算法的時間效率的標準是：在查找過程中關鍵字的平均比較次數(shù)或平均讀寫磁盤次數(shù)(只適合于外部查找)，這個標準也稱為平均查找長度ASL(AverageSearchLengt

3、h)，通常它是查找結構中對象總數(shù)n或文件結構中物理塊總數(shù)n的函數(shù)。另外衡量一個查找算法還要考慮算法所需要的存儲量和算法的復雜性等問題。在靜態(tài)查找表中，數(shù)據(jù)對象存放于數(shù)組中，利用數(shù)組元素的下標作為數(shù)據(jù)對象的存放地址。查找算法根據(jù)給定值x，在數(shù)組中進行查找。直到找到x在數(shù)組中的存放位置或可確定在數(shù)組中找不到x為止。9.1.1順序表的查找(SequentialSearch)所謂順序查找，又稱線性查找，主要用于在線性結構中進行查找。存儲結構：typedefstruct{ElemType*elem;intlength;}SSTable;查找過程：從表中最后一個元素開始，順序用

4、各元素的關鍵字與給定值x進行比較，若找到與其值相等的元素，則查找成功，給出該元素在表中的位置；否則，若直到第一個記錄仍未找到關鍵字與x相等的對象，則查找失敗。有序順序表的順序查找(10,20,30,40,50,60)105060======203040<<<<<<>>>>>>最后一次查找失敗需比較6次算法9.1（p217）Search_Seq(SSTableST,KeyTypekey){//順序查找的算法，0號元素為監(jiān)視哨inti；ST.elem[0].key=key;for(i=ST.length;!EQ(ST.elem[i].key,key);--i);retu

5、rni;}順序查找的平均查找長度設查找第i個元素的概率為pi，查找到第i個元素所需比較次數(shù)為ci，則查找成功的平均查找長度:在順序查找情形，ci=n-i+1,i=1,?,n，因此在等概率情形，pi=1/n,i=0,1,?,n-1。9.1.2有序表的查找折半查找：先求位于查找區(qū)間正中的對象的下標mid，用其關鍵字與給定值x比較:Element[mid].getKey()=x，查找成功；Element[mid].getKey()>x，把查找區(qū)間縮小到表的前半部分，再繼續(xù)進行對分查找；Element[mid].getKey()

6、對分查找。每比較一次，查找區(qū)間縮小一半。如果查找區(qū)間已縮小到一個對象，仍未找到想要查找的對象，則查找失敗。9.1.2有序表的查找折半查找：（1）mid=(low+high)/2」（2）比較ST.elem[mid].key==key?如果ST.elem[mid].key==key，則查找成功，返回mid值如果ST.elem[mid].key>key，則置high=mid-1如果ST.elem[mid].keyhigh時，表明查找不成功，查找結束。查找成功的例

7、子查找失敗的例子算法9.2(p220)intSearch_Bin(SSTableST,KeyTypekey)//折半查找{intlow,high,mid;low=1;high=ST.length;while(low