数据结构之哈希表

哈希表的数据结构

#define SUCCESS 1 #define UNSUCCESS 0 #define HASHSIZE 12 /*定义散列表的长为数组的长度*/ #define NULLKEY -32768 typedef struct HashTable { int *elem; /*数据元素存储基址,动态分配数组*/ int count; /*当前数据元素个数*/ }HashTable; int m = 0; /*散列表表长,全局变量*/

初始化哈希表

int InitHashTable(HashTable *H) { int i; m = HASHSIZE; H->count = m; H->elem = (int*)malloc(m * sizeof(int)); for (i = 0; i < m; i++) H->elem[i] = NULLKEY; return 0; }

哈希函数

int Hash(int key) { return key%m;/*除留余数法*/ }

插入关键字进入哈希表

void InsertHash(HashTable *H, int key) { int addr = Hash(key); /*求散列地址*/ while (H->elem[addr] != NULLKEY) /*如果不为空则冲突*/ addr = (addr + 1) % m; H->elem[addr] = key; /*直到有空位后插入关键字*/ }

哈希表查找关键字

int SearchHash(HashTable H, int key, int *addr) { *addr = Hash(key); /*求散列地址*/ while (H.elem[*addr] != key) { *addr = (*addr + 1) % m; /*开放定址法*/ if (H.elem[*addr] == NULLKEY || *addr == Hash(key)) { /*循环回未找到或者回到原点*/ return UNSUCCESS; } } return SUCCESS; }