查找算法刷题【哈希表算法】

一、哈希表结构体

二、代码

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>typedef struct Node
{char* s;struct Node* next;
}g_Node;typedef struct HashTable
{struct Node* node;int cnt, size;
}g_HashTable;//函数的声明
bool insert(g_HashTable* h, const char* s);/* 创建一个链表节点 */
g_Node* getNewNode(const char* s)
{g_Node* pNode = (g_Node*)malloc(sizeof(g_Node));pNode->next = NULL;pNode->s = (char*)malloc(strlen(s) + 1);strcpy(pNode->s, s);pNode->s[strlen(s)] = '\0';return pNode;
}/* 创建一个哈希表元素 */
g_HashTable* getNewHashTable(int n)
{g_HashTable* pHt = (g_HashTable*)malloc(sizeof(g_HashTable));   //创建哈希表管理结构体pHt->node = (g_Node*)malloc(sizeof(g_Node) * n);     //创建哈希表数组for (int i = 0; i < n; i++) pHt->node[i].next = NULL;pHt->cnt = 0;pHt->size = n;return pHt;
}/* 回收哈希表链表节点 */
void clearNode(g_Node* p)
{if (p == NULL) return;if (p->s)  free(p->s);free(p);
}/* 回收整个哈希表元素 */
void clearHashTable(g_HashTable* h)
{if (h == NULL) return;for (int i = 0; i < h->size; i++){g_Node* p = h->node[i].next, * q;while (p){q = p->next;clearNode(p);p = q;}}free(h->node);   //因为数组是统一申请的，所以一块释放了就可以了free(h);return;
}
/*==============================哈希表扩容操作===============================*//* 交换哈希表头 */
void swapHashTable(HashTable* h1, HashTable* h2) {g_Node* node;int data;node = h1->node;h1->node = h2->node;h2->node = node;data = h1->cnt;h1->cnt = h2->cnt;h2->cnt = data;data = h1->size;h1->size = h2->size;h1->size = data;return;
}/* 哈希表的扩容操作:创建新的哈希表，然后进行移植 */
void expand(g_HashTable* h)
{if (NULL == h) return;printf("expand Hash Table %d -> %d\n", h->size, h->size * 2);g_HashTable* h_new = getNewHashTable(h->size * 2);            //使用函数创建新的哈希表for (int i = 0; i < h->size; i++){g_Node* p = h->node[i].next;while (p){insert(h_new, p->s);p = p->next;}}h = h_new;clearHashTable(h_new);
}/*=============================哈希表的动作================================*/
/* 字符串的哈希算法 */
int hash_func(const char* s)
{int seed = 131, h = 0;for (int i = 0; s[i]; i++){h = h * seed + s[i];}return h & 0x7fffffff;
}/* 向哈希表元素插入一个链表节点 */
bool insert(g_HashTable* h, const char* s)
{if (h == NULL) return false;if (h->cnt >= h->size * 2) {expand(h);}int hcode = hash_func(s);int index = hcode % h->size;g_Node* node = getNewNode(s);node->next = h->node[index].next;   //直接向后插入，说明哈希数组中的链表头节点不存储数据。h->node[index].next = node;h->cnt++;    //哈希表中总的元素return true;
}/* 从哈希表中找到对应元素 */
bool find(g_HashTable* h, const char* s)
{if (NULL == h) return false;int hcode = hash_func(s), index = hcode % h->size;g_Node* pnode = h->node[index].next;while (pnode){if (0 == strcmp(pnode->s, s)) return true;pnode = pnode->next;}return false;
}/* 哈希表的输出 */
void output(g_HashTable* h) {printf("\n\nHash Table(%d / %d) : \n", h->cnt, h->size);for (int i = 0; i < h->size; i++) {printf("%d : ", i);g_Node* p = h->node[i].next;while (p) {printf("%s -> ", p->s);p = p->next;}printf("\n");}return;
}int main()
{char s[100];
#define MAX_N 2g_HashTable* h = getNewHashTable(MAX_N);while (~scanf("%s", s)) {if (strcmp(s, "end") == 0) break;insert(h, s);}output(h);while (~scanf("%s", s)) {printf("find(%s) = %d\n", s, find(h, s));}
#undef  MAX_Nreturn 0;
}

运行结果：