哈希表2

哈希表的初始化

void HashInit(HashTable* ht, HashFunc func) { if(ht == NULL) { return; } ht -> size = 0; ht -> func = func; size_t i = 0; for(; i < MaxSize; i++) { ht -> data[i] = NULL; } }

哈希表的结点创建

HashElem* CreateHashElemNode(KeyType key, ValueType value) { HashElem* new_node = (HashElem*)malloc(sizeof(HashElem)); new_node -> key = key; new_node -> value = value; new_node -> next = NULL; return new_node; } void DestroyHashElemNode(HashElem* node) { if(node == NULL) { return; } free(node); }

哈希表的销毁

void HashDestroy(HashTable* ht) { if(ht == NULL) { return; } ht -> size = 0; ht -> func = NULL; size_t i = 0; for(; i < MaxSize; i++) { HashElem* cur = ht -> data[i]; while(cur != NULL) { HashElem* next = cur -> next; DestroyHashElemNode(cur); cur = next; } } }

哈希表的查找

int HashBucketFind(HashElem* node, KeyType key) { if(node == NULL) { return 0; } HashElem* cur = node; while(cur != NULL) { if(cur -> key == key) { return 1; } cur = cur -> next; } return 0; } int HashFind(HashTable* ht, KeyType key, ValueType* value) { if(ht == NULL || value == NULL) { return 0; } size_t offset = ht -> func(key); HashElem* cur = ht -> data[offset]; while(cur != NULL) { if(cur -> key == key) { *value = cur -> value; return 1; } cur = cur -> next; } return 0; } int HashBucketFindEx(HashElem* node, KeyType key, HashElem** cur_node, HashElem** prev_node) { if(node == NULL) { return 0; } if(cur_node == NULL || prev_node == NULL) { return 0; } HashElem* cur = node; HashElem* prev = NULL; while(cur != NULL) { prev = cur; if(cur -> key == key) { break; } cur = cur -> next; } if(cur == NULL) { return 0; } *cur_node = cur; *prev_node = prev; return 1; }

哈希表的插入

void HashInsert(HashTable* ht, KeyType key, ValueType value) { if(ht == NULL) { return; } size_t offset = ht -> func(key); HashElem* new_node = CreateHashElemNode(key, value); int ret = HashBucketFind(ht -> data[offset], key); if(ret == 1) { return; } new_node -> next = ht -> data[offset]; ht -> data[offset] = new_node; ht -> size++; }

哈希表的删除

void HashRemove(HashTable* ht, KeyType key) { if(ht == NULL) { return; } if(ht -> size == 0) { return; } size_t offset = ht -> func(key); HashElem* cur = NULL; HashElem* prev = NULL; int ret = HashBucketFindEx(ht -> data[offset], key, &cur, &prev); if(ret == 0) { return;//没有找到 } if(prev == NULL) { ht -> data[offset] = cur -> next; } else { prev -> next = cur -> next; } DestroyHashElemNode(cur); cur = NULL; ht -> size--; }