《《算法與數(shù)據(jù)結(jié)構(gòu)》教學(xué)課件第6章 字典和高級字典C語言描述（第2版）張乃孝編著》由會員分享，可在線閱讀，更多相關(guān)《《算法與數(shù)據(jù)結(jié)構(gòu)》教學(xué)課件第6章 字典和高級字典C語言描述（第2版）張乃孝編著（96頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、6.1 集合及其抽象數(shù)據(jù)類型*6.2 集合的實現(xiàn)*6.3 字典及其抽象數(shù)據(jù)類型6.4 字典的順序表示6.5 字典的散列表示6.3 字典及其抽象數(shù)據(jù)類型6.3.1 基本概念 字典：是一種集合，其中每個元素由兩部分組成，分別稱為關(guān)鍵碼和屬性。這種包含關(guān)鍵碼和屬性得二元組稱作關(guān)聯(lián)。 對字典進(jìn)行的操作主要有：檢索、插入元素和刪除元素。字典中最主要的運算是進(jìn)行檢索。 靜態(tài)字典：一經(jīng)建立就基本保持不變； 動態(tài)字典：經(jīng)常需要改動。 存儲方法存儲方法：順序法、散列法、二叉樹法和B樹。 存儲方法的選擇：考慮檢索效率、元素的插入和刪除是否簡便。 檢索效率的標(biāo)準(zhǔn)檢索效率的標(biāo)準(zhǔn)：檢索過程中和關(guān)鍵碼的平均比較次數(shù)，即平

2、均檢索長度ASL，定義為： ASL = pici 每個元素的檢索概率相等時， pi=1/n。ni=16.3.2 抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型ADT6.2 字典的抽象數(shù)據(jù)類型字典的抽象數(shù)據(jù)類型ADT dictionary isoperation Dictionary createEmptyDictionary(void) int search(Dictionary dic,KeyType key,Position p) int insert(Dictionary dic,DicElement ele) int delete(Dictionary dic,KeyType key)end ADT dic

3、tionary字典的順序表示定義如下typedef int KeyType;typedef int DataType;typedef struct KeyType key; /* 字典元素的關(guān)鍵碼字段字典元素的關(guān)鍵碼字段*/DataType value; /* 字典元素的屬性字段字典元素的屬性字段*/DicElement;typedef struct int MAXNUM;int n; /*字典中元素的個數(shù)字典中元素的個數(shù) */ DicElement *element; SeqDictionary; 6.4.1 6.4.1 存儲結(jié)構(gòu)存儲結(jié)構(gòu)算法算法6.11 順序檢索算法順序檢索算法int se

4、qSearch(SeqDictionary *pdic, KeyType key, int &position) /*在字典中順序檢索關(guān)鍵碼為在字典中順序檢索關(guān)鍵碼為key的元素的元素*/int i; for(i=0; in; i+) /* 從頭開始向后掃描從頭開始向后掃描*/ if(pdic-elementi.key=key) position=i; return(1); /* 檢索成功檢索成功 */ position=pdic-n;return(0); /* 檢索失敗檢索失敗 */6.4.2 6.4.2 算法的實現(xiàn)算法的實現(xiàn)l算法算法6.11 6.11 順序檢索算法順序檢索算法ASL =

5、1*p1 +2* p2 + +n* pn = (1+2+n)/n (pi=1/n) = (n+1)/2=O(n) 優(yōu)點是算法簡單且適應(yīng)面廣，無論字典中元素是否有序均可使用。缺點是平均檢索長度較大，特別是當(dāng)n很大時，檢索效率較低。6.4.2 6.4.2 算法的實現(xiàn)算法的實現(xiàn)6.4.3 有序順序表與二分法檢索 按照關(guān)鍵碼大小排序的順序表稱為有序順序表。 二分法檢索又稱折半檢索。要求字典的元素在順序表中按關(guān)鍵碼排序（從小到大）。 05,10,18,25,27,32,41,51,68,73,99 05,10,18,25,27,32,41,51,68,73,99 05,10,18,25,27,32,41

6、,51,68,73,99檢索關(guān)鍵碼2505,10,18,25,27,32,41,51,68,73,9905,10,18,25,27,32,41,51,68,73,9905,10,18,25,27,32,41,51,68,73,9905,10,18,25,27,32,41,51,68,73,99檢索關(guān)鍵碼75l算法算法6.12 6.12 二分法檢索算法二分法檢索算法 條件：字典中的元素按關(guān)鍵碼排序。 優(yōu)點是比較次數(shù)少，檢索速度快。缺點是要將字典按關(guān)鍵碼排序，且只適用于順序存儲結(jié)構(gòu)。算法算法6.12二分法檢索算法二分法檢索算法int binarySearch(SeqDictionary * pdi

7、c, KeyType key, int &position) /* 在字典中用二分法查找關(guān)鍵碼為在字典中用二分法查找關(guān)鍵碼為key的元素的元素 */ int low, mid, high; low=0; high=pdic-n-1; while(lowelementmid.key=key) /* 檢索成功檢索成功 */ position=mid; return(1); else if(pdic-elementmid.keykey) high=mid-1; else low=mid+1; /* 要檢索的元素在右半?yún)^(qū)要檢索的元素在右半?yún)^(qū) */ position=low; return(0); /*

8、 檢索失敗檢索失敗 */折半查找的判定樹l用一棵二叉樹來描述折半用一棵二叉樹來描述折半查找過程：二叉樹結(jié)點中查找過程：二叉樹結(jié)點中的數(shù)值表示有序表記錄中的數(shù)值表示有序表記錄中的序號。的序號。虛黑線虛黑線表示查找表示查找2525比較過的記錄，比較過的記錄，虛紅線虛紅線表示查找表示查找7575經(jīng)過的記錄。經(jīng)過的記錄。記錄在判定樹上的層次恰記錄在判定樹上的層次恰為找到此記錄時所需比較為找到此記錄時所需比較的次數(shù)。的次數(shù)。l設(shè)每個記錄查找概率相等，設(shè)每個記錄查找概率相等，查找成功的平均查找長度：查找成功的平均查找長度：ASL（12233334+4+4+4)/11=33/11=3321868254173

9、515992710 05,10,18,25,27,32,41,51,68,73,996.5 6.5 字典的散列表示字典的散列表示 前面介紹的查找方法都是建立在前面介紹的查找方法都是建立在“比較比較”的基礎(chǔ)的基礎(chǔ)上，查找的效率依賴于查找過程中所進(jìn)行比較的次數(shù)。上，查找的效率依賴于查找過程中所進(jìn)行比較的次數(shù)。 理想的情況理想的情況是希望不進(jìn)行任何比較，一次存取便能得是希望不進(jìn)行任何比較，一次存取便能得到所查記錄。這樣就需要在關(guān)鍵碼和記錄的存儲位置到所查記錄。這樣就需要在關(guān)鍵碼和記錄的存儲位置之間建立一個確定的對應(yīng)關(guān)系之間建立一個確定的對應(yīng)關(guān)系. key 存儲地址存儲地址h 6.5.1 基本概念 6

10、.5.2 散列函數(shù) 6.5.3 碰撞的處理 6.5.4 散列文件散列函數(shù)散列函數(shù)： 使每個關(guān)鍵碼都和結(jié)構(gòu)中存儲位置對應(yīng)使每個關(guān)鍵碼都和結(jié)構(gòu)中存儲位置對應(yīng),這樣的一這樣的一個對應(yīng)關(guān)系稱為個對應(yīng)關(guān)系稱為散列（哈希散列（哈希Hash）函數(shù)）函數(shù)。 關(guān)鍵碼關(guān)鍵碼 存儲地址存儲地址碰撞碰撞：若：若key1 key2 ,h(key1)=h(key2). key1和和key2稱為稱為同義詞同義詞。h(key)的值域所對應(yīng)的的值域所對應(yīng)的地址空間稱為地址空間稱為基本區(qū)域基本區(qū)域。發(fā)生碰撞時，發(fā)生碰撞時，同義詞可以存放在同義詞可以存放在基本區(qū)域中未被占基本區(qū)域中未被占用的單元，也用的單元，也可以存放到另開的可以

11、存放到另開的區(qū)域中。區(qū)域中。負(fù)載因子負(fù)載因子： 散列表中結(jié)點數(shù)散列表中結(jié)點數(shù) 基本區(qū)域能容納的結(jié)點數(shù)基本區(qū)域能容納的結(jié)點數(shù)6.5.1 基本概念h = 關(guān)鍵碼關(guān)鍵碼經(jīng)過經(jīng)過散列函數(shù)散列函數(shù)得到一個隨機地址，得到一個隨機地址，以便使一組關(guān)鍵碼的散列地址均勻地分布在以便使一組關(guān)鍵碼的散列地址均勻地分布在逐個地址區(qū)間中，從而減少沖突。逐個地址區(qū)間中，從而減少沖突。 常用的散列函數(shù)有：常用的散列函數(shù)有：1 1 數(shù)字分析法數(shù)字分析法2 2 折疊法折疊法 3. 3. 中平方法中平方法 4. 4. 基數(shù)轉(zhuǎn)換法基數(shù)轉(zhuǎn)換法 5. 5. 除余法除余法6.5.2 散列函數(shù)1. 數(shù)字分析法數(shù)字分析法 假設(shè)關(guān)鍵碼是以假設(shè)

12、關(guān)鍵碼是以r為基的數(shù)，并且哈希表中可為基的數(shù)，并且哈希表中可能現(xiàn)的關(guān)鍵碼都是事先知道的，則可取關(guān)鍵碼的能現(xiàn)的關(guān)鍵碼都是事先知道的，則可取關(guān)鍵碼的若干數(shù)位組成散列地址。若干數(shù)位組成散列地址。 Key h(key) 000319426 326 000718309 709 000629443 643 000758615 715 000919697 997 000310329 3292. 折疊法折疊法 將關(guān)鍵碼分割成幾部分，然后取這幾部分的疊加和將關(guān)鍵碼分割成幾部分，然后取這幾部分的疊加和作為地址。作為地址。 key=582422241 58 | 2422 | 241 58 | 2422 | 241

13、8 5 5 8 1 4 2 2 4 1 2 4 2 2 2 4 2 2 1 1 0 6 4 2 7 2 13. 中平方法中平方法 先求出關(guān)鍵碼的平方，然后取中間幾位作為地址。先求出關(guān)鍵碼的平方，然后取中間幾位作為地址。 key=4731 (4731)2 = 22382361 h(key)=3824. 基數(shù)轉(zhuǎn)換法基數(shù)轉(zhuǎn)換法 把關(guān)鍵碼看成基數(shù)為把關(guān)鍵碼看成基數(shù)為r1的數(shù)，將它轉(zhuǎn)換成基數(shù)為的數(shù)，將它轉(zhuǎn)換成基數(shù)為r2的數(shù)，用數(shù)字分析法取中間幾位作為散列地址。的數(shù)，用數(shù)字分析法取中間幾位作為散列地址。r1和和r2最好互素。例如，最好互素。例如，key=236075, r1=13, r2=10, (236

14、075)13=2*135+3*134+6*133+7*13+5 =(841547)10 h(key)=41545. 除余法除余法 取關(guān)鍵碼被某個不大于散列表長度取關(guān)鍵碼被某個不大于散列表長度m的數(shù)的數(shù)p除后所得余數(shù)為散列地址。數(shù)除后所得余數(shù)為散列地址。數(shù)p的選?。阂话愕倪x取：一般可選它為質(zhì)數(shù)。可選它為質(zhì)數(shù)。 h(key)=key % p; m=128, 256, 512, 1024 p=127, 251, 503, 1019實際工作中需視情況的不同而采用不同的散列函實際工作中需視情況的不同而采用不同的散列函數(shù)，通常需要考慮的因素有：數(shù)，通常需要考慮的因素有： A. 計算哈希函數(shù)所需時間計算哈希

15、函數(shù)所需時間; B. 關(guān)鍵碼的長度關(guān)鍵碼的長度; C. 哈希表的大小哈希表的大小; D. 關(guān)鍵碼的分布情況關(guān)鍵碼的分布情況; E. 記錄的查找頻率。記錄的查找頻率?？傊?，是總之，是“雜湊雜湊”出來的。出來的。 開地址法開地址法在在基本區(qū)域基本區(qū)域內(nèi)形成一個內(nèi)形成一個探查序列探查序列 Hi = (H(key) + di)MOD m, i = 1, 2, , k ( k m-1)其中：其中：m為表長，為表長，di為增量序列，可有多種取法：為增量序列，可有多種取法： A. di = 1, 2, 3, , m-1, 稱稱線性探查序列線性探查序列; B. di = i*h2(key), h2(key)是

16、另一個是另一個散列函數(shù)，稱散列函數(shù)，稱 雙散列探查序列雙散列探查序列; C. di = 12, -12, 22, -22, , k2, -k2 (k m/2)稱為稱為二次探查序列二次探查序列； D. di = 偽隨機數(shù)序列，稱偽隨機數(shù)序列，稱偽隨機探查序列偽隨機探查序列。 當(dāng)發(fā)生碰撞時，則沿探查序列進(jìn)行查找，當(dāng)發(fā)生碰撞時，則沿探查序列進(jìn)行查找， 插插入時，直到找到一個空單元；查找時，或查找到入時，直到找到一個空單元；查找時，或查找到關(guān)健碼為關(guān)健碼為key的元素或查找到達(dá)一個空單元。例如：的元素或查找到達(dá)一個空單元。例如： K=18, 73, 10, 05, 68, 99, 27, 41, 51

17、, 32, 25 5, 8, 10, 5, 3, 8, 1, 2, 12, 6, 12 h(key)=key%13; 地址 0 1 2 3 4 5 6 7 8 9 10 11 12 關(guān)鍵碼 1873100568992741513225 采用采用線性探測序列線性探測序列，容易出現(xiàn)，容易出現(xiàn)堆積堆積現(xiàn)象，即在處現(xiàn)象，即在處理同義詞的過程中又添加了非同義詞的沖突。理同義詞的過程中又添加了非同義詞的沖突。存儲結(jié)構(gòu)存儲結(jié)構(gòu)typedef int KeyTypetypedef int DataType;typedef struct KeyType key; DataType value;DicElemen

18、t;typedef struct int m; DicElement *element;HashDictionary;typedef HashDictionary *PHashDictionary;（教材缺）（教材缺）算法算法6.13 6.13 創(chuàng)建空散列表創(chuàng)建空散列表PHashDictionary createEmptyDictionary(intPHashDictionary createEmptyDictionary(int m) m) PHashDictionary phd PHashDictionary phd = = new HashDictionarynew HashDictio

19、nary; ; if (phd if (phd!=NULL)!=NULL) phd phd-element = -element = new DicElementmnew DicElementm; if(phd if(phd-element)-element) phd phd-m = m;-m = m; for( for(intint i=0; im; i+) i=0; ielementi phd-elementi.key.key = 0; = 0; return phd return phd; ; else else deletedelete phd phd; ; cout“Out of s

20、pace!”endl cout“Out of space!”endl; ; return NULL; return NULL; 在散列表上進(jìn)行查找和構(gòu)造散列表的過程基本一在散列表上進(jìn)行查找和構(gòu)造散列表的過程基本一致。給定致。給定key值，根據(jù)散列函數(shù)求得散列地址，若表值，根據(jù)散列函數(shù)求得散列地址，若表中沒有記錄，則查找不成功；否則比較關(guān)鍵碼，若中沒有記錄，則查找不成功；否則比較關(guān)鍵碼，若和給定值相等，則查找成功；否則根據(jù)造表時設(shè)定和給定值相等，則查找成功；否則根據(jù)造表時設(shè)定的沖突處理方法找的沖突處理方法找“下一地址下一地址”，直到散列表某個，直到散列表某個位置為空或表中所填記錄的關(guān)鍵碼等于給定

21、值時為位置為空或表中所填記錄的關(guān)鍵碼等于給定值時為止。止。 算法算法6.14 散列表的檢索散列表的檢索算法算法6.15 散列表的插入散列表的插入散列表的查找散列表的查找算法算法6.14 散列表的檢索算法散列表的檢索算法用線性探查法解決碰撞用線性探查法解決碰撞int linearSearch(HashDictionary *phash, KeyType key, int *position) int d, inc; d=h(key);/* d為散列地址，散列函數(shù)為為散列地址，散列函數(shù)為h(key) */ for(inc=0; incm; inc+) if(phash-elementd.key=k

22、ey) *position=d; return(1); /* 檢索成功檢索成功 */ else if(phash-elementd.key=0) *position=d; return(0); /檢索失敗，找到插入位置檢索失敗，找到插入位置 d=(d+1)%phash-m; *position = -1;/* 散列表溢出散列表溢出 */ return(0);算法算法6.15 散列表的插入算法散列表的插入算法用線性探查法解決碰撞用線性探查法解決碰撞int linearInsert(HashDictionary *phash, DicElement ele) int position; if(li

23、nearSearch(phash, ele.key, &position) = 1 ) /* 散列表中已有關(guān)鍵碼為散列表中已有關(guān)鍵碼為key 的結(jié)點的結(jié)點 */ printf(“Findn”); else if(position!=-1) phash-elementposition = ele; /* 插入結(jié)點，忽略對插入結(jié)點，忽略對value字段的賦值字段的賦值 */ else return(0); /* 散列表溢出散列表溢出 */ return(1); K=18, 73, 10, 05, 68, 99, 27, 41, 51, 32, 25 5, 8, 10, 5, 3, 8, 1, 2,

24、 12, 6, 12 h1(key)=key%13; h2(key)=key%11+1；187310 05689927 415132 25h1(25)=25%13=12;h1(25)+h2(25)=25%13+(25%11+1)=12+4=16;h1(25)+2*h2(25)=25%13+2*(25%11+1)=12+8=20;雙散列函數(shù)法雙散列函數(shù)法 拉鏈法拉鏈法 設(shè)設(shè)基本區(qū)域基本區(qū)域長度為長度為m，建立，建立m條條鏈表，將所有關(guān)鏈表，將所有關(guān)鍵字為同義詞的記錄存儲在同一鍵字為同義詞的記錄存儲在同一條條線性鏈表中。線性鏈表中。 K=18, 73, 10, 05, 68, 99, 27, 41

25、, 51, 32, 25 5, 8, 10, 5, 3, 8, 1, 2, 12, 6, 12 h(key)=key%13; ，27，41，68， ，18，05, 32， ，73， 99， ，10， ，51，25 27 41 68 18 5 32 73 99 10 51 25 圖6.4 用拉鏈法解決碰撞 在外存上，同義詞表可以采用順序表或散列表。在外存上，同義詞表可以采用順序表或散列表。有時把存放同義詞的表稱為有時把存放同義詞的表稱為“桶桶”。 按按“桶桶”散列的文件由若干桶和一個桶目錄構(gòu)散列的文件由若干桶和一個桶目錄構(gòu)成成。6.5.4 散列文件 桶目錄桶：由若干頁塊組成每個頁塊存放若干記錄l

26、作業(yè)：p. 198l復(fù)習(xí)題 2，3，4l算法題 3，4l網(wǎng)絡(luò)課堂測試: 6 集合與字典 l上機實驗5.2 5.3 5.67.3 7.3 二叉排序樹二叉排序樹7.4 7.4 最佳二叉排序樹最佳二叉排序樹* *7.5 7.5 平衡二叉排序樹平衡二叉排序樹 字典采用二叉排序樹作為存儲結(jié)構(gòu)，既有較高的檢索效率，又具有鏈?zhǔn)酱鎯r元素插入、刪除操作的靈活性。 二叉排序樹二叉排序樹定義定義 二叉排序樹(Binary Sort Tree)或者是一棵空二叉樹；或者具有下列性質(zhì)的二叉樹： A. 若它的左子樹不空，則左子樹上所有結(jié)點的 值均小于它的根結(jié)點的值； B. 若它的右子樹不空，則右子樹上所有結(jié)點 的值均大于

27、它的根結(jié)點的值； C. 它的左右子樹也分別為二叉排序樹。實際上，折半查找法的判定樹就是一棵二叉排序樹。K= 18, 73, 10, 05, 68, 99, 27, 41, 51, 32, 251810739968272541325105圖7.5 二叉排序樹示例struct BinSearchNodestruct BinSearchNode; ;typedef struct BinSearchNode typedef struct BinSearchNode * *PBinSearchNodePBinSearchNode; ; struct BinSearchNode struct BinSea

28、rchNode KeyTypeKeyType key; key;/ /* * 結(jié)點的關(guān)鍵碼字段結(jié)點的關(guān)鍵碼字段 * */ / PBinSearchNode llink, rlinkPBinSearchNode llink, rlink; ; / /* * 二叉樹的左、右指針二叉樹的左、右指針 * */ / ; ; typedef struct BinSearchNode typedef struct BinSearchNode * *BinSearchTreeBinSearchTree; ;typedef BinSearchTree typedef BinSearchTree * *PBinS

29、earchTreePBinSearchTree; ;二叉排序樹的存儲結(jié)構(gòu)（llink_rlink)： L.keyT.keykey) 查左子樹；查左子樹； else 查右子樹；查右子樹； 算法7.1 二叉排序樹的檢索算法 TLR算法算法7.1 7.1 二叉排序樹的檢索算法二叉排序樹的檢索算法int search(PBinSearchTree ptree, KeyTypeint search(PBinSearchTree ptree, KeyType key, key, PBinSearchNode PBinSearchNode * *position)position) PBinSearchNo

30、de PBinSearchNode p, q; p, q; p= p=* *ptreeptree; q=p; q=p; while(p while(p!=NULL) !=NULL) q=p; q=p; if(p-key=key if(p-key=key) ) * *position=p; return(1); position=p; return(1); else if(p-keykey) p=p-llink else if(p-keykey) p=p-llink; ; else p=p-rlink else p=p-rlink; ; * *position=q; return(0);posi

31、tion=q; return(0); 當(dāng)樹中不存在關(guān)鍵字等于給定值的結(jié)點時，需要生成新結(jié)點并插入到二叉樹中。而新插入的結(jié)點必定是一個葉子結(jié)點，并且是查找不成功時查找路徑上訪問的最后一個結(jié)點的左孩子或右孩子結(jié)點。 算法： if ( 二叉排序樹中查不到該結(jié)點) 建立新結(jié)點； if (原二叉排序樹是空樹) 新結(jié)點作為根結(jié)點; else if (新結(jié)點key=key; p-llink=p-rlink=NULL; if(position=NULL) *ptree=p; else if(keykey) position-llink=p; /插入的左子樹插入的左子樹else position-rlink=p

32、; /* 插入插入position的右子樹的右子樹 */ return 1; 若從空樹出發(fā)，經(jīng)過一系列插入操作后，可生成一棵二叉排序樹。 例如，K=18, 73, 10, 05, 68, 99, 27, 41, 51, 32, 251873100568992741513225圖7.7 二叉排序樹 的生成過程示例 容易看出，中序遍歷可以得到一個關(guān)鍵字的有序序列，這就是說，一個無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個有序序列。 另外可以看到，每次插入的新結(jié)點都是樹中一個葉子結(jié)點，因此在進(jìn)行插入的時候不必移動其他結(jié)點，僅需改動某個結(jié)點的指針。由此可見： 二叉排序樹既有折半查找的特性，又采用了鏈表

33、作存儲結(jié)構(gòu)。因此是動態(tài)查找表的適宜結(jié)構(gòu)。刪除二叉排序樹的某個指定結(jié)點后，仍然是二叉排序樹。假設(shè)指針p指向要刪除的結(jié)點, 指針parentp指向*p的父結(jié)點。 1. 若*p是葉子結(jié)點，由于刪除葉子結(jié)點不破壞整棵樹的結(jié)構(gòu)，因此，只需要修改其雙親結(jié)點的指針。 2. 若*p只有左子樹PL或只有右子樹PR，此時，只要令PL或PR的根結(jié)點直接代替*p即可.PR*p*parentpPl*p*parentp*parent *p PR*parent Pl *p二叉排序樹結(jié)點的刪除二叉排序樹結(jié)點的刪除3. 若*p的左右子樹均不空，則從下圖可知,在刪除 *p 之前，中序遍歷該二叉樹得到的序列為L *p R 刪除*p

34、之后，為保持其它元素之間的相對位置不 變，可以有兩種做法。rrLRr*pLRr第一種方法：令*p的左子樹的根結(jié)點代替*p ，而*p的右子樹為 的右子樹; 在p的左子樹中找出關(guān)鍵碼最大的結(jié)點r，將r的右指針指向p的右子女，用p的左子女代替p結(jié)點。4518731059927415132257.8 刪除結(jié)點73的過程p為被刪除的結(jié)點r為p的左子樹中關(guān)鍵碼最大的的結(jié)點 在p的左子樹中找出關(guān)鍵碼最大的結(jié)點r，將r的右指針指向p的右子女，用p的左子女代替p結(jié)點。4518731059927415132257.8 刪除結(jié)點73的過程p為被刪除的結(jié)點r為p的左子樹中關(guān)鍵碼最大的的結(jié)點 在p的左子樹中找出關(guān)鍵碼最

35、大的結(jié)點r，將r的右指針指向p的右子女，用p的左子女代替p結(jié)點。181057.8 刪除結(jié)點73的過程p為被刪除的結(jié)點45992741513225r為p的左子樹中關(guān)鍵碼最大的的結(jié)點第二種方法： （a）按對稱序周游p的左子樹，找到關(guān)鍵碼最大的 結(jié)點r，刪除r（用r的左子女代替r）； （b）用r結(jié)點代替被刪除結(jié)點p。LRr*pLRrL r *p RL r R 刪除r（用r的左子女代替r），用r結(jié)點代替被刪除結(jié)點p 。4518731059927415132257.8 刪除結(jié)點73的過程p為被刪除的結(jié)點r為p的左子樹中關(guān)鍵碼最大的的結(jié)點 刪除r（用r的左子女代替r），用r結(jié)點代替被刪除結(jié)點p 。4518

36、5110599274132257.8 刪除結(jié)點73的過程p為被刪除的結(jié)點r為p的左子樹中關(guān)鍵碼最大的的結(jié)點 查找被刪除結(jié)點*p； if(*p無左子女) 用*p的右子女代替*p； else 找*p的左子樹中最右下結(jié)點*r； 用*r的右指針指向*p的右子女； 用*p的左子女代替*p； 算法 7.4 從二叉排序樹上刪除一個結(jié)點算法算法7.4 7.4 二叉排序樹的刪除算法二叉排序樹的刪除算法int delete(PBinSearch ptree, KeyTypeint delete(PBinSearch ptree, KeyType key) key) PBinSearchNode parentp P

37、BinSearchNode parentp, p, r;, p, r; p= p=* *ptree; parentpptree; parentp=NULL;=NULL; while(p while(p!=NULL) !=NULL) if(p-key=key if(p-key=key) break; ) break; / /* * 找到了關(guān)鍵碼為找到了關(guān)鍵碼為keykey的結(jié)點的結(jié)點 * */ / parentp parentp=p;=p; if(p-keykey)p=p-llink if(p-keykey)p=p-llink; ; / /* *進(jìn)入左子樹進(jìn)入左子樹 * */ / else p=

38、p-rlink else p=p-rlink; ; / /* *進(jìn)入右子樹進(jìn)入右子樹 * */ / if(p if(p=NULL) return 0;=NULL) return 0; / /* * 二叉排序樹中無關(guān)鍵碼為二叉排序樹中無關(guān)鍵碼為keykey的結(jié)點的結(jié)點 * */ /if(p-llinkif(p-llink=NULL) =NULL) / /* *結(jié)點結(jié)點* *p p無左子樹無左子樹* */ / if(parentp=NULL) if(parentp=NULL) * *ptree=p-rlinkptree=p-rlink; ; / /* *被刪除的結(jié)點是原二叉排序樹的根結(jié)點被刪除的結(jié)

39、點是原二叉排序樹的根結(jié)點* */ / else if(parentp-llink=p) parentp-llink=p-rlink else if(parentp-llink=p) parentp-llink=p-rlink; ; / /* * 將將* *p p的右子樹鏈到其父結(jié)點的左鏈上的右子樹鏈到其父結(jié)點的左鏈上 * */ / else parentp-rlink=p-rlink else parentp-rlink=p-rlink; ; / /* * 將將* *p p的右子樹鏈到其父結(jié)點的右鏈上的右子樹鏈到其父結(jié)點的右鏈上 * */ / else else / /* *結(jié)點結(jié)點* *p

40、p有左子樹有左子樹* */ / r=p-llink r=p-llink; ; while(r-rlink!=NULL) r=r-rlink while(r-rlink!=NULL) r=r-rlink; ; / /* * 在在* *p p的左子樹中找最右下結(jié)點的左子樹中找最右下結(jié)點* *r r * */ / r-rlink=p-rlink r-rlink=p-rlink; ;/ /* * 用用* *r r的右指針指向的右指針指向* *p p的右子女的右子女 * */ / if(parentp=NULL) if(parentp=NULL) * *ptree=p-llinkptree=p-llin

41、k; ; else if(parentp-llink=p)parentp-llink=p-llink else if(parentp-llink=p)parentp-llink=p-llink; ; else parentp-rlink=p-llink else parentp-rlink=p-llink; ; free(p free(p););return 1; return 1; / /* * 釋放被刪除結(jié)點釋放被刪除結(jié)點 * */ / 性能分析 在二叉排序樹上查找關(guān)鍵字實際上是走了一條從根結(jié)點到某個結(jié)點的路徑的過程，比較的次數(shù)等于路徑長度加1。因此，比較的次數(shù)不超過樹的深度+1。但是具有

42、n個結(jié)點的二叉樹可以有不同的形態(tài)，因此，對于不同形態(tài)的二叉排序樹，其平均查找長度也是不同的。最壞的情況下蛻變?yōu)閱沃洌藭r的平均查找長度為（n+1)/2。 在隨機的情況下，平均性能為：P(n) = 2(1+1/n) ln n 由此可見，在隨機情況下的平均查找長度和ln n是等數(shù)量級的，然而在某些情況下，還需進(jìn)行“平衡化”處理。 n個結(jié)點按不同的次序插入到二叉排序樹中，有n!棵二叉排序樹(其中有的形態(tài)相同) 。271005734151991825051018252741517399圖7.9 由同一組關(guān)鍵碼構(gòu)成的兩棵形態(tài)不同的二叉排序樹7.4 7.4 最佳二叉排序樹最佳二叉排序樹* *平衡二叉樹定

43、義 平衡二叉樹又稱AVL樹。它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：它的左右子樹均為平衡二叉樹，且左右子樹的深度之差的絕對值不超過1。 若定義二叉樹上結(jié)點的平衡因子BF(Balance Factor)為該結(jié)點的右子樹的高度減去左子樹的高度，在平衡二叉樹上所有結(jié)點平衡因子只可能為-1, 0, 1。只要二叉樹上有一個結(jié)點的平衡因子的絕對值大于1，則該二叉樹就是不平衡的。 對于平衡二叉樹來說，它的深度和logN是同數(shù)量級的，因此我們希望任何初始序列構(gòu)成的二叉排序樹都是AVL樹。 -1-1-110001-1-200-1圖7.14 平衡和不平衡二叉樹示例最小不平衡子樹: 指離插入結(jié)點最近，且以平衡

44、因子絕對值大于1的結(jié)點為根的子樹。27105118412500-1-112圖 6.13 最小不平衡子樹插入結(jié)點7.5.2 7.5.2 調(diào)整平衡的模式調(diào)整平衡的模式 設(shè)最小不平衡子樹的根為A，調(diào)整的規(guī)律可歸納為下列四種： 1. LL型調(diào)整； 2. RR型調(diào)整； 3. LR型調(diào)整； 4. RL型調(diào)整； 上面的幾種情況在經(jīng)過平衡旋轉(zhuǎn)處理后，以*b或*c為根的新子樹為平衡二叉樹，而且它的深度和插入之前以*a為根的子樹相同。因此，當(dāng)平衡的二叉排序樹因插入結(jié)點而失去平衡時，僅需對最小不平衡子樹進(jìn)行旋轉(zhuǎn)處理即可。 A A B B B A h h h+1 h h h h h h -1 0 -2 1 0 0 L

45、L型調(diào)整操作示意圖 (B)A()= ()B(A) 調(diào)整規(guī)則是將A的左子女B提升為新二叉樹的根；原來的根A連同其右子樹向右下旋轉(zhuǎn)成為B的右子樹；B的原右子樹作為A的左子樹。 27100-1BA27100-1BA05-2271000BA05051270-1BA100051800030-1-1-251270BA10005180030-10圖6.15 LL型調(diào)整操作示例 A A B B B A h h h+1 h h h h h h 1 0 0 0 2 1 RR型調(diào)整操作示意圖 ()A(B)= (A)B() 調(diào)整規(guī)則：將A的右子女B提升為新二叉樹的根；原來的根A連同其左子樹向左下旋轉(zhuǎn)成為B的左子樹；B

46、的原左子樹作為A的右子樹。 275101BA275101BA732735100BA27051270 1BA1007341099730BA510274101000-1圖6.17 RR型調(diào)整操作示例0990 1 12 A A C B B B A h h C C h h h h h-1 h h-1 h-1 h h-1 -1 -2 0 1 0 1 0 0 -1 LR型調(diào)整操作示意圖 ()B(C)A()= (B)C(A) 調(diào)整規(guī)則設(shè)C為A的左子女的右子女，將A的孫子結(jié)點C提升為新二叉樹的根；原C的父結(jié)點B連同其左子樹向左下旋轉(zhuǎn)成為新根C的左子樹，原C的左子樹成為B的右子樹；原根A連同其右子樹向右下旋轉(zhuǎn)成

47、為新根C的右子樹，原C的右子樹成為A的左子樹。 51270-1BA100051800C51270CA180101600500 1B圖6.19 LR型調(diào)整操作示例5127 1BA10005180-1C160-2 A A C B B A B h h C C h h h h h-1 h h-1 h-1 h h-1 0 1 0 0 -1 0 1 2 RL型調(diào)整操作示意圖 ()A(C)B()= (A)C(B) 調(diào)整規(guī)則：設(shè)C為A的右子女的左子女，將A的孫子結(jié)點C提升為新二叉樹的根，原來C的父結(jié)點B連同其右子樹向右下旋轉(zhuǎn)成為新根C的右子樹，C的原右子樹成為B的左子樹；原來的根A連同其左子樹向左下旋轉(zhuǎn)成為新

48、根C的左子樹，原來C的左子樹成為A的右子樹。 51270 1BA1007341073510CA410B273001000 1圖6.21 RL型調(diào)整操作示例000C51270 1BA1007341-103000-1 2C 設(shè) 在平衡二叉樹上插入一個關(guān)鍵碼為key的結(jié)點,二叉樹采用llink_rlink表示，結(jié)點中增加一個字段存儲結(jié)點的平衡因子。算法中包括以下幾個部分：6.5.2 6.5.2 插入元素的算法插入元素的算法（1）找最小不平衡子樹。找插入位置時，令*A離插入位置最近，且平衡因子不為0的結(jié)點，若這樣的結(jié)點不存在，則A指向根結(jié)點；若插入后使AVL樹失去平衡，則*A是最小不平衡子樹的根。（2

49、）修改一些結(jié)點的平衡因子 路徑： *A， ，新結(jié)點。插入前，僅*A的平衡因子不為0。插入后，從*A的子女開始，順序掃描路徑上的結(jié)點*P,若新結(jié)點插入*P的左子樹中，則*P平衡因子變?yōu)?；否則變?yōu)?1。 (3)判別以*A為根的子樹是否失去了平衡。 若*A的平衡因子為0，則插入后不會； 若*A的平衡因子為1，且插入到*A的左子樹，則失去平衡，進(jìn)一步，若插入到*A的左子女的左子樹，則采用LL型調(diào)整；若插入到*A的左子女的右子樹，則采用LR型調(diào)整; 若*A的平衡因子為-1, 且插入到*A的右子樹,則失去平衡，進(jìn)一步,若插入到*A的右子女的右子樹,則采用RR型調(diào)整;若插入到*A的右子女的左子樹,則采用R

50、L型調(diào)整;算法算法6.10 AVL樹的檢索和插入性能分析 含有n個結(jié)點的平衡二叉樹的高度是h= O(log2n)。插入關(guān)鍵碼為key的結(jié)點的時間耗費最大為樹的深度O(log2n)。算法在查找插入結(jié)點的同時也找到最小不平衡子樹。最小不平衡子樹中平衡因子的調(diào)整時間最大為最小不平衡子樹的深度。而四種子樹調(diào)整時間耗費為常數(shù)O( 1 ).因此， 整個算法的時間復(fù)雜度為 O(log2n). 最佳二叉排序樹的檢索效率是最好的，但是，當(dāng)進(jìn)行結(jié)點的插入或刪除操作后，保持其最佳性的時間代價太大。平衡二叉排序樹的檢索效率與最佳二叉排序樹的檢索效率是同級的，因此，動態(tài)字典常采用平衡二叉排序樹作為存儲結(jié)構(gòu)。 B樹和B樹

51、用于外存文件的索引。 6.6.1 B樹 6.6.2 B+樹一、B樹的定義 一棵m階的B樹，或為空樹，或是滿足下列特性的m叉樹： （1）樹中每個結(jié)點至多有m棵子樹； （2） 除根之外的所有分支結(jié)點至少有m/2棵子樹； （3）若根結(jié)點不是葉子結(jié)點，則至少有兩棵子樹； （4） 有j個子女的非葉結(jié)點中恰好有j-1個關(guān)鍵碼， 且 按遞增順 序排列，結(jié)點中包含的信息為 (p0, k1, p1, k2, , kj-1, pj)6.6 .1 B6.6 .1 B樹樹 其中ki(i=1,.,j-1)為關(guān)鍵碼，且ki ki+1(i=1,j-2); pi(i=0,j-1)為指向子樹根結(jié)點的指針，且pi-1所指子樹中所

52、有結(jié)點的關(guān)鍵碼均小于ki(i=1,j-1), pj-1所指子樹中所有結(jié)點的關(guān)鍵碼均大于kj, j（ m/2 = j = m-1）為關(guān)鍵碼的個數(shù)。 （ 5）所有葉子結(jié)點都在同一層上，實際上這些 結(jié)點不存在。 當(dāng)m=2時，m階B樹實際上就是二叉排序樹。所以m階B樹是二叉排序樹的推廣。其查找過程和二叉排序樹類似，它是一個沿指針查找結(jié)點和在結(jié)點的關(guān)鍵碼中進(jìn)行順序查找交叉進(jìn)行的過程。 實際應(yīng)用中， m和內(nèi)外存交換的單位有關(guān)，一般，m=1024 040008375045 112 236392 490 560 631 670110050212142135279240237388381378471435400

53、396393553502492629626557660652633678673671圖6.22 一棵6階的B樹B樹主要用于文件的索引 。結(jié)點類型可以如下說明：#define m3typedef struct BTNode int keyNum; /* 關(guān)鍵字個數(shù) */ struct BTNode *parent; /* 指向父結(jié)點*/ KeyType keym+1; /* 關(guān)鍵字向量 */ struct BTNode *ptrm+1; /* 子樹指針向量 */ Record *recPtrm+1; /* 指向文件中的記錄號 */ BTNode, *BTree;二. B樹的運算 1. B樹的檢索

54、 key ki ki+1 pi 首先在根結(jié)點的關(guān)鍵碼集合中進(jìn)行檢索，若key= = ki ，則檢索成功；否則， key一定在ki 和 ki+1 之間（存在某個i），沿pi繼續(xù)查找，重復(fù)上述過程，直到檢索成功，或pi為空，檢索失敗。性能分析 在B樹是進(jìn)行查找包含兩種基本操作：（1）在B樹中找結(jié)點；（2）在結(jié)點中找關(guān)鍵字。由于B樹通常存儲在磁盤上，因此前一操作是在磁盤上進(jìn)行的，而后一操作是在內(nèi)存中進(jìn)行的，即在磁盤上找到指針p所指結(jié)點后，先將結(jié)點中信息讀入內(nèi)存，然后查詢。而在磁盤上進(jìn)行操作比在內(nèi)存中操作慢得多，因此在磁盤上進(jìn)行查找的次數(shù)，即待查關(guān)鍵字所在結(jié)點在B樹是的層次數(shù)，是決定B樹查找效率的關(guān)鍵

55、因素。 現(xiàn)在考慮最壞的情況：含n個關(guān)鍵字的m階B樹的最大深度為log m/2(n+1)/2 + 12. B樹的插入 深度為h的m階B樹，新結(jié)點一般插入到h層，首先檢索到第h層，確定插入結(jié)點位置。 （1）若被插入結(jié)點中關(guān)鍵碼個數(shù)小于m-1，則插入。 （2）若被插入結(jié)點中關(guān)鍵碼個數(shù)等于m-1，則引起 結(jié)點“分裂”。 可如下實現(xiàn)“分裂”： 假設(shè)*p結(jié)點中含有信息為：m,p0, (k1,p1), , (km, pm)將*p分裂為*p和*p兩個結(jié)點，分別含有信息為： *p ： m/21, p0, (k1,p1), (k m/21,pm/21) *p：(m- m/2, pm/2, (k m/2+1, p

56、m/2+1), (km, pm)把關(guān)鍵字k m/2和指針*p一起插入到*p的雙親結(jié)點中。 375 400 045 112 236 375 400 560 631 670040 008110 050212 142135297 240237388 381378471 460435396 393553 502492629 626557圖6.23 一棵6階B樹的插入示例3. B樹的刪除 在深度為h的m階B樹中刪除一個關(guān)鍵碼，首先檢索到該關(guān)鍵碼所在的結(jié)點,然后根據(jù)不同情況進(jìn)行刪除。（1)若結(jié)點在第h層，且關(guān)鍵碼數(shù)目大于m/2-1， 則只需從該結(jié)點中刪去該關(guān)鍵碼ki。（2）若結(jié)點在第h層，且關(guān)鍵碼數(shù)目等于

57、m/2-1， 該結(jié)點左兄弟（或右兄弟）結(jié)點中的關(guān)鍵碼數(shù)目 大于m/21，則需調(diào)整被刪除關(guān)鍵碼的結(jié)點， 兄弟結(jié)點，以及父結(jié)點中的信息。方法：設(shè)父結(jié) 點 中的信息為：（p0, k1,p1,k2,p2,kxpx),由pi指向 被刪除關(guān)鍵碼的結(jié)點，其的信息為： （p 0, k 1,p 1,k 2,p 2,k y p y), 兄弟結(jié)點中的 信息為：（p 0, k 1 ,p 1 ,k 2 ,p 2 ,k z p z)。 則應(yīng)將k(x+y)/2上移到父結(jié)點中，并將左（或右） 兄第中大于（或小于） k(x+y)/2及父結(jié)點中的ki移 到被刪除關(guān)鍵碼的結(jié)點中。 (3) 若結(jié)點在h層，且關(guān)鍵碼數(shù)目及其相鄰的兄弟結(jié)

58、 點中的關(guān)鍵碼數(shù)目均等于m/21，則需合并結(jié) 點。假設(shè)該結(jié)點有右兄弟，且其右兄弟結(jié)點由雙 親結(jié)點中的指針pi所指，則在刪去關(guān)鍵碼之后， 它所在結(jié)點中剩余的關(guān)鍵碼和指針，加上雙親結(jié) 點中的關(guān)鍵碼ki一起，合并到pi所指兄弟結(jié)點中 （若沒有右兄弟結(jié)點，則合并到左兄弟結(jié)點中）。(4) 若結(jié)點的層數(shù)小于h，設(shè)刪除結(jié)點中第i個關(guān)鍵碼 ki ，則用pi所指的子樹中的最小關(guān)鍵碼k與ki互換，然后再刪除關(guān)鍵碼ki 。 50 63 20 35 23 30 66 90 56 42 3 7 3035 （a) 一棵三階B樹 圖6.24 (b) 從（a)中刪除關(guān)鍵碼66 （c) 從(b)中刪除關(guān)鍵碼42 50 63 2

59、0 3023 90 56 35 3 7 （d) 從 ( c ) 中刪除關(guān)鍵碼35圖6.24 (e) 從（d)中刪除關(guān)鍵碼56 23 30 56 20 50 3 7 23 30 63 90 50 63 20 3023 90 56 35 3 7 （d) 從 ( c ) 中刪除關(guān)鍵碼35圖6.24 (e) 從（d)中刪除關(guān)鍵碼56 23 30 56三. B樹在索引文件中的應(yīng)用 (B, ) (E, ) (C, ) (D, ) (F, ) (G, ) (A, ) 圖6.25 用B樹組織索引順序文件B+樹是B樹的變形。一. B+樹的定義： 一棵m階的B樹，或為空樹，或是滿足下列條件的m叉樹： （1）樹中每

60、個結(jié)點至多有m棵子樹； （2） 除根之外的所有分支結(jié)點至少有m/2棵子樹； （3）若根結(jié)點不是葉子結(jié)點，則至少有兩棵子樹； （4） 有n棵子樹的結(jié)點有n個關(guān)鍵碼； （5）葉結(jié)點中存放數(shù)據(jù)文件中記錄的關(guān)鍵碼及指向該記錄的指針（或存放數(shù)據(jù)文件分塊后每塊的最大關(guān)鍵碼及指向該塊的指針。葉結(jié)點按關(guān)鍵碼值大小順 序 鏈接。可以把每個葉結(jié)點看成一個基本索引塊。 6.6 .2 B+6.6 .2 B+樹樹 (6) 所有分支結(jié)點可看成是索引的索引，使結(jié)點中僅包含它的各子結(jié)點中最大（或最?。╆P(guān)鍵碼及指向子結(jié)點的指針。一棵m階的B樹和B樹的差異在于： （A）有n棵子樹的結(jié)點中含有n個關(guān)鍵碼； （B）所有的葉子結(jié)點中包

61、含了全部關(guān)鍵碼的信息，及指向含這些關(guān)鍵碼記錄的指針，且葉子結(jié)點的本身依關(guān)鍵碼的大小從小到大順序鏈接。 （C）所有的非終端結(jié)點可以看成是索引部分，結(jié)點中僅含有其子樹（根結(jié)點）中最大（或最?。╆P(guān)鍵碼。 通常在B樹上有兩個頭指針，一個指向根結(jié)點，另一個指向關(guān)鍵碼最小的葉子結(jié)點。 60 99 85 99 20 39 60 27 36 39 92 99 65 79 85 46 51 60 10 20圖6.26 一棵三階的B+樹 二. B+樹的運算 1. B+樹的檢索 (1) 和B樹的檢索方式相似。從根結(jié)點開始進(jìn)行隨 機檢索， key一定在ki 和 ki+1 之間（存在個i）， 沿pi繼續(xù)查找，重復(fù)上述過

62、程，直到檢索到葉 結(jié)點，若key = = ki ，則檢索成功；否則檢索 失敗。 （2） 從最小關(guān)鍵碼開始沿葉結(jié)點鏈順序檢索。 2 . B+樹的插入 和B樹的插入相似，但總是在葉結(jié)點上進(jìn)行，當(dāng) 結(jié)點中原關(guān)鍵碼個數(shù)等于m時，該結(jié)點分裂。 (3) B+樹的刪除 僅在葉結(jié)點中進(jìn)行刪除操作，在和兄第結(jié)點合并 時，父結(jié)點中作為分界的關(guān)鍵碼不放入合并后的結(jié) 點中。三. B+樹在索引順序文件中的應(yīng)用 主文件的每個頁塊作B+樹的一個外部結(jié)點，并且 這些頁塊之間連成單鏈。 B+樹的樹葉層是主文件的 稀疏索引，整個B+樹構(gòu)成多級索引。索引項就是B+ 樹中一個關(guān)鍵碼和它對應(yīng)的指針?biāo)鶚?gòu)成的二元組。 A D D E A

63、B C 圖6.27 用B+樹組織索引順序文件1. 靜態(tài)字典（1）順序表示 A. 順序檢索：簡單，常用于未排序元素的檢索， 但檢索效率不高； B. 二分法檢索：僅用于排序元素，檢索效率較高當(dāng)插入、刪除運算時會引起大量數(shù)據(jù)的移動。（2）散列表示：檢索操作達(dá)到近乎隨機存取的速度 。但散列表示經(jīng)常出現(xiàn)碰撞與堆積現(xiàn)象，增加 了檢索長度。（3）二叉樹表示二叉排序樹：元素插入次序不同，會構(gòu)成不同的二叉排序樹。最佳二叉排序樹 的平均檢索長度為O(log2n) 。2. 動態(tài)字典 平衡二叉排序樹表示：維持較高的檢索效率。3. 對于較大的必須存放在外存貯器上的字典，應(yīng) 采用B樹或B+樹表示。B+樹是B樹的變種。B樹

64、 和B+樹都能動態(tài)地調(diào)整，保持均衡，而使動態(tài) 字典保持較高的檢索效率。小小 結(jié)結(jié) 字典是一種特殊的集合，其最主要的操作為字典中元素的檢索。本章介紹了字典的各種存儲表示及相應(yīng)的檢索方法，它們是字典的各種線性表示（例如：順序表表示，鏈表表示和目錄表表示等）、各種散列表示（例如：開地址法、拉鏈法和桶散列等）、各種二叉樹表示（例如：一般的二叉排序樹、最佳二叉排序樹和平衡的二叉排序樹等）以及各種多叉樹表示（例如B樹和B+樹）。其中順序表示的線性表、開地址法處理碰撞的散列表和最佳二叉排序樹主要使用于靜態(tài)或基本靜態(tài)的字典；鏈表表示的線性表、拉鏈法處理碰撞的散列表、桶散列結(jié)構(gòu)、平衡的二叉排序樹、B樹和B+樹等較多地考慮到元素的動態(tài)處理，適合于組織各種動態(tài)的字典；其中B樹、B+樹和桶散列結(jié)構(gòu)主要使用于外存的大型字典表示。 l作業(yè)：p.243 復(fù)習(xí)題 1、7、8 p.244 算法題 1l網(wǎng)絡(luò)課堂測試：6 字典與高級字典l上機：實驗5.4