《《數(shù)據(jù)結(jié)構(gòu)c語言版》復(fù)習(xí)重點》由會員分享，可在線閱讀，更多相關(guān)《《數(shù)據(jù)結(jié)構(gòu)c語言版》復(fù)習(xí)重點（9頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、數(shù)據(jù)結(jié)構(gòu)(C語言版)復(fù)習(xí)重點重點在二、三、六、七、九、十章，考試內(nèi)容兩大類：概念，算法第1章、緒論1. 數(shù)據(jù)：是對客觀事物的符號表示，在計算機科學(xué)中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。2. 數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進(jìn)行考慮和處理。3. 數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。其4類基本結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)4. 邏輯結(jié)構(gòu)：是數(shù)據(jù)元素之間的邏輯關(guān)系的描述。5. 物理結(jié)構(gòu)(存儲結(jié)構(gòu))：是數(shù)據(jù)結(jié)構(gòu)在計算機中的表示(又稱映像)。其4種存儲結(jié)構(gòu)：順序存數(shù)結(jié)構(gòu)、鏈?zhǔn)酱鏀?shù)結(jié)構(gòu)、索引存數(shù)結(jié)構(gòu)、散列存數(shù)結(jié)構(gòu)6.

2、 算法：是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。其5個重要特性：有窮性、確定性、可行性、輸入、輸出7 .時間復(fù)雜度：算法中基本操作重復(fù)執(zhí)行的次數(shù)是問題規(guī)模n的某個函數(shù)f(n),算法的時間度量記作，T(n)=O(f(n);他表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱做算法的漸進(jìn)時間復(fù)雜度，簡稱時間復(fù)雜度。例如：(a)+x;s=0;(b) for(i=1;i=n;+i)+x;s+=x;(c) for(j=1;j=n;+j)for(k=1;knext為第一個結(jié)點地址，L-next=NULL為空表。生成結(jié)點：p=(LinkLis

3、t)malloc(sizeof(LNode)回收結(jié)點：free(q)2) 循環(huán)鏈表特點：表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)。循環(huán)鏈表的操作與線性鏈表基本一致，差別僅在于算法中的循環(huán)條件不是P或P-next是否為空，而是它們是否等于頭指針。3) 雙向鏈表特點：有2個指針域，其一指向直接后繼，另一指向直接前趨。第3章、棧和隊列1. 棧：是限定僅在表尾進(jìn)行插入或刪除操作的線性表。表尾端稱為棧頂，表頭端稱為棧底，不含有元素的空表稱為空棧；棧又稱為后進(jìn)先出的線性表。2. 隊列：是一種先進(jìn)先出的線性表，它只允許在表的一端進(jìn)行插入，而另一端刪除元素。允許插入的一端叫做隊尾，允許刪除的一端

4、則稱為隊頭。1) 鏈隊列：用鏈表示的隊列。一個隊列需要兩個分別指示隊頭和隊尾的指針(分別成為頭指針和尾指針)才能確定唯一。和單鏈表一樣，也給鏈隊列添加一個頭結(jié)點，并令頭指針指向頭結(jié)點。2) 循環(huán)隊列：與順序棧類似，除了用一組地址連續(xù)的存儲單元依次存放從隊列頭到隊列尾的元素之外，尚需附設(shè)兩個指針front和rear分別指示隊列頭元素及隊列尾元素的位置。初始化建空隊列時，令front=rear=0，每當(dāng)插入新的隊列尾元素時，“尾指針增1”；每當(dāng)刪除隊列頭元素時，“頭指針增1”。第4章、串1. 串：是由零個或多個字符組成的有限序列。第5章、數(shù)組和廣義表2. 數(shù)組特點：與線性表一樣，所有數(shù)據(jù)元素都必須

5、屬于同一數(shù)據(jù)類型。3. 數(shù)組的順序存儲結(jié)構(gòu)：由于數(shù)組一般不作插入或刪除操作，一旦建立了數(shù)組，則結(jié)構(gòu)中的數(shù)據(jù)元素個數(shù)和元素之間的關(guān)系就不會發(fā)生變動，因此采用順序存儲結(jié)構(gòu)表示數(shù)組。存儲位置計算：假設(shè)每個數(shù)據(jù)元素需占用L個存儲單元，則二維數(shù)組A中任一元素aij的存儲位置可由下式確定以行序為主序的存儲結(jié)構(gòu)：LOC(i,j)=LOC(0,0)+(b2*i+j)*L以列序為主序的存儲結(jié)構(gòu)：LOC(i,j)=LOC(0,0)+(b2*j+i)*L式中LOC(i,j)是aij的存儲位置；LOC(0,0)是a00的存儲位置，即二維數(shù)組A的起始存儲位置，也稱基地址或基址；b2在以行序為主序的存儲結(jié)構(gòu)時為每行存儲元

6、素的個數(shù)(列數(shù))，在以列序為主序的存儲結(jié)構(gòu)時為每列存儲元素的個數(shù)(行數(shù))。4. 廣義表：是線性表的推廣，也有人稱其為列表(lists，用復(fù)數(shù)形式以示與統(tǒng)稱的表list的區(qū)別)。記作LS=(a1,a2,-an),其中LS是廣義表(a1,a2,七門)的名稱，n是它的長度。在線性表的定義中，ai(11）02）性質(zhì)2：深度為k的二叉樹至多有2的k次方減1個結(jié)點（k1）0深度為k的二叉樹至少有k個結(jié)點（k1）0深度為k的完全二叉樹至少有2的k次方減2的k減1次方個結(jié)點（k1）o3）性質(zhì)3:對任何一棵二叉樹T,如果其終端結(jié)點數(shù)為n0,度為2的結(jié)點數(shù)為n2,則n0=n2+1。4）性質(zhì)4:具有n個結(jié)點的完全二

7、叉樹的深度為log2n+1。5）性質(zhì)5:如果對一棵有n個結(jié)點的完全二叉樹（其深度為log2n+1）的結(jié)點按層序編號（從第1層到第log2n+1層，每層從左到右），則對任一結(jié)點i（1i1,則其雙親PARENT（i心結(jié)點i/2。b）如果2in,則結(jié)點i無左孩子（結(jié)點i為葉子結(jié)點）；否則其左孩子LCHILD（i）是結(jié)點2i。c）如果2i+1n,則結(jié)點i無右孩子；否則其右孩子RCHILD（i）是結(jié)點2i+1。3 .滿二叉樹：一顆深度為k且有2的k次方減1個結(jié)點的二叉樹。4 .完全二叉樹：深度為k的，有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點對應(yīng)。5 .遍歷二叉樹

8、：1）根據(jù)二叉樹寫遍歷結(jié)果a）先序遍歷（先根遍歷）-+a*b-cd/efb）中序遍歷（中根遍歷）a+b*c-d-e/fc）后序遍歷（后根遍歷）abcd-*+ef/-2）根據(jù)遍歷結(jié)果畫二叉樹DLRLDRLRDdcBEH一棵二叉樹的先序、中序和后序序列分別如下，其中有部分未給出，試求出空格處的結(jié)點字符，并畫出該二叉樹。先序：BEHIFGK中序：DHEIACJG后序：_H_EBF_KG_A解題思路：Ca）由先序或后序確定根結(jié)點；如本題后序最后一個為A,根結(jié)點為A,所以先序第一個空就為Ab)在中序找出根結(jié)點，根結(jié)點左側(cè)為左子樹，右側(cè)為右子樹；如本題D_HEI為左子樹，_CJG_為右子樹。c)由先序確定

9、緊跟在根結(jié)點后的左子樹根；如本題緊跟在A后的是B,B為左子樹根，中序根結(jié)點的左子樹只有一個空，所以為B。d)繼續(xù)由中序確定左子樹根的左右子樹，左側(cè)為左子樹，右側(cè)為右子樹；如本題B的左子樹為D,右子樹為HEI,所以先序第二個空為Doe)重復(fù)c)、d)步驟確定整棵左子樹；如本題先序中緊跟在D后的是E,E為B的右子樹，由中序中看出E左子樹為H,右子樹為I,補充后序填空，前兩空分別為D和I。f)由后序確定右子樹根的左子樹，再由中序確定右子樹根；如本題緊跟在B后的是F,F為右子樹根的左子樹，已知中序_CJG_為右子樹，F(xiàn)只可能第一個空，那第二個空為K,補全先序、中序、后序填空并可畫出二叉樹。6. 森林與

10、二叉樹的轉(zhuǎn)換：1) 樹轉(zhuǎn)換成二叉樹：連兄弟，留長子，刪孩子。a) 連線，連接所有兄弟結(jié)點。b) 刪線，僅保留雙親與長子結(jié)點的連線，刪除與其他孩子結(jié)點之間的連線。c) 整理，原有的長子結(jié)點為左子樹，從兄弟轉(zhuǎn)換為孩子的結(jié)點為右子樹。d) 注意，由于樹根沒有兄弟結(jié)點，固樹轉(zhuǎn)換為二叉樹后，二叉樹根結(jié)點的右子樹必為空。2) 森林轉(zhuǎn)換成二叉樹：連樹根及兄弟，留長子，刪孩子。a) 連線，連接每棵樹的根結(jié)點及所有兄弟結(jié)點。b) 刪線，僅保留雙親與長子結(jié)點的連線，刪除與其他孩子結(jié)點之間的連線。c) 整理，第一棵樹根結(jié)點為二叉樹根結(jié)點，原有的長子結(jié)點為左子樹，從兄弟轉(zhuǎn)換為孩子的結(jié)點為右子樹。3)二叉樹轉(zhuǎn)換成樹：連

11、左孩子的右孩子及其右孩子，刪原樹右孩子。a)連線，若某結(jié)點X存在左孩子XL,則將這個左孩子的右孩子結(jié)點XLR左孩子的右孩子的右孩子結(jié)點XLRR左孩子的右孩子的右孩子的右孩子結(jié)點XLRRR都與X結(jié)點連線。d) 刪線，刪除原二叉樹的所有雙親與右孩子結(jié)點的連線。e) 整理，原二叉樹根結(jié)點為樹根結(jié)點。4)二叉樹轉(zhuǎn)換成森林：連左孩子的右孩子及其右孩子，刪原樹右孩子。a)連線，若某結(jié)點X存在左孩子XL,則將這個左孩子的右孩子結(jié)點XLR左孩子的右孩子的右孩子結(jié)點XLRR左孩子的右孩子的右孩子的右孩子結(jié)點XLRRR都與X結(jié)點連線。f) 刪線，刪除原二叉樹的所有雙親與右孩子結(jié)點的連線。g) 整理，調(diào)整為多棵樹的

12、森林。7. 赫夫曼樹：又稱最優(yōu)樹，是一類帶權(quán)路徑長度最短的樹。a) 兩個最小數(shù)值組成一對，小的在前，大的在后；如上圖中2與4最小，2在前，4在后。b) 將兩個最小數(shù)值的和算作一個數(shù)，再與其他數(shù)重復(fù)a)步驟；如上圖中2與4的和為6，5與6最小，5在前，6在后。c)最后計算WPL它等于每個數(shù)值乘以從根結(jié)點到這個數(shù)值的連線個數(shù)的積之和；如上圖中WPL=2*3+4*3+5*2+7*1=35。8. 赫夫曼編碼：a） 在赫夫曼樹上，左分支代表0，右分支代表1。b） 由根結(jié)點到指定結(jié)點的路徑（從上到下把0、1連起來），就是該結(jié)點的赫夫曼編碼；如上圖（d）中a為0，b為10，c為110，d為111。第7章、圖

13、1. 圖：多個結(jié)點，結(jié)點之間的關(guān)系可以是任意的，圖中任意兩個數(shù)據(jù)元素之間都有可能相關(guān)。2. 無向完全圖：有n（n-1）/2條邊的無向圖。3. 有向完全圖：有n（n-1）條邊的有向圖。4. 入度：以頂點V為頭的弧的數(shù)目稱為V的入度。5. 出度：以V為尾的弧的數(shù)目稱為V的出度。6. 連通圖：在無向圖中，任意兩個頂點之間都有路徑。7. 連通分量：在無向圖中的極大連通子圖。8. 鄰接矩陣：無向圖的鄰接矩陣關(guān)于主對角線對稱，在整個矩陣中非零元素的個數(shù)等于邊個數(shù)的2倍，第i行和第i列中非零元素的個數(shù)等于該結(jié)點的度。9. 鄰接表：無向圖的鄰接矩陣關(guān)于主對角線對稱，在整個矩陣中非零元素的個數(shù)等于邊個數(shù)的2倍，

14、第i行和第i列中非零元素的個數(shù)等于該結(jié)點的度。10. 深度優(yōu)先遍歷：從圖中某個頂點出發(fā)，搜索與之相關(guān)聯(lián)的頂點，選擇一個訪問（從左到右，從上到下）；再從該頂點出發(fā)，搜索與之相關(guān)聯(lián)且未訪問過的頂點，選擇一個訪問；重復(fù)上步驟，直到?jīng)]有相關(guān)聯(lián)且未訪問過的頂點；后退一個頂點繼續(xù)搜索訪問，直到所有頂點都被訪問過。a）從V0出發(fā)，先找到V0的關(guān)聯(lián)頂點V3。b）由V3出發(fā)，找到V1;由V1出發(fā)，沒有關(guān)聯(lián)的頂點。c）回到V3,從V3出發(fā)，找到V2;由V2出發(fā)，沒有關(guān)聯(lián)的頂點。d）回到V3,再回到V0,由V0出發(fā)，找到V4e）從V4出發(fā)，找到V1,因為V1已經(jīng)被訪問過了，所以不訪問。所以最后順序是V0,V3,V1

15、,V2,V4。11. 廣度優(yōu)先遍歷：從圖中某個頂點出發(fā)，搜索與之相關(guān)聯(lián)的頂點，逐個訪問（從左到右，從上到下）；再從這些頂點出發(fā)，搜索與之相關(guān)聯(lián)且未訪問過的頂點，逐個訪問；重復(fù)上步驟，直到所有頂點都被訪問過。a）從V0出發(fā)，先找到V0的關(guān)聯(lián)頂點V3、V4b）由V3出發(fā)，找到VI、V2;由V4出發(fā)，找到V1,因為V1已經(jīng)被訪問過了，所以不訪問。c）由V1出發(fā)，沒有關(guān)聯(lián)的頂點；由V2出發(fā)，沒有關(guān)聯(lián)的頂點。所以最后順序是V0,V3,V4,V1,V2。12. 最小生成樹：1） 普里姆算法：連相鄰權(quán)值最小的。2） 克魯斯卡爾算法：先連權(quán)值最小的，再依次連。13. 拓?fù)渑判颍河赡硞€集合上的一個偏序得到該集合

16、上的一個全序的操作。14. 關(guān)鍵路徑：路徑長度最長的路徑。1） 如圖，先求各事件的最早發(fā)生時間（順序為V1V9）V1的最早發(fā)生時間為0,V2的最早發(fā)生時間為6,V3的最早發(fā)生時間為4,V4的最早發(fā)生時間為5。對于V5,需要V2,V3均發(fā)生，V2發(fā)生且完成的時間為6+1=7;V3發(fā)生且完成的時間為4+1=5，因而V5的最早發(fā)生時間為7。同理可求出各頂點的最早發(fā)生時間：V1V2V3V4V5V6V7V8V9e（i）0645771614182） 求各事件的最晚發(fā)生時間（順序為V9V1）V9的最晚時間為18，V8的最晚時間為18-a11=14，V7的最晚時間為18-a10=16，V6的最晚時間為14-a

17、9=10,V5的最晚時間為V7的最晚時間減去a7和V8的最晚時間減去a8兩者較小的，則V5的最晚時間為7,同理可得其他頂點的最晚發(fā)生時間：V1V2V3V4V5V6V7V8V9l（i）0668710161418則li與ei相等的事件即為關(guān)鍵事件即：V1，V2，V5，V7，V8，V9可得關(guān)鍵路徑：V1,V2,V5,V7,V9或V1,V2,V5,V8,V93） 求各活動的最早發(fā)生時間a1a2a8a3a9a4a10a5a11a6a7e(i)00064577716144)求各活動的最晚發(fā)生時間a1a2a3a4a5a6a7a8a9a10a11l(i)6-6=06-4=28-5=37-1=67-1=610-

18、2=816-9=714-7=714-4=1018-2=1618-4=14則li與ei相等的活動即為關(guān)鍵活動即：a1，a4，a7，a8，a10，a11可得關(guān)鍵路徑：V1,V2,V5,V7,V9或V1,V2,V5,V8,V915. 最短路徑：從某頂點出發(fā)，沿圖的邊到達(dá)另一頂點所經(jīng)過的路徑中，各邊上權(quán)值之和最小的一條路徑。1） 迪杰斯特拉算法：2） 弗洛伊德算法：方法：兩條線，從左上角開始計算一直到右下角如下所示：給出矩陣，其中矩陣A是鄰接矩陣，而矩陣Path記錄u,v兩點之間最短路徑所必須經(jīng)過的點。最后A3即為所求結(jié)果。第9章、查找1. 查找表：是由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。2. 關(guān)

19、鍵字：是數(shù)據(jù)元素（或記錄）中某個數(shù)據(jù)項的值，用它可以標(biāo)識（識別）一個數(shù)據(jù)元素（或記錄）。3. 靜態(tài)查找表：查詢某個特定的數(shù)據(jù)元素是否在查找表中，檢索某個特定的數(shù)據(jù)元素的各種屬性。1） 順序查找法：從表中最后一個記錄開始，逐個進(jìn)行記錄的關(guān)鍵字和給定值比較，若某個記錄的關(guān)鍵字和給定值比較相等，則查找成功，找到所查記錄；反之若直至第一個記錄，其關(guān)鍵字和給定值比較都不相等，則表明表中沒有所查記錄，查找不成功。其存儲結(jié)構(gòu)要求：以順序表或線性鏈表表示的靜態(tài)查找表。其平均查找長度：假設(shè)每個記錄的查找概率相等，即Pi=1/n，則在等概率情況下順序查找的平均查找長度為，ASL=（n+1）/2。2） 折半查找法（

20、二分查找法）：先確定待查記錄所在的范圍（區(qū)間），然后逐步縮小范圍直到找到或找不到該記錄為止。其存儲結(jié)構(gòu)要求：以有序表表示的靜態(tài)查找表。其平均查找長度：假設(shè)表中每個記錄的查找概率相等（Pi=1/n），則查找成功時折半查找的平均查找長度為，ASL=（n+1）/n*log2（n+1）-1。3） 索引順序表查找法（分塊查找法）：先確定待查記錄所在的塊（子表），然后在塊中順序查找。其存儲結(jié)構(gòu)要求：以索引順序表表示的靜態(tài)查找表。其平均查找長度：將長度為n的表均勻地分成b塊，每塊含有s個記錄，即b=n/s；又假設(shè)表中每個記錄的查找概率相等，則每塊查找概率為1/b，塊中每個記錄的查找概率為1/s，若用順序查找

21、確定所在塊，則分塊查找的平均查找長度為，ASL=（n/s+s）/2+1；若用折半查找確定所在塊，則分塊查找的平均查找長度為，AS3log2（n/s+1）+s/2。4. 動態(tài)查找表：在查找過程中同時插入查找表中不存在的數(shù)據(jù)元素，或者從查找表中刪除已存在的某個數(shù)據(jù)元素。1） 二叉排序樹：或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹：1、若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；2、若它的右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；3、它的左、右子樹也分別為二叉排序樹。2） 平衡二叉樹（AVL樹）：它或者是一棵空樹；或者是具有下列性質(zhì)的二叉樹：它的左子樹和右子樹都是平衡

22、二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。若將二叉樹上結(jié)點的平衡因子BF定義為該結(jié)點的左子樹的深度減去它的右子樹的深度，則平衡二叉樹上所有結(jié)點的平衡因子只可能是-1、0和1。只要二叉樹上有一個結(jié)點的平衡因子的絕對值大于1，則該二叉樹就是不平衡的。下面即四種情況分別為：左左、右右、左右、右左，每種情況又有兩個圖、，是該情況的最簡單的圖形，是該情況的一般的圖形。設(shè)x為最小不平衡子樹的根結(jié)點，y為剛插入的點左左：即在x的左孩子a的左孩子c上插入一個結(jié)點y（該結(jié)點也可以是c,如圖），即y可以是c,也可以是c的左孩子（如圖），也可以是c的右孩子（不在畫出）。圖就不用說了，結(jié)點x和結(jié)點a變換，則

23、樹平衡了；那么圖就是樹中的一般情況了a結(jié)點有右孩子d，那要進(jìn)行x和a變換，那么a的右孩子放哪?。亢芎唵?，如圖放在x的左孩子上；分析：xd,da,所以d可作為x的左孩子，且可作為a的右孩子中的孩子。下邊這樣的類似情況不再一一分析，自己分析分析實現(xiàn)：找到根結(jié)點x,與它的左孩子a進(jìn)行交換即可使二叉樹樹再次平衡；右右：即在x的右孩子a的右孩子c上插入一個結(jié)點y（該結(jié)點也可以是c,如圖），即y可以是c,也可以是c的右孩子（如圖），也可以是c的左孩子（不在畫出）。實現(xiàn)：找到根結(jié)點x,與它的右孩子a進(jìn)行交換即可使二叉樹樹再次平衡；左右：即在x的左孩子a的右孩子c上插入一個結(jié)點y（該結(jié)點也可以是c,如圖），即

24、y可以是c,也可以是c的右孩子（如圖），也可以是c的左孩子（不在畫出）。這個左右和下邊的右左，稍微復(fù)雜了點，需要進(jìn)行兩次交換，才能達(dá)到平衡，注意這時y是c的右孩子，最終y作為x的左孩子；若y是c的左孩子，最終y作為a的右孩子，畫圖分析一下下邊類似，不再敖述。實現(xiàn)：找到根結(jié)點x，讓x的左孩子a與x的左孩子a的右孩子c進(jìn)行交換，然后再讓x與x此時的左孩子c進(jìn)行交換，最終達(dá)到平衡；右左：即在x的右孩子a的左孩子c上插入一個結(jié)點y(該結(jié)點也可以是c,如圖)，即y可以是c,也可以是c的右孩子(如圖)，也可以是c的左孩子(不在畫出)。實現(xiàn)：找到根結(jié)點x，讓x的右孩子a與x的右孩子a的左孩子c進(jìn)行交換，然后

25、再讓x與x此時的右孩子c進(jìn)行交換，最終達(dá)到平衡；上邊的四種情況包含了所有插入時導(dǎo)致不平衡的情況，上面給出的僅僅是一棵大樹中的最小不平衡子樹，一定要想清楚，別迷了！另外一定要注意這個交換操作，比如a與b交換(a在上，b在下)，b一定要占據(jù)a的位置！什么意思？就是b要放在(覆蓋)儲存a的那塊內(nèi)存上，再通俗點說，若a是x的左孩子，則交換后b要做x的左孩子；這就是所謂的b占據(jù)a的位置！5. 哈希表：1) 構(gòu)造方法：a) 直接定址法：取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為散列地址。即H(key)=key或H(key)=a-key+b,其中a和b為常數(shù)(這種散列函數(shù)叫做自身函數(shù))。若其中H(key)中已經(jīng)有值

26、了，就往下一個找，直到H(key)中沒有值了，就放進(jìn)去。b) 數(shù)字分析法：分析一組數(shù)據(jù)，比如一組員工的出生年月日，這時我們發(fā)現(xiàn)出生年月日的前幾位數(shù)字大體相同，這樣的話，出現(xiàn)沖突的幾率就會很大，但是我們發(fā)現(xiàn)年月日的后幾位表示月份和具體日期的數(shù)字差別很大，如果用后面的數(shù)字來構(gòu)成散列地址，則沖突的幾率會明顯降低。因此數(shù)字分析法就是找出數(shù)字的規(guī)律，盡可能利用這些數(shù)據(jù)來構(gòu)造沖突幾率較低的散列地址。c) 平方取中法：當(dāng)無法確定關(guān)鍵字中哪幾位分布較均勻時，可以先求出關(guān)鍵字的平方值，然后按需要取平方值的中間幾位作為哈希地址。這是因為：平方后中間幾位和關(guān)鍵字中每一位都相關(guān)，故不同關(guān)鍵字會以較高的概率產(chǎn)生不同的哈

27、希地址。d) 折疊法：將關(guān)鍵字分割成位數(shù)相同的幾部分，最后一部分位數(shù)可以不同，然后取這幾部分的疊加和(去除進(jìn)位)作為散列地址。數(shù)位疊加可以有移位疊加和間界疊加兩種方法。移位疊加是將分割后的每一部分的最低位對齊，然后相加；間界疊加是從一端向另一端沿分割界來回折疊，然后對齊相加。e)除留余數(shù)法：取關(guān)鍵字被某個不大于散列表表長m的數(shù)p除后所得的余數(shù)為散列地址。即H(key)=keyMODp,p=m。不僅可以對關(guān)鍵字直接取模，也可在折疊、平方取中等運算之后取模。對p的選擇很重要，一般取素數(shù)或m,若p選的不好，容易產(chǎn)生同義詞。2) 處理沖突方法：a)開放定址法：Hi=(H(key)+di)MODm,i=

28、1,2,，k(k=m-1),其中H(key)為散列函數(shù)，m為散列表長，di為增量序列，可有下列三種取法：1.1. di=1,2,3,，m-1,稱線性探測再散列；1.2. di=1A2,-1A2,2A2,-2A2,3A2,，kA2,(kL.r2.key），則將兩個記錄交換之，然后比較第二個記錄和第三個記錄的關(guān)鍵字。以此類推，直至第n-1個記錄和第n個記錄的關(guān)鍵字進(jìn)行過比較為止。5. 快速排序：通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠郑渲幸徊糠钟涗浀年P(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個序列有序。6. 堆排序：只需要一個記錄大小的輔助空間，每個待排序的記錄僅占有一個存儲空間。