《《數據結構(C語言版)》復習重點(總31頁)》由會員分享，可在線閱讀，更多相關《《數據結構(C語言版)》復習重點(總31頁)（32頁珍藏版）》請在裝配圖網上搜索。

1、《數據結構(C語言版)》復習重點 重點在二、三、六、七、九、十章，考試內容兩大類：概念，算法 第1章、緒論 1. 數據：是對客觀事物的符號表示，在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。 2. 數據元素：是數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。 3. 數據結構：是相互之間存在一種或多種特定關系的數據元素的集合。 其4類基本結構：集合、線性結構、樹形結構、圖狀結構或網狀結構 4. 邏輯結構：是數據元素之間的邏輯關系的描述。 5. 物理結構（存儲結構）：是數據結構在計算機中的表示（又稱映像）。 其4種存儲結構：順序存數結構

2、、鏈式存數結構、索引存數結構、散列存數結構 6. 算法：是對特定問題求解步驟的一種描述，它是指令的有限序列，其中每一條指令表示一個或多個操作。 其5個重要特性：有窮性、確定性、可行性、輸入、輸出 7. 時間復雜度：算法中基本操作重復執(zhí)行的次數是問題規(guī)模n的某個函數f(n),算法的時間度量記作，T(n)=O(f(n)) ；他表示隨問題規(guī)模n的增大，算法執(zhí)行時間的增長率和f(n)的增長率相同，稱做算法的漸進時間復雜度，簡稱時間復雜度。 例如： (a) {++x;s=0;} (b) for(i=1;i<=n;++i){++x;s += x;} (c) for(j=1;j<=n;++j)

3、 for(k=1;k<=n;++k){++x;s += x;} 含基本操作“x增1”的語句的頻度分別為1、n和n，則這3個程序段的時間復雜度分別為O(1)、O(n)和O(n)，分別稱為常量階、線性階和平方階。還可呈現對數階O(log n)、指數階O(2的n次方)等。 8. 空間復雜度：算法所需存儲空間的度量記作，S(n)=O(f(n))。 第2章、線性表 1. 線性表：是最常用最簡單的一種數據結構，一個線性表是n個數據元素的有限序列。 2. 線性表的順序存儲結構：是用一組地址連續(xù)的存儲單元依次存儲線性表的數據元素。其特點為邏輯關系上相鄰的兩個元素在物理位置上也相鄰，可以

4、隨機存取表中任一元素。 存儲位置計算：假設線性表的每個元素需占用L個存儲單元，并以所占的第一個單元的存儲地址作為數據元素的存儲位置，線性表的第i個數據元素ai的存儲位置為LOC(ai)=LOC(a1)+(i-1)*L 式中LOC(a1)是線性表第一個元素a1的存儲位置，通常稱做線性表的起始位置或基地址。 3. 線性表的鏈式存儲結構：是用一組任意的存儲單元存儲線性表的數據元素(這組存儲單元可以是連續(xù)的，也可以是不連續(xù)的)。 數據元素ai的存儲映像稱為結點，包括2個域：存數據的數據域、存后繼存儲位置的指針域。 1) 線性鏈表(單鏈表)特點：每個結點只包含1個指針域。 在單鏈表的第一個結點

5、之前附設的一個結點，稱之為頭結點。 假設L是LinkList型變量，則L為單鏈表的頭指針，它指向表中第一個結點；L->next為第一個結點地址，L->next=NULL為空表。 生成結點：p=(LinkList)malloc(sizeof(LNode)) 回收結點：free(q) 2) 循環(huán)鏈表特點：表中最后一個結點的指針域指向頭結點，整個鏈表形成一個環(huán)。 循環(huán)鏈表的操作與線性鏈表基本一致，差別僅在于算法中的循環(huán)條件不是P或P->next是否為空，而是它們是否等于頭指針。 3) 雙向鏈表特點：有2個指針域，其一指向直接后繼，另一指向直接前趨。 第3章、棧和

6、隊列 1. 棧：是限定僅在表尾進行插入或刪除操作的線性表。表尾端稱為棧頂，表頭端稱為棧底，不含有元素的空表稱為空棧；棧又稱為后進先出的線性表。 2. 隊列：是一種先進先出的線性表，它只允許在表的一端進行插入，而另一端刪除元素。允許插入的一端叫做隊尾，允許刪除的一端則稱為隊頭。 1) 鏈隊列：用鏈表示的隊列。一個隊列需要兩個分別指示隊頭和隊尾的指針（分別成為頭指針和尾指針）才能確定唯一。和單鏈表一樣，也給鏈隊列添加一個頭結點，并令頭指針指向頭結點。 2) 循環(huán)隊列：與順序棧類似，除了用一組地址連續(xù)的存儲單元依次存放從隊列頭到隊列尾的元素之外，尚需附設兩個指針front和rear分別指

7、示隊列頭元素及隊列尾元素的位置。初始化建空隊列時，令front = rear = 0，每當插入新的隊列尾元素時，“尾指針增1”；每當刪除隊列頭元素時，“頭指針增1”。 第4章、串 1. 串：是由零個或多個字符組成的有限序列。 第5章、數組和廣義表 1. 數組特點：與線性表一樣，所有數據元素都必須屬于同一數據類型。 2. 數組的順序存儲結構：由于數組一般不作插入或刪除操作，一旦建立了數組，則結構中的數據元素個數和元素之間的關系就不會發(fā)生變動，因此采用順序存儲結構表示數組。 存儲位置計算：假設每個數據元素需占用L個存儲單元，則二維數組A中任一元素aij的存儲位置可由下式

8、確定 以行序為主序的存儲結構：LOC(i,j)=LOC(0,0)+(b2*i+j)*L 以列序為主序的存儲結構：LOC(i,j)=LOC(0,0)+(b2*j+i)*L 式中LOC(i,j)是aij的存儲位置；LOC(0,0)是a00的存儲位置，即二維數組A的起始存儲位置，也稱基地址或基址；b2在以行序為主序的存儲結構時為每行存儲元素的個數(列數)，在以列序為主序的存儲結構時為每列存儲元素的個數(行數)。 3. 廣義表：是線性表的推廣，也有人稱其為列表（lists，用復數形式以示與統稱的表list的區(qū)別）。記作LS=(a1,a2,…an) ，其中LS是廣義表(a1,a2,…an)的名稱

9、，n是它的長度。在線性表的定義中，ai(1≤i≤n)只限于是單個元素。而在廣義表的定義中，ai可以是單個元素，也可以是廣義表，分別稱為廣義表LS的原子和子表。 例如： 第6章、樹和二叉樹 1. 二叉樹：是一種樹型的結構，它的特點是每個結點至多只有兩棵子樹（即二叉樹中不存在度大于2的結點），并且，二叉樹的子樹有左右之分，其次序不能任意顛倒。 2. 二叉樹的性質： 1) 性質1：在二叉樹的第i層上至多有2的i減1次方個結點(i≥1)。 2) 性質2：深度為k的二叉樹至多有2的k次方減1個結點(k≥1)。 深度為k的二叉樹至少有k個結點(k≥1)。 深度為k的完全二叉樹至少有

10、2的k次方減2的k減1次方個結點(k≥1)。 3) 性質3：對任何一棵二叉樹T，如果其終端結點數為n0，度為2的結點數為n2，則n0=n2+1。 4) 性質4：具有n個結點的完全二叉樹的深度為[log2n]+1。 5) 性質5：如果對一棵有n個結點的完全二叉樹（其深度為[log2n]+1）的結點按層序編號（從第1層到第[log2n]+1層，每層從左到右），則對任一結點i（1≤i≤n）有： a) 如果i=1，則結點i是二叉樹的根，無雙親；如果i>1，則其雙親PARENT(i)是結點[i/2]。 b) 如果2i>n，則結點i無左孩子（結點i為葉子結點）；否則其左孩子LCHILD(i)是結

11、點2i。 c) 如果2i+1>n，則結點i無右孩子；否則其右孩子RCHILD(i)是結點2i+1。 3. 滿二叉樹：一顆深度為k且有 2的k次方減1個結點的二叉樹。 4. 完全二叉樹：深度為k的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應。 5. 遍歷二叉樹： 1) 根據二叉樹寫遍歷結果： a) 先序遍歷（先根遍歷）：DLR - + a * b - c d / e f b) 中序遍歷（中根遍歷）：LDR a + b * c - d - e / f c) 后序遍歷（后根遍歷）：LRD a b c d - * + e

12、 f / - 2) 根據遍歷結果畫二叉樹： 一棵二叉樹的先序、中序和后序序列分別如下，其中有部分未給出，試求出空格處的結點字符，并畫出該二叉樹。 先序：__B__EHI__FG__K 中序：D__HEIA__CJG__ 后序：__H__EBF__KG__A 解題思路： a) 由先序或后序確定根結點；如本題后序最后一個為A，根結點為A，所以先序第一個空就為A。 b) 在中序找出根結點，根結點左側為左子樹，右側為右子樹；如本題D__HEI為左子樹，__CJG__為右子樹。 c) 由先序確定緊跟在根結點后的左子樹根；如本題緊跟在A后的是B，B為左子樹根，中序根結點的左子樹只

13、有一個空，所以為B。 d) 繼續(xù)由中序確定左子樹根的左右子樹，左側為左子樹，右側為右子樹；如本題B的左子樹為D，右子樹為HEI，所以先序第二個空為D。 e) 重復c)、d)步驟確定整棵左子樹；如本題先序中緊跟在D后的是E，E為B的右子樹，由中序中看出E左子樹為H，右子樹為I，補充后序填空，前兩空分別為D和I。 f) 由后序確定右子樹根的左子樹，再由中序確定右子樹根；如本題緊跟在B后的是F，F為右子樹根的左子樹，已知中序__CJG__為右子樹，F只可能第一個空，那第二個空為K，補全先序、中序、后序填空并可畫出二叉樹。 6. 森林與二叉樹的轉換： 1) 樹轉換成二叉樹：連兄弟，留長子，刪

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

15、右孩子及其右孩子…，刪原樹右孩子。 a) 連線，若某結點X存在左孩子XL，則將這個左孩子的右孩子結點XLR、左孩子的右孩子的右孩子結點XLRR、左孩子的右孩子的右孩子的右孩子結點XLRRR…都與X結點連線。 b) 刪線，刪除原二叉樹的所有雙親與右孩子結點的連線。 c) 整理，原二叉樹根結點為樹根結點。 4) 二叉樹轉換成森林：連左孩子的右孩子及其右孩子…，刪原樹右孩子。 a) 連線，若某結點X存在左孩子XL，則將這個左孩子的右孩子結點XLR、左孩子的右孩子的右孩子結點XLRR、左孩子的右孩子的右孩子的右孩子結點XLRRR…都與X結點連線。 b) 刪線，刪除原二叉樹的所有雙親與右

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

17、該結點的赫夫曼編碼；如上圖(d)中a為0，b為10，c為110，d為111。 第7章、圖 1. 圖：多個結點，結點之間的關系可以是任意的，圖中任意兩個數據元素之間都有可能相關。 2. 無向完全圖：有n(n-1)/2條邊的無向圖。 3. 有向完全圖：有n(n-1)條邊的有向圖。 4. 入度：以頂點V為頭的弧的數目稱為V的入度。 5. 出度：以V為尾的弧的數目稱為V的出度。 6. 連通圖：在無向圖中，任意兩個頂點之間都有路徑。 7. 連通分量：在無向圖中的極大連通子圖。 8. 鄰接矩陣：無向圖的鄰接矩陣關于主對角線對稱，在整個矩陣中非零元素的個數等于邊個數的2倍，第i行和

18、第i列中非零元素的個數等于該結點的度。 9. 鄰接表：無向圖的鄰接矩陣關于主對角線對稱，在整個矩陣中非零元素的個數等于邊個數的2倍，第i行和第i列中非零元素的個數等于該結點的度。 10. 深度優(yōu)先遍歷：從圖中某個頂點出發(fā)，搜索與之相關聯的頂點，選擇一個訪問（從左到右，從上到下）；再從該頂點出發(fā)，搜索與之相關聯且未訪問過的頂點，選擇一個訪問；重復上步驟，直到沒有相關聯且未訪問過的頂點；后退一個頂點繼續(xù)搜索訪問，直到所有頂點都被訪問過。 a) 從V0出發(fā)，先找到V0的關聯頂點V3。 b) 由V3出發(fā)，找到V1；由V1出發(fā)，沒有關聯的頂點。 c) 回到V3，從V3出發(fā)，找到V2

19、；由V2出發(fā)，沒有關聯的頂點。 d) 回到V3，再回到V0，由V0出發(fā)，找到V4。 e) 從V4出發(fā)，找到V1，因為V1已經被訪問過了，所以不訪問。 所以最后順序是V0, V3, V1, V2, V4。 11. 廣度優(yōu)先遍歷：從圖中某個頂點出發(fā)，搜索與之相關聯的頂點，逐個訪問（從左到右，從上到下）；再從這些頂點出發(fā)，搜索與之相關聯且未訪問過的頂點，逐個訪問；重復上步驟，直到所有頂點都被訪問過。 a) 從V0出發(fā)，先找到V0的關聯頂點V3、V4。 b) 由V3出發(fā)，找到V1、V2；由V4出發(fā)，找到V1，因為V1已經被訪問過了，所以不訪問。 c) 由V1出發(fā)，沒有關聯的頂點；由V

20、2出發(fā)，沒有關聯的頂點。 所以最后順序是V0, V3, V4, V1, V2。 12. 最小生成樹： 1) 普里姆算法：連相鄰權值最小的。 2) 克魯斯卡爾算法：先連權值最小的，再依次連。 13. 拓撲排序：由某個集合上的一個偏序得到該集合上的一個全序的操作。 14. 關鍵路徑：路徑長度最長的路徑。 1) 如圖，先求各事件的最早發(fā)生時間（順序為V1~V9） 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的最

21、早發(fā)生時間為7。同理可求出各頂點的最早發(fā)生時間： V1 V2 V3 V4 V5 V6 V7 V8 V9 e(i) 0 6 4 5 7 7 16 14 18 2) 求各事件的最晚發(fā)生時間（順序為V9~V1） V9的最晚時間為18，V8的最晚時間為18-a11=14，V7的最晚時間為18-a10=16，V6的最晚時間為14-a9=10，V5的最晚時間為V7的最晚時間減去a7和V8的最晚時間減去a8兩者較小的，則V5的最晚時間為7，同理可得其他頂點的最晚發(fā)生時間： V1 V2 V3 V4 V5 V6 V7 V8 V9 l(i) 0

22、6 6 8 7 10 16 14 18 則l[i]與e[i]相等的事件即為關鍵事件 即：V1，V2，V5，V7，V8，V9 可得關鍵路徑：V1，V2，V5，V7，V9或V1，V2，V5，V8，V9 3) 求各活動的最早發(fā)生時間 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 e(i) 0 0 0 6 4 5 7 7 7 16 14 4) 求各活動的最晚發(fā)生時間 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11

23、 l(i) 6-6=0 6-4=2 8-5=3 7-1=6 7-1=6 10-2=8 16-9=7 14-7=7 14-4=10 18-2=16 18-4=14 則l[i]與e[i]相等的活動即為關鍵活動 即：a1，a4，a7，a8，a10，a11 可得關鍵路徑：V1，V2，V5，V7，V9或V1，V2，V5，V8，V9 15. 最短路徑：從某頂點出發(fā)，沿圖的邊到達另一頂點所經過的路徑中，各邊上權值之和最小的一條路徑。 1) 迪杰斯特拉算法： 2) 弗洛伊德算法： 方法：兩條線，從左上角開始計算一直到右下角 如下所示： 給出矩陣，其中

24、矩陣A是鄰接矩陣，而矩陣Path記錄u,v兩點之間最短路徑所必須經過的點。 最后A3即為所求結果。 第9章、查找 1. 查找表：是由同一類型的數據元素（或記錄）構成的集合。 2. 關鍵字：是數據元素（或記錄）中某個數據項的值，用它可以標識（識別）一個數據元素（或記錄）。 3. 靜態(tài)查找表：查詢某個特定的數據元素是否在查找表中，檢索某個特定的數據元素的各種屬性。 1) 順序查找法：從表中最后一個記錄開始，逐個進行記錄的關鍵字和給定值比較，若某個記錄的關鍵字和給定值比較相等，則查找成功，找到所查記錄；反之若直至第一個記錄，其關鍵字和給定值比較都不相等，則表明表中沒有所查

25、記錄，查找不成功。 其存儲結構要求：以順序表或線性鏈表表示的靜態(tài)查找表。 其平均查找長度：假設每個記錄的查找概率相等，即Pi=1/n，則在等概率情況下順序查找的平均查找長度為，ASL=(n+1)/2。 2) 折半查找法（二分查找法）：先確定待查記錄所在的范圍（區(qū)間），然后逐步縮小范圍直到找到或找不到該記錄為止。 其存儲結構要求：以有序表表示的靜態(tài)查找表。 其平均查找長度：假設表中每個記錄的查找概率相等（Pi=1/n），則查找成功時折半查找的平均查找長度為，ASL=(n+1)/n*log2(n+1)-1。 3) 索引順序表查找法（分塊查找法）：先確定待查記錄所在的塊（子表），然后在塊

26、中順序查找。 其存儲結構要求：以索引順序表表示的靜態(tài)查找表。 其平均查找長度：將長度為n的表均勻地分成b塊，每塊含有s個記錄，即b=[n/s]；又假設表中每個記錄的查找概率相等，則每塊查找概率為1/b，塊中每個記錄的查找概率為1/s，若用順序查找確定所在塊，則分塊查找的平均查找長度為，ASL=(n/s+s)/2+1；若用折半查找確定所在塊，則分塊查找的平均查找長度為，ASL≈log2(n/s+1)+s/2。 4. 動態(tài)查找表：在查找過程中同時插入查找表中不存在的數據元素，或者從查找表中刪除已存在的某個數據元素。 1) 二叉排序樹：或者是一棵空樹；或者是具有下列性質的二叉樹：1、若它的左

27、子樹不空，則左子樹上所有結點的值均小于它的根結點的值；2、若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；3、它的左、右子樹也分別為二叉排序樹。 2) 平衡二叉樹（AVL樹）：它或者是一棵空樹；或者是具有下列性質的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。若將二叉樹上結點的平衡因子BF定義為該結點的左子樹的深度減去它的右子樹的深度，則平衡二叉樹上所有結點的平衡因子只可能是 -1、0和1。只要二叉樹上有一個結點的平衡因子的絕對值大于1，則該二叉樹就是不平衡的。 下面即四種情況分別為：左左、右右、左右、右左，每種情況又有兩個圖①、②

28、，①是該情況的最簡單的圖形，②是該情況的一般的圖形。 設x為最小不平衡子樹的根結點，y為剛插入的點 左左：即在x的左孩子a的左孩子c上插入一個結點y（該結點也可以是c,如圖①），即y可以是c，也可以是c的左孩子（如圖②），也可以是c的右孩子（不在畫出）。 圖①就不用說了，結點x和結點a變換，則樹平衡了；那么圖②就是樹中的一般情況了a結點有右孩子d，那要進行x和a變換，那么a的右孩子放哪??？很簡單，如圖放在x的左孩子上；分析：x>d,d>a,所以d可作為x的左孩子，且可作為a的右孩子中的孩子。下邊這樣的類似情況不再一一分析，自己分析分析~ 實現：找到根結點x，與它的左孩子a進行交換即

29、可使二叉樹樹再次平衡； 右右：即在x的右孩子a的右孩子c上插入一個結點y（該結點也可以是c,如圖①），即y可以是c，也可以是c的右孩子（如圖②），也可以是c的左孩子（不在畫出）。 實現：找到根結點x，與它的右孩子a進行交換即可使二叉樹樹再次平衡； 左右：即在x的左孩子a的右孩子c上插入一個結點y（該結點也可以是c,如圖①），即y可以是c，也可以是c的右孩子（如圖②），也可以是c的左孩子（不在畫出）。 這個左右和下邊的右左，稍微復雜了點，需要進行兩次交換，才能達到平衡，注意這時y是c的右孩子，最終y作為x的左孩子；若y是c的左孩子，最終y作為a的右孩子，畫圖分析一下~~下邊類似，

30、不再敖述。 實現：找到根結點x，讓x的左孩子a與x的左孩子a的右孩子c進行交換，然后再讓x與x此時的左孩子c進行交換，最終達到平衡； 右左：即在x的右孩子a的左孩子c上插入一個結點y（該結點也可以是c,如圖①），即y可以是c，也可以是c的右孩子（如圖②），也可以是c的左孩子（不在畫出）。 實現：找到根結點x，讓x的右孩子a與x的右孩子a的左孩子c進行交換，然后再讓x與x此時的右孩子c進行交換，最終達到平衡； 上邊的四種情況包含了所有插入時導致不平衡的情況，上面給出的僅僅是一棵大樹中的最小不平衡子樹，一定要想清楚，別迷了！另外一定要注意這個交換操作，比如a與b交換（a在上，b在下）

31、，b一定要占據a的位置！什么意思？就是b要放在（覆蓋）儲存a的那塊內存上，再通俗點說，若a是x的左孩子，則交換后b要做x的左孩子；這就是所謂的b占據a的位置！ 5. 哈希表： 1) 構造方法： a) 直接定址法：取關鍵字或關鍵字的某個線性函數值為散列地址。即H(key)=key或H(key) = akey + b，其中a和b為常數（這種散列函數叫做自身函數）。若其中H(key）中已經有值了，就往下一個找，直到H(key）中沒有值了，就放進去。 b) 數字分析法：分析一組數據，比如一組員工的出生年月日，這時我們發(fā)現出生年月日的前幾位數字大體相同，這樣的話，出現沖突的幾率就會很大，但是我們

32、發(fā)現年月日的后幾位表示月份和具體日期的數字差別很大，如果用后面的數字來構成散列地址，則沖突的幾率會明顯降低。因此數字分析法就是找出數字的規(guī)律，盡可能利用這些數據來構造沖突幾率較低的散列地址。 c) 平方取中法：當無法確定關鍵字中哪幾位分布較均勻時，可以先求出關鍵字的平方值，然后按需要取平方值的中間幾位作為哈希地址。這是因為：平方后中間幾位和關鍵字中每一位都相關，故不同關鍵字會以較高的概率產生不同的哈希地址。 d) 折疊法：將關鍵字分割成位數相同的幾部分，最后一部分位數可以不同，然后取這幾部分的疊加和（去除進位）作為散列地址。數位疊加可以有移位疊加和間界疊加兩種方法。移位疊加是將分割后的每一

33、部分的最低位對齊，然后相加；間界疊加是從一端向另一端沿分割界來回折疊，然后對齊相加。 e) 除留余數法：取關鍵字被某個不大于散列表表長m的數p除后所得的余數為散列地址。即 H(key) = key MOD p,p<=m。不僅可以對關鍵字直接取模，也可在折疊、平方取中等運算之后取模。對p的選擇很重要，一般取素數或m，若p選的不好，容易產生同義詞。 2) 處理沖突方法： a) 開放定址法：Hi=(H(key) + di) MOD m,i=1,2，…，k(k<=m-1），其中H(key）為散列函數，m為散列表長，di為增量序列，可有下列三種取法： 1.1. di=1,2,3，…，m-1，稱線

34、性探測再散列； 1.2. di=1^2,-1^2,2^2,-2^2，3^2，…，k^2,(k<=m/2）稱二次探測再散列； 1.3. di=偽隨機數序列，稱偽隨機探測再散列。 b) 再哈希法：Hi=RHi(key),i=1,2，…，k RHi均是不同的散列函數，即在同義詞產生地址沖突時計算另一個散列函數地址，直到沖突不再發(fā)生，這種方法不易產生“聚集”，但增加了計算時間。 c) 鏈地址法（拉鏈法）：將所有關鍵字為同義詞的記錄存儲在同一線性鏈表中。假設某哈希函數產生的哈希地址在區(qū)間[0,m-1]上，則設立一個指針型向量Chain ChainHash[m]；其每個分量的初始狀態(tài)都是空指針。

35、凡哈希地址為i的記錄都插入到頭指針為ChainHash[i]的鏈表中。在鏈表中的插入位置可以在表頭或表尾；也可以在中間，以保持同義詞在同一線性鏈表中按關鍵字有序。 d) 建立一個公共溢出區(qū)：假設哈希函數的值域為[0,m-1]，則設向量HashTable[0..m-1]為基本表，每個分量存放一個記錄，另設立向量OverTable[0..v]為溢出表。所有關鍵字和基本表中關鍵字為同義詞的記錄，不管它們有哈希函數得到的哈希地址是什么，一旦發(fā)生沖突，都填入溢出表。 第10章、內部排序 1. 排序：是計算機程序設計中的一種重要操作，它的功能是將一個數據元素（或記錄）的任意序列，重新排列

36、成一個按關鍵字有序的序列。 2. 直接插入排序：將一個記錄插入到已排好序的有序表中，從而得到一個新的、記錄數增1的有序表。 3. 希爾排序（縮小增量排序）：先將整個待排記錄序列分割成若干子序列分別進行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進行一次直接插入排序。 4. 冒泡排序：首先將一個記錄的關鍵字和第二個記錄的關鍵字進行比較，若為逆序（即L.r[1].key>L.r[2].key），則將兩個記錄交換之，然后比較第二個記錄和第三個記錄的關鍵字。以此類推，直至第n-1個記錄和第n個記錄的關鍵字進行過比較為止。 5. 快速排序：通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分記錄的關鍵字小，則可分別對這兩部分記錄繼續(xù)進行排序，以達到整個序列有序。 6. 堆排序：只需要一個記錄大小的輔助空間，每個待排序的記錄僅占有一個存儲空間。