數(shù)據(jù)結(jié)構(gòu)答案查找學(xué)習(xí)與指導(dǎo)

1、第9章 查找9.1 知識點分析1. 基本概念（1）查找表由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合稱為查找表。（2）靜態(tài)查找在查找過程中僅查找某個特定元素是否存在或它的屬性的，稱為靜態(tài)查找。 （3）動態(tài)查找在查找過程中對查找表進行插入元素或刪除元素操作的，稱為動態(tài)查找。 （4）關(guān)鍵字關(guān)鍵字是數(shù)據(jù)元素（或記錄）中某個數(shù)據(jù)項的值，用它可以標識數(shù)據(jù)元素（或記錄）。關(guān)鍵字分主關(guān)鍵字（唯一地標識一個記錄的關(guān)鍵字）和次關(guān)鍵字（標識若干個記錄的關(guān)鍵字）。（5）查找在查找表中確定是否存在一個數(shù)據(jù)元素的關(guān)鍵字等于給定值的操作，稱為查找（也稱為檢索）。（6）內(nèi)查找、外查找整個查找過程全部在內(nèi)存進行，則稱為內(nèi)查找；若

2、在查找過程中還需要訪問外存，則稱為外查找。（7）平均查找長度ASL查找成功時平均查找長度： 其中：Pi為找到表中第i個數(shù)據(jù)元素的概率，且有： Ci為查找表中第i個數(shù)據(jù)元素所用到的比較次數(shù)。不同的查找方法有不同的Ci。2順序查找順序查找又稱線性查找，是最基本的查找方法之一。順序查找既適用于順序表，也適用于鏈表。順序查找的基本思想：從表的一端開始，順序掃描線性表，依次按給定值kx與關(guān)鍵字（Key）進行比較，若相等，則查找成功，并給出數(shù)據(jù)元素在表中的位置；若整個表查找完畢，仍未找到與kx相同的關(guān)鍵字，則查找失敗，給出失敗信息。3二分查找 二分查找也叫折半查找，是一種效率較高的查找方法，但前提是表中元

3、素必須按關(guān)鍵字有序（按關(guān)鍵字遞增或遞減）排列。二分查找的基本思想：在有序表中，取中間元素作為比較對象，若給定值與中間元素的關(guān)鍵字相等，則查找成功；若給定值小于中間元素的關(guān)鍵字，則在中間元素的左半?yún)^(qū)繼續(xù)查找；若給定值大于中間元素的關(guān)鍵字，則在中間元素的右半?yún)^(qū)繼續(xù)查找。不斷重復(fù)上述查找過程，直到查找成功，或所查找的區(qū)域無數(shù)據(jù)元素，查找失敗。4分塊查找將具有n個元素的主表分成m個塊（也稱為子表），每塊內(nèi)的元素可以無序，但要求塊與塊之間必須有序，并建立索引表。索引表包括兩個字段：關(guān)鍵字字段 (存放對應(yīng)塊中的最大關(guān)鍵字值) 和指針字段 (存放指向?qū)?yīng)塊的首地址) 。查找方法如下：（1）在索引表中檢測關(guān)鍵

4、字字段，以確定待找值kx所處的分塊（可用二分查找）位置；（2）根據(jù)索引表指示的首地址，在該塊內(nèi)進行順序查找。5二叉排序樹（Binary Sort Tree） 二叉排序樹或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹：（1）若左子樹不空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；（2）若右子樹不空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值；（3）左右子樹也都是二叉排序樹。6平衡二叉樹(AVL樹) 所謂平衡二叉樹是指樹中任一結(jié)點的左、右子樹高度大致相等的二叉樹。平衡二叉樹（AVL樹）定義如下：平衡二叉樹或者是一棵空樹，或者是具有以下性質(zhì)的二叉排序樹：（1）它的左子樹和右子樹的高度之差（稱為平衡因子）的絕對

5、值不超過1；（2）它的左子樹和右子樹又都是平衡二叉樹。7哈希表選取某個函數(shù)，依該函數(shù)按關(guān)鍵字計算元素的存儲位置，并按此存放。查找時，由同一個函數(shù)對給定值kx計算地址，將kx與地址單元中元素關(guān)鍵字進行比，確定查找是否成功，這就是哈希方法。哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希函數(shù)，按這個思想構(gòu)造的表稱為哈希表。9.2 典型習(xí)題分析【例1】靜態(tài)查找和動態(tài)查找兩者的根本區(qū)別在于（）。 A邏輯結(jié)構(gòu)不同 B存儲實現(xiàn)不同 C施加的操作不同 D數(shù)據(jù)元素類型不同分析：根據(jù)施加不同運算，查找分為靜態(tài)查找和動態(tài)查找兩類，靜態(tài)查找僅包含檢索操作，而動態(tài)查找不僅包含檢索操作，還允許增加元素和刪除元素等操作。所以是施加的操作

6、不同，選擇C?！纠?】順序查找法與二分查找法對存儲結(jié)構(gòu)的要求是( )。A順序查找與二分查找均只適用于順序表B順序查找只適用于順序表C順序查找與二分查找既適用于順序表，也適用于鏈表D二分查找只適用于順序表分析：由第1題知道順序查找比較適用于順序表和鏈表。故A和B不對。二分查找表中元素必須按關(guān)鍵字有序（按關(guān)鍵字遞增或遞減）排列，在有序表中，取中間元素作為比較對象，若給定值與中間元素的關(guān)鍵字相等，則查找成功。從這里可以看出二分查找，要隨機取元素的關(guān)鍵字和查找對像比較，二分查找只適合順序存儲，C也不正確，選D?！纠?】順序表可以采用的三種查找方法是什么？這三種查找方法對查找表中元素的要求各是什么？在含

7、n個元素的順序表中，其等概率情況下查找成功的平均查找長度各是多少？分析：順序表可以采用的三種查找方法，分別是順序查找法、二分查找法和分塊查找法。順序查找法：表中的元素可以任意存放。二分查找法：表中元素必須按關(guān)鍵字有序存放。分塊查找法：要求表中元素是分塊有序，即前一塊的關(guān)鍵字值均小于后一塊的關(guān)鍵字值，同一塊內(nèi)元素可以按任意次序存放。具有n個元素的順序表在等概率情況下，三種查找方法的查找成功的平均查找長度分別為：順序查找法：ASL=（1+n）/2；二分查找法：ASL=log2（1+n）-1分塊查找法：設(shè)每塊含有s個元素，若用順序查找確定元素所在的塊，ASL=（n/s+s）/2+1；若用二分查找確定

8、元素所在的塊，ASL= log2（n/s+1）s/2。由此可見，二分查找法的平均查找長度最小，分塊查找法次之，順序查找法平均查找長度最大?！纠?】 畫出對長度為20的有序表進行二分查找的判定樹，并指出在等概率情況下，查找成功的平均查找長度以及查找失敗時所需的最多與關(guān)鍵字值的比較次數(shù)。分析：對長度為20的有序順序表進行二分查找的判定樹如圖9-1所示。11131916141720256371849101812D15圖9-1 判定樹等概率情況下的平均查找長度：ASL=(1*1+2*2+3*4+4*8+6*5)/20=74/20=3.7二分查找在查找失敗時所需與鍵值比較次數(shù)不超過判定樹的高度，因為判定

9、樹中度小于2的結(jié)點只可能在最下面的兩層上，所以n個結(jié)點的判定樹高度與n個結(jié)點的完全二叉樹的高度相同，即為。所以n個元素的有序表，查找失敗時與關(guān)鍵字值最多比較次。所以20個元素的有序表查找失敗時最多與關(guān)鍵字值的比較次數(shù)為：=5?！纠?】對含有n個互不相同元素的集合，同時找最大元素和最小元素至少需進行多少次比較? 分析：設(shè)變量max和min用于存放最大元素和最小元素的位置，第一次取兩個元素進行比較，大的放入max，小的放入min。從第2次開始，每次取一個元素先和max比較，如果大于max則以它替換max，并結(jié)束本次比較；若小于max則再與min相比較，在最好的情況下，比較下去都不用和mi

10、n相比較，所以這種情況下，至少要進行n-1次比較就能找到最大元素和最小元素。解：n-1次?！纠?】構(gòu)造有12個元素的二分查找的判定樹，并求解下列問題：（1）各元素的查找長度最大是多少？（2）查找長度為1、2、3、4的元素各有多少？具體是哪些元素？（3）查找第5個元素依次要比較哪些元素？分析：12個元素的判斷樹如圖9-2所示：圖9-2 判定樹（1）最大查找長度是樹的深度4。（2）查找長度為1的元素有1個，為第6個。查找長度為2的元素有2個，為第3個和第9個。查找長度為3的元素有4個，為第1、4、7、11個。查找長度為4的元素有5個，為第2、5、8、10、12個。（3）查找第五個元素依次比較6，3

11、，4，5?！纠?】對于給定結(jié)點的關(guān)鍵字集合K=42，57，82，32，70，35，12，48，96，18 ，（1）試構(gòu)造一棵二叉排序樹；（2）求等概率情況下的平均查找長度ASL；（3）如何得到關(guān)鍵字值的有序序列；（4）對于上述10個關(guān)鍵字值的不同排列次序，構(gòu)造不同的二叉排序樹中，最好和最壞情況下的高度各是多少；（5）查找70，要比較多少次才能找到；（6）畫出刪除結(jié)點42，以后的二叉排序樹。分析：（1）二叉排序樹構(gòu)造如圖9-3所示。 573532D12428270961848圖9-3 構(gòu)造二叉排序（2）ASL=(1*1+2*2+3*4+4*3)/10=29/10=2.9（3）對二叉排序樹進行中序

12、遍歷即可以得到原關(guān)鍵字值的有序序列。（4）對于關(guān)鍵字值的不同排列次序構(gòu)造的二叉排序樹中，最好情況二叉排序樹的高度為=4；最壞情況是原關(guān)鍵字值有序排列，則二叉排序樹的高度為10。（5）查找70，要比較4次才能找到,依次與42、57、82、70進行比較。（6）在二叉樹中刪除結(jié)點可用中序直接前驅(qū)法（如圖9-4）或中序直接后繼法（如圖9-4）。573532D1248827096185732D12358270961848 圖9-4 中序直接前驅(qū)法 圖9-5中序直接后繼法【例8】現(xiàn)有一組單詞（WEK,SUN, MON, TUE,WED,THU,FRI ,SAT），其相應(yīng)的散列函數(shù)值為(3，2，6，3，2，

13、5，6，0)，散列表長度為10（散列地址空間為0.9），要求：（1）構(gòu)造該散列表，并用線性探測法解決沖突；（2）若對每個元素查找一次，求總的比較次數(shù)。分析：（1）構(gòu)造散列函數(shù)Hkey % 10WEK關(guān)鍵字為3，H=3 %10=3，WEK放在3單元。SUN關(guān)鍵字為2，H=2 %10=2，SUN放在2單元。MON關(guān)鍵字為6，H=6 %10=2，MON放在6單元。TUE關(guān)鍵字為3，H=3%10=3，和WEK沖突，由線性探測法H（31）%104，TUE放在4單元。WED關(guān)鍵字為2，H=2%10=2，和SUN沖突，由線性探測法H（21）%103，還沖突，再求H（22）%104，還沖突。再求H=（23）%

14、105，WED放在5單元。THU關(guān)鍵字為5，H=5%10=5，沖突。H=(5+1)%10=6，還沖突。H=(5+2)%10=7，THU放在7單元。FRI關(guān)鍵字為6，H=6%10=6，沖突。H=(6+1)%10=7，還沖突。H=(6+2)%10=8，F(xiàn)RI放在7單元。SAT關(guān)鍵字為0，H=0 %10=0，WEK放在0單元。0123456789SATSUNWEKTUEWEDMONTHUFRI（2）WEK查找1次，SUN查找1次，MON查找1次，TUE查找2次，WED查找4次，THU查找2次，F(xiàn)RI查找3次，SAT查找1次?？偙容^次數(shù)=1+1+1+2+4+2+3+1=15(次)?！纠?】給定結(jié)點的關(guān)

15、鍵字序列為：12，18，30，70，20，8，63，15，19，設(shè)散列函數(shù)為H(k)=k % 11，試畫出采用拉鏈法解決沖突所構(gòu)造的哈希表，并求等概率情況下的ASL。解：拉鏈法解決沖突的結(jié)果如圖9-6所示。圖9-6 拉鏈法  在等概率情況下成功的平均查找長度為：   ASL (1*5+2*2+3*1+4*1)/9=16/9【例10】設(shè)計一個算法，求出指定結(jié)點在給定的二叉排序樹中所在的層數(shù)。分析：查找成功時的比較次數(shù)即為結(jié)點所在層數(shù)?？稍O(shè)置查找時計數(shù)，比較一次計數(shù)器加1。如查找成功時返回計數(shù)器累加數(shù)字； 不成功時，返回0。算法如下：#include &qu

16、ot;stdio.h"#include "type.h"int search_depth(BiTree T,ElemType key) / 求當前結(jié)點所在層數(shù) BiTNode *p;int dep=0;p=T;while(p) if (key=T->data) dep+; break; else if (key>T->data) dep+; p=p->rchild; else dep+; p=p->lchild; if (p) return dep;else return 0;【例11】試編寫利用二分查找法確定記錄的所在塊的分塊查找算

17、法。分析：采用分塊查找時，除了順序表之外，還要有索引表。其中索引表中含有各塊索引。在各塊中進行順序查找時，監(jiān)視哨可設(shè)在本塊的表尾，即將下一塊的第一個記錄暫時移走（若本塊內(nèi)記錄沒有填滿，則監(jiān)視哨的位置仍在本塊的尾部），待塊內(nèi)順序查找完成后再移回來。此時增加了賦值運算，但免去了判斷下標變量是否越界的比較。注意，最后一塊需進行特殊處理。在塊內(nèi)進行順序查找時，如果需要設(shè)置監(jiān)視哨，則必須先保存相鄰塊的相鄰元素，以免數(shù)據(jù)丟失。算法如下：#include "type.h"int Search_Idx(IdxSqlist L,int key) / 分塊查找，二分查找確定塊，塊內(nèi)順序查找 i

18、nt i,j,k,low,high,mid,found,temp; if (key>L.idxL.blknum.maxkey) return -1; / 超過最大元素，返回-1 low=1;high=L.blknum; found=0; while (low<=high&&!found) mid=(low+high)/2; if (key<=L.idxmid.maxkey && key>L.idxmid-1.maxkey) found=1; else if (key>L.idxmid.maxkey) low=mid+1; else

19、high=mid-1; i=L.idxmid.firstloc; / 塊的下界 j=i+blksize-1; temp=L.elemi-1; / 保存相鄰元素 L.elemi-1=key; / 設(shè)置監(jiān)視哨 for(k=j;L.elemk!=key;k-); / 順序查找 L.elemi-1=temp; / 恢復(fù)元素 if(k<i) return -1; / 未找到，返回-1 return k;【例12】選取散列函數(shù)H( k)=k % m，并采用鏈地址法解決沖突，構(gòu)造散列表。分析：鏈地址法是散列查找最經(jīng)常使用且很有效的解決沖突的一種方法，它是在散列表中每一個記錄位置增加一個指針把產(chǎn)生沖突的

20、關(guān)鍵字對應(yīng)的記錄，采用鏈表結(jié)構(gòu)鏈接在它的后面，是一種采用動態(tài)鏈式存儲結(jié)構(gòu)將發(fā)生沖突的記錄鏈接在同一鏈表中。元素類型定義和程序如下：#include<stdio.h>typedef struct nodel int key;struct nodel *next; nodel;nodel ht12;void createhash (nodel ht,int k,int m) / ht為散列表，k為插入關(guān)鍵字 int i;nodel *p,*q;i=k % m;if(hti.key=k) printf("查找成功n");else if (hti.key= -1) ht

21、i.key=k; / 散列表中沒有關(guān)鍵字k記錄且沒有值，將k插入else if (hti.next=NULL) p=new nodel; / p=( nodel *)malloc(sizeof(nodel); p->key=k; / 插入記錄k p->next=NULL;hti.next=p; else / 在沖突鏈表中查找 q=hti.next; while(q->next!=NULL&& q->key!=k) q=q->next; if (q->key=k) printf("查找成功n"); else p=new no

22、del; / p=( nodel *)malloa(sizeof(nodel); p->key=k; / 插入記錄k p->next=NULL; q->next=p; void main() int m=11,a10=23,36,16,28,40,87,49,60,61; int j,i; nodel *p; for(j=0;j<12;j+) / 初始化散列表 htj.key=-1; htj.next=NULL; for(j=0;j<9;j+) createhash(ht,aj,m); / 調(diào)用散列插入函數(shù) for(j=0;j<12;j+) / 輸出散列表

23、printf("n%4dt",j); if (htj.key!=-1) printf("%4d",htj.key); p=htj.next; while(p) printf("%4d",p->key); p=p->next; printf("n"); 9.3 單元練習(xí)9解答一判斷題答案題目12345678910答案×××××二填空題答案（1） 任意（2） 索引（3） 靜態(tài)（4） 靜態(tài)（5） O（n）（6） O（log2n）（7） O（1）（8） 4（9）

24、 7（10） 左（11） 動態(tài)（12） 散列（13） 查找（14） 沖突（15） 沖突（16） 拉鏈法（或鏈地址法（17） 散列表（或散列）（18） 質(zhì)數(shù)（19） 動態(tài)（20） 1三選擇題答案題目12345678910答案ABBDBAACBC題目11121314151617181920答案BCCDDCABAB四應(yīng)用題答案（1）答： 構(gòu)造二叉排序樹 ： ASL=(1*1+2*2+3*4+4*3)/10=2.974312596108D（2）答：構(gòu)造二叉排序樹 ：1853D2410191579ASL=(1*1+2*2+3*4+4*2+5*1)/10=3（3）答：1509080D25731000019

25、113832562（4）答：1385D37129110 答：85D371391101385D371019 或（5）答：構(gòu)造二叉排序樹18269245D76543438ASL=（1*1+2*2+3*3+4*2）/ 8 =2.75 （或=11/4）（6）答：構(gòu)造二叉排序樹2396D87415ASL=（1*1+2*2+3*4+4*2）/ 9 =2.78 （或=25/9）（7）答：長度為10的判定樹：2396D8451107 - 1次能找到 - 2次能找到 - 3次能找到 - 4次能找到 ASL=1/10（1*1+2*2+3*4+4*3）=2.9（8）答：8159562D9040231232208239562D90403212 （9）答：線性探測再散列解決沖突時所構(gòu)造的散列表：012345678910111214168275519208479231110 平均查找長度ASL=（1*6+2*1+3*3+4*1+9*1）/12=30/3=3 （10）答：平方探測再散列解決沖突時所構(gòu)造的散列表。012345678910112234792167298 平均查找長度ASL=（1*5+2*3+3*1）/9 = 14/9 （或1.56）（11）答： 鏈地址法解決沖突時所構(gòu)造的哈希表。0114 12779236855456198472089102310111112平均查找長度ASL=