近日周立功教授公開了數年的心血之作《程序設計與數據結構》，電子版已無償性分享到電子工程師與高校群體下載，經周立功教授授權，特對本書內容進行連載。

>>>>1.1.1 哈希表的實現

1. 初始化

hash_db_init()接口用于哈希表實例的初始化，在定義哈希表結構體類型時，哈希表數組大小、記錄長度、關鍵字長度和哈希函數都需要由用戶根據實際情況確定，其函數原型定義如下（hash_db.h）：

int hash_db_init (

hash_db_t *p_hash, //指向哈希表實例的指針

unsigned int size, //哈希表大小

unsigned int key_len, //關鍵字長度

unsigned int value_len, //記錄長度

hash_func_t pfn_hash); //哈希函數

在這里，以學生記錄為例，創建一個大小為250組的哈希表：

hash_db_t hash_students;

hash_db_init(

&hash_students,

250, //大小為250

6, //關鍵字長度為6字節

sizeof(student_t), //記錄的長度

(hash_func_t)db_id_to_idx); //哈希函數

在初始化函數的實現中，需要按照size指定的大小分配內存，用于存儲哈希表的各個表項（鏈表頭），接著需要完成各個鏈表頭和結構體成員的初始化，初始化函數的實現范例詳見程序清單3.63。

程序清單3.63初始化函數范例程序

1 int hash_db_init (hash_db_t *p_hash, unsigned int size, unsigned int key_len,

2 unsigned int value_len, hash_func_t pfn_hash)

3 {

4 int i;

5 if ((p_hash == NULL) || (pfn_hash == NULL)){

6 return NULL;

7 }

8 p_hash -> p_head = (slist_head_t *)malloc(size * sizeof(slist_head_t));

9 if (p_hash -> p_head == NULL) {

10 return -1;

11 }

12 for (i = 0; i < size; i++){

13 slist_init(&p_hash -> p_head[i]);

14 }

15 p_hash -> size = size;

16 p_hash -> key_len = key_len;

17 p_hash -> value_len = value_len;

18 p_hash -> pfn_hash = pfn_hash;

19 return 0;

20 }

2. 添加記錄

hash_db_add()接口用于向已經初始化的哈希表中添加一條記錄，添加一條記錄時，需要指定關鍵字信息和記錄值信息，其函數原型定義（hash_db.h）：

int hash_db_add (hash_db_t *p_hash, void *key, const void *value);

其中，p_hash為指向哈希表實例的指針，key為指向關鍵字的指針，value為指向記錄值的指針。特別地，由于在添加記錄時，程序不會修改key和value指針所指向的值，因此，指針都加了const修飾符。以添加一條學生記錄為例，使用范例如下：

student_t stu = {

"zhangsan",

'M',

173.3,

60

};

unsigned char id[6] = {0x20, 0x14, 0x44, 0x70, 0x02, 0x39};

hash_db_add(&hash_students, id, &stu);

在添加記錄函數的實現中，首先需要使用哈希函數找到關鍵字對應的記錄在哈希表中的索引，以確定該條記錄所在鏈表的表頭，然后分配一個存儲記錄的結點空間，將關鍵字、記錄等信息存儲在該空間中，然后將結點添加到對應鏈表的頭部（由于記錄在鏈表中的具體位置不重要，因此直接添加在鏈表頭部，效率更高）。函數實現的范例詳見程序清單3.64。

程序清單3.64添加記錄函數范例程序

1 int hash_db_add (hash_db_t *p_hash, const void *key, const void *value)

2 {

3 int idx = p_hash -> pfn_hash(key); //使用哈希函數通過關鍵字得到哈希值

4 //分配內存，存儲鏈表結點+關鍵字+記錄

5 char *p_mem = (char *)malloc(sizeof(slist_node_t) + p_hash -> key_len + p_hash -> value_len);

6 if (p_mem == NULL) {

7 return -1;

8 }

9 memcpy(p_mem + sizeof(slist_node_t), key, p_hash -> key_len); //存儲關鍵字

10 memcpy(p_mem + sizeof(slist_node_t) + p_hash->key_len, value, p_hash->value_len); //存儲記錄

11 return slist_add_head(&p_hash -> p_head[idx], (slist_node_t *)p_mem); //將結點加入鏈表

12 }

程序分配了一個結點的空間，該結點的空間需要存儲一個slist_node_t類型鏈表結點，便于添加結點到鏈表中，存儲長度為p_hash->key_len的關鍵字，存儲長度為p_hash->value_len的記錄值，詳見圖3.26，其內存的大小為：

sizeof(slist_node_t) + p_hash -> key_len + p_hash -> value_len

圖3.26 結點存儲空間

由于結點空間的首部用于存儲結點slist_node_t的值以組織鏈表。因此需要將結點添加到鏈表中時，直接將p_mem轉換為slist_node_t*類型使用即可，通用鏈式哈希表的結構示意圖詳見圖3.27。

圖3.27 通用的鏈式哈希表結構示意圖

與圖3.25中管理學生記錄的鏈式哈希表結構示意圖對比發現，它們表達的含義是完全一致的，僅僅是具體類型變為了更加通用的void *類型。

3. 查找記錄

hash_db_search()接口通過關鍵字查找與之對應的記錄，查找記錄時，需要指定關鍵字信息，同時還需要使用一個指向記錄的指針獲取查找到的記錄值，其函數原型（hash_db.h）如下：

int hash_db_search(hash_db_t *p_hash,const void *key, void *value);

雖然參數與添加記錄是完全一樣的，但value表示的含義卻不一樣，此處的value是輸出參數，用于得到查找到的記錄值。而添加記錄函數中的value是輸入參數，提供需要存儲的記錄值。由于此處的value指向指向的值是需要被改變的（改變為查找到的記錄值），因此，其不能增加const修飾符。以查找ID為201444700239的學生記錄為例，使用范例如下：

student_t stu;

unsigned char id[6] = {0x20, 0x14, 0x44, 0x70, 0x02, 0x39};

if (hash_db_search(&hash_students, id, &stu) == 0) {

//查找到該學號的學生記錄

} else {

//查找失敗，未找到該學號的學生記錄

}

在該函數的實現中，首先需要使用哈希函數找到關鍵字對應的記錄在哈希表中的索引，以確定該條記錄所在鏈表的表頭，然后遍歷鏈表的各個結點，將提供的關鍵字與結點中存儲的關鍵字比對，直到找到關鍵字完全一致的記錄（查找成功）或鏈表遍歷結束（查找失敗）。找到該記錄對應的結點后，將結點中存儲的value值拷貝到參數value指針指向的空間中即可。函數實現的范例詳見程序清單3.65。

程序清單3.65查找記錄函數范例程序

1 //尋找結點的上下文（僅內部使用）

2 struct _node_find_ctx {

3 void *key; //查找關鍵字

4 unsigned int key_len; //關鍵字長度

5 slist_node_t *p_result; //用于存儲查找到的結點

6 };

7

8 //遍歷鏈表的回調函數，查找指定結點

9 static int __hash_db_node_find (void *p_arg, slist_node_t *p_node)

10 {

11 struct _node_find_ctx *p_info = (struct _node_find_ctx *)p_arg; //用戶參數為尋找結點的上下文

12 char *p_mem = (char *)p_node + sizeof(slist_node_t); //關鍵字存儲在結點之后

13

14 if (memcmp(p_mem, p_info->key, p_info->key_len) == 0) {

15 p_info->p_result = p_node;

16 return -1; //找到該結點，終止遍歷

17 }

18 return 0;

19 }

20

21 int hash_db_search(hash_db_t *p_hash, const void *key, void *value)

22 {

23 int idx = p_hash->pfn_hash(key); //得到關鍵字對應的哈希表的索引

24 struct _node_find_ctx info = {key, p_hash->key_len, NULL}; //設置遍歷鏈表的上下文信息

25 slist_foreach(&p_hash->p_head[idx], __hash_db_node_find, &info); //遍歷，尋找關鍵字對應結點

26

27 if (info.p_result != NULL) { //找到對應結點, 將存儲的記錄值拷貝到用戶提供的空間中

28 memcpy(value, (char *)info.p_result+sizeof(slist_node_t)+p_hash->key_len+p_hash->value_len);

29 return 0;

30 }

31 return -1;

32 }

程序中，由于查找結點時需要遍歷鏈表，關鍵字比對的操作需要在遍歷函數的回調函數中完成，因此，需要將用戶查找記錄使用的關鍵字信息（關鍵字及其長度）提供給回調函數，同時，當查找到記錄時，需要將查找到的結點反饋給調用遍歷函數的主程序。為此，定義了一個內部使用的用于尋找一個結點的上下文結構體：

struct _node_find_ctx {

const void *key; //查找關鍵字

unsigned int key_len; //關鍵字長度

slist_node_t *p_result; //用于存儲查找到的結點

};

調用遍歷函數時，需要提供一個設置好關鍵字信息的結構體作為回調函數的用戶參數。遍歷函數結束時，可以通過該結構體中的p_result成員獲取遍歷結果。

4. 刪除記錄

該接口用于刪除指定關鍵字對應的記錄，可以定義其函數名為：hash_db_del()。刪除記錄時，需要指定關鍵字信息。可以定義函數的原型為：

int hash_db_del(hash_db_t *p_hash, const void *key);

以刪除學號為201444700239的學生記錄為例，使用范例如下：

unsigned char id[6] = {0x20, 0x14, 0x44, 0x70, 0x02, 0x39};

hash_db_del(&hash_students, id);

在該函數的實現中，絕大部分操作與查找記錄是相同的，唯一的不同是，當找到關鍵字對應的結點時，不再需要將記錄值提取出來，直接將該結點刪除即可。函數實現的范例詳見程序清單3.66。

程序清單3.66刪除記錄函數范例程序

1 int hash_db_del (hash_db_t *p_hash, const void *key)

2 {

3 int idx = p_hash->pfn_hash(key); //得到關鍵字對應的哈希表的索引

4 struct _node_find_ctx info = {key, p_hash->key_len, NULL}; //設置遍歷鏈表的上下文信息

5 slist_foreach(&p_hash->p_head[idx], __hash_db_node_find, &info); //遍歷，尋找關鍵字對應結點

6 if (info.p_result != NULL) {

7 slist_del(&p_hash->p_head[idx], info.p_result); //從鏈表中刪除該結點

8 free(info.p_result); //釋放結點空間

9 return 0;

10 }

11 return -1;

12 }

5. 解初始化

對應于哈希表的初始化，用于當不再使用哈希表時，釋放相關的空間。可以定義其函數名為：hash_db_deinit()。需要通過參數指定需要解初始化的哈希表實例，可以定義函數的原型為（hash_db.h）：

int hash_db_deinit (hash_db_t *p_hash);

如不再使用學生信息管理系統，則需使用解初始化函數釋放哈希表的相關資源，使用范例如下：

hash_db_deinit(&hash_students);

在該函數的實現中，需要釋放程序中分配的所有空間，主要包括添加記錄時分配的結點空間，鏈表頭結點數組空間。函數實現詳見程序清單3.67。

程序清單3.67解初始化函數范例程序

1 int hash_db_deinit (hash_db_t *p_hash)

2 {

3 int i;

4 slist_node_t *p_node;

5 for (i = 0; i < p_hash->size; i++) { //釋放哈希表中各個表項中存儲的所有結點

6

7 while (slist_begin_get(&p_hash->p_head[i]) != slist_end_get(&p_hash->p_head[i])) {

8 p_node = slist_begin_get(&p_hash->p_head[i]);

9 slist_del(&p_hash->p_head[i], p_node); //刪除第一個結點

10 free(p_node);

11 }

12 }

13 free(p_hash->p_head); //釋放鏈表頭結點數組空間

15 return 0;

16 }

為便于查閱，如程序清單3.29所示展示了hash_db.h文件的內容。

程序清單3.68 hash_db.h文件內容

1 #pragma once;

2 #include "slist.h"

3

4 typedef unsigned int (*hash_func_t) (const void *key); //哈希函數類型，返回值為整數，參數為關鍵字

5 struct _hash_db{

6 slist_head_t *p_head; //指向數組首地址

7 unsigned int size; //數組成員數

8 unsigned int value_len; //一條記錄的長度

9 unsigned int key_len; //關鍵字的長度

10 hash_func_t pfn_hash; //哈希函數

11 };

12 typedef struct _hash_db *hash_db_t; //指向哈希表對象的指針類型

13

14 int hash_db_init (hash_db_t *p_hash, // 哈希表初始化

15 unsigned int size,

16 unsigned int key_len,

17 unsigned int value_len,

18 hash_func_t pfn_hash);

19

20 int hash_db_add (hash_db_t *p_hash, const void *key,const void *value); //添加記錄

21 int hash_db_del (hash_db_t *p_hash, const void *key); //刪除記錄

22 int hash_db_search(hash_db_t *p_hash, const void *key, void *value); // 查找記錄

23 int hash_db_deinit (hash_db_t *p_hash); //解初始化

以使用該鏈式哈希表管理系統來管理學生記錄為例，綜合范例程序詳見程序清單3.30。

程序清單3.69哈希表綜合范例程序

1 #include

2 #include

3 #include "hash_db.h"

4

5 typedef struct _student{

6 char name[10]; //姓名

7 char sex; //性別

8 float height, weight; //身高、體重

9 } student_t;

10

11 int db_id_to_idx (unsigned char id[6]) //通過ID得到數組索引

12 {

13 int i;

14 int sum = 0;

15 for (i = 0; i < 6; i++){

16 sum += id[0];

17 }

18 return sum % 250;

19 }

20

21 int student_info_generate (unsigned char *p_id, student_t *p_student) //隨機產生一條學生記錄

22 {

23 int i;

24 for (i = 0; i < 6; i++) {?????????????????????????? ?? //?隨機產生一個學號

25 p_id[i] = rand();

26 }

27 for (i = 0; i < 9; i++) {????????????????????????? ???? //?隨機名字，由 'a' ~ 'z' 組成

28 p_student->name[i] = (rand() % ('z' - 'a')) + 'a';

29 }

30 p_student->name[i]= '\0'; //字符串結束符

31 p_student->sex = (rand() & 0x01) ? 'F' : 'M'; //隨機性別

32 p_student->height = (float)rand() / rand();

33 p_student->weight = (float)rand() / rand();

34 return 0;

35 }

36

37 int main ()

38 {

39 student_t stu;

40 unsigned char id[6];

41 int i;

42 hash_db_t hash_students;

43

44 hash_db_init(&hash_students, 250, 6, sizeof(student_t), (hash_func_t)db_id_to_idx);

45

46 for (i = 0; i < 100; i++) {???????????? ?????????? //?添加100個學生的信息

47 student_info_generate(id, &stu); //設置學生的信息，當前一隨機數作為測試

48 if (hash_db_search(&hash_students, id, &stu) == 0) { //查找到已經存在該ID的學生記錄

49 printf("該ID的記錄已經存在！\n");

50 continue;

51 }

52 printf("增加記錄：ID : %02x%02x%02x%02x%02x%02x",id[0],id[1],id[2],id[3],id[4],id[5]);

53 printf("信息： %s %c %.2f %.2f\n", stu.name, stu.sex, stu.height, stu.weight);

54 if (hash_db_add(&hash_students, id, &stu) != 0) {

55 printf("添加失敗");

56 }

57 }

58

59 printf("查找ID為：%02x%02x%02x%02x%02x%02x的信息\n",id[0],id[1],id[2],id[3],id[4],id[5]);

60 if (hash_db_search(&hash_students, id, &stu) == 0) {

61 printf("學生信息： %s %c %.2f %.2f\n", stu.name, stu.sex, stu.height, stu.weight);

62 } else {

63 printf("未找到該ID的記錄！\r\n");

64 }

65 hash_db_deinit(&hash_students);

66 return 0;

67 }

在這里，首先創建了一個哈希表，然后向其中添加了100個學生信息（以隨機數的方式產生的），接著查找了ID對應的學生信息（這里的ID沒有特別設置，即查找最后添加的學生記錄），最后釋放哈希表。