數(shù)據(jù)結(jié)構(gòu)總復(fù)習(xí)資料(完整版)

1、 /62查找比較順序查找折半查找分塊查找平均查找長度最大最小二者之間表結(jié)構(gòu)有序表，無序表有序表分塊有序表存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)，線性鏈表順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)，線性鏈表9.3二叉排序樹二叉排序樹的定義或是一棵空樹，或者是具有如下性質(zhì)的非空二叉樹（1）左子樹的所有結(jié)點均小于根的值；（2）右子樹的所有結(jié)點均大于根的值；（3）它的左右子樹也分別為二叉排序樹。二叉排序樹的插入與刪除二叉排序樹既有類似于折半查找的特性，又采用了鏈表存儲，它是動態(tài)查找表的一種適宜表示。查找算法：若二叉排序樹為空，則返回插入位置，否則，先拿根結(jié)點值與待查值進行比較，若相等，則查找成功，若根結(jié)點值大于待查值，則進入左子樹重復(fù)此

2、步驟，否則，進入右子樹重復(fù)此步驟。插入算法：若二叉排序樹為空，則被查結(jié)點為新的根節(jié)點；否則，作為一個新的葉子結(jié)點插入在由查找返回的位置上。刪除算法：（1）P為葉結(jié)點，則直接刪除該結(jié)點即可。只需修改p雙親f的指針f-lchild二NULL或f-rchild二NULL。（2）p只有左子樹或p只有右子樹。p只有左子樹，用p的左孩子代替pp只有右子樹，用p的右孩子代替p（3）p左、右子樹均非空二叉排序樹的查找分析9.4哈希查找表哈希表的概念哈希表：即散列存儲結(jié)構(gòu)。散列法存儲的基本思想：建立關(guān)鍵碼字與其存儲位置的對應(yīng)關(guān)系，或者說，由關(guān)鍵碼的值決定數(shù)據(jù)的存儲地址。查找速度極快（0（1），查找效率與元素個數(shù)

3、n無關(guān)！哈希方法：選取某個函數(shù)，依該函數(shù)按關(guān)鍵字計算元素的存儲位置，并按此存放；查找時，由同一個函數(shù)對給定值k計算地址，將k與地址單元中元素關(guān)鍵碼進行比較，確定查找是否成功。哈希函數(shù)：哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希函數(shù)（雜湊函數(shù)）。59/62哈希表：按上述思想構(gòu)造的表稱為哈希表(雜湊表)。沖突：通常關(guān)鍵碼的集合比哈希地址集合大得多，因而經(jīng)過哈希函數(shù)變換后，可能將不同的關(guān)鍵碼映射到同一個哈希地址上，這種現(xiàn)象稱為沖突。哈希函數(shù)的構(gòu)造方法直接定址法Hash(key)=akey+b(a、b為常數(shù))優(yōu)點：以關(guān)鍵碼key的某個線性函數(shù)值為哈希地址，不會產(chǎn)生沖突。缺點：要占用連續(xù)地址空間，空間效率低。例如

4、：關(guān)鍵碼集合為100，300,500,700,800,900，選取哈希函數(shù)為Hash(key)二key/100,則存儲結(jié)構(gòu)(哈希表)如下：下標(biāo)0123456789值100300500700800900除留余數(shù)法Hash(key)=keymodp(p是一個整數(shù))特點：以關(guān)鍵碼除以p的余數(shù)作為哈希地址。關(guān)鍵：如何選取合適的p?技巧：若設(shè)計的哈希表長為m,則一般取pWm且為質(zhì)數(shù)(也可以是不包含小于20質(zhì)因子的合數(shù))。乘余取整法Hash(key)二B*(A*keymod1)(A、B均為常數(shù)，且0A1，B為整數(shù))特點：以關(guān)鍵碼key乘以A，取其小數(shù)部分，然后再放大B倍并取整，作為哈希地址。數(shù)字分析法特點

5、：某關(guān)鍵字的某幾位組合成哈希地址。所選的位應(yīng)當(dāng)是：各種符號在該位上出現(xiàn)的頻率大致相同。例如：有一組(例如80個)關(guān)鍵碼，其樣式如下：333333333470524491487482696485270486305498058479671473919第1、2位均是“3和4”，第3位也只有“7、8、9”，因此，這幾位不能用，余下四位分布較均勻，可作為哈希地址選用。若哈希地址取兩位(因元素僅80個)，則可取這四位中的任意兩位組合成哈希地址，也可以取其中兩位與其它兩位疊加求和后，取低兩位作哈希地址。3平方取中法3特點：對關(guān)鍵碼平方后，按哈希表大小，取中間的若干位作為哈希地址。理由：因為中間幾位與數(shù)據(jù)的每

6、一位都相關(guān)。例：2589的平方值為6702921，可以取中間的029為地址。沖突處理方法開放定址法(開地址法)設(shè)計思路：有沖突時就去尋找下一個空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入。具體實現(xiàn)：線性探測法i=(Hash(key)+di)modm(1Wim)其中：Hash(key)為哈希函數(shù)m哈希表長度di為增量序列1,2,m-1，且di=i含義：一旦沖突，就找附近(下一個)空地址存入。例如：解釋：47、7(以及11、16、92)均是由哈希函數(shù)得到的沒有沖突的哈希地址；Hash(29)二7，哈希地址有沖突，需尋找下一個空的哈希地址：由H1二(Hash(29)+1)m

7、od1仁8，哈希地址8為空，因此將29存入。另外，22、8、3同樣在哈希地址上有沖突，也是由H1找到空的哈希地址的。優(yōu)點：只要哈希表未被填滿，保證能找到一個空地址單元存放有沖突的元素；缺點：可能使第i個哈希地址的同義詞存入第i+1個哈希地址，這樣本應(yīng)存入第i+1個哈希地址的元素變成了第i+2個哈希地址的同義詞，因此，可能出現(xiàn)很多元素在相鄰的哈希地址上“堆積”起來，大大降低了查找效率。二次探測法鏈地址法再哈希法建立一個公共溢出區(qū)9.5例題例1：折半查找有序表(4，6，12，20，28，38，50，70，88，100)，若查找表中元素20，它將依次與表中元素28，6，12，20比較大小。例2:假設(shè)

8、在有序線性表a20上進行折半查找，則比較一次查找成功的結(jié)點數(shù)為1:比較兩次查找成功的結(jié)點數(shù)為2:比較四次查找成功的結(jié)點數(shù)為8:平均查找長度為3.7。解：全部元素的查找次數(shù)為=(1+2X2+4X3+8X4+5X5)=74；ASL=74/20二3.7。例3:從供選擇的答案中，選出應(yīng)填入下面敘述？內(nèi)的最確切的解答，把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。數(shù)據(jù)結(jié)構(gòu)反映了數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系。鏈表是一種A，它對于數(shù)據(jù)元素的插入和刪除B。通常查找線性表數(shù)據(jù)元素的方法有C和D兩種方法.其中C是一種只適合于順序存儲結(jié)構(gòu)但E的方法：而D是一種對順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)均適用的方法。供選擇的答案：A：順序存儲線性表非順序存儲非

9、線性表順序存儲非線性表非順序存儲線性表B：不需要移動結(jié)點，不需改變結(jié)點指針不需要移動結(jié)點，只需改變結(jié)點指針只需移動結(jié)點，不需改變結(jié)點指針既需移動結(jié)點，又需改變結(jié)點指針61/62C:順序查找循環(huán)查找D:順序查找C:順序查找循環(huán)查找D:順序查找隨機查找E:效率較低的線性查找效率較高的非線性查找條件查找二分法查找二分法查找分塊查找效率較低的非線性查找效率較高的線性查找答案：A=B=.C=.D=E=例4:設(shè)哈希(Hash)表的地址范圍為017,哈希函數(shù)為：H(K)=KMOD16。K為關(guān)鍵字，用線性探測法再散列法處理沖突，輸入關(guān)鍵字序列：(10.24.32.17.31.30.46.47.40.63.49)造出Hash表，試回答下列問題：畫出哈希表的示意圖；若查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字進行比較？若查找關(guān)鍵字60，需要依次與哪些關(guān)鍵字比較？假定每個關(guān)鍵字的查找概率相等，求查找成功時的平均查找長度。解：(1)畫表如下：012345678910111213141516173217634924401030314647(2)查找63，首先要與H(63)=63%16=15號單元內(nèi)容比較，即63vs31,no；然后順移，與46,47,32,17,63相比，一共比較了6次！查找60,首先要與H(60)=60%16=12號單元內(nèi)容比較，但因為12