1. hash_db.h
1 #ifndef _HASH_DB_H 2 #define _HASH_DB_H 3 4 #include "slist.h" 5 6 typedef unsigned int (*hash_func_t) (const void *key); //哈希函式型別，回傳值為整數，引數為關鍵字 7 struct _hash_db 8 { 9 slist_head_t *p_head; //指向陣列首地址 10 unsigned int size; //陣列成員數 11 unsigned int value_len; //一條記錄的長度 12 unsigned int key_len; //關鍵字的長度 13 hash_func_t pfn_hash; //哈希函式 14 }; 15 typedef struct _hash_db hash_db_t; //指向哈希表物件的指標型別 16 17 int hash_db_init(hash_db_t *p_hash, //哈希表初始化 18 unsigned int size, 19 unsigned int key_len, 20 unsigned int value_len, 21 hash_func_t pfn_hash); 22 23 int hash_db_add(hash_db_t *p_hash, const void *key,const void *value); //添加記錄 24 int hash_db_del(hash_db_t *p_hash, const void *key); //洗掉記錄 25 int hash_db_search(hash_db_t *p_hash, const void *key, void *value); //查找記錄 26 int hash_db_deinit(hash_db_t *p_hash); //解初始化 27 28 #endif
2. hash_db.c
1 #include "hash_db.h" 2 #include <stdlib.h> 3 #include <string.h> 4 5 /* 尋找結點的背景關系，僅內部使用 */ 6 struct _node_find_ctx 7 { 8 const void *key; //查找關鍵字 9 unsigned int key_len; //關鍵字長度 10 slist_node_t *p_result; //用于存盤查找到的結點 11 }; 12 13 /** 14 * @brief 遍歷鏈表的回呼函式，查找指定結點 15 */ 16 static int __hash_db_node_find (void *p_arg, slist_node_t *p_node) 17 { 18 struct _node_find_ctx *p_info = (struct _node_find_ctx *)p_arg; //用戶引數為尋找結點的背景關系 19 char *p_mem = (char *)p_node + sizeof(slist_node_t); //關鍵字存盤在結點之后 20 21 if (memcmp(p_mem, p_info->key, p_info->key_len) == 0) 22 { 23 p_info->p_result = p_node; 24 return -1; //找到該結點，終止遍歷 25 } 26 return 0; 27 } 28 29 30 /** 31 * @brief 哈希表初始化 32 */ 33 int hash_db_init(hash_db_t *p_hash, 34 unsigned int size, 35 unsigned int key_len, 36 unsigned int value_len, 37 hash_func_t pfn_hash) 38 { 39 int i; 40 if ((p_hash == NULL) || (pfn_hash == NULL)) 41 { 42 return -1; 43 } 44 p_hash->p_head = (slist_head_t *)malloc(size * sizeof(slist_head_t)); 45 if (p_hash->p_head == NULL) 46 { 47 return -1; 48 } 49 for (i = 0; i < size; i++) 50 { 51 slist_init(&p_hash->p_head[i]); 52 } 53 p_hash->size = size; 54 p_hash->key_len = key_len; 55 p_hash->value_len = value_len; 56 p_hash->pfn_hash = pfn_hash; 57 return 0; 58 } 59 60 int hash_db_add(hash_db_t *p_hash, const void *key, const void *value) 61 { 62 int idx = p_hash -> pfn_hash(key); //使用哈希函式通過關鍵字得到哈希值 63 /* 分配記憶體，存盤鏈表結點+關鍵字+記錄 */ 64 char *p_mem = (char *)malloc(sizeof(slist_node_t) + p_hash -> key_len + p_hash -> value_len); 65 if (p_mem == NULL) 66 { 67 return -1; 68 } 69 memcpy(p_mem + sizeof(slist_node_t), key, p_hash -> key_len); //存盤關鍵字 70 memcpy(p_mem + sizeof(slist_node_t) + p_hash->key_len, value, p_hash->value_len); //存盤記錄 71 return slist_add_head(&p_hash -> p_head[idx], (slist_node_t *)p_mem); //將結點加入鏈表 72 } 73 74 int hash_db_del(hash_db_t *p_hash, const void *key) 75 { 76 int idx = p_hash->pfn_hash(key); //得到關鍵字對應哈希表的索引 77 struct _node_find_ctx info = {key, p_hash->key_len, NULL}; //設定遍歷鏈表的背景關系資訊 78 slist_foreach(&p_hash->p_head[idx], __hash_db_node_find, &info); //遍歷，尋找關鍵字對應的結點 79 if (info.p_result != NULL) 80 { 81 slist_del(&p_hash->p_head[idx], info.p_result); //從鏈表中洗掉該結點 82 free(info.p_result); //釋放結點空間 83 return 0; 84 } 85 return -1; 86 } 87 88 int hash_db_search(hash_db_t *p_hash, const void *key, void *value) 89 { 90 int idx = p_hash->pfn_hash(key); ////得到關鍵字對應哈希表的索引 91 struct _node_find_ctx info = {key, p_hash->key_len, NULL}; //設定遍歷鏈表的背景關系資訊 92 slist_foreach(&p_hash->p_head[idx], __hash_db_node_find, &info); //遍歷，尋找關鍵字對應的結點 93 94 if (info.p_result != NULL) 95 { //找到對應結點，將存盤的記錄值拷貝到用戶提供的空間中 96 memcpy(value, (char *)info.p_result+sizeof(slist_node_t)+p_hash->key_len, p_hash->value_len); 97 return 0; 98 } 99 return -1; 100 } 101 102 int hash_db_deinit(hash_db_t *p_hash) 103 { 104 int i; 105 slist_node_t *p_node; 106 for (i = 0; i < p_hash->size; i++) 107 { //釋放哈希表中各個表項中存盤的所有結點 108 109 while (slist_begin_get(&p_hash->p_head[i]) != slist_end_get(&p_hash->p_head[i])) 110 { 111 p_node = slist_begin_get(&p_hash->p_head[i]); 112 slist_del(&p_hash->p_head[i], p_node); //釋放第一個結點 113 free(p_node); 114 } 115 } 116 free(p_hash->p_head); //釋放鏈表頭結點陣列空間 117 return 0; 118 }
3. demo
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include "hash_db.h" 4 5 typedef struct _student 6 { 7 char name[10]; 8 char sex; 9 float height, weight; 10 } student_t; 11 12 int db_id_to_idx(unsigned char id[6]) //通過ID得到陣列索引 13 { 14 int i; 15 int sum = 0; 16 for (i = 0; i < 6; i++) 17 { 18 sum += id[0]; 19 } 20 return sum % 250; 21 } 22 23 int student_info_generate(unsigned char *p_id, student_t *p_student) 24 { 25 int i; 26 for (i = 0; i < 6; i++) 27 { //隨機產生一個學號 28 p_id[i] = rand(); 29 } 30 for (i = 0; i < 9; i++) 31 { 32 p_student->name[i] = (rand() % ('z' - 'a')) + 'a'; 33 } 34 p_student->name[i]= '\0'; 35 p_student->sex = (rand() & 0x01) ? 'F' : 'M'; 36 p_student->height = (float)rand() / rand(); 37 p_student->weight = (float)rand() / rand(); 38 return 0; 39 } 40 41 int main(void) 42 { 43 student_t stu; 44 unsigned char id[6]; 45 int i; 46 hash_db_t hash_students; 47 48 hash_db_init(&hash_students, 250, 6, sizeof(student_t), (hash_func_t)db_id_to_idx); 49 50 for(i = 0; i < 100; i++) 51 { //添加100個學生資訊 52 student_info_generate(id, &stu); //設定學生的資訊，當前一亂數作為測驗 53 if (hash_db_search(&hash_students, id, &stu) == 0) 54 { //查找到該ID已存在的學生記錄 55 printf("該ID的記錄已存在！\n"); 56 continue; 57 } 58 printf("增加記錄：ID : %02x%02x%02x%02x%02x%02x ",id[0],id[1],id[2],id[3],id[4],id[5]); 59 printf("?資訊：%s %c %.2f %.2f\n", stu.name, stu.sex, stu.height, stu.weight); 60 if (hash_db_add(&hash_students, id, &stu) != 0) 61 { 62 printf("添加失敗"); 63 } 64 } 65 printf("查找ID為：%02x%02x%02x%02x%02x%02x的資訊\n",id[0],id[1],id[2],id[3],id[4],id[5]); 66 if (hash_db_search(&hash_students, id, &stu) == 0) 67 { 68 printf("學生資訊：%s %c %.2f %.2f\n", stu.name, stu.sex, stu.height, stu.weight); 69 } 70 else 71 { 72 printf("未找到該ID的記錄\n"); 73 } 74 hash_db_deinit(&hash_students); 75 return 0; 76 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/62083.html
標籤：其他
上一篇：c語言雙向鏈表的實作