數(shù)據(jù)結(jié)構(gòu)(下)課件

1、數(shù)據(jù)結(jié)構(gòu)(下)1第8章查找第9章 排序第10章 索引與散列2第8章 查找3 查找，也稱為檢索。查找某人的地址、電話號碼；查某單位45歲以上職工等，都屬于查找范疇。本書中，我們規(guī)定查找是按關(guān)鍵字進行的，所謂關(guān)鍵字(key)是數(shù)據(jù)元素(或記錄)中某個數(shù)據(jù)項的值，用它可以標(biāo)識(或識別)一個數(shù)據(jù)元素。例如，描述一個考生的信息，可以包含：考號、姓名、性別、年齡、家庭住址、電話號碼、成績等關(guān)鍵字。但有些關(guān)鍵字不能唯一標(biāo)識一個數(shù)據(jù)元素，而有的關(guān)鍵字可以唯一標(biāo)識一個數(shù)據(jù)元素。如剛才的考生信息中，姓名不能唯一標(biāo)識一個數(shù)據(jù)元素(因有同名同姓的人)，而考號可以唯一標(biāo)識一個數(shù)據(jù)元素(每個考生考號是唯一的，不能相同)。

2、我們將能唯一標(biāo)識一個數(shù)據(jù)元素的關(guān)鍵字稱為主關(guān)鍵字，而其它關(guān)鍵字稱為次關(guān)鍵字。一、查找的基本概念4 有了主關(guān)鍵字及關(guān)鍵字后，我們可以給查找下一個完整的定義。所謂查找，就是根據(jù)給定的值，在一個表中查找出其關(guān)鍵字等于給定值的數(shù)據(jù)元素(即記錄)，若表中有這樣的元素，則稱查找是成功的，此時查找的信息為給定整個數(shù)據(jù)元素的輸出或指出該元素在表中的位置；若表中不存在這樣的記錄，則稱查找是不成功的，或稱查找失敗，并可給出相應(yīng)的提示。5 要衡量一種查找算法的優(yōu)劣，主要是看要找的值與關(guān)鍵字的比較次數(shù)，但我們將找到給定值與關(guān)鍵字的比較次數(shù)的平均值(平均查找長度)來作為衡量一個查找算法好壞的標(biāo)準(zhǔn)，對于一個含有n個元素的

3、表，查找成功時的平均查找長度可表示為ASL= ，其中i為查找第i個元素的概率，且 =1。一般情形下我們認(rèn)為查找每個元素的概率相等，i為查找第i個元素所用到的比較次數(shù)。 61、 順序查找二、 靜態(tài)查找表 順序查找的基本思想 順序查找是一種最簡單的查找方法，它的基本思想是：從表的一端開始，順序掃描線性表，依次將掃描到的結(jié)點關(guān)鍵字和待找的值相比較，若相等，則查找成功，若整個表掃描完畢，仍末找到關(guān)鍵字等于的元素，則查找失敗。 順序查找既適用于順序表，也適用于鏈表。若用順序表，查找可從前往后掃描，也可從后往前掃描，但若采用單鏈表，則只能從前往后掃描。另外，順序查找的表中元素可以是無序的。7 順序查找性能

4、分析(1)在最壞的情況下，順序查找需要比較n次，即最大查找長度MSL=n。(2)假設(shè)在每個記錄查找的概率相等，即有pi=1/n，由于查找第i個記錄需要比較i次，即Ci=i，于是，查找成功的平均查找長度 ASL= = = 從ASL可知，當(dāng)n較大時，ASL值較大，查找的效率較低。 順序查找的優(yōu)點是算法簡單。順序查找的缺點是查找效率低，當(dāng)n較大時，不宜采用順序查找。 82、折半查找 首先將待查值K與有序表R1到Rn的中點mid上的關(guān)鍵字Rmid.key進行比較，若相等，則查找成功；否則，若Rmid.keyk， 則在R1到Rmid-1中繼續(xù)查找，若有Rmid.keyk ,則在Rmid+1到Rn中繼續(xù)查

5、找。每通過一次關(guān)鍵字的比較，區(qū)間的長度就縮小一半，區(qū)間的個數(shù)就增加一倍，如此不斷進行下去，直到找到關(guān)鍵字為K的元素；若當(dāng)前的查找區(qū)間為空(表示查找失敗)。 折半查找的基本思想 折半查找，也稱二分查找，它是一種高效查找方法。9從上述查找思想可知，每進行一次關(guān)鍵字比較，區(qū)間長度縮小一半，故稱為折半（查找的范圍縮小一半）。而區(qū)間數(shù)目增加一倍，故也稱為二分（區(qū)間一分為二），mid= (low+high)/2注：折半查找的結(jié)束條件是(1)區(qū)間中間位置記錄的關(guān)鍵字等于給定的值，則表明查找成功。(2)查找區(qū)間的大小差小于0，表明查找不成功。10例：假設(shè)給定有序表中關(guān)鍵字為8,17,25,44,68,77,9

6、8,100,115,125，將查找K=17和K=120的情況描述為圖8-1及圖8-2所示。11121314折半查找的性能分析 可用二叉樹來描述折半查找過程。把當(dāng)前查找區(qū)間的中點作為根結(jié)點，左子區(qū)間和右子區(qū)間分別作為根的左子樹和右子樹，左子區(qū)間和右子區(qū)間再按類似的方法，由此得到的二叉樹稱為二分查找的判定樹。例如，圖8-1給定的關(guān)鍵字序列的判定樹見圖8-3。15 從圖8-3可知，查找根結(jié)點68，需一次查找，查找17和100，各需二次查找，查找8、25、77、115各需三次查找，查找44、98、125各需四次查找。于是，可以得到結(jié)論：二叉樹第k層結(jié)點的查找次數(shù)各為k次(根結(jié)點為第1層)，而第k層結(jié)點

7、數(shù)最多為2k-1個。假設(shè)該二叉樹的深度為h，則折半查找的成功的平均查找長度為（假設(shè)每個結(jié)點的查找概率相等）：ASL= =1/n 1/n（1+22+322+h2h-1）16三、動態(tài)查找表 1、二叉排序樹二叉排序樹的概述 二叉排序樹或者是一棵空樹，或者是一棵具有如下特征的非空二叉樹：(1)若它的左子樹非空，則左子樹上所有結(jié)點的關(guān)鍵字均小于根結(jié)點的關(guān)鍵字；(2)若它的右子樹非空，則右子樹上所有結(jié)點的關(guān)鍵字均大于等于根結(jié)點的關(guān)鍵字； (3)左、右子樹本身又都是一棵二叉排序樹。17二叉排序樹的數(shù)據(jù)類型描述可用一個二叉鏈表來描述一棵二叉排序樹，具體為： struct Btreenode elemtype

8、key; /代表關(guān)鍵字 Btreenode *lch,*rch; /代表左、右孩子 ;二叉排序樹的插入運算 若二叉排序樹為空，則作為根結(jié)點插入，否則，若待插入的值小于根結(jié)點值，則作為左子樹插入，否則作為右子樹插入。18例：給定關(guān)鍵字序列79，62，68，90，88，89，17，5，100，120，生成二叉排序樹過程如圖8-4所示。(注：二叉排序樹與關(guān)鍵字排列順序有關(guān)，排列順序不一樣，得到的二叉排序樹也不一樣)1920二叉排序樹上的查找 若二叉排樹為空，則查找失敗，否則，先拿根結(jié)點值與待查值進行比較，若相等，則查找成功，若根結(jié)點值大于待查值，則進入左子樹重復(fù)此步驟，否則，進入右子樹重復(fù)此步驟，若

9、在查找過程中遇到二叉排序樹的葉子結(jié)點時，還沒有找到待找結(jié)點，則查找不成功。二叉排序樹查找的性能分析 在二叉排序樹查找中，成功的查找次數(shù)不會超過二叉樹的深度，而具有n個結(jié)點的二叉排序樹的深度，最好為log2n，最壞為n。因此，二叉排序樹查找的最好時間復(fù)雜度為O(log2n)，最壞的時間復(fù)雜度為O(n) 。212、平衡二叉樹查找平衡二叉樹概述 由阿德爾森一維爾斯和蘭迪斯(Adelson-Velskii and Landis)于1962年首先提出的，所以又稱為AVL樹。 若一棵二叉樹中每個結(jié)點的左、右子樹的深度之差的絕對值不超過1，則稱這樣的二叉樹為平衡二叉樹。 將該結(jié)點的左子樹深度減去右子樹深度的

10、值，稱為該結(jié)點的平衡因子(balance factor)。即，一棵二叉排序樹中，所有結(jié)點的平衡因子只能為0、1、-1時，則該二叉排序樹就是一棵平衡二叉樹，否則就不是一棵平衡二叉樹。22 非平衡二叉樹的平衡處理 LL型的處理(左左型)23 如圖8-7所示，在C的左孩子B上插入一個左孩子結(jié)點A，使C的平衡因子由1變成了2，成為不平衡的二叉樹序樹。這時的平衡處理為：將C順時針旋轉(zhuǎn)，成為B的右子樹，而原來B的右子樹則變成C的左子樹，待插入結(jié)點A作為B的左子樹。24LR型的處理(左右型) 如圖8-8所示，在C的左孩子A上插入一個右孩子B，使的C的平衡因子由1變成了2，成為不平衡的二叉排序樹。這是的平衡處

11、理為：將B變到A與C 之間，使之成為LL型，然后按第(1)種情形LL型處理。25RR型的處理(右右型) 如圖8-9所示，在A的右孩子B上插入一個右孩子C，使A的平衡因子由-1變成-2，成為不平衡的二叉排序樹。這時的平衡處理為：將A逆時針旋轉(zhuǎn)，成為B的左子樹，而原來B的左子樹則變成A的右子樹，待插入結(jié)點C成為B的右子樹。26RL型的處理(右左型) 如圖8-10所示，在A的右孩子B上插入一個右孩子C，使A的平衡因子由-1變成-2，成為不平衡的二叉排序樹。這時的平衡處理為：將A逆時針旋轉(zhuǎn)，成為B的左子樹，而原來B的左子樹則變成A的右子樹，待插入結(jié)點C成為B的右子樹。27例：設(shè)一組記錄的關(guān)鍵字按以下次

12、序進行插入：4、5、7，2、1、3、6，其生成及調(diào)整成二叉平衡樹的過程示于圖8-11。圖8-11 二叉平衡樹插入結(jié)點(結(jié)點旁的數(shù)字為其平衡因子) 28平衡二叉樹的查找及性能分析 平衡二叉樹本身就是一棵二叉排序樹，故它的查找與二叉排序樹完全相同。但它的查找 性能優(yōu)于二叉排序樹，不像二叉排序樹一樣，會出現(xiàn)最壞的時間復(fù)雜度O(n)，它的時間復(fù)雜度與二叉排序樹的最好時間復(fù)雜相同，都為O(log2n)。 例：對關(guān)鍵字序列4,5,7,2,1,3,6，試用二叉排序樹和平衡二叉樹兩種方法查找，給出查找6的次數(shù)及成功的平均查找長度。分析：由于關(guān)鍵字序列的順序己經(jīng)確定，故得到的二叉排序樹和平衡二叉樹都是唯一的。得

13、到的平衡二叉樹見圖8-12，得到的二叉排序樹見圖8-13。29圖8-12 由關(guān)鍵字序列4,5,7,2,1,3,6生成的平衡二叉樹從圖8-13的二叉排序樹可知，查找6需4次，平均查找長度ASL=(1+2+2+3+3+3+4)/7=18/72.57。從圖8-12的平衡二叉樹可知，查找6需2次，平均查找長度ASL=(1+2+2+3+3+3+3)=17/72.43。從結(jié)果可知，平衡二叉樹的查找性能優(yōu)于二叉排序樹。 30第9章 排序 31學(xué)習(xí)重點： 排序的基本概念和術(shù)語 插入排序：直接插入排序和希爾排序 交換排序：冒泡排序和快速排序 選擇排序：簡單選擇排序和堆排序 歸并排序 基數(shù)排序 各種排序方法的比較

14、分析329.1 排序的基本概念9.2 插入排序9.3 交換排序9.4選擇排序9.5 歸并排序9.6 基數(shù)排序9.7 小結(jié)339.1 排序的基本概念 排序（Sorting）排序又稱分類，是把一組記錄（元素）按照某個域的值的遞增（即由小到大）或遞減（即由大到小）的次序重新排列的過程。可以使雜亂無章的數(shù)據(jù)序列重新排列成有序序列。34排序方法的分類 內(nèi)部排序是指待排序的記錄存放在計算機內(nèi)存之中；外部排序是指待排序的記錄數(shù)量很大，以至于內(nèi)存容納不下而存放在外存儲器之中，排序過程需要訪問外存。 本章主要討論內(nèi)部排序 35 排序的依據(jù)可以是記錄的主關(guān)鍵字，也可以是次關(guān)鍵字，甚至是若干數(shù)據(jù)項的組合。為了方便討

15、論，把排序所依據(jù)的數(shù)據(jù)項統(tǒng)稱排序關(guān)鍵字，簡稱關(guān)鍵字。 假設(shè)含有n個記錄的序列為R1, R2, , Rn，其相應(yīng)的關(guān)鍵字序列為K1，K2 ，Kn，所謂排序就是將記錄Ri按關(guān)鍵字Ki非遞減(或非遞增)的順序重新排列起來。36內(nèi)部排序的方法插入類交換類選擇類 歸并類其它方法37 將要排序的記錄集合，在本章中選用順序存儲方法。 為了討論方便，在此把排序關(guān)鍵字假設(shè)為整型。假設(shè)排序依據(jù)的關(guān)鍵字為整型。記錄的結(jié)構(gòu)定義如下： const MAXSIZE=1000; /* 數(shù)組最大容量*/ typedef int ElemType; /* 關(guān)鍵字的類型*/ typedef struct /* 記錄結(jié)構(gòu) * El

16、emType key; /* 排序關(guān)鍵字域 */ int oth; /* 其它域，根據(jù)需要自己設(shè)定 */ node;389.2 插入排序插入排序（Insertion Sort）又可分幾種不同的方法，這里僅介紹三種方法：直接插入排序折半插入排序希爾排序399.2.1 直接插入排序 直接插入排序（Straight Insertion Sort）是一種最簡單的排序方法。 它的基本操作是將一個記錄插入到一個長度為m（假設(shè)）的有序表中，使之仍保持有序，從而得到一個新的長度為m1的有序表。40算法思路：設(shè)有一組關(guān)鍵字K1，K2 ，Kn ；排序一開始就認(rèn)為K1是一個有序序列；讓K2插入上述表長為1的有序序列

17、，使之成為一個表長為2的有序序列；然后讓K3插入上述表長為2的有序序列，使之成為一個表長為3的有序序列；依次類推，最后讓Kn插入上述表長為n-1的有序序列，得一個表長為n的有序序列。41例9.1設(shè)有一組關(guān)鍵字序列55，22，44，11，33，這里n=5，即有5個記錄。請將其按由小到大的順序排序。42直接插入排序算法如下：void stinsort ( node rMAXSIZE， int n) for (i=2； i r0.key) rj+1=rj；j-； rj+1=r0； /*將r0即原ri記錄內(nèi)容，插到rj后一位置*/ /*sinsort*/43 此算法外循環(huán)n-1次，在一般情況下內(nèi)循環(huán)平

18、均比較次數(shù)的數(shù)量級為(n)，所以算法總時間復(fù)雜度為(n2 )。由于比較過程中，當(dāng)Kj 與K0 相等時并不移動記錄，因此直接插入排序方法是穩(wěn)定的。 直接插入排序也可用單鏈表做存儲結(jié)構(gòu) 449.2.2 折半插入排序 當(dāng)直接插入排序進行到某一趟時，對于ri.key來講，前邊i-1個記錄已經(jīng)按關(guān)鍵字有序。此時不用直接插入排序的方法，而改為折半查找，找出ri.key應(yīng)插的位置，然后插入。這種方法就是折半插入排序（Binary insertion sort）。 算法如下：45 void binasort(struct node rMAXSIZE， int n) for (i=2； i=n； i+) r0=

19、ri； l=1； h=i-1；/*認(rèn)為在rlow和ri-1之間已經(jīng)有序*/ whil (l=h) /*對有序表進行折半查找*/ mid= (l+h)/2； if(r0.key=l； j-) rj+1=rj； rl=r0； /*此處可以改為rh=r0；嗎？*/ /*binasort*/46 折半插入排序，關(guān)鍵字的比較次數(shù)由于采用了折半查找而減少，數(shù)量級為(nlog2n)，但是元素移動次數(shù)仍為(n2 )。故折半插入排序時間復(fù)雜度仍為(n2 )。 折半插入排序方法是穩(wěn)定的。479.2.3 希爾排序希爾排序（shell sort）是D.希爾（D.L.Shell）提出的“縮小增量”的排序方法。它的作法不

20、是每次一個元素挨一個元素的比較。而是初期選用大跨步（增量較大）間隔比較，使記錄跳躍式接近它的排序位置；然后增量縮小；最后增量為 1，這樣記錄移動次數(shù)大大減少，提高了排序效率。希爾排序?qū)υ隽啃蛄械倪x擇沒有嚴(yán)格規(guī)定。48算法思路：1先取一個正整數(shù)d1(d1 n)，把全部記錄分成d1 個組，所有距離為d1 的倍數(shù)的記錄看成一組，假設(shè)d1=4，那么記錄共分4組： 第1組：r1,r5,r9,; 第2組：r2,r6,r10; 第3組：r3,r7,; 第4組：r4,r8,; 在各組內(nèi)部進行插入排序，使得數(shù)據(jù)在每組內(nèi)是有序的，但整個記錄表仍然無序；492. 然后取d2 (d2=1)，即所有記錄成為一個大組為止

21、。此時整個記錄表有序，排序完成。一般選d1 約為n/2，d2 為d1 /2，d3為d2 /2，di=150例9.2有一組關(guān)鍵字76，81，60，22，98，33，12，79，將其按由小到大的順序排序。這里n=8，取d1 =4，d2=2，d3 =1，其排序過程如圖9.2所示。51算法如下： void shellsort(struct node rMAXSIZE，int n) k=n/2； /*k值代表前文中的d值*/ while(k=1) /*循環(huán)*/ for(i=k+1；ir0.key)& (j=0) rj+k=rj；j=j-k； rj+k=r0； k=k/2； /*shellsort*/ 5

22、2希爾排序的分析是一個復(fù)雜的問題，因為它的時間是所選定的“增量序列”的函數(shù)，這涉及到數(shù)學(xué)上一些尚未解決的難題。到目前為止沒有人找到一種最好的增量序列。有人在大量實驗基礎(chǔ)上推出，它的時間復(fù)雜度約為O(n1.3)。如果對關(guān)鍵字序列6,7,51,2,52,8進行希爾排序，可以看出希爾排序是不穩(wěn)定的。539.3 交換排序交換排序主要是根據(jù)記錄的關(guān)鍵字的大小，將記錄進行交換來排序的。交換排序的特點是：將關(guān)鍵字值較大的記錄向序列的后部移動，關(guān)鍵字較小的記錄向前移動。54兩種交換排序方法：冒泡排序和快速排序。為了方便理解算法，本小節(jié)使用數(shù)組時均從下標(biāo)1開始。假設(shè)數(shù)組名是a，第一個數(shù)據(jù)元素放在a1 之中。55

23、9.3.1 冒泡排序冒泡排序(Bubble Sort)是一種人們熟知的、最簡單的交換排序方法。在排序過程中，關(guān)鍵字較小的記錄經(jīng)過與其他記錄的對比交換，好像水中的氣泡向上冒出一樣，移到數(shù)據(jù)序列的首部，故稱此方法為冒泡排序法。56排序的算法思路是：(1)讓j取n至2，將rj.key與rj-1.key比較，如果rj.keyi;j-) if (rj.keyrj-1.key) x=rj;rj=rj-1; rj-1=x;tag=1; i+; while (tag=1 & i=n); /*bubblesort*/61該算法的時間復(fù)雜度為O(n2)。但是，當(dāng)原始關(guān)鍵字序列已有序時，只進行一趟比較就結(jié)束，此時時

24、間復(fù)雜度為O(n)。 629.3.2 快速排序快速排序由霍爾(Hoare)提出，它是一種對冒泡排序的改進。由于其排序速度快故稱快速排序(Quick Sort)?？焖倥判蚍椒ǖ膶嵸|(zhì)是將一組關(guān)鍵字K1,K2,Kn進行分區(qū)交換排序。63算法思路：（1）以第一個關(guān)鍵字K1為控制字，將K1,K2,Kn分成兩個子區(qū)，使左區(qū)所有關(guān)鍵字小于等于K1，右區(qū)所有關(guān)鍵字大于等于K1，最后控制字K1居兩個子區(qū)中間的適當(dāng)位置。但在子區(qū)內(nèi)數(shù)據(jù)尚處于無序狀態(tài)。（2）將右區(qū)首、尾指針(記錄的下標(biāo)號)保存入棧。對左區(qū)進行與第（1）步相類似的處理，又得到它的左子區(qū)和右子區(qū)，控制字居中。（3）重復(fù)第（1）、（2）步，直到左區(qū)處理完

25、畢。然后退棧對一個個子區(qū)進行相類似的處理，直到棧空為止。換句話講，就是直到分區(qū)的大小為一個記錄為止。 64例9.4設(shè)有一組關(guān)鍵字46,56,14,43,95,19,18,72，這里n=8。試用快速排序方法由小到大進行排序。 65算法實現(xiàn) ：先設(shè)計一個算法hoare()，它僅對某一待排序文件進行左、右子區(qū)的劃分，使控制字居中；再設(shè)計一個主體框架算法quicksort()，在這里多次調(diào)用hoare()函數(shù)以實現(xiàn)對整個文件的排序 兩個算法如下：66分區(qū)處理算法hoare()：int hoare(struct node rMAXSIZE,int l,int h) i=1;j=h;x=ri; do wh

26、ile(i=x.key) j-;if (ij) ri=rj;i+;while(ij) &(ri.key=x.key) i+;if (ij) rj=ri; j-;while(ij); ri=x;return(i);/* 控制字放在兩個子文件的中間*/ return(i); /* i 是控制字的位置 */ /*hoare*/67void quicksort2(struct node rMAXSIZE,int l,int h) /*遞歸的快速排序主體函數(shù)*/ if(lh) i=hoare(r,l,h); /*劃分兩個區(qū)，調(diào)用分區(qū)處理函數(shù)hoare( )*/ quicksort2(r,l,i-1);

27、/*對左分區(qū)快速排序*/ quicksort2(r,i+1,h); /*對右分區(qū)快速排序*/ /*quicksort2*/快速排序主體框架算法：68快速排序主體算法時間運算量約O(log2n)，劃分子區(qū)函數(shù)運算量約O(n)，所以總的時間復(fù)雜度為O(n.log2n)，它顯然優(yōu)于冒泡排序O(n2)。可是算法的優(yōu)勢并不是絕對的。當(dāng)原文件關(guān)鍵字有序時，快速排序時間復(fù)雜度就是O(n2),這種情況下快速排序不快。而這種情況的冒泡排序是O(n),反而很快。在原文件記錄關(guān)鍵字無序時的多種排序方法中，快速排序被認(rèn)為是最好的一種排序方法。69例9.5試用6,7,51,2,52,8進行快速排序。排序過程簡述如下：

28、6 7 51 2 52 8 初始狀態(tài)52 7 51 6 7 82 52 51 6 7 82 52 51 6 7 8 最后狀態(tài)從結(jié)果中可以看出原先位于51之后的52在排序之后移到了51的前面，所以說快速排序是不穩(wěn)定的 709.4選擇排序選擇排序也有幾種不同的方法，這里僅介紹簡單選擇排序和堆排序。為了方便理解算法，本小節(jié)使用數(shù)組時均從下標(biāo)1開始。假設(shè)數(shù)組名是a，第一個數(shù)據(jù)元素放在a1 之中。719.4.1簡單選擇排序簡單排序的具體思路是 ：對于一組關(guān)鍵字 K1,K2,Kn ，首先從K1,K2,Kn中選擇最小值，假如它是Kz，則將Kz與K1對換；然后從K2，K3，Kn中選擇最小值Kz，再將Kz與K2

29、對換。如此進行選擇和調(diào)換n-2趟，第(n-1)趟，從Kn-1、Kn中選擇最小值Kz，將Kz與Kn-1對換，最后剩下的就是該序列中的最大值，一個由小到大的有序序列就這樣形成 。7273算法如下：void sisort(struct node rMAXSIZE,int n)for (i=1;in;i+) z=i; for (j=i+1;j=n;j+) if (rj.keyrz.key) z=j; if(zi) x=ri; ri=rz; rz=x; /*sisort*/其時間復(fù)雜度為O(n2)。并且排序是穩(wěn)定的。 749.4.2堆排序堆是n個元素的有限序列 K1,K2,Kn ，當(dāng)且僅當(dāng)滿足如下關(guān)系：

30、 稱為堆。這是一個上小、底大的堆。若是一個上大、底小的堆，只需把“=”即可。堆是一種數(shù)據(jù)元素之間的邏輯關(guān)系，常用向量做存儲結(jié)構(gòu) 75用堆的概念分析向量中的數(shù)據(jù)，它顯然滿足（上小、底大）堆的關(guān)系。不難看出滿足堆的邏輯關(guān)系的一組數(shù)據(jù)，可畫成二叉樹的形狀，并且它是一棵完全二叉樹樹形 .76771堆排序思路把n個記錄存于向量r之中，把它看成完全二叉樹，此時關(guān)鍵字序列不一定滿足堆的關(guān)系。堆排序大體分兩步處理。 (1)初建堆。從堆的定義出發(fā)，當(dāng)i=1,2, ,n/2時應(yīng)滿足ki=k2i和ki=k2i+1。所以先取i=n/2(它一定是第n個結(jié)點雙親的編號)，將以i結(jié)點為根的子樹調(diào)整為堆；然后令i=i-1，將

31、以i結(jié)點為根的子樹調(diào)整為堆。此時可能會反復(fù)調(diào)整某些結(jié)點，直到i=1為止，堆初步建成。 78(2)堆排序。首先輸出堆頂元素（一般是最小值），讓堆中最后一個元素上移到原堆頂位置，然后恢復(fù)成堆。因為經(jīng)過第一步輸出堆頂元素的操作后，往往破壞了堆關(guān)系，所以要將其恢復(fù)成堆。重復(fù)執(zhí)行輸出堆頂元素、堆尾元素上移和恢復(fù)堆的步驟，直到全部元素輸出完為止。79例9.6設(shè)有n個記錄(n=8)的關(guān)鍵字是46,55,13,42,94,17,5,80，試對它們進行堆排序。第一步：初建堆。因為n=8，所以從i=4開始 。80第二步：堆排序。這是一個反復(fù)輸出堆頂元素，將堆尾元素移至堆頂，再調(diào)整恢復(fù)堆的過程。 注意：每輸出一次堆

32、頂元素，所謂堆尾元素移至堆頂位置，實質(zhì)上是堆尾元素與堆頂元素進行交換。同時，堆尾的邏輯位置退1，直到堆中剩下一個元素為止。 81排序過程（1） 82排序過程（2） 83排序過程（3） 84排序過程（4） 85排序過程（5） 86排序過程（6） 87堆排序算法實現(xiàn)（1）由上述可知，調(diào)整恢復(fù)堆要被多次反復(fù)調(diào)用， 為此專門設(shè)計算法heap ()完成此功能。（2）另外，需再設(shè)計一個主體算法，使在初建堆階段，讓i從n/2變化到1，循環(huán)調(diào)用函數(shù)heap ()，而在堆排序階段，每輸出一次堆頂元素將堆尾元素移至堆頂之后，就調(diào)用一次heap ()函數(shù)來恢復(fù)堆。主體算法由函數(shù)heapsort()實現(xiàn)。88(1)以

33、編號為i的結(jié)點為根，調(diào)整為堆的算法：void heap(struct node rMAXSIZE,int i, int m) x=ri;j=2*i; /*x保存根記錄內(nèi)容，j為左孩子編號*/ while (j=m & bol=0) if (jrj+1.key) j+; /*當(dāng)結(jié)點i有左、右兩個孩子時，j取關(guān)鍵字較小的孩子結(jié)點編號*/ if ( rj.keyx.key) bol=1; /* 已是堆關(guān)系*/ else ri=rj ; i=j; j=2*i; /*較小數(shù)上移,向下一層探測*/ ri=x;/*heap*/ 89(2) 堆排序主體算法：void heapsort(struct node

34、rMAXSIZE,int n) /*n為文件的實際記錄數(shù),r0沒有使用*/for (i=n/2;i=1;i-) heap(r,i,n); /*初建堆*/ /*以下For語句為輸出堆頂元素，調(diào)整堆操作*/ for (v=n;v=2;v-) /*邏輯堆尾下標(biāo)m不斷變小*/ printf(“%5d”,r1.key); /*輸出堆頂元素*/ x=r1; r1=rv; rv=x; /*堆頂與堆尾元素交換*/ heap(r,1,v-1); /*本次比上次少處理一個記錄*/ printf(“%5d”,r1.key);/*heapsort*/909.5 歸并排序歸并的含義是將兩個或兩個以上的有序表合并成一個新

35、的有序表。歸并排序(Merge Sort)有多路歸并排序、兩路歸并排序?？捎糜趦?nèi)排序，也可以用于外排序。這里僅對內(nèi)排序的兩路歸并方法進行討論91兩路歸并排序算法思路(1)把n個記錄看成n個長度為l的有序子表；(2)進行兩兩歸并使記錄關(guān)鍵字有序，得到 個長度為2的有序子表；(3)重復(fù)第（2）步直到所有記錄歸并成一個長度n為的有序表為止。92例9.7 有一組關(guān)鍵字4,7,5,3,2,8,6,1,n=8,將其按由小到大的順序排序。兩路歸并排序操作過程如圖9.12所示，其中 l為子表長度。93算法實現(xiàn)分三步來討論 ：首先，讓子表表長L=1進行處理；不斷地使L=2*L，進行子表處理，直到L=n為止，把這

36、一過程寫成一個主體框架函數(shù)mergesort()。 其次，對于某確定的子表表長L，將n個記錄分成若干組子表，兩兩歸并，這里顯然要循環(huán)若干次，把這一步寫成一個函數(shù)mergepass()，可由mergesort()調(diào)用。 最后，再看每一組（一對）子表的歸并。歸并操作作為核心算法寫成函數(shù)merge()，由mergepass()來調(diào)用。94(1)主體框架算法描述如下：void mergesort(struct node rMAXSIZE,int n)/*r是包含有n個記錄的原文件，歸并過程中另需一個r2作為輔助存儲空間*/l=1; /*子表初始長度*/while (l=2*l) /*剩下的記錄數(shù)目大于

37、兩個子表長度時*/ h1=i; mid=h1+l-1;h2=i+2*l-1; merge(r,r2,h1,mid,h2); /*調(diào)用歸并核心算法*/ i=i+2*l; /*跳過兩個子表，指向新的一對子表的首記錄*/ if (n-i+1)=l) /*剩下的記錄數(shù)目小于一個子表時*/ for (j=i;j=n;j+) r2j=rj else /*剩下的記錄數(shù)目大于一個，小于兩個子表時*/ h1=i;mid=h1+l-1;h2=n; merge(r,r2,h1,mid,h2); /*調(diào)用歸并核心算法*/ /* mergesort*/96(3)歸并排序核心算法描述如下：void merge(struc

38、t node rMAXSIZE,struct node r2MAXSIZE,int h1,int mid, int h2 ) /*h1為第一個子表首元素的下標(biāo)，mid 為第一個子表末元素的下標(biāo)，*/ /* h2為第二個子表末元素的下標(biāo) */i=h1;j=mid+1;k=h1-1; /* k是r2的初始指針*/ while (i=mid) & (j=h2) k=k+1; if (ri.key=rj.key) r2k=ri;i+; else r2k=rj;j+; while (i=mid) k+;r2k=ri;i+; while (j=h2) k+;r2=rj;j+;/* merge*/97主體算

39、法調(diào)用mergepass約log2n趟。每一趟處理考慮兩兩子表歸并，其運算數(shù)量級為O(n)。故歸并排序時間復(fù)雜度為O(nlog2n) 歸并排序是穩(wěn)定的 989.6 基數(shù)排序前幾節(jié)所介紹的排序方法主要是通過比較記錄的關(guān)鍵字來實現(xiàn)，基數(shù)排序(Radix Sort)是與前面所介紹的各類排序方法完全不同的一種排序方法?；鶖?shù)排序法不必經(jīng)過關(guān)鍵字的比較來實現(xiàn)排序，而是根據(jù)關(guān)鍵字每個位上的有效數(shù)字的值，借助于“分配”和“收集”兩種操作來實現(xiàn)排序。99基數(shù)排序有兩種方法： 一種方法是首先根據(jù)最高位有效數(shù)字進行排序，然后根據(jù)次高位有效數(shù)字進行排序，依次類推，直到根據(jù)最低位（個位）有效數(shù)字進行排序，產(chǎn)生一個有序序

40、列，這種方法稱最高位優(yōu)先法(Most Significant Digit first)，簡稱MSD法。100另一方法是首先根據(jù)關(guān)鍵字最低位（個位）有效數(shù)字進行排序，然后根據(jù)次低位（十位）有效數(shù)字進行排序，依次類推，直到根據(jù)最高位有效數(shù)字進行排序，產(chǎn)生一個有序序列，這種方法稱最低位優(yōu)先法(Least Significant Digit)，簡稱LSD法。101算法實現(xiàn)：第一趟“分配”，根據(jù)關(guān)鍵字個位有效數(shù)字，把所有記錄分配到相應(yīng)的10個隊列中去。用f0,e0表示3號隊列的頭、尾指針，f9，e9表示9號隊列的頭、尾指針。例如，關(guān)鍵字為184的記錄就分配到4號隊列中去。第一趟“收集”把所有非空隊列（1

41、0個隊列中可能有空隊）按隊列號由小到大的順序頭、尾相接，收集成一個新的序列。此序列若觀察其關(guān)鍵字的個位，則它是有序的；若觀察其關(guān)鍵字的高位，則它尚處于無序狀態(tài)。以后各趟，分別根據(jù)關(guān)鍵字的十位、百位有效數(shù)字重復(fù)類同第（1）、（2）步的“分配”與“收集”操作，最終得到一個按關(guān)鍵字由小到大的序列。102例9.8 有一組關(guān)鍵字278,109,063,930,589,184,505,269,008,083,將它們按由小到大的順序排序。操作的具體過程見圖9.13103104105106int radixsort(struct node rMAXSIZE,int n) int f10,e10; for (i

42、=1;in;i+) ri.point=i+1; rn.point=0;p=1; /*建立靜態(tài)鏈表，p指向鏈表的第一個元素*/ for (i=1;i=d;i+) /*下面是分配隊列*/ for (j=0;j10;j+) fj=0;ej=0;while (p!=0) k=yx(rp.key,i); /*取關(guān)鍵字倒數(shù)第i位有效數(shù)字*/ if (fk=0) fk=p; ek=p; /*讓頭尾指針指向同一元素*/ else l=ek;rl.point=p; ek=p; /*在k號隊列尾部入隊*/ p=rp.point; /*在r向量中，p指針向后移*/ /*下面是收集*/ 107 j=0; while

43、(fj=0) j+; /*找第一個非空隊列*/ p=fj; t=ej; /*p記下隊頭做收集后的靜態(tài)鏈表頭指針/ while (j10) j+; while (j10) & (fj=0) j+; if (fj!=0) rt.point=fj; t=ej; /*將前邊一個非空隊列的隊尾元素指針指向現(xiàn)在隊頭元素并記下現(xiàn)在隊尾位置*/ rt.point=0; /*這是一趟分配與收集之后的鏈表最后一個元素*/ /* for i */ return(p); /*基數(shù)排序結(jié)果p指向靜態(tài)鏈表的第一個元素，即關(guān)鍵字最小的記錄* /*radixsort*/108radixsort()算法中基數(shù)為10，這里用rd

44、表示它，最高有效數(shù)字位是4，這里用d表示，記錄總數(shù)為n?；鶖?shù)排序時間復(fù)雜度為O(d(n+rd)，這是因為總共循環(huán)d趟，每趟分配運算量數(shù)量級為O(n)，收集運算量數(shù)量級為O(rd)，所以總時間復(fù)雜度為O(d(n+rd)。它的空間占用情況是，向量r多了n個指針域，輔助空間為2rd個隊列指針?；鶖?shù)排序是穩(wěn)定的。109本章小結(jié)重點掌握各種排序的基本思想，執(zhí)行過程，設(shè)計和算法之間的比較。學(xué)習(xí)難點是快速排序，堆排序，歸并排序等算法的設(shè)計。要求能夠根據(jù)數(shù)據(jù)序列，分別采用快速排序，堆排序，歸并排序不同方法，寫出排序過程的圖示。110111本章介紹的排序方法各有優(yōu)點缺點，沒有哪一種排序方法絕對最優(yōu)。在不同的應(yīng)用

45、條件下可選擇較合適的不同方法，甚至可將多種方法結(jié)合使用。 (1)當(dāng)問題的規(guī)模不大，即待排序的記錄數(shù)n不大時(n=50)，可選用表中前三種排序方法之一。它們的時間復(fù)雜度雖為O(n2)，但方法簡單易掌握。直接插入排序和冒泡排序在原文件記錄按關(guān)鍵字“基本有序”時，排序速度比較快。其中直接插入排序更為常用。(2)當(dāng)n值很大，并不強求排序的穩(wěn)定性，并且內(nèi)存容量不寬余時，應(yīng)該選用快速排序或堆排序。一般來講，它們排序速度非?？臁５焖倥判?qū)υ蛄谢居行虻那闆r，速度減慢接近O(n2)，而堆排序不會出現(xiàn)最壞情況。112(3)當(dāng)n值很大，對排序穩(wěn)定性有要求，存儲容量較寬余時，選用歸并排序最為合適。排序速度很快，

46、并且穩(wěn)定性好。(4)當(dāng)n值很大并且關(guān)鍵字位數(shù)較小時，采用靜態(tài)鏈表基數(shù)排序較好。不僅速度較快并且穩(wěn)定性好。113第10章 索引結(jié)構(gòu)與散列 114學(xué)習(xí)重點： B_樹的插入、刪除和查找方法； 散列的基本思想和基本概念； 幾種常見的散列函數(shù)； 散列技術(shù)中處理沖突的方法。11510.1 靜態(tài)索引結(jié)構(gòu) 10.2 動態(tài)索引結(jié)構(gòu)（B_樹和B+樹）10.3 鍵樹及Trie樹 10.4 哈希表及其查找11610.1 靜態(tài)索引結(jié)構(gòu) 10.1.1 索引表分塊查找又稱索引順序查找，這是順序查找的一種改進方法，在此查找法中，除表本身以外，尚需建立一個“索引表”。 如下列所示：117例如，某大學(xué)的所有學(xué)生是一個集合。若是查

47、找某個學(xué)生，可以采取按順序查找一個一個地查找，但這種方法比較慢。因每個學(xué)生都分屬不同的學(xué)院，若是按學(xué)院進行查找，速度就會快很多，此時可以將各個學(xué)院做出一張表，我們稱之為索引表，如圖10.1所示。118 圖10.1 索引表119多級索引也就是當(dāng)數(shù)據(jù)量相當(dāng)大時，一級索引也不夠用時，可以建立二級索引、三級索引，。如上例中查找某個學(xué)院的學(xué)生，可以按年級再建立一個索引表，如圖10.2所示（假設(shè)學(xué)號的設(shè)置規(guī)律為年級學(xué)院班級班內(nèi)編號，各占兩位）。120圖10.2 多級索引表12110.1.2 索引表查找表中含有18個紀(jì)錄，可分成三個子表(r0，r1，r2，r5)、(r6，r7，r8，r11)、(r12，r1

48、3，r14，r17)，對每個子表(或稱塊)建立一個索引項，其中包括兩項內(nèi)容：關(guān)鍵字項(其值為該子表內(nèi)的最大關(guān)鍵字)和指針項(指示該子表的第一個紀(jì)錄在表中位置)。 122索引表按關(guān)鍵字有序，則表或者有序或者分塊有序。所謂“分塊有序”指的是第二個子表中所有紀(jì)錄的關(guān)鍵字均大于第一個子表中的最大關(guān)鍵字，第三個子表中的所有關(guān)鍵字均大于第二個子表中的最大關(guān)鍵字，依次類推。123分塊查找過程需要分兩步進行: 先確定待查記錄所在的塊(子表)然后在塊中順序查找。 124由于索引項組成的索引表按關(guān)鍵字有序，則確定塊的查找可以用順序查找，可以用折半查找，而塊中紀(jì)錄是任意排列的，則在塊中只能是順序查找。因此，分塊查找

49、的算法即為這兩種查找算法的簡單合成。用折半查找確定所在塊，則分塊查找的平均長度為：12510.2 動態(tài)索引結(jié)構(gòu)（B_樹和B+樹）樹型索引技術(shù)適合于動態(tài)查找。第8章中的動態(tài)查找中用平衡二叉樹也可以完成作為磁盤文件的索引組織。但是，若以結(jié)點作為內(nèi)、外存交換的單位，則查找到需要的關(guān)鍵字之前，平均要對磁盤進行l(wèi)og2n次訪問，這樣浪費了很多的時間。1970年R.Bayer和E.Mc.Crerght提出了一種適用于外查找的樹，它幾乎是反有大型文件的訪問方法。它是一種平衡的多叉樹，其特點是插入、刪除時易于平衡，外部查找效率高，適合于組織磁盤文件的動態(tài)索引結(jié)構(gòu)，這就是我們將要討論的B_樹和B+樹。12610

50、.2.1 B_樹的定義一棵m階的B-樹，或為空樹，或為滿足下列條件的m叉樹： 樹中每個結(jié)點最多有m棵子樹； 除根結(jié)點和葉結(jié)點外，其它每個結(jié)點至少有 棵子樹； 根結(jié)點要么是一個葉結(jié)點，要么至少有兩棵子樹； 所有的葉結(jié)點在同一層上，葉結(jié)點不包含任何關(guān)鍵字信息，葉子結(jié)點的雙親結(jié)點稱為終端結(jié)點； 有K個孩子的非葉結(jié)點恰好包含K-1個關(guān)鍵字。 127在B_樹里，每個結(jié)點中關(guān)鍵字的個數(shù)為子樹的個數(shù)減1，結(jié)點中的關(guān)鍵字從小到大排列，由于葉結(jié)點不包含關(guān)鍵字，所以，可以把葉結(jié)點看成在樹中實際上并不存在的外部結(jié)點，指向這些外部結(jié)點的指針為空。葉結(jié)點的總數(shù)正好等于樹中所包含的關(guān)鍵字總個數(shù)加1。 67 34 20 5

51、4 80 95 98 81 87 93 75128 B_樹的所有非終端結(jié)點都包含n個關(guān)鍵字，n1個指針，一般形式為：其中，Ki(1in)是關(guān)鍵字，且滿足K1K2Kn，而Ai(1in)是指向子樹根結(jié)點的指針。Ai是指向包括在Ki和Ki+1之間的關(guān)鍵字的子樹，A0指向小于K1的關(guān)鍵字的子樹，An指向大于Kn的關(guān)鍵字的子樹。129B_樹涉及在實現(xiàn)基于磁盤的檢索樹結(jié)構(gòu)時遇到的所有問題。一般情況下，B_的葉子結(jié)點可以看作是外部結(jié)點或查找失敗的結(jié)點。實際上這些結(jié)點不存在，指向這些結(jié)點的指針都為空（這些葉子結(jié)點可以不用畫出）。B_樹的葉子出現(xiàn)在同一層上，它總是樹高平衡的。B_樹把相關(guān)的記錄（即與關(guān)鍵字值相似

52、的值）放在同一磁盤塊中，從而利用了訪問局部性原理。B_樹更新和檢索操作只影響一些磁盤塊。B_樹保證了樹中內(nèi)部結(jié)點的最小孩子數(shù)量，也保證了最少關(guān)鍵字?jǐn)?shù)量。那么在檢索和更新操作會減少需要的磁盤讀寫次數(shù)。 13010.2.2 B_樹的運算 查找查找關(guān)鍵字包括兩種基本操作，分別是：在B_樹中查找結(jié)點；在結(jié)點中查找關(guān)鍵字；因B_樹通常存儲在磁盤上，操作是在磁盤上進行的，操作是在內(nèi)存中進行的。131 B_樹的查找效率 在含有n個關(guān)鍵字的B-樹 上進行查找時，從根結(jié)點到關(guān)鍵字所在結(jié)點的路徑上，涉及的結(jié)點數(shù)不超過L層次數(shù)。即：這意味著若n1、999、998，m199，則L至多等于4，而一次查找最多進行L次存取

53、。 13210.2.2 B_樹的運算 插入 插入的關(guān)鍵字總是在終端結(jié)點中。共有二種情況：第一：插入新關(guān)鍵字，不改變B_的形態(tài)。若在一個包含jm-1個關(guān)鍵字的結(jié)點中插入一個新的關(guān)鍵字，則插入過程將局限于該結(jié)點，把新關(guān)鍵字直接插入該結(jié)點即可。 133第二：插入新關(guān)鍵字，改變B_樹。若把一個新的關(guān)鍵字插入一個已有m-1(m為B_樹的階)個關(guān)鍵字的結(jié)點，則將引起結(jié)點的分裂。134分裂結(jié)點注意： 如果雙親結(jié)點也是滿的，因下層分裂而提升上來一個關(guān)鍵字，則雙親結(jié)點也需要再分裂，方法同上段描述。最壞的情況是這個過程可能一直傳到根，而不能插入。由于根是沒有雙親的，若需要分裂根，就要建立一個新的根結(jié)點，則整個B_

54、樹增加了一層。13510.2.2 B_樹的運算 刪除 如果刪除的關(guān)鍵字不是終端結(jié)點，則先把此關(guān)鍵字與它在B_樹中的后繼關(guān)鍵字的位置對換，然后再刪除該關(guān)鍵字。 刪除關(guān)鍵字80，則先找到80的后繼關(guān)鍵字81，把80和81的位置對換，然后再刪除80 136如果刪除的關(guān)鍵字是終端結(jié)點中，則把它從所在的結(jié)點里去掉。 若因刪除這樣一個關(guān)鍵字，可能導(dǎo)致此結(jié)點所包含關(guān)鍵字的個數(shù)小于 1。這種情況下，應(yīng)該考察該結(jié)點的左或右兄弟結(jié)點，然后從兄弟結(jié)點中移若干個關(guān)鍵字到該結(jié)點中來，若兄弟結(jié)點里的關(guān)鍵字?jǐn)?shù)量夠多，那么將借來的關(guān)鍵字放到雙親結(jié)點中，并將雙親結(jié)點中相應(yīng)的關(guān)鍵字下移到被刪除的結(jié)點中，使兩個結(jié)點所含關(guān)鍵字的個數(shù)

55、基本相同；137若兄弟結(jié)點中的關(guān)鍵字?jǐn)?shù)量也不夠多，剛好等于1時，那么就將被刪除結(jié)點中的關(guān)鍵字取出并將其與兄弟結(jié)點合并，然后刪除這個空結(jié)點。因為刪除一個結(jié)點，其雙親少了一個孩子，所以要把雙親結(jié)點中的一個關(guān)鍵碼移到合并結(jié)點中。這種合并過程可能會傳到根結(jié)點，若根結(jié)點的兩個孩子合并，B_樹就會減少一層。 138圖10.8(a)所示的B_樹中刪除58的過程： 13910.2.3 B+樹一棵m階的B+樹有如下特征：(1)有m棵子樹的結(jié)點中含有m個關(guān)鍵字，即每個結(jié)點的關(guān)鍵字個數(shù)與孩子個數(shù)相同；(2)所有的葉子結(jié)點中包含了全部關(guān)鍵字的信息，及指向含這些關(guān)鍵字記錄的指針； (3)結(jié)點中的關(guān)鍵字Ki對應(yīng)子樹中的最

56、大關(guān)鍵字；(4) 葉子結(jié)點本身依關(guān)鍵字的大小自小而大順序鏈接，形成單鏈表。140例如圖10.9所示為一棵3階B+樹，通常在B+樹上有兩個頭指針，一個指向根結(jié)點，另一個指向關(guān)鍵字最小的葉子結(jié)點。因此，可以對B+樹進行兩種查找運算：一種是從最小關(guān)鍵字起順序查找；另一種是從根結(jié)點開始，進行隨機查找。141在B+樹上進行隨機查找、插入和刪除的過程基本上與B_樹類似。只是在查找時，若非終端結(jié)點上的關(guān)鍵字等于給定值，并不終止，而是繼續(xù)向下直到葉子結(jié)點 14210.3 鍵樹及Trie樹鍵樹：又稱數(shù)字搜索樹(Digital Search Trees)。它是一棵度2的樹，樹中的每個結(jié)點中不是包含一個或幾個關(guān)鍵字

57、，而是只含有組成關(guān)鍵字的符號。 例如，若關(guān)鍵字是數(shù)值，則結(jié)點中只包含一個數(shù)位；若關(guān)鍵字是單詞，則結(jié)點中只包含一個字母字符。這種樹會給某種類型關(guān)鍵字的表的查找?guī)矸奖恪?43假設(shè)有如下13個關(guān)鍵字組成的集合:a,and,are,be,but,by,for,from,had,have,he,her,here可對此集合作如下的逐層分割：圖10.10 鍵 樹144在鍵樹中,每一棵子樹代表具有相同前綴的關(guān)鍵字值的子集合 ，如圖10.11所示的子樹代表具有相同前綴“ha-”的關(guān)鍵字值的子集合 had,have。圖10.11 子樹及其代表的關(guān)鍵字值的子集合14510.3.2 雙鏈樹將森林和樹轉(zhuǎn)換成二叉樹的方

58、法將圖10.10的鍵樹轉(zhuǎn)換成二叉樹，然后采用二叉鏈表存儲之，這時向下是第一個孩子，向右是下一個兄弟。圖10.12 給出圖10.10 所示鍵樹的雙鏈樹的部分結(jié)構(gòu)。圖10.12 雙鏈樹示例146雙鏈樹的搜索可以這樣進行： 從雙鏈樹的根結(jié)點開始，將關(guān)鍵字（字符串）的第一個字符與該結(jié)點的字符比較，若相同，則沿孩子結(jié)點往下再比較下一個字符，否則沿兄弟結(jié)點順序搜索，直到某個結(jié)點的值等于待比較的字符，或者某個結(jié)點的字符大于待查字符，或者不再有兄弟為止，則搜索失敗。若比較在葉子結(jié)點處終止，則搜索成功，葉子結(jié)點包含指向該關(guān)鍵字值所標(biāo)識的元素的指針。147雙鏈樹的插入方法是：首先進行搜索，如插入關(guān)鍵字 age，搜

59、索在第二層的$與n字符間失敗。插入位置通常由三個指針指示：r、q 和 p 。本例中，我們將在 q 和 p 之間插入子樹g,e $, 如圖 10.13所示。 (a)插入前 (b) 插入后圖 10.13 雙鏈樹上插入子樹g,e $14810.3.3 Trie 樹若鍵樹以多重鏈表表示，則樹中每個結(jié)點含有 d 個指針域，d 是鍵樹的度，它與關(guān)鍵字值的“基”有關(guān)。 基就是每一位字符所有可取的值的數(shù)自，包括結(jié)束符。 此時的鍵樹又稱 Trie（retrieve 的中間四個字母）樹。 149Trie 樹上有兩類結(jié)點：分支結(jié)點和葉子結(jié)點。每個分支結(jié)點包含 d 個指針域和一個指示該結(jié)點非空指針域個數(shù)的整數(shù)。分支結(jié)

60、點不包括實際字符，它所代表的字符由其雙親結(jié)點中指向它的指針在該雙親結(jié)點中的位置隱含確定。葉子結(jié)點包括關(guān)鍵字域和指向元素的指針域。150Trie 樹上進行搜索的過程為：從根結(jié)點開始，沿著待查關(guān)鍵字值相應(yīng)的指針逐層往下比較，直到葉子結(jié)點。若該結(jié)點的關(guān)鍵字值等于待查值，則搜索成功，否則搜索失敗。 151在 Trie 樹插入和刪除操作：插入時，只需相應(yīng)地增加一些分支結(jié)點和葉子結(jié)點。刪除時，當(dāng)分支結(jié)點中的非空指針數(shù)為 1 時便可刪除。152雙鏈樹和 Trie 樹是鍵樹的兩種不同的表示法，它們各有特點。從其存儲結(jié)構(gòu)可見，若鍵樹中結(jié)點的度較大，則采用 Trie 樹為宜。綜上所述，搜索樹的搜索都是從根結(jié)點開始