Hash表 数据结构_针对某个集体中人名设计一个哈希表,哈希函数用除留余数法构造,用线性探测再散列法

Hash 表
key: value
key 保存信息的唯一标识
将char*类型的key转化为int型作为寻找信息的方式
假设有10000个人, 分成100个表保存信息, 每个表保存100个人

使用Hash算法对key做唯一标识计算

// main.cpp
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#include "hashclass.h"
 
int main(int argc, char* argv[]) {
	HashTab* t1 = createTab(10);
 
	insertHashElem(t1, "1", (void*)"河南");
	insertHashElem(t1, "2", (void*)"北京");
	insertHashElem(t1, "3", (void*)"天津");
	insertHashElem(t1, "13", (void*)"天津");
	insertHashElem(t1, "23", (void*)"天津");
	insertHashElem(t1, "33", (void*)"天津");
	insertHashElem(t1, "43", (void*)"天津");
	
	insertHashElem(t1, "4", (void*)"河北");
	insertHashElem(t1, "5", (void*)"安徽");
 
	char* addr = (char*)findHashElem(t1, "1");
	printf("%s\n", addr);
 
	resetHashElem(t1, "2", (void*)"China");
	addr = (char*)findHashElem(t1, "2");
	printf("%s\n", addr);
 
	deleteHashElem(t1, "23");
	if (addr = (char*)findHashElem(t1, "23")) {
		printf("%s\n", addr);
	}
	else {
		printf("没有");
	}
	clearHashElemList(t1);
	
	printf("%s\n", (char*)findHashElem(t1, "5"));
 
	system("pause");
	return 0;
}

// HashClass.cpp
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#include "HashClass.h"
 
#define my_malloc malloc
#define my_free free
 
// 哈希算法
static unsigned int
algorimthHash(const char* key) {
	register unsigned int h;
	register unsigned char* p;
	for (h = 0, p = (unsigned char*)key; *p; p++) {
		h = (32 << 5)*h + *p;
	}
	return h;
}
 
struct HashNode {
	char* key;
	void* value;
	HashNode* next;
};
 
struct HashTab {
	int group;
	HashNode** Hash_sets;
};
 
HashTab* createTab(int n) {
	HashTab* tab = (HashTab*)my_malloc(sizeof(HashTab));
	memset(tab, 0, sizeof(HashTab));
 
	tab->Hash_sets = (HashNode**)my_malloc(sizeof(HashNode*)*n);
	memset(tab->Hash_sets, 0, sizeof(HashNode*)*n);
	tab->group = n;
 
	return tab;
}
 
void deleteTab(HashTab* tab) {
	clearHashElemList(tab);
	if (tab->Hash_sets) {
		free(tab->Hash_sets);
		tab->Hash_sets = NULL;
	}
	free(tab);
}
 
void insertHashElem(HashTab* tab, const char* key, void* value) {
	HashNode* node = (HashNode*)my_malloc(sizeof(HashNode));
	memset(node, 0, sizeof(HashNode));
 
	node->key = strdup(key);
	node->value = value;
 
	int g_index = algorimthHash(key) % tab->group;
 
	HashNode* head = tab->Hash_sets[g_index];
	node->next = head;
	tab->Hash_sets[g_index] = node;
}
 
void resetHashElem(HashTab* tab, const char* key, void* value) {
	int g_index = algorimthHash(key) % tab->group;
	HashNode** transNode = &tab->Hash_sets[g_index];
 
	while (*transNode) {
		if (strcmp((*transNode)->key, key) == 0) {
			(*transNode)->value = value;
			return;
		}
		transNode = &(*transNode)->next;
	}
	
	HashNode* node = (HashNode*)my_malloc(sizeof(HashNode));
	memset(node, 0, sizeof(HashNode));
 
	node->key = strdup(key);
	node->value = value;
	*transNode = node;
}
 
void* findHashElem(HashTab* tab, const char* key) {
	int g_index = algorimthHash(key) % tab->group;
	HashNode* transNode = tab->Hash_sets[g_index];
 
	while (transNode) {
		if (strcmp(transNode->key, key) == 0) {
			return transNode->value;
		}
		transNode = transNode->next;
	}
	return NULL;
}
 
void deleteHashElem(HashTab* tab, const char* key) {
	int g_index = algorimthHash(key) % tab->group;
	HashNode** transNode = &tab->Hash_sets[g_index];
	while (*transNode) {
		if (strcmp((*transNode)->key, key) == 0) {
			HashNode* node = *transNode;
			*transNode = (*transNode)->next;        // 将下一个链表节点接到上一个
			node->next = NULL;
			free(node->key);
			free(node); 
		}
		else {
			transNode = &(*transNode)->next;        // 将链表节点后移一次,并将二级指针的值修改为链表后移前的值
		}
	}
}
 
void clearHashElemList(HashTab* tab) {
	for (int i = 0; i < tab->group; i++) {
		HashNode* transNode = tab->Hash_sets[i];
		tab->Hash_sets[i] = NULL;
 
		while (transNode) {
			HashNode* node = transNode;
			transNode = transNode->next;
			node->next = NULL;
			free(node->key);
			free(node);
		}
	}
}