数据结构查找-哈希表(创建+查找+删除)+(C语言代码)
#include<stdlib.h>
#include<stdio.h>
#include<stdbool.h>
#define NULLKEY -1//单元为空
#define DELKEY -2//单元内容被删除
#define M 20
typedef struct
{int key;//关键字int count;//统计哈希冲突探测次数
}HashTable;
//插入到哈希表
void InsertHT(HashTable ha[], int* n, int m,int p,int key)//n为哈希表的元素个数,m为哈希表的表长总数
{int i, adr;adr = key % p;//获得插入的哈希地址if (ha[adr].key == NULLKEY || ha[adr].key == DELKEY){ha[adr].key = key;ha[adr].count = 1;}else{i = 1;do{adr = (adr + 1) % m;i++;} while (ha[adr].key != NULLKEY && ha[adr].key != DELKEY);ha[adr].key = key;ha[adr].count = i;}n++;//哈希表的元素个数
}
//创建哈希表
void CreateHT(HashTable ha[], int* n, int m, int p, int keys[],int n1)
{int i;//初始化哈希表内容for (int i = 0; i < m; i++){ha[i].key = NULLKEY;ha[i].count = 0;}n = 0;//统计插入的个数for (i = 0; i < n1; i++){InsertHT(ha, n, m, p, keys[i]);}printf("哈希表如下:\n");for (int j = 0; j < m; j++){printf("%d 比较次数 %d\n", ha[j].key,ha[j].count);}printf("\n");
}
//查找哈希表
int SearchHT(HashTable ha[],int p,int m,int n1,int key)
{int i, Hi;int HO = key % p;//求出key的哈希地址if (ha[HO].key == NULLKEY){ha->count = 1;return -1;}else if (ha[HO].key == key){ha->count = 1;return HO;}else{ha->count = 1;for (i = 1; i <= n1; i++){Hi = (HO + i) % m;if (ha[Hi].key == NULLKEY){ha->count = ha->count + i;return -1;}else if (ha[Hi].key == key){ha->count = ha->count + i;return Hi;}}}
}
//删除哈希值
bool DeleteHT(HashTable ha[], int* n, int m, int p, int key)
{int i = 1, adr;adr = key % p;while(ha[adr].key != NULLKEY && ha[adr].key != key){adr = (adr + i) % m;i++;}if (ha[adr].key == key){ha[adr].key = DELKEY;return true;}else{return false;}
}
int main()
{HashTable ha[M];int keys[] = { 19,14,23,1,68,20,84,27,55,11,10,79 };int n1 = sizeof(keys) / sizeof(keys[0]);int n;int p = 13;//哈希表的创建+打印CreateHT(ha, &n, M, p, keys, n1);//哈希表的查找int num = 79;int result = SearchHT(ha, p, M,n1, num);if (result != -1){printf("找到key = %d,位置在 %d 比较次数为%d\n", num, result,ha->count);}else{printf("没有找到key = %d , 比较次数为%d\n", num, ha->count);}//删除哈希值num = 23;DeleteHT(ha, &n, M, p, num);printf("删除后:\n");for (int j = 0; j < M; j++){if (ha[j].key != NULLKEY && ha[j].key != DELKEY){printf(" %d ", ha[j].key);}else {printf(" * ");}}printf("\n");return 0;
}