1、基本內容基本內容： 集合集合 字典的基本概念字典的基本概念 順序表檢索順序表檢索 順序檢索順序檢索 二分法檢索二分法檢索 分塊檢索分塊檢索 散列表檢索散列表檢索 樹表檢索樹表檢索 二叉樹表示二叉樹表示 AVL樹表示樹表示 B樹表示樹表示重點：各種檢索方法的思想、算法、時間效率度量重點：各種檢索方法的思想、算法、時間效率度量1. 基本概念：集合、成員、空集、有序集基本概念：集合、成員、空集、有序集2. 主要運算：并、交、差、子集、相等主要運算：并、交、差、子集、相等3. 集合的實現：順序（位向量），鏈接（單鏈表）集合的實現：順序（位向量），鏈接（單鏈表）元素是否存在的位向量：元素是否存在的位向量

2、：0/1（不存在（不存在/存在）存在）typedef structint size; /字符數組長度字符數組長度char *array; /位向量空間，位向量空間， /一個字節表達一個字節表達8個元素個元素 BitSet 6.1 集合集合0101001d1d2d3didn-2dn-1dn公共超集集合中是否存在對應元素？元素個數與字符數組長度的關系：元素個數與字符數組長度的關系：size = (n+7)/8每個字符每個字符8位，最后一個字符可能不滿。位，最后一個字符可能不滿。給定成員位置給定成員位置idx，確定在那個字符中：，確定在那個字符中：which_char = idx 3;/即：即：id

3、x/8確定哪一位：確定哪一位：which_bit = idx & 07;/即：即：idx%8 (后三位后三位)765432109821010101010arraysizeS=1,3,5,7,9創建空集合：創建空集合：BitSet *CreateEmptySet(int n)BitSet *s = (BitSet *)malloc(sizeof(BitSet);if (!s) return NULL;s-size = (n+7)/8;s-array = (char *)malloc(s-size);memset(s-array, 0, s-size);return s;插入運算：插入運算

4、：int Insert(BitSet *s, int idx)if (idx = 0 & (idx 3 size)s-arrayidx 3 |= (1 = 0 & (idx 3 size)s-arrayidx 3 &= (1 = 0 & (idx 3 size)return (s-arrayidx 3 & (1 size != s1-size | s2-size != s1-size) return 0;for (i = 0; i size; i+)s2-arrayi = s0-arrayi | s1-arrayi; return 1;011000100

5、111001101010001000010010111001101111011S1S0S1S0S2集合交：集合交：通過對應位通過對應位“與與”運算完成運算完成int Intersection(BitSet *s0, BitSet *s1, BitSet *s2)int i;if (s0-size != s1-size | s2-size != s1-size) return 0;for (i = 0; i size; i+)s2-arrayi = s0-arrayi & s1-arrayi; return 1;01100010011100110101000100001001010000

6、0000000001S0S1S0S1S2集合差：在第一個集合中，同時不在第二個集合中集合差：在第一個集合中，同時不在第二個集合中 第一個集合與第二個集合的逆做第一個集合與第二個集合的逆做“與與”運算運算int Difference(BitSet *s0, BitSet *s1, BitSet *s2)int i;if (s0-size != s1-size | s2-size != s1-size) return 0;for (i = 0; i size; i+)s2-arrayi = s0-arrayi & (s1-arrayi); return 1;1001110110001100

7、010100010000100100010001000010000110001001110011S1S1S0S0S1S2單鏈表：有序單鏈表，各個結點存放成員本身。單鏈表：有序單鏈表，各個結點存放成員本身。struct NodeDataType info;struct Node *link;typedef struct Node *PNode;基本運算實現基本運算實現：p177180 注意兩個有序單鏈表運算如何實現集合運算。注意兩個有序單鏈表運算如何實現集合運算。1. 字典的組成：字典的組成： 關鍵碼關鍵碼+屬性屬性2. 字典與索引字典與索引:6.2 字典的基本概念字典的基本概念key1key2

8、key3keyikeyn-2keyn-1keynd1d2d3didn-2dn-1dn目錄表字典字典相關的運算（排序、檢索等），直接在字典的目錄表（索引）下進行，不用關心字典本身。3. 檢索檢索： 按照關鍵碼進行按照關鍵碼進行 給定一個值給定一個值key, 按照某種次序在字典中進行檢索按照某種次序在字典中進行檢索（與關鍵碼進行比較），如果找到則檢索成功，（與關鍵碼進行比較），如果找到則檢索成功， 否則失敗。否則失敗。4. 存儲結構存儲結構：靜態、動態：靜態、動態 靜態：一旦建立，不再修改，只有檢索運算靜態：一旦建立，不再修改，只有檢索運算 動態：除檢索外，字典經常變化（插入、刪除）動態：除檢索外

9、，字典經常變化（插入、刪除）5. 衡量檢索算法的標準衡量檢索算法的標準 平均查找長度平均查找長度 pi為查找第為查找第i個元素的概率，個元素的概率， ci為查找第為查找第i個元素的比較次數個元素的比較次數 如不特別聲明為等概率查找，如不特別聲明為等概率查找，pi=1/n6. 檢索中的基本運算檢索中的基本運算： 關鍵碼與給定值的比較關鍵碼與給定值的比較7. 字典（索引）的表示字典（索引）的表示：順序表，散列表順序表，散列表，樹表樹表niiicpASL1靜態字典動態字典順序檢索、二分法檢索、分塊檢索順序檢索、二分法檢索、分塊檢索1. 順序表的表示順序表的表示typedef struct /* 元素

10、結構元素結構 */ KeyType key; /* 元素的關鍵碼元素的關鍵碼 */DataType other; /* 其它屬性字段其它屬性字段 */ DicElement;typedef struct /* 字典結構字典結構 */ DicElement elementMAXNUM; /* 字典數組字典數組 */ int n; /* 實際元素個數實際元素個數 */ SeqDictionary;6.3 順序表檢索順序表檢索KeyType: intDataType: int2. 順序檢索順序檢索（1）思想）思想：從字典一端開始順序掃描，將字典元素的：從字典一端開始順序掃描，將字典元素的關鍵碼與給定

11、值進行比較。如果相等，則檢索成功；當關鍵碼與給定值進行比較。如果相等，則檢索成功；當全部元素皆比較完，到達了字典的另一端，則檢索失敗。全部元素皆比較完，到達了字典的另一端，則檢索失敗。（2）算法）算法：int SeqSearch( SeqDictionary *pdic, KeyType key, int *pos) int i; for ( i = 0; i n; i+) /* 從頭開始從頭開始 */ if (pdic-elementi.key = key) /* 成功成功 */ *pos = i;return TRUE; *pos = i; return FALSE; /* 失敗失敗 */

12、(3) 時間效率分析時間效率分析 從算法可以看出：從算法可以看出：c1 = 1, c2 = 2, , ci = i , (找到第找到第i個元素），個元素）， 因此，查找成功因此，查找成功 如果等概率查找，則如果等概率查找，則pi = 1/n, ASL=(1+2+i+n)/n=(n+1)/2 查找失敗的比較次數：查找失敗的比較次數： n次次 時間復雜度為：時間復雜度為：O(n)niipiLA1.S(4) 不等概率情況下的改進：不等概率情況下的改進： 在不等概率情況下，當在不等概率情況下，當P1 P2 Pn時，時，ASL最小。最小。 因此，在不等概率時，因此，在不等概率時，應該保持概率最大的元素在

13、最應該保持概率最大的元素在最前面，概率最小的元素在最后面前面，概率最小的元素在最后面。 通常，無法預先知道各個元素的查找概率，解決的辦通常，無法預先知道各個元素的查找概率，解決的辦法是為用檢索成功次數代替查找概率，當檢索元素法是為用檢索成功次數代替查找概率，當檢索元素成功時，其檢索成功次數加成功時，其檢索成功次數加1，保持檢索成功次數最，保持檢索成功次數最大的元素在前面，檢索成功次數最小的元素在最后大的元素在前面，檢索成功次數最小的元素在最后面。面。RsCmaxCmin(5) 順序檢索的優缺點順序檢索的優缺點： 優點優點：算法簡單，適應面廣，對字典結構無要求，：算法簡單，適應面廣，對字典結構無

14、要求，無論是否按關鍵碼有序，適用于順序表和鏈表。無論是否按關鍵碼有序，適用于順序表和鏈表。 缺點缺點：ASL長，長，O(n)數量級，大約一半元素個數數量級，大約一半元素個數 的比較次數。的比較次數。3. 二分法檢索（折半檢索）二分法檢索（折半檢索）（1）思想）思想： 當字典按關鍵碼有序時，將字典元素按關鍵碼從小當字典按關鍵碼有序時，將字典元素按關鍵碼從小到大保存在數組中。到大保存在數組中。 首先給定值首先給定值key與字典的中間位置元素進行比較，如與字典的中間位置元素進行比較，如果相等，則檢索成功；否則根據果相等，則檢索成功；否則根據key與中間位置元素的與中間位置元素的關鍵碼的比較確定在左邊

15、進行繼續查找，還是在右邊關鍵碼的比較確定在左邊進行繼續查找，還是在右邊繼續查找。如繼續查找。如key小，則在左邊繼續進行二分法檢索，小，則在左邊繼續進行二分法檢索，否則，在右邊繼續二分法檢索。否則，在右邊繼續二分法檢索。 從上面可以看出，折半檢索的實質是從上面可以看出，折半檢索的實質是逐步縮小查找逐步縮小查找區間區間的檢索方法。的檢索方法。 例如給定值例如給定值key = 25和和78的檢索：的檢索： 0 1 2 3 4 5 6 7 8 9 100 1 2 3 4 5 6 7 8 9 10 05 05， 1010， 1818， 2525， 2727， 3232， 4141， 5151， 686

16、8， 7373， 9999 05 05， 1010， 1818， 2525， 27 4127 41， 5151， 6868， 7373， 9999 25 25， 27 7327 73， 9999 99 99成功成功失敗失敗需要指定搜索區間。對于順序表：低界，高界（2） 算法算法int BinSearch( SeqDictionary *pdic, KeyType key, int *pos) int low, mid, high; low = 0; high = pdic-n-1; /* 初始搜索區間初始搜索區間 */ while (low elementmid.key) /* 查找成功查找成

17、功 */ *pos = mid; return TRUE; else if (key elementmid.key) high = mid-1; /* 左邊區間繼續左邊區間繼續 */ else low = mid+1; /* 右邊區間繼續右邊區間繼續 */ *pos = low; return FALSE; /* 查找失敗查找失敗 */（3） 時間效率分析時間效率分析每比較一次縮小一半的查找區間。為了分析折半檢索的性能，每比較一次縮小一半的查找區間。為了分析折半檢索的性能，可以用二叉樹來描述折半檢索的過程。當前檢索區間中間記可以用二叉樹來描述折半檢索的過程。當前檢索區間中間記錄作為根，左半區間

18、和右半區間中的記錄分別為根的左子樹錄作為根，左半區間和右半區間中的記錄分別為根的左子樹和右子樹，這樣得到的二叉樹稱為和右子樹，這樣得到的二叉樹稱為折半檢索二叉樹折半檢索二叉樹。樹中結點數字表示結點在有序表中的位置。樹中結點數字表示結點在有序表中的位置。 536092810714右圖為右圖為11個記錄的折半檢索二叉樹。如個記錄的折半檢索二叉樹。如要檢索第要檢索第6個記錄，則只需要一次比較；個記錄，則只需要一次比較；檢索第檢索第3、9個記錄需要個記錄需要2次比較；檢索第次比較；檢索第1、4、7、10個記錄需要個記錄需要3次比較；檢索次比較；檢索第第2、5、8、11個記錄需要個記錄需要4次比較。次比

19、較。536092810714由此可見，由此可見，折半檢索的過程恰好是在折半檢索的過程恰好是在判定樹中走了一條從根到檢索結點的判定樹中走了一條從根到檢索結點的路徑，比較的關鍵碼個數恰為該結點路徑，比較的關鍵碼個數恰為該結點在二叉樹中的層數。因此，成功折半在二叉樹中的層數。因此，成功折半檢索關鍵碼比較次數不會超過樹的深檢索關鍵碼比較次數不會超過樹的深度度：那么，折半檢索的那么，折半檢索的ASL等于多少？等于多少？) 1(log2n假定記錄數假定記錄數n=2h-1， 即即h=log2(n+1)，則描述折半檢索的判定樹，則描述折半檢索的判定樹是一棵深度為是一棵深度為h的的全滿二叉樹全滿二叉樹。在該全滿

20、二叉判定樹中，有：。在該全滿二叉判定樹中，有： 第第1層的結點個數為層的結點個數為20， 比較比較1次；次； 第第2層的結點個數為層的結點個數為21， 比較比較2次；次； 第第k層的結點個數為層的結點個數為2k-1，比較，比較k次；次； 第第h層的結點個數為層的結點個數為2h-1，比較，比較h次；次；等概率檢索下，檢索成功時的等概率檢索下，檢索成功時的當當n很大時，如很大時，如n100，則得到，則得到: ASLlog2(n+1)-1nnnnkncpASLhkkhkkk11)1(log1212111由此可見，折半檢索的效率要高于順序檢索。如由此可見，折半檢索的效率要高于順序檢索。如n=1000，

21、順序，順序ASL=500，而折半，而折半ASL9。（4）優缺點）優缺點 優點優點：檢索效率高，：檢索效率高， ASLlog2(n+1)-1缺點缺點：只適用于數據元素很少變動的：只適用于數據元素很少變動的有序順序有序順序 表表，應用范圍有限制。，應用范圍有限制。每行中：列按照經度有序每列中：行按照緯度有序經度數組緯度數組問題描述問題描述： 地球觀測網格點m行m列，網格點經緯度位置分別存儲在經度數組和緯度數組中。對于經度數組，各行按照列經度有序；對于緯度數組，各列按照行緯度有序。算法設計算法設計： 給定一個經緯度值（lon, lat），檢索最近網格點的行列坐標。 void geo2grid(flo

22、at lon, float lat, int *gx, int *gy);-雙折半實現，速度較順序檢索，大大提高。 順序：m2/2, 雙折半：(log2(m+1)-1)2, 分區雙折半：(log2(m/2+1)-1)2。 如：m = 2000, ASL 【2000000, 100, 82(81+1)】經度數組(每行中：經度有序)MidYTopBottomLeftRightMidXvoid geo2grid(float lon, float lat, int *gx, int *gy) int top = 0, bottom = rows-1, midy; int left, right, mi

23、dx; while (top = bottom) /緯度控制的行折半檢索 midy = (top+bottom)/2; /中間行 left = 0, right = cols-1; /在中間行中折半經度檢索 while (left = right) midx = (left+right)/2; /中間列 if (lon = lonsmidymidx) break; /找到列 else if (lon lonsmidymidx) right = midx-1; else left = midx+1; if (lat = latsmidymidx) break; /成功 else if (lat

24、latsmidymidx) bottom = midy-1; else top = midy+1; *ix = midx; *iy = midy; /近似解近似解進一步改進: (lon,lat)先與中心點經緯度進行比較，確定在那個1/4區域，再在該區域內雙折半檢索。4. 分塊檢索分塊檢索(Blocking Search)（1）數據元素排列）數據元素排列 又稱索引順序檢索，是介于順序、折半之間的檢又稱索引順序檢索，是介于順序、折半之間的檢索方法。索方法。 分塊檢索要求所有的記錄分成若干塊，并且塊間分塊檢索要求所有的記錄分成若干塊，并且塊間按關鍵碼有序，而塊內不一定有序。即：第一塊中按關鍵碼有序，

25、而塊內不一定有序。即：第一塊中所有記錄的關鍵碼均不超過第二塊中任意記錄的關所有記錄的關鍵碼均不超過第二塊中任意記錄的關鍵碼，而第二塊中所有記錄的關鍵碼均不超過第三鍵碼，而第二塊中所有記錄的關鍵碼均不超過第三塊中任意記錄的關鍵碼，塊中任意記錄的關鍵碼，塊內記錄可以任意，塊內記錄可以任意排列。排列。 這樣，可以建立一個這樣，可以建立一個塊索引表塊索引表，存儲每塊的最大，存儲每塊的最大關鍵碼值以及該塊第一個元素在字典中的位置。關鍵碼值以及該塊第一個元素在字典中的位置。塊索引表數據元素結構：字典：(27, 13, 8, 9, 12, 5, 6, 35, 43, 38, 47, 59 ,58, 79,

26、82, 52)最大關鍵碼值第一個記錄的位置2704778211塊索引表塊索引表最小關鍵碼值最后一個記錄的位置5635105215（2）檢索思想）檢索思想 給定值給定值key, 首先在塊索引表中進行檢索確定下一步首先在塊索引表中進行檢索確定下一步要檢索的塊，然后到確定的塊中進行檢索。由于塊索要檢索的塊，然后到確定的塊中進行檢索。由于塊索引表按關鍵碼有序，因此塊間檢索可以采用折半檢索，引表按關鍵碼有序，因此塊間檢索可以采用折半檢索，也可以采用順序檢索。但由于塊內記錄無序，任意排也可以采用順序檢索。但由于塊內記錄無序，任意排列，只能采用順序檢索。列，只能采用順序檢索。 由此可以看出，分塊檢索有兩步組

27、成：由此可以看出，分塊檢索有兩步組成：塊間檢索和塊間檢索和塊內檢索塊內檢索。 如上例中檢索如上例中檢索key=38，首先在塊索引表中檢索發現，首先在塊索引表中檢索發現在第二塊，然后在第二塊中順序檢索，得到記錄是第在第二塊，然后在第二塊中順序檢索，得到記錄是第二塊的第三個記錄（總的字典位置為二塊的第三個記錄（總的字典位置為7+2)。 又如又如key=15，有塊索引表得到如果記錄存在，必定，有塊索引表得到如果記錄存在，必定在第一塊。在第一塊中順序檢索失敗，因此字典中不在第一塊。在第一塊中順序檢索失敗，因此字典中不存在這樣的記錄，分塊檢索失敗。存在這樣的記錄，分塊檢索失敗。（3）檢索算法）檢索算法

28、索引表結構索引表結構 typedef struct KeyType maxkey; /* 塊中最大關鍵字塊中最大關鍵字 */ int pos_1rec; /* 塊的第一個元素的位置塊的第一個元素的位置 */ IndexNode; typedef struct IndexNode idx_blockMAXNUM; /* 塊索引表塊索引表 */ int num_block; /* 實際塊數實際塊數 */ *Pindex; int BlockSearch(SeqDictionary *pdic, Pindex idx, KeyType key, int *pos) int i=0, j, last_

29、j; /在塊索引表中確定塊在塊索引表中確定塊 while (inum_block & key idx-idx_blocki.maxkey) i+; if (i idx-num_block) *pos = -1; /塊間檢索失敗塊間檢索失敗 else /塊內順序檢索，確定檢索范圍塊內順序檢索，確定檢索范圍 j = idx-idx_blocki.pos_1rec; /起始記錄起始記錄 if (i = idx-num_block) last_j = pdic-n-1; /終止記錄終止記錄 else last_j = idx-idx_blocki+1.pos_1rec-1; while (j

30、elementj.key) j+; if ( j last_j)*pos = -1; /塊內檢索失敗塊內檢索失敗 else *pos = j; /檢索成功檢索成功 /檢索成功或失敗檢索成功或失敗 if (*pos -1) return TRUE; else return FALSE;（4）檢索效率）檢索效率 ASLbs = Lb+Lw 其中，其中，Lb為塊間檢索的為塊間檢索的ASL，Lw為塊內檢索的為塊內檢索的ASL假定總共有假定總共有n個記錄，分成個記錄，分成b塊，每塊含有塊，每塊含有s個記錄，即個記錄，即s=n/b。假定塊間檢索為等概率：假定塊間檢索為等概率：1/b，塊內檢索仍然等概率：，

31、塊內檢索仍然等概率：1/s。根據。根據塊間檢索方法不同，塊間檢索方法不同，ASL計算不同。計算不同。 塊間順序檢索塊間順序檢索 Lb = (b+1)/2 Lw = (s+1)/2 ASL=(b+s)/2+1 = (n/s+s)/2+1由此可見，由此可見，ASL不僅與不僅與n有關，而且與每塊記錄數目有關，而且與每塊記錄數目s有有關。對上式關。對上式ASL求導，可以得到求導，可以得到當當 時，時，ASL取最取最小值小值 。 如：如：n=1000時，時， ，ASL 32 順序檢索：順序檢索： ASL 500 折半檢索：折半檢索： ASL 9 因此，因此，分塊檢索介于順序、折半檢索之間分塊檢索介于順序

32、、折半檢索之間。 塊間折半檢索塊間折半檢索 ASL = log2(n/s+1)-1+(s+1)/2 log2(n/s+1)+s/2ns 1n31ns開始掃描角度開始掃描角度終止掃描角度終止掃描角度Nint find_bin(float azim) int si, ei, mi; if (azim = a0) si = 0; ei = i_max; else si = i_min, ei = n-1; while (si = ei) mi = (si+ei)/2; if (azim = ami) return mi; else if (azim 1時，碰撞不可避免時，碰撞不可避免。由此可以看出，

33、散列表的構造和檢索中，需要解決的主要問題由此可以看出，散列表的構造和檢索中，需要解決的主要問題有：有：（1）如何選擇合適的散列函數構造散列表？）如何選擇合適的散列函數構造散列表？（2）碰撞發生時如何處理？）碰撞發生時如何處理？（3）散列表如何檢索？檢索效率如何？檢索效率與那些因素）散列表如何檢索？檢索效率如何？檢索效率與那些因素有關？有關？數基本區域能容納的結點散列表中結點數目2. 散列函數的選擇散列函數的選擇散列函數的選擇在散列表的構造和檢索中是非常重要的，合適散列函數的選擇在散列表的構造和檢索中是非常重要的，合適的散列函數可以減少碰撞的發生，提高檢索效率。的散列函數可以減少碰撞的發生，提高

34、檢索效率。散列函數的選擇標準散列函數的選擇標準： 字典中的關鍵碼均勻分布在散列地址空間中，減少碰撞的字典中的關鍵碼均勻分布在散列地址空間中，減少碰撞的 發生；發生； 散列函數盡可能簡單，提高計算速度。散列函數盡可能簡單，提高計算速度。常用的散列函數常用的散列函數：（1）直接定址法）直接定址法 h(key) = a*key+b適用于關鍵碼分布基本連續情況。若關鍵碼分布不連續，適用于關鍵碼分布基本連續情況。若關鍵碼分布不連續，容易造成空單元，存儲空間浪費。容易造成空單元，存儲空間浪費。（2）除留余數法）除留余數法 h(key) = key%pp的選擇非常重要，通常選擇小于等于散列表長度的選擇非常重

35、要，通常選擇小于等于散列表長度m的某個的某個最大素數。最大素數。如：如：m = 600，則，則p可以選擇為可以選擇為599。除留余數法計算簡單，許多情況下效果較好，是一種常用除留余數法計算簡單，許多情況下效果較好，是一種常用的散列函數。的散列函數。（3）數字分析法）數字分析法對關鍵碼的數字位進行分析，然后用其中的某些較分散的對關鍵碼的數字位進行分析，然后用其中的某些較分散的數字位構成散列函數。數字位構成散列函數。通常用于已知記錄關鍵碼，并且關鍵碼各位分布已經知道通常用于已知記錄關鍵碼，并且關鍵碼各位分布已經知道的情況。的情況。例如：例如：(395003, 395010, 395012, 395

36、085, 395097)中，前四位中，前四位相同，后兩位隨機分布，故可以取后兩位構成散列函數，相同，后兩位隨機分布，故可以取后兩位構成散列函數，得到的散列地址為（得到的散列地址為（03，10，12，85，97）（4）折疊法）折疊法如果關鍵碼的位數多于地址位數，且各位分布均勻，此時如果關鍵碼的位數多于地址位數，且各位分布均勻，此時可以將關鍵碼分成若干塊，塊長度不超過地址位數。各塊可以將關鍵碼分成若干塊，塊長度不超過地址位數。各塊相加，舍棄進位，最后的和作為散列地址。相加，舍棄進位，最后的和作為散列地址。 如：如：key = 0582422241，地址位數為，地址位數為4。 2241 224122

37、41 2241 8242 2428 8242 2428 +) 05 +) 05 +) 05 +) 05 10488 4672 10488 4672移動疊加移動疊加 間界疊加間界疊加（5）平方取中法）平方取中法先求出關鍵碼的平方，然后取中間若干位構成散列函數。先求出關鍵碼的平方，然后取中間若干位構成散列函數。例如：例如：key = 4731，key2 = 22382361，如地址碼為，如地址碼為3位，則可位，則可以取以取382為散列地址，即為散列地址，即h(4731) = 382（6）基數轉換法）基數轉換法將關鍵碼首先看作是另一進制的表示，然后再轉換為原來的將關鍵碼首先看作是另一進制的表示，然后

38、再轉換為原來的進制數，用數字分析法取若干位作為散列地址。一般轉換基進制數，用數字分析法取若干位作為散列地址。一般轉換基數大于原基數，且最好二者互素。數大于原基數，且最好二者互素。例如：例如： key = (236075)10, 把它看作把它看作13進制數進制數(236075)13,再轉再轉換為換為10進制，地址位數為進制，地址位數為4： (236075)13 = 2*135+3*134+6*133+7*131+5 = (841547)10 選擇選擇25，得到散列地址，得到散列地址h(236075) = 4154 上面為常用的散列函數選擇，實際情況應該根據問題的要求上面為常用的散列函數選擇，實際

39、情況應該根據問題的要求選擇適合散列表構造和檢索的散列函數。選擇適合散列表構造和檢索的散列函數。 從上面的散列函數選擇可以看出，無論選擇何種散列函數，從上面的散列函數選擇可以看出，無論選擇何種散列函數，碰撞都可能發生。換句話講，合適的散列函數可以減少碰撞發碰撞都可能發生。換句話講，合適的散列函數可以減少碰撞發生的幾率，但不能保證不發生碰撞。生的幾率，但不能保證不發生碰撞。碰撞發生時如何處理？碰撞發生時如何處理？3. 碰撞的處理（開放地址法，拉鏈法）碰撞的處理（開放地址法，拉鏈法）(1) 開放地址法開放地址法（基本區域內解決基本區域內解決) ) 假定散列表地址空間為假定散列表地址空間為0，m-1，

40、碰撞指的是由關鍵碼得，碰撞指的是由關鍵碼得到的散列地址為到的散列地址為j(0jm-1)的位置上已經存在記錄，則處理的位置上已經存在記錄，則處理碰撞就是為該關鍵碼找到一個空的散列地址。找到該空的碰撞就是為該關鍵碼找到一個空的散列地址。找到該空的散列地址可能需要經過一個地址序列散列地址可能需要經過一個地址序列Hi(i=0,1,2,k)，即在，即在處理碰撞時，如果得到的散列地址處理碰撞時，如果得到的散列地址H1仍然沖突，則再求下仍然沖突，則再求下一個地址一個地址H2，如，如H2沖突，再求沖突，再求H3，直到，直到Hk不發生沖突不發生沖突為止。為止。 Hi = (H(key)+di) % m (i=1

41、,2, , k km-1) 其中，其中，H(key)為散列函數，為散列函數， m為散列表長度，為散列表長度， di為增量序列。為增量序列。H1H2H3Hk線性探測容易出現不同的關鍵碼爭奪同一個散列地址問題，這線性探測容易出現不同的關鍵碼爭奪同一個散列地址問題，這種現象稱為種現象稱為“二次聚集二次聚集 堆積堆積 ”。例如：長度為例如：長度為11的散列表已填有關鍵碼分別為的散列表已填有關鍵碼分別為17，60，29的記的記錄錄散列函數散列函數h(key)=key%11，現第，現第4個記錄的關鍵碼為個記錄的關鍵碼為38，由，由散列函數得到其散列地址為散列函數得到其散列地址為5，由于該地址已經存放關鍵碼

42、為，由于該地址已經存放關鍵碼為60的記錄，產生沖突。的記錄，產生沖突。如何尋找下一個空的地址？如何尋找下一個空的地址？6060171729290 1 2 3 4 5 6 7 8 9 10a 線性探測線性探測： di=1,2,3,m-1di有下面三種形式：有下面三種形式： b 平方探測平方探測： di=12,-12,22,-22,k2,-k2 (km/2)c 隨機探測隨機探測： di=偽隨機數序列偽隨機數序列 按照按照線性探測線性探測得到下一個地址為得到下一個地址為6，仍然沖突，繼續探測得，仍然沖突，繼續探測得到下一個地址為到下一個地址為7，仍然沖突，再繼續探測下一個地址為，仍然沖突，再繼續探測

43、下一個地址為8，該，該地址為空，因此將關鍵碼為地址為空，因此將關鍵碼為38的記錄存放在地址為的記錄存放在地址為8的單元。的單元。 如果如果按照平方探測按照平方探測方法，則得到地址為方法，則得到地址為4的空地址用于存放的空地址用于存放關鍵碼為關鍵碼為38的記錄。的記錄。 如果如果按照隨機探測按照隨機探測方法，則得到地址為方法，則得到地址為3的空地址用于存放的空地址用于存放關鍵碼為關鍵碼為38的記錄。的記錄。在線性探測中可以發現，當表中在線性探測中可以發現，當表中i、i+1、i+2位置上已填有記錄時，散列位置上已填有記錄時，散列地址為地址為i、i+1、i+2、i+3的記錄都將的記錄都將填入填入i+

44、3的位置上，此時的位置上，此時出現出現“二次聚集二次聚集堆積堆積”問題。這不問題。這不利于查找。但是，當散列表未滿時利于查找。但是，當散列表未滿時總可以找到一個空單元。平方探測總可以找到一個空單元。平方探測和隨機探測不能保證一定能找到下和隨機探測不能保證一定能找到下一個空單元。一個空單元。6060171729296060171729296060171729296060171729293838383838380 1 2 3 4 5 6 7 8 9 10 再散列再散列:當發生碰撞時，當發生碰撞時，Hi的計算可以采用其它的散列函數的計算可以采用其它的散列函數得到。得到。 Hi = Rhi(key),

45、 i=0,1,2, k(2)拉鏈法拉鏈法（溢出區內解決）（溢出區內解決） 將所有關鍵碼為同義詞的記錄存儲在同一個線性鏈表中。將所有關鍵碼為同義詞的記錄存儲在同一個線性鏈表中。假定由散列函數得到的散列地址空間為假定由散列函數得到的散列地址空間為0，m-1，則可以建立，則可以建立一個指針向量：一個指針向量： Chain ChainHashm其初始狀態皆為空指針。其初始狀態皆為空指針。散列地址為散列地址為i的記錄都插入到頭的記錄都插入到頭指針為指針為ChainHashi的鏈表中。的鏈表中。鏈表中記錄排列可以是任意的，鏈表中記錄排列可以是任意的，也可以按照關鍵碼有序。也可以按照關鍵碼有序。 如如: (

46、8, 13, 3, 6, 10), H(key)=key%7 8 83 36 613131010 0 01 12 23 34 45 56 64. 4. 散列表的建立與檢索散列表的建立與檢索 散列表的建立與檢索是通過相同的散列函數進行的，并且散列表的建立與檢索是通過相同的散列函數進行的，并且當出現碰撞時應采用相同的解決碰撞的方法。當出現碰撞時應采用相同的解決碰撞的方法。 對于給定關鍵碼值對于給定關鍵碼值key，計算，計算H(key)，得到散列地址。，得到散列地址。 對于對于散列表的建立散列表的建立，如果該散列地址對應的單元為空，表，如果該散列地址對應的單元為空，表明沒有沖突，直接將記錄插入；否則

47、如果該散列地址對應的單明沒有沖突，直接將記錄插入；否則如果該散列地址對應的單元非空，表明該單元已經被前面的記錄占用，出現碰撞問題。元非空，表明該單元已經被前面的記錄占用，出現碰撞問題。此時，需要按照解決碰撞的方法進行處理此時，需要按照解決碰撞的方法進行處理如果采用開放地址如果采用開放地址法，則按照一定的序列尋找下一個空單元；如果是采用拉練法，法，則按照一定的序列尋找下一個空單元；如果是采用拉練法，則在碰撞地址對應的同義詞鏈表中完成插入則在碰撞地址對應的同義詞鏈表中完成插入。 對于對于散列表的檢索散列表的檢索，如果該散列地址對應的單元（或指針），如果該散列地址對應的單元（或指針）為空，表明檢索失

48、敗；否則為空，表明檢索失??；否則: (1) 如果散列表是如果散列表是采用開放地址法解決碰撞采用開放地址法解決碰撞建立的，那么給建立的，那么給定值定值key與該單元存儲的記錄的關鍵碼進行比較。如果相等，與該單元存儲的記錄的關鍵碼進行比較。如果相等，表明檢索成功；否則按照散列表建立時尋找下一個單元的序列表明檢索成功；否則按照散列表建立時尋找下一個單元的序列尋找下一個地址，如此反復進行，直到關鍵碼比較相等（尋找下一個地址，如此反復進行，直到關鍵碼比較相等（檢索檢索成功成功）或找到空單元（）或找到空單元（檢索失敗檢索失?。橹梗唬橹?； (2) 如果散列表是如果散列表是采用拉練法解決碰撞采用拉練法解決

49、碰撞建立的，那么沿著該非建立的，那么沿著該非空指針進入同義詞單鏈表，在該鏈表中進行檢索。如果找到某空指針進入同義詞單鏈表，在該鏈表中進行檢索。如果找到某個結點的存儲記錄的關鍵碼與給定值個結點的存儲記錄的關鍵碼與給定值key相同，相同，檢索成功檢索成功；否；否則，則，檢索失敗檢索失敗。/開放地址法，散列表結構定義：開放地址法，散列表結構定義：typedef struct DicElement elementREGION_LEN; int m; /* m=REGION_LEN, 基本區域長度基本區域長度 */ HashDictionary;/ 使用開放地址法中的線性探測方法解決碰撞的散列表檢索使用

50、開放地址法中的線性探測方法解決碰撞的散列表檢索int LinearSearch(HashDictionary *phash, KeyType key, int *pos) int d, inc; d = H(key); /計算散列地址計算散列地址 for (inc=0; inc m; inc+) if (phash-elementd.key = key) /檢索成功檢索成功 *pos = d; return TRUE; else if (phash-elementd.key = NIL) /檢索失敗，找到插入位置檢索失敗，找到插入位置 *pos = d; return FALSE; d = (

51、d+1)%phash-m; /采用線性探測找下一個探測地址采用線性探測找下一個探測地址 *pos = -1; return FALSE; /散列表溢出散列表溢出/ 使用開放地址法中的線性探測方法解決碰撞的散列表建立使用開放地址法中的線性探測方法解決碰撞的散列表建立int LinearInsert(HashDictionary *phash, KeyType key) int pos; if (LinearSearch(phash, key, &pos)= TRUE) printf(“找到相同的記錄！找到相同的記錄！n”); /散列表中已經存在關鍵碼為散列表中已經存在關鍵碼為key的記錄

52、，不能再插入的記錄，不能再插入 else if (pos != -1) phash-elementpos.key = key; /插入記錄插入記錄 else return FALSE; /散列表溢出散列表溢出 return TRUE;5. 檢索效率分析檢索效率分析從散列表的檢索過程可以發現：從散列表的檢索過程可以發現：（1）雖然散列表在關鍵碼與記錄的存儲位置之間建立了直接）雖然散列表在關鍵碼與記錄的存儲位置之間建立了直接映象，但由于映象，但由于“碰撞碰撞”的產生，使得散列表的檢索過程仍然的產生，使得散列表的檢索過程仍然是一個給定值和記錄關鍵碼進行比較的過程。因此，仍需要是一個給定值和記錄關鍵碼

53、進行比較的過程。因此，仍需要以平均查找長度作為衡量散列表查找效率的度量。以平均查找長度作為衡量散列表查找效率的度量。（2）查找過程中需和關鍵碼進行比較的次數取決于下列三個）查找過程中需和關鍵碼進行比較的次數取決于下列三個因素：因素： 散列函數散列函數 處理碰撞的方法處理碰撞的方法 裝填因子裝填因子 散列函數散列函數的的“好壞好壞”首先影響出現沖突的頻率。對于同一首先影響出現沖突的頻率。對于同一組隨機的關鍵碼，組隨機的關鍵碼，“均勻分布均勻分布”的散列函數產生碰撞的可的散列函數產生碰撞的可能性相同，則可不考慮它對能性相同，則可不考慮它對ASL的影響。的影響。對同樣一組關鍵碼，相同的散列函數，但不

54、同的對同樣一組關鍵碼，相同的散列函數，但不同的碰撞處理碰撞處理方法方法得到的散列表不一樣，其得到的散列表不一樣，其ASL也必然不同，通常拉鏈也必然不同，通常拉鏈法的法的ASL要小于開放地址法。要小于開放地址法。線性探測容易產生線性探測容易產生“二次聚集二次聚集堆積堆積”問題，而拉鏈法不會問題，而拉鏈法不會出現這種情況。出現這種情況。 另外，處理碰撞相同的散列表，其另外，處理碰撞相同的散列表，其ASL依賴于散列表的依賴于散列表的裝裝填因子填因子。裝填因子表示散列表的裝滿程度。裝填因子越小，。裝填因子表示散列表的裝滿程度。裝填因子越小，發生碰撞的可能性越??；反之，裝填因子越大，表中已填發生碰撞的可

55、能性越?。环粗b填因子越大，表中已填入的記錄多，再填記錄時，發生碰撞的可能性就越大，檢入的記錄多，再填記錄時，發生碰撞的可能性就越大，檢索時比較次數就越多。索時比較次數就越多。在在“開放地址法開放地址法”處理碰撞時，刪除的元素需要特別標注，處理碰撞時，刪除的元素需要特別標注，否則今后會出現檢索錯誤。否則今后會出現檢索錯誤。例如：散列函數例如：散列函數 key%116. 散列表的刪除散列表的刪除5166刪除5后，再檢索16：失??！166特殊標志，如-1-1166檢索時，碰到-1，繼續按照找空單元的方法檢索下一單元。插入時，碰到-1，與空單元一樣處理【可以插入】6.5 樹表的檢索樹表的檢索折半檢

56、索效率高，但只適合于有序的順序表折半檢索效率高，但只適合于有序的順序表。順序表中插入、刪除結點需要數據元素移動，效率低。能否找順序表中插入、刪除結點需要數據元素移動，效率低。能否找到一種既能把鏈式存儲結構的優點與折半檢索高效率結合，并到一種既能把鏈式存儲結構的優點與折半檢索高效率結合，并且又不要求有序表的檢索方法？且又不要求有序表的檢索方法？樹表：樹表：二叉排序樹、平衡二叉排序樹（二叉排序樹、平衡二叉排序樹（AVL樹）、樹）、 B樹樹1. 二叉排序樹二叉排序樹（1）定義）定義： 或者是一棵空二叉樹；或者是一棵空二叉樹； 或者具有下列性質的二叉樹：或者具有下列性質的二叉樹：若它的左子樹不空，則左

57、子樹上所有若它的左子樹不空，則左子樹上所有 結點的值均小于它的根結點的值；結點的值均小于它的根結點的值；若它的右子樹不空，則右子樹上所有若它的右子樹不空，則右子樹上所有 結點的值均大于它的根結點的值；結點的值均大于它的根結點的值；它的左右子樹也分別為二叉排序樹。它的左右子樹也分別為二叉排序樹。1810057368272599413251K=18, 73, 10, 05, 68, 99, 27, 41, 51, 32, 25字典的二叉排序樹索引字典的二叉排序樹索引1810057368272599413251字典的二叉排序樹表示字典的二叉排序樹表示二叉排序樹二叉排序樹D1D2Dn（2）為什么二叉排

58、序樹是動態字典的合適表達？）為什么二叉排序樹是動態字典的合適表達？無序序列構造得到二叉排序樹，然后中序遍歷，得到一個有無序序列構造得到二叉排序樹，然后中序遍歷，得到一個有序的序列。字典的檢索效率非常高。另外，二叉排序樹插入、序的序列。字典的檢索效率非常高。另外，二叉排序樹插入、刪除結點都非常方便。因此二叉排序樹是動態字典的合適表刪除結點都非常方便。因此二叉排序樹是動態字典的合適表達。達。（3）檢索思想）檢索思想首先根據無序序列的先后順序，構造二叉排序樹。然后根據首先根據無序序列的先后順序，構造二叉排序樹。然后根據二叉排序樹的定義進行檢索二叉排序樹的定義進行檢索: 若二叉排序樹為空樹，檢索失??；

59、若二叉排序樹為空樹，檢索失??； 否則，否則， 如給定值如給定值key等于二叉排序樹的根結點的關鍵字，等于二叉排序樹的根結點的關鍵字， 則檢索成功；則檢索成功； 如給定值如給定值key小于二叉排序樹的根結點的關鍵字，小于二叉排序樹的根結點的關鍵字， 則說明待檢索記錄只可能在左子樹中，繼續在左則說明待檢索記錄只可能在左子樹中，繼續在左 子樹檢索；子樹檢索； 如給定值如給定值key大于二叉排序樹的根結點的關鍵字，大于二叉排序樹的根結點的關鍵字， 則說明待檢索記錄只可能在右子樹中，繼續在右則說明待檢索記錄只可能在右子樹中，繼續在右 子樹檢索；子樹檢索；與折半相似與折半相似縮小區間搜索縮小區間搜索=（4

60、）二叉排序樹結構描述與檢索算法）二叉排序樹結構描述與檢索算法typedef struct BinNodeKeyTypekey; /* 結點的關鍵碼字段結點的關鍵碼字段 */ DataType other;/* 結點的屬性字段結點的屬性字段 */ struct BinNode *llink;/* 二叉樹的左指針二叉樹的左指針 */struct BinNode *rlink; /* 二叉樹的右指針二叉樹的右指針 */BinTreeNode, *PBinTreeNode, BinTree, *PBinTree;1810057368272599413251pqint SearchNode(PBinTree ptree, KeyType key, PBinTreeNode