【数据结构】哈希表的基本操作

这个哈希表如果出现哈希冲突，用的是闭散列的方法，继续往后面插入

这些代码主要实现的功能有：

创建哈希表，然后实现哈希表的插入删除和查找，是一个通用的哈希表

插入时，如果当前位置的statu为valid，表示该位置已经有元素了，就不能插入了

否则，无论是invalid还是empty表示都可以插入，invalid表示该位置元素被删除了

删除一个元素时，如果当前元素位置为valid，而且和要删除的元素一样，就可以删除，

删除完成之后把状态标志位置为invalid

查找，跟上面差不多，只需要把具体条件想清楚就好了。

代码如下：

HashTable.h

#pragma once #include#define HASHTABLEMAX 1000typedef int HashType;
typedef int ValueType;typedef enum Status{Empty,Valid,Invalid
}Statu;typedef size_t (*HashFunc)(HashType);typedef struct HashElem{HashType key;ValueType value;Statu Statu;
}HashElem;typedef struct HashTable{HashElem data[HASHTABLEMAX];size_t size;HashFunc hash_func;
}HashTable;/*初始化*/
void HashTableInit(HashTable* ht);/*插入*/
void HashTableInsert(HashTable* ht, HashType key, ValueType value);/*
**查找
**输入key，查找key对应的value
*/
int HashTableFind(HashTable* ht, HashType key, ValueType* value);/*删除*/
void HashTableRemove(HashTable* ht, HashType key);int HashEmpty(HashTable* ht);size_t HashTableSize(HashTable* ht);void HashDestory(HashTable* ht);

HashTable.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"HashTable.h"
#includesize_t Hash_Func(HashType key) {return key % HASHTABLEMAX;
}/*初始化*/
void HashTableInit(HashTable* ht) {if (ht == NULL) {return;}int i = 0;for (; i < HASHTABLEMAX; i++) {ht->data[i].Statu = Empty;}ht->size = 0;ht->hash_func = Hash_Func;
}/*插入*/
void HashTableInsert(HashTable* ht, HashType key, ValueType value) {if (ht == NULL) {return;}/*判断是不是满了*/if (ht->size >= HASHTABLEMAX * 0.8) {printf("满了！");return;}//1.通过哈希函数找到该元素要插入的位置size_t offset = ht->hash_func(key);while (1) {//2.看该位置状态是不是已经有元素了if (ht->data[offset].Statu == Valid) {if (ht->data[offset].key == key) {return 0;}/*出现了哈希冲突,*/++offset;if (offset >= HASHTABLEMAX) {offset -= HASHTABLEMAX;}}else {//如果当前位置为空，就直接插入/*无论当前位置的状态是invalid还是valid都可以插入*/ht->data[offset].key = key;ht->data[offset].Statu = Valid;ht->data[offset].value = value;++ht->size;return 1;}}return;
}/*
**查找
**输入key，查找key对应的value
*/
int HashTableFind(HashTable* ht, HashType key, ValueType* value) {if (ht == NULL) {return;}size_t offset = ht->hash_func(key);while (1) {/*查找key*/if (ht->data[offset].Statu == Empty) {/*这个位置表示空，则哈希表中没有这个元素*/return 0;}/*表示该位置有元素，而且元素的状态是valid*/else if(ht->data[offset].key == key && ht->data[offset].Statu == Valid){/*如果这个位置的元素等于要查找的元素*/*value = ht->data[offset].value;return 1;}else {/*当前位置不是空的，也不等于要查找的元素，就继续向后查找*/++offset;if (offset >= HASHTABLEMAX) {offset -= HASHTABLEMAX;}}}return 0;
}/*删除*/
void HashTableRemove(HashTable* ht, HashType key) {if (ht == NULL) {return;}size_t offset = ht->hash_func(key);while (1) {/*如果该位置为空，表示该位置没有元素，所以没有找到*/if (ht->data[offset].Statu == Empty) {return;}else if (ht->data[offset].key == key && ht->data[offset].Statu == Valid) {/*该位置有元素，状态为valid，而且与要删除的元素相等*/ht->data[offset].Statu = Invalid;--ht->size;return;}else {/***该位置不为空，状态为valid,但是该元素不是要删除的元素**或者该位置状态为invalid，表示已经被删除了**这两种情况，都是继续找下一个位置*/++offset;if (offset >= HASHTABLEMAX) {offset -= HASHTABLEMAX;}} /*这里是else的代码块结束的地方*/}/*这里是while循环结束的部分*/return;
}int HashEmpty(HashTable* ht) {if (ht == NULL) {return 1;}if (ht->size == 0) {return 1;}return 0;
}size_t HashTableSize(HashTable* ht) {if (ht == NULL) {return;}return ht->size;
}void HashDestory(HashTable* ht) {if (ht == NULL) {return;}int i = 0;for (; i < HASHTABLEMAX; i++) {ht->data[i].Statu = Empty;}ht->size = 0;ht->hash_func = NULL;
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"HashTable.h"
#include
#include#define TESTHEADER printf("------------%s------------\n",__FUNCTION__)void HashPrint(HashTable* ht, char* msg) {if (ht == NULL) {return;}printf("\n%s:\n", msg);int i = 0;for (; i < HASHTABLEMAX; i++) {if (ht->data[i].Statu != Empty && ht->data[i].Statu != Invalid) {printf("[%lu], key = %d, value = %d, statu = %d\n",i, ht->data[i].key, ht->data[i].value, ht->data[i].Statu);}}
}void TestInit() {HashTable ht;TESTHEADER;HashTableInit(&ht);int i = 0;for (; i < HASHTABLEMAX; i++) {if (ht.data->Statu != Empty) {printf("有%d个元素未初始化！\n");}}printf("expect 0,actual:%d\n", ht.size);
}void TestInsert() {HashTable ht;TESTHEADER;HashTableInit(&ht);/*试着插入五个元素*/int arr[] = { 1, 1001, 1001, 2001, 3001, 4001, 5001, 2};int i = 0;for (; i < sizeof(arr) / sizeof(arr[0]); i++){HashTableInsert(&ht, arr[i], 400);}HashPrint(&ht, "插入四个元素");
}void TestFind() {HashTable ht;TESTHEADER;HashTableInit(&ht);ValueType value = 1001;/*试着插入五个元素*/int arr[] = { 1, 1001, 1545, 2001, 3003, 4001, 5001, 4446 };int i = 0;for (; i < sizeof(arr) / sizeof(arr[0]); i++){HashTableInsert(&ht, arr[i], i);}HashPrint(&ht, "插入几个元素");int ret = HashTableFind(&ht, 4446, &value);printf("\nexpect 1, acutal: %d\n", ret);printf("value ecpect , actual:%d\n", value);int ret2 = HashTableFind(&ht, 11243, &value);printf("ecpect 0,actual:%d\n", ret2);
}void TestRemove() {HashTable ht;TESTHEADER;HashTableInit(&ht);ValueType value = 1001;/*试着插入五个元素*/int arr[] = { 1, 2, 3, 2001, 3003, 4002, 5003 };int i = 0;for (; i < sizeof(arr) / sizeof(arr[0]); i++){HashTableInsert(&ht, arr[i], i);}HashPrint(&ht, "插入几个元素");HashTableRemove(&ht, 2001);HashPrint(&ht, "删除一个元素");HashTableRemove(&ht, 2001);HashPrint(&ht, "删除一个已经删除的元素");HashTableRemove(&ht, 2542);HashPrint(&ht, "删除一个没有的元素");
}void TestEmpty_Size_Destory() {HashTable ht;TESTHEADER;HashTableInit(&ht);ValueType value = 1001;int ret1 = HashEmpty(&ht);printf("expect 1, actual:%d\n", ret1);/*试着插入五个元素*/int arr[] = { 1, 2, 3, 2001, 3003, 4002, 5003 };int i = 0;for (; i < sizeof(arr) / sizeof(arr[0]); i++){HashTableInsert(&ht, arr[i], i);}HashPrint(&ht, "插入几个元素");int ret = HashEmpty(&ht);printf("expect 0, actual:%d\n", ret);int sz = HashTableSize(&ht);printf("expect 7,  actual:%d\n", sz);HashDestory(&ht);int j = 0;for (; j < HASHTABLEMAX; j++) {if (ht.data[j].Statu != Empty) {printf("第%d个元素存在！\n", j + 1);}}printf("ht->size expect 0,actual:%d\n", ht.size);
}void TestHashNum() {/*得到数组中有多少个元素相同*/HashTable ht;TESTHEADER;HashTableInit(&ht);/***核心思路**每次查找当前哈希表中是否存在该元素，如果不存在就直接插入**如果存在，就删除该元素，然后传入value + 1，value初始化为1，**最后得到该元素的value为该元素在数组中出现的次数*/int arr[] = { 1, 1, 1, 2, 2, 3, 3, 3, 3 };int i = 0;int value = 1;for (; i < sizeof(arr) / sizeof(arr[0]); i++) {int ret = HashTableFind(&ht, arr[i], &value);if (ret == 0) {/*表明该元素不存在*/value = 1;HashTableInsert(&ht, arr[i], value);}else {HashTableRemove(&ht, arr[i]);HashTableInsert(&ht, arr[i], value + 1);}}int ret1 = HashTableFind(&ht, 3, &value);printf("expect 4, actual:%d\n", value);int ret2 = HashTableFind(&ht, 2, &value);printf("expect 2, actual:%d\n", value);int ret3 = HashTableFind(&ht, 1, &value);printf("expect 3, actual:%d\n", value);}int main() {TestInit();TestInsert();TestFind();TestRemove();TestEmpty_Size_Destory();TestHashNum();system("pause");return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！