哈希表算法实现
哈希表算法实现
本文博客链接:http://blog.csdn.net/jdh99,作者:jdh,转载请注明.
环境：
主机:WINXP
开发环境:MINGW
说明:
本程序建立的哈希表示意图:
哈希函数为对哈希表长取余
源代码:
/********************************************************************** 哈希表算法实现*(c)copyright 2013,jdh* All Right Reserved*文件名:main.c*程序员:jdh**********************************************************************/#include <stdio.h>#include <stdlib.h>/**********************************************************************宏定义**********************************************************************//**********************************************************************数据类型重定义**********************************************************************/#define uint8_t unsigned char#define uint16_t unsigned short#define uint32_t unsigned long/**********************************************************************哈希表长度**********************************************************************/#define HASH_TABLE_LEN128/**********************************************************************数据结构**********************************************************************///链表节点typedef struct _Link_Node { uint16_t id;uint16_t data; struct _Link_Node *next; }Link_Node,*Link_Node_Ptr; //哈希表头typedef struct _Hash_Header { struct _Link_Node *next; }Hash_Header,*Hash_Header_Ptr;/**********************************************************************全局变量**********************************************************************///哈希表Hash_Header_Ptr Hash_Table[HASH_TABLE_LEN];/**********************************************************************函数**********************************************************************//**********************************************************************哈希表函数*说明:*1.用哈希函数生成id对应的哈希表中的位置输入:id返回:位置**********************************************************************/uint8_t hash_func(uint16_t id){uint8_t pos = 0;pos = id % HASH_TABLE_LEN;return pos;}/**********************************************************************初始化节点*返回:结点指针**********************************************************************/Link_Node_Ptr init_link_node(void){Link_Node_Ptr node;//申请节点node = (Link_Node_Ptr) malloc(sizeof(Link_Node));//初始化长度为0node->next = NULL;return node;}/**********************************************************************初始化哈希表头结点*返回哈希表头结点指针**********************************************************************/Hash_Header_Ptr init_hash_header_node(void){Hash_Header_Ptr node;//申请节点node = (Hash_Header_Ptr) malloc(sizeof(Hash_Header));//初始化长度为0node->next = NULL;return node;}/**********************************************************************哈希表初始化*说明:*1.初始化哈希表Hash_Table*2.哈希表长度最大不能超过256**********************************************************************/void init_hash_table(void){uint8_t i = 0;for (i = 0;i < HASH_TABLE_LEN;i++){Hash_Table[i] = init_hash_header_node();Hash_Table[i]->next = NULL;}}/**********************************************************************在哈希表增加节点*说明:*1.在哈希表的某个链表末增加数据输入:new_node:新节点**********************************************************************/void append_link_node(Link_Node_Ptr new_node){Link_Node_Ptr node;uint8_t pos = 0;//用哈希函数获得位置pos = hash_func(new_node->id);//判断是否为空链表if (Hash_Table[pos]->next == NULL){//空链表Hash_Table[pos]->next = new_node;}else{//不是空链表//获取根节点node = Hash_Table[pos]->next;//遍历while (node != NULL && node->next != NULL){node = node->next;}//插入node->next = new_node;}}/**********************************************************************在哈希表查询节点*说明:*1.知道在哈希表某处的单链表中,并开始遍历.*2.返回的是查询节点的前一个节点指针.这么做是为了做删除操作.输入:pos:哈希表数组位置,从0开始计数 id:所需要查询节点的id root:如果是根节点,则*root = 1,否则为0返回:所需查询的节点的前一个节点指针,如果是根节点则返回根节点,失败返回0**********************************************************************/Link_Node_Ptr search_link_node(uint16_t id,uint8_t *root){Link_Node_Ptr node;uint8_t pos = 0;//用哈希函数获得位置pos = hash_func(id);//获取根节点node = Hash_Table[pos]->next;//判断单链表是否存在if (node == NULL){return 0;}//判断是否是根节点if (node->id == id){//是根节点*root = 1;return node;}else{//不是根节点*root = 0;//遍历while (node->next != NULL){if (node->next->id == id){return node;}else{node = node->next;}}return 0;}}/**********************************************************************在哈希表删除节点*说明:*1.删除的不是当前节点,而是当前节点后的一个节点输入:node:删除此节点后面的一个节点 new_node:新节点**********************************************************************/void delete_link_node(Link_Node_Ptr node){Link_Node_Ptr delete_node;//重定向需要删除的前一个节点delete_node = node->next;node->next = delete_node->next;//删除节点free(delete_node);delete_node = NULL;}/**********************************************************************在哈希表删除根节点输入:node:根节点**********************************************************************/void delete_link_root_node(Link_Node_Ptr node){uint8_t pos = 0;//用哈希函数获得位置pos = hash_func(node->id);//哈希表头清空Hash_Table[pos]->next = NULL;//删除节点free(node);node = NULL;}/**********************************************************************主函数*说明:实现对哈希表的新建,建立节点,查询及增加,删除节点的操作**********************************************************************/int main(){Link_Node_Ptr node;uint8_t temp = 0;init_hash_table();//插入数据id = 1,data = 2;node = init_link_node();node->id = 1;node->data = 2;append_link_node(node);//插入数据id = 100,data = 101node = init_link_node();node->id = 100;node->data = 101;append_link_node(node);//id = 1000,data = 1001node = init_link_node();node->id = 1000;node->data = 1001;append_link_node(node);//id = 10000,data = 10001node = init_link_node();node->id = 10000;node->data = 10001;append_link_node(node);//查询id = 1000;node = search_link_node(1000,&temp);if (node != 0){if (temp == 0){printf("所需查询id的值为%d\n",node->next->data);//删除delete_link_node(node);}else{//根节点printf("所需查询id的值为%d\n",node->data);//删除delete_link_root_node(node);}}else{printf("查询失败\n");}//查询id = 1000;node = search_link_node(1001,&temp);if (node != 0){if (temp == 0){printf("所需查询id的值为%d\n",node->next->data);}else{//根节点printf("所需查询id的值为%d\n",node->data);}}else{printf("查询失败\n");}getchar();return 0;}