資源描述：
《算法與數(shù)據(jù)結(jié)構(gòu)ppt課件.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。
1、第九章.查找（Chapter9.Searching)查找運算是計算機(jī)中最常用的操作之一。有人統(tǒng)計過，計算機(jī)大約有40%的運算是與查找相關(guān)的。數(shù)據(jù)元素（或記錄）的某個數(shù)據(jù)項，能用來標(biāo)識一個數(shù)據(jù)元素。若能唯一的標(biāo)識一個數(shù)據(jù)元素，則稱為主關(guān)鍵字（primarykey），反之則為次關(guān)鍵字（secondarykey）。關(guān)鍵字（key）查找表（searchtable）§9.1靜態(tài)表的查找查找（searching）根據(jù)某個給定的值，在查找表中找尋關(guān)鍵字等于給定值的數(shù)據(jù)元素（或記錄）。若表中存在這樣的數(shù)據(jù)元素，則稱查找是成功的，查找結(jié)果即為查找到的數(shù)據(jù)元素；反之則稱查找是不成功的，此時查找結(jié)果為空
2、。由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。表中的元素基本上是固定的，這類查找表稱為靜態(tài)查找表（staticsearchtable）；若在查找過程中將不存在的元素插入查找表中，則稱這類查找表為動態(tài)查找表（dynamicsearchtable）。實際查找時，通常將給定值放在第0個記錄處，然后從后向前查找，直到找到所查記錄為止，找不到則返回結(jié)果0。因為記錄0像哨兵一樣看守著查找表下界，所以不會越界。typedefstruct{keytypekey;......}elemtype;一、無序表的查找：查找表中的各元素（或記錄）的關(guān)鍵字的值是無序的。typedefstruct{elemtyp
3、e*elem;intlength;}sstable;intseqsearch(sstableR,keytypeK){R.elem[0].key:=K;for(i=R.length;R.elem[i].key!=K;i--);returni;}查找表的長度為n：查找性能分析：平均查找長度（averagesearchlength）為了確定記錄在查找表中的位置，需與給定值比較的關(guān)鍵字的個數(shù)的期望值稱為平均查找長度。對含有n個記錄的查找表，查找成功時的平均查找長度為：ASL=∑PiCi，其中Pi為查找第i個記錄的概率，且∑Pi=1。ni=1i=1n在等概率情況下，順序查找無序表的平均查找長
4、度為：ASL成功=（n+1)/2和ASL不成功=n+1。二、有序表的查找：查找表中的各元素（或記錄）的關(guān)鍵字的值是有序的。這類有序表的查找仍可以用順序查找，但在找不到時不需比較到表尾，只需比較到比給定值大的記錄就可終止。在等概率情況下，順序查找有序表的平均查找長度為：ASL成功=（n+1)/2和ASL不成功=（n+2)/2。有序表的查找比較好的方法是折半查找（binarysearch）：將給定值與中間的記錄進(jìn)行比較，若找到則查找成功；否則若給定值比中間記錄小，則對前一半子表進(jìn)行折半查找，反之則對后一半子表進(jìn)行折半查找。若在查找過程中，遇到查找子表的上界小于下界，則表示查找失敗。in
5、tseqsearch(sstableR,keytypeK){R.elem[0].key:=K;for(i=R.length;R.elem[i].key>K;i--);if(R.elem[i].key=K)returni;elsereturn0;}intbinsearch(sstableR,keytypeK){low=1;high=R.length;while(low<=high){mid=(low+high)/2;if(R.elem[mid]==K)returnmid;elseif(R.elem[mid]>K)high=mid-1;elselow=mid+1;}return0;}i
6、ntbinsearch(sstableR,intlow,inthigh,keytypeK){if(low>high)return0;mid=(low+high)/2;if(R.elem[mid]==K)returnmid;if(R.elem[mid]>K)returnbinsearch(R,low,mid-1,K);returnbinsearch(R,mid+1,high,K);}查找性能分析：折半查找每次只查表的一半，其所有記錄的查找路徑構(gòu)成一棵二叉樹，稱為折半查找樹（或判定樹），每次查找只走了該樹的一條分支，故平均查找長度不超過log2n+1。有一組記錄的關(guān)鍵字為{1，2，3，
7、4，5，6，7，8}，求其在等概率情況下查找成功的平均查找長度：例：42516378其查找樹如左圖所示：ASL成功==21/8。1*1+2*2+3*4+4*18有序表的查找也可用其它的查找方法，如費波拉契查找（Fibonaccisearch）。設(shè)查找表記錄數(shù)為某個費波拉契數(shù)減一，即n=Fu-1，則可將給定值與第Fu-1個記錄比較，若比其小，則在1~Fu-1-1記錄間查找，否則在Fu-1+1~Fu-1記錄間查找。如下圖所示：4251637若有序表的關(guān)鍵字是均勻分布的，則
