第?26?章?鏈表、二叉樹和哈希表 · Linux C 一站式學習

# 第?26?章?鏈表、二叉樹和哈希表 **目錄** + [1\. 鏈表](ch26s01.html) + [1.1\. 單鏈表](ch26s01.html#id2844144) + [1.2\. 雙向鏈表](ch26s01.html#id2845376) + [1.3\. 靜態鏈表](ch26s01.html#id2845707) + [1.4\. 本節綜合練習](ch26s01.html#id2845773) + [2\. 二叉樹](ch26s02.html) + [2.1\. 二叉樹的基本概念](ch26s02.html#id2845875) + [2.2\. 排序二叉樹](ch26s02.html#id2846120) + [3\. 哈希表](ch26s03.html) ## 1.?鏈表 ### 1.1.?單鏈表 [圖?23.6 “鏈表”](ch23s09.html#pointer.linkedlist)所示的鏈表即單鏈表（Single Linked List），本節我們學習如何創建和操作這種鏈表。每個鏈表有一個頭指針，通過頭指針可以找到第一個節點，每個節點都可以通過指針域找到它的后繼，最后一個節點的指針域為`NULL`，表示沒有后繼。數組在內存中是連續存放的，而鏈表在內存中的布局是不規則的，我們知道訪問某個數組元素`b[n]`時可以通過`基地址+n×每個元素的字節數`得到它地址，或者說數組支持隨機訪問，而鏈表是不支持隨機訪問的，只能通過前一個元素的指針域得知后一個元素的地址，因此只能從頭指針開始順序訪問各節點。以下代碼實現了單鏈表的基本操作。 **例?26.1.?單鏈表** ``` /* linkedlist.h */ #ifndef LINKEDLIST_H #define LINKEDLIST_H typedef struct node *link; struct node { unsigned char item; link next; }; link make_node(unsigned char item); void free_node(link p); link search(unsigned char key); void insert(link p); void delete(link p); void traverse(void (*visit)(link)); void destroy(void); void push(link p); link pop(void); #endif ``` ``` /* linkedlist.c */ #include <stdlib.h> #include "linkedlist.h" static link head = NULL; link make_node(unsigned char item) { link p = malloc(sizeof *p); p->item = item; p->next = NULL; return p; } void free_node(link p) { free(p); } link search(unsigned char key) { link p; for (p = head; p; p = p->next) if (p->item == key) return p; return NULL; } void insert(link p) { p->next = head; head = p; } void delete(link p) { link pre; if (p == head) { head = p->next; return; } for (pre = head; pre; pre = pre->next) if (pre->next == p) { pre->next = p->next; return; } } void traverse(void (*visit)(link)) { link p; for (p = head; p; p = p->next) visit(p); } void destroy(void) { link q, p = head; head = NULL; while (p) { q = p; p = p->next; free_node(q); } } void push(link p) { insert(p); } link pop(void) { if (head == NULL) return NULL; else { link p = head; head = head->next; return p; } } ``` ``` /* main.c */ #include <stdio.h> #include "linkedlist.h" void print_item(link p) { printf("%d\n", p->item); } int main(void) { link p = make_node(10); insert(p); p = make_node(5); insert(p); p = make_node(90); insert(p); p = search(5); delete(p); free_node(p); traverse(print_item); destroy(); p = make_node(100); push(p); p = make_node(200); push(p); p = make_node(250); push(p); while (p = pop()) { print_item(p); free_node(p); } return 0; } ``` 在初始化時把頭指針`head`初始化為`NULL`，表示空鏈表。然后`main`函數調用`make_node`創建幾個節點，分別調用`insert`插入到鏈表中。 ``` void insert(link p) { p->next = head; head = p; } ``` **圖?26.1.?鏈表的插入操作** ![鏈表的插入操作](https://box.kancloud.cn/2016-04-02_56ff80d6bf684.png) 正如上圖所示，`insert`函數雖然簡單，其中也隱含了一種特殊情況（Special Case）的處理，當`head`為`NULL`時，執行`insert`操作插入第一個節點之后，`head`指向第一個節點，而第一個節點的`next`指針域成為`NULL`，這很合理，因為它也是最后一個節點。所以空鏈表雖然是一種特殊情況，卻不需要特殊的代碼來處理，和一般情況用同樣的代碼處理即可，這樣寫出來的代碼更簡潔，但是在讀代碼時要想到可能存在的特殊情況。當然，`insert`函數傳進來的參數`p`也可能有特殊情況，傳進來的`p`可能是`NULL`，甚至是野指針，本章的函數代碼都假定調用者的傳進來的參數是合法的，不對參數做特別檢查。事實上，對指針參數做檢查是不現實的，如果傳進來的是`NULL`還可以檢查一下，如果傳進來的是野指針，根本無法檢查它指向的內存單元是不是合法的，C標準庫的函數通常也不做這種檢查，例如`strcpy(p, NULL)`就會引起段錯誤。接下來`main`函數調用`search`在鏈表中查找某個節點，如果找到就返回指向該節點的指針，找不到就返回`NULL`。 ``` link search(unsigned char key) { link p; for (p = head; p; p = p->next) if (p->item == key) return p; return NULL; } ``` `search`函數其實也隱含了對于空鏈表這種特殊情況的處理，如果是空鏈表則循環體一次都不執行，直接返回`NULL`。然后`main`函數調用`delete`從鏈表中摘除用`search`找到的節點，最后調用`free_node`釋放它的存儲空間。 ``` void delete(link p) { link pre; if (p == head) { head = p->next; return; } for (pre = head; pre; pre = pre->next) if (pre->next == p) { pre->next = p->next; return; } } ``` **圖?26.2.?鏈表的刪除操作** ![鏈表的刪除操作](https://box.kancloud.cn/2016-04-02_56ff80d6d02f9.png) 從上圖可以看出，要摘除一個節點需要首先找到它的前趨然后才能做摘除操作，而在單鏈表中通過某個節點只能找到它的后繼而不能找到它的前趨，所以刪除操作要麻煩一些，需要從第一個節點開始依次查找要摘除的節點的前趨。`delete`操作也要處理一種特殊情況，如果要摘除的節點是鏈表的第一個節點，它是沒有前趨的，這種情況要用特殊的代碼處理，而不能和一般情況用同樣的代碼處理。這樣很不爽，能不能把這種特殊情況轉化為一般情況呢？可以把`delete`函數改成這樣： ``` void delete(link p) { link *pnext; for (pnext = &head; *pnext; pnext = &(*pnext)->next) if (*pnext == p) { *pnext = p->next; return; } } ``` **圖?26.3.?消除特殊情況的鏈表刪除操作** ![消除特殊情況的鏈表刪除操作](https://box.kancloud.cn/2016-04-02_56ff80d6e618f.png) 定義一個指向指針的指針`pnext`，在`for`循環中`pnext`遍歷的是指向鏈表中各節點的指針域，這樣就把`head`指針和各節點的`next`指針統一起來了，可以在一個循環中處理。然后`main`函數調用`traverse`函數遍歷整個鏈表，調用`destroy`函數銷毀整個鏈表。請讀者自己閱讀這兩個函數的代碼。如果限定每次只在鏈表的頭部插入和刪除元素，就形成一個LIFO的訪問序列，所以在鏈表頭部插入和刪除元素的操作實現了堆棧的`push`和`pop`操作，`main`函數的最后幾步把鏈表當成堆棧來操作，從打印的結果可以看到出棧的順序和入棧是相反的。想一想，用鏈表實現的堆棧和[第?2?節 “堆棧”](ch12s02.html#stackqueue.stack)中用數組實現的堆棧相比有什么優點和缺點？ #### 習題 1、修改`insert`函數實現插入排序的功能，鏈表中的數據按從小到大排列，每次插入數據都要在鏈表中找到合適的位置再插入。在[第?6?節 “折半查找”](ch11s06.html#sortsearch.binary)中我們看到，如果數組中的元素是有序排列的，可以用折半查找算法更快地找到某個元素，想一想如果鏈表中的節點是有序排列的，是否適用折半查找算法？為什么？ 2、基于單鏈表實現隊列的`enqueue`和`dequeue`操作。在鏈表的末尾再維護一個指針`tail`，在`tail`處`enqueue`，在`head`處`dequeue`。想一想能不能反過來，在`head`處`enqueue`而在`tail`處`dequeue`？ 3、實現函數`void reverse(void);`將單鏈表反轉。如下圖所示。 **圖?26.4.?單鏈表的反轉** ![單鏈表的反轉](https://box.kancloud.cn/2016-04-02_56ff80d703b28.png) ### 1.2.?雙向鏈表鏈表的`delete`操作需要首先找到要摘除的節點的前趨，而在單鏈表中找某個節點的前趨需要從表頭開始依次查找，對于n個節點的鏈表，刪除操作的時間復雜度為O(n)。可以想像得到，如果每個節點再維護一個指向前趨的指針，刪除操作就像插入操作一樣容易了，時間復雜度為O(1)，這稱為雙向鏈表（Doubly Linked List）。要實現雙向鏈表只需在上一節代碼的基礎上改動兩個地方。在`linkedlist.h`中修改鏈表節點的結構體定義： ``` struct node { unsigned char item; link prev, next; }; ``` 在`linkedlist.c`中修改`insert`和`delete`函數： ``` void insert(link p) { p->next = head; if (head) head->prev = p; head = p; p->prev = NULL; } void delete(link p) { if (p->prev) p->prev->next = p->next; else head = p->next; if (p->next) p->next->prev = p->prev; } ``` **圖?26.5.?雙向鏈表** ![雙向鏈表](https://box.kancloud.cn/2016-04-02_56ff80d713808.png) 由于引入了`prev`指針，`insert`和`delete`函數中都有一些特殊情況需要用特殊的代碼處理，不能和一般情況用同樣的代碼處理，這非常不爽，如果在表頭和表尾各添加一個Sentinel節點（這兩個節點只用于界定表頭和表尾，不保存數據），就可以把這些特殊情況都轉化為一般情況了。 **例?26.2.?帶Sentinel的雙向鏈表** ``` /* doublylinkedlist.h */ #ifndef DOUBLYLINKEDLIST_H #define DOUBLYLINKEDLIST_H typedef struct node *link; struct node { unsigned char item; link prev, next; }; link make_node(unsigned char item); void free_node(link p); link search(unsigned char key); void insert(link p); void delete(link p); void traverse(void (*visit)(link)); void destroy(void); void enqueue(link p); link dequeue(void); #endif ``` ``` /* doublylinkedlist.c */ #include <stdlib.h> #include "doublylinkedlist.h" struct node tailsentinel; struct node headsentinel = {0, NULL, &tailsentinel}; struct node tailsentinel = {0, &headsentinel, NULL}; static link head = &headsentinel; static link tail = &tailsentinel; link make_node(unsigned char item) { link p = malloc(sizeof *p); p->item = item; p->prev = p->next = NULL; return p; } void free_node(link p) { free(p); } link search(unsigned char key) { link p; for (p = head->next; p != tail; p = p->next) if (p->item == key) return p; return NULL; } void insert(link p) { p->next = head->next; head->next->prev = p; head->next = p; p->prev = head; } void delete(link p) { p->prev->next = p->next; p->next->prev = p->prev; } void traverse(void (*visit)(link)) { link p; for (p = head->next; p != tail; p = p->next) visit(p); } void destroy(void) { link q, p = head->next; head->next = tail; tail->prev = head; while (p != tail) { q = p; p = p->next; free_node(q); } } void enqueue(link p) { insert(p); } link dequeue(void) { if (tail->prev == head) return NULL; else { link p = tail->prev; delete(p); return p; } } ``` ``` /* main.c */ #include <stdio.h> #include "doublylinkedlist.h" void print_item(link p) { printf("%d\n", p->item); } int main(void) { link p = make_node(10); insert(p); p = make_node(5); insert(p); p = make_node(90); insert(p); p = search(5); delete(p); free_node(p); traverse(print_item); destroy(); p = make_node(100); enqueue(p); p = make_node(200); enqueue(p); p = make_node(250); enqueue(p); while (p = dequeue()) { print_item(p); free_node(p); } return 0; } ``` **圖?26.6.?帶Sentinel的雙向鏈表** ![帶Sentinel的雙向鏈表](https://box.kancloud.cn/2016-04-02_56ff80d7210a3.png) 這個例子也實現了隊列的`enqueue`和`dequeue`操作，現在每個節點有了`prev`指針，可以反過來在`head`處`enqueue`而在`tail`處`dequeue`了。現在結合[第?5?節 “環形隊列”](ch12s05.html#stackqueue.circular)想一想，其實用鏈表實現環形隊列是最自然的，以前基于數組實現環形隊列，我們還需要“假想”它是首尾相接的，而如果基于鏈表實現環形隊列，我們本來就可以用指針串成首尾相接的。把上面的程序改成環形鏈表（Circular Linked List）也非常簡單，只需要把`doublylinkedlist.c`中的 ``` struct node tailsentinel; struct node headsentinel = {0, NULL, &tailsentinel}; struct node tailsentinel = {0, &headsentinel, NULL}; static link head = &headsentinel; static link tail = &tailsentinel; ``` 改成： ``` struct node sentinel = {0, &sentinel, &sentinel}; static link head = &sentinel; ``` 再把`doublylinkedlist.c`中所有的`tail`替換成`head`即可，相當于把`head`和`tail`合二為一了。 **圖?26.7.?環形鏈表** ![環形鏈表](https://box.kancloud.cn/2016-04-02_56ff80d735e29.png) ### 1.3.?靜態鏈表回想一下我們在[例?12.4 “用廣度優先搜索解迷宮問題”](ch12s04.html#stackqueue.bfs)中使用的數據結構，我把圖重新畫在下面。 **圖?26.8.?廣度優先搜索的隊列數據結構** ![廣度優先搜索的隊列數據結構](https://box.kancloud.cn/2016-04-02_56ff80d2448f8.png) 這是一個靜態分配的數組，每個數組元素都有`row`、`col`和`predecessor`三個成員，`predecessor`成員保存一個數組下標，指向數組中的另一個元素，這其實也是鏈表的一種形式，稱為靜態鏈表，例如上圖中的第6、4、2、1、0個元素串成一條鏈表。 ### 1.4.?本節綜合練習 1、Josephus是公元1世紀的著名歷史學家，相傳在一次戰役中他和另外幾個人被圍困在山洞里，他們寧死不屈，決定站成一圈，每次數到三個人就殺一個，直到全部死光為止。Josephus和他的一個朋友不想死，于是串通好了站在適當的位置上，最后只剩下他們倆的時候這個游戲就停止了。如果一開始的人數為`N`，每次數到`M`個人就殺一個，那么要想不死應該站在什么位置呢？這個問題比較復雜，[[具體數學]](bi01.html#bibli.concrete "Concrete Mathematics")的1.3節研究了Josephus問題的解，有興趣的讀者可以參考。現在我們做個比較簡單的練習，用鏈表模擬Josephus他們玩的這個游戲，`N`和`M`作為命令行參數傳入，每個人的編號依次是1~N，打印每次被殺者的編號，打印最后一個幸存者的編號。 2、在[第?2.11?節 “本節綜合練習”](ch25s02.html#stdlib.ioproblem)的習題1中規定了一種日志文件的格式，每行是一條記錄，由行號、日期、時間三個字段組成，由于記錄是按時間先后順序寫入的，可以看作所有記錄是按日期排序的，對于日期相同的記錄再按時間排序。現在要求從這樣的一個日志文件中讀出所有記錄組成一個鏈表，在鏈表中首先按時間排序，對于時間相同的記錄再按日期排序，最后寫回文件中。比如原文件的內容是： ``` 1 2009-7-30 15:16:42 2 2009-7-30 15:16:43 3 2009-7-31 15:16:41 4 2009-7-31 15:16:42 5 2009-7-31 15:16:43 6 2009-7-31 15:16:44 ``` 重新排序輸出的文件內容是： ``` 1 2009-7-31 15:16:41 2 2009-7-30 15:16:42 3 2009-7-31 15:16:42 4 2009-7-30 15:16:43 5 2009-7-31 15:16:43 6 2009-7-31 15:16:44 ``` ## 2.?二叉樹 ### 2.1.?二叉樹的基本概念鏈表的每個節點可以有一個后繼，而二叉樹（Binary Tree）的每個節點可以有兩個后繼。比如這樣定義二叉樹的節點： ``` typedef struct node *link; struct node { unsigned char item; link l, r; }; ``` 這樣的節點可以組織成下圖所示的各種形態。 **圖?26.9.?二叉樹的定義和舉例** ![二叉樹的定義和舉例](https://box.kancloud.cn/2016-04-02_56ff80d74fb67.png) 二叉樹可以這樣遞歸地定義： 1. 就像鏈表有頭指針一樣，每個二叉樹都有一個根指針（上圖中的`root`指針）指向它。根指針可以是`NULL`，表示空二叉樹，或者 2. 根指針可以指向一個節點，這個節點除了有數據成員之外還有兩個指針域，這兩個指針域又分別是另外兩個二叉樹（左子樹和右子樹）的根指針。上圖舉例示意了幾種情況。 * 單節點的二叉樹：左子樹和右子樹都是空二叉樹。 * 只有左子樹的二叉樹：右子樹是空二叉樹。 * 只有右子樹的二叉樹：左子樹是空二叉樹。 * 一般的二叉樹：左右子樹都不為空。注意右側由圈和線段組成的簡化圖示，以后我們都采用這種簡化圖示法，在圈中標上該節點數據成員的值。鏈表的遍歷方法是顯而易見的：從前到后遍歷即可。二叉樹是一種樹狀結構，如何做到把所有節點都走一遍不重不漏呢？有以下幾種方法： **圖?26.10.?二叉樹的遍歷** ![二叉樹的遍歷](https://box.kancloud.cn/2016-04-02_56ff80d7690b0.png) 前序（Pre-order Traversal）、中序（In-order Traversal）、后序遍歷（Post-order Traversal）和深度優先搜索的順序類似，層序遍歷（Level-order Traversal）和廣度優先搜索的順序類似。前序和中序遍歷的結果合在一起可以唯一確定二叉樹的形態，也就是說根據遍歷結果可以構造出二叉樹。過程如下圖所示： **圖?26.11.?根據前序和中序遍歷結果構造二叉樹** ![根據前序和中序遍歷結果構造二叉樹](https://box.kancloud.cn/2016-04-02_56ff80d77c331.png) 想一想，根據中序和后序遍歷結果能否構造二叉樹？根據前序和后序遍歷結果能否構造二叉樹？ **例?26.3.?二叉樹** ``` /* binarytree.h */ #ifndef BINARYTREE_H #define BINARYTREE_H typedef struct node *link; struct node { unsigned char item; link l, r; }; link init(unsigned char VLR[], unsigned char LVR[], int n); void pre_order(link t, void (*visit)(link)); void in_order(link t, void (*visit)(link)); void post_order(link t, void (*visit)(link)); int count(link t); int depth(link t); void destroy(link t); #endif ``` ``` /* binarytree.c */ #include <stdlib.h> #include "binarytree.h" static link make_node(unsigned char item) { link p = malloc(sizeof *p); p->item = item; p->l = p->r = NULL; return p; } static void free_node(link p) { free(p); } link init(unsigned char VLR[], unsigned char LVR[], int n) { link t; int k; if (n <= 0) return NULL; for (k = 0; VLR[0] != LVR[k]; k++); t = make_node(VLR[0]); t->l = init(VLR+1, LVR, k); t->r = init(VLR+1+k, LVR+1+k, n-k-1); return t; } void pre_order(link t, void (*visit)(link)) { if (!t) return; visit(t); pre_order(t->l, visit); pre_order(t->r, visit); } void in_order(link t, void (*visit)(link)) { if (!t) return; in_order(t->l, visit); visit(t); in_order(t->r, visit); } void post_order(link t, void (*visit)(link)) { if (!t) return; post_order(t->l, visit); post_order(t->r, visit); visit(t); } int count(link t) { if (!t) return 0; return 1 + count(t->l) + count(t->r); } int depth(link t) { int dl, dr; if (!t) return 0; dl = depth(t->l); dr = depth(t->r); return 1 + (dl > dr ? dl : dr); } void destroy(link t) { post_order(t, free_node); } ``` ``` /* main.c */ #include <stdio.h> #include "binarytree.h" void print_item(link p) { printf("%d", p->item); } int main() { unsigned char pre_seq[] = { 4, 2, 1, 3, 6, 5, 7 }; unsigned char in_seq[] = { 1, 2, 3, 4, 5, 6, 7 }; link root = init(pre_seq, in_seq, 7); pre_order(root, print_item); putchar('\n'); in_order(root, print_item); putchar('\n'); post_order(root, print_item); putchar('\n'); printf("count=%d depth=%d\n", count(root), depth(root)); destroy(root); return 0; } ``` #### 習題 1、本節描述了二叉樹的遞歸定義，想一想單鏈表的遞歸定義應該怎么表述？請仿照本節的例子用遞歸實現單鏈表的各種操作函數： ``` link init(unsigned char elements[], int n); void pre_order(link t, void (*visit)(link)); void post_order(link t, void (*visit)(link)); int count(link t); void destroy(link t); ``` ### 2.2.?排序二叉樹排序二叉樹（BST，Binary Search Tree）具有這樣的性質：對于二叉樹中的任意節點，如果它有左子樹或右子樹，則該節點的數據成員大于左子樹所有節點的數據成員，且小于右子樹所有節點的數據成員。排序二叉樹的中序遍歷結果是從小到大排列的，其實上一節的[圖?26.10 “二叉樹的遍歷”](ch26s02.html#linkedlist.binarytraverse)就是排序二叉樹。 **例?26.4.?排序二叉樹** ``` /* bst.h */ #ifndef BST_H #define BST_H typedef struct node *link; struct node { unsigned char item; link l, r; }; link search(link t, unsigned char key); link insert(link t, unsigned char key); link delete(link t, unsigned char key); void print_tree(link t); #endif ``` ``` /* bst.c */ #include <stdlib.h> #include <stdio.h> #include "bst.h" static link make_node(unsigned char item) { link p = malloc(sizeof *p); p->item = item; p->l = p->r = NULL; return p; } static void free_node(link p) { free(p); } link search(link t, unsigned char key) { if (!t) return NULL; if (t->item > key) return search(t->l, key); if (t->item < key) return search(t->r, key); /* if (t->item == key) */ return t; } link insert(link t, unsigned char key) { if (!t) return make_node(key); if (t->item > key) /* insert to left subtree */ t->l = insert(t->l, key); else /* if (t->item <= key), insert to right subtree */ t->r = insert(t->r, key); return t; } link delete(link t, unsigned char key) { link p; if (!t) return NULL; if (t->item > key) /* delete from left subtree */ t->l = delete(t->l, key); else if (t->item < key) /* delete from right subtree */ t->r = delete(t->r, key); else { /* if (t->item == key) */ if (t->l == NULL && t->r == NULL) { /* if t is leaf node */ free_node(t); t = NULL; } else if (t->l) { /* if t has left subtree */ /* replace t with the rightmost node in left subtree */ for (p = t->l; p->r; p = p->r); t->item = p->item; t->l = delete(t->l, t->item); } else { /* if t has right subtree */ /* replace t with the leftmost node in right subtree */ for (p = t->r; p->l; p = p->l); t->item = p->item; t->r = delete(t->r, t->item); } } return t; } void print_tree(link t) { if (t) { printf("("); printf("%d", t->item); print_tree(t->l); print_tree(t->r); printf(")"); } else printf("()"); } ``` ``` /* main.c */ #include <stdio.h> #include <stdlib.h> #include <time.h> #include "bst.h" #define RANGE 100 #define N 6 void print_item(link p) { printf("%d", p->item); } int main() { int i, key; link root = NULL; srand(time(NULL)); for (i = 0; i < N; i++) root = insert(root, rand() % RANGE); printf("\t\\tree"); print_tree(root); printf("\n\n"); while (root) { key = rand() % RANGE; if (search(root, key)) { printf("delete %d in tree\n", key); root = delete(root, key); printf("\t\\tree"); print_tree(root); printf("\n\n"); } } } ``` ``` $ ./a.out \tree(83(77(15()(35()()))())(86()(93()()))) delete 86 in tree \tree(83(77(15()(35()()))())(93()())) delete 35 in tree \tree(83(77(15()())())(93()())) delete 93 in tree \tree(83(77(15()())())()) delete 15 in tree \tree(83(77()())()) delete 83 in tree \tree(77()()) delete 77 in tree \tree() ``` 程序的運行結果可以用Greg Lee編寫的The Tree Preprocessor（[http://www.essex.ac.uk/linguistics/clmt/latex4ling/trees/tree/](http://www.essex.ac.uk/linguistics/clmt/latex4ling/trees/tree/)）轉換成樹形： ``` $ ./a.out | ./tree/tree 83 ___|___ | | 77 86 _|__ _|__ | | | | 15 93 _|__ _|__ | | | | 35 _|__ | | delete 86 in tree 83 ___|___ | | 77 93 _|__ _|__ | | | | 15 _|__ | | 35 _|__ | | delete 35 in tree 83 ___|___ | | 77 93 _|__ _|__ | | | | 15 _|__ | | delete 93 in tree 83 _|__ | | 77 _|__ | | 15 _|__ | | delete 15 in tree 83 _|__ | | 77 _|__ | | delete 83 in tree 77 _|__ | | delete 77 in tree ``` ## 3.?哈希表下圖示意了哈希表（Hash Table）這種數據結構。 **圖?26.12.?哈希表** ![哈希表](https://box.kancloud.cn/2016-04-02_56ff80d78f7df.png) 如上圖所示，首先分配一個指針數組，數組的每個元素是一個鏈表的頭指針，每個鏈表稱為一個槽（Slot）。哪個數據應該放入哪個槽中由哈希函數決定，在這個例子中我們簡單地選取哈希函數h(x) = x % 11，這樣任意數據x都可以映射成0~10之間的一個數，就是槽的編號，將數據放入某個槽的操作就是鏈表的插入操作。如果每個槽里至多只有一個數據，可以想像這種情況下`search`、`insert`和`delete`操作的時間復雜度都是O(1)，但有時會有多個數據被哈希函數映射到同一個槽中，這稱為碰撞（Collision），設計一個好的哈希函數可以把數據比較均勻地分布到各個槽中，盡量避免碰撞。如果能把n個數據比較均勻地分布到m個槽中，每個糟里約有n/m個數據，則`search`、`insert`和`delete`和操作的時間復雜度都是O(n/m)，如果n和m的比是常數，則時間復雜度仍然是O(1)。一般來說，要處理的數據越多，構造哈希表時分配的槽也應該越多，所以n和m成正比這個假設是成立的。請讀者自己編寫程序構造這樣一個哈希表，并實現`search`、`insert`和`delete`操作。如果用我們學過的各種數據結構來表示n個數據的集合，下表是`search`、`insert`和`delete`操作在平均情況下的時間復雜度比較。 **表?26.1.?各種數據結構的search、insert和delete操作在平均情況下的時間復雜度比較** | 數據結構 | search | insert | delete | | --- | --- | --- | --- | | 數組 | O(n)，有序數組折半查找是O(lgn) | O(n) | O(n) | | 雙向鏈表 | O(n) | O(1) | O(1) | | 排序二叉樹 | O(lgn) | O(lgn) | O(lgn) | | 哈希表（n與槽數m成正比） | O(1) | O(1) | O(1) | ### 習題 1、統計一個文本文件中每個單詞的出現次數，然后按出現次數排序并打印輸出。單詞由連續的英文字母組成，不區分大小寫。 2、實現一個函數求兩個數組的交集：`size_t intersect(const int a[], size_t nmema, const int b[], size_t nmemb, int c[], size_t nmemc);`。數組元素是32位`int`型的。數組`a`有`nmema`個元素且各不相同，數組`b`有`nmemb`個元素且各不相同。要求找出數組`a`和數組`b`的交集保存到數組`c`中，`nmemc`是數組`c`的最大長度，返回值表示交集中實際有多少個元素，如果交集中實際的元素數量超過了`nmemc`則返回`nmemc`個元素。數組`a`和數組`b`的元素數量可能會很大（比如上百萬個），需要設計盡可能快的算法。