数据结构--第八天

--哈希表

-哈希表的概念

哈希表：用散列法存储的线性表被称为哈希表，使用的函数被称为散列函数或者哈希函数，f(k)被称为散列地址或者哈希地址。。通常情况下，散列表的储存空间是一个一维数组，而哈希地址为数组的下标

-哈希表的基本思想

以节点的关键字k为自变量，通过一个确定的函数关系f，计算出对应的函数值，把这个函数值解释为节点的存储地址，将节点存储到f(k)所指示的的存储位置上，在查找时再根据要查找的关键字，用同样的函数计算地址，然后到对应的单元读取。

-哈希表的优点

顺序表的特点是：寻址容易，插入和删除困难

链表的特点是：寻址困难，插入和删除简单

哈希表则结合了俩者的特点，既寻址容易又插入和删除容易

-哈希冲突的解决方法

开放地址法

即当一个关键字和另一个关键字发生冲突时，使用某种探测技术在Hash表中形成一个探测序列，然后沿着这个探测序列依次查找下去，当碰到一个空的单元时，则插入，比如有一组关键字{12，13，25，23，38，34，6，84，91}，Hash表长为14，Hash函数为address(key)=key%11，当插入12，13，25时可以直接插入，而当插入23时，地址1被占用了，因此沿着地址1依次往下探测(探测步长可以根据情况而定)，直到探测到地址4，发现为空，则将23插入其中。

链地址法

采用数组和链表相结合的办法，将Hash地址相同的记录存储在一张线性表中，而每张表的表头的序号即为计算得到的Hash地址。如上述例子中，采用链地址法形成的Hash表存储表示为：

示例代码：学生管理系统

main.c

#include "linkedlist.h"void menu();int main(){while(!login_status){login();}int select;hash_t* hashtable=NULL;// 创建hashtablecreate_hashtable(&hashtable);if(NULL == hashtable){printf("hash table is NULL\n");exit(EXIT_FAILURE);}do{menu();	printf("请选择:");scanf("%d",&select);switch(select){case 1:insert_stu(hashtable);break;case 2:show_stus(hashtable);break;case 3:search_stu_by_id(hashtable);break;case 4:modify_stu_by_id(hashtable);break;case 5:del_stu_by_id(hashtable);break;case 0:printf("欢迎下次光临!\n");clear_hashtable(&hashtable);exit(EXIT_SUCCESS);case 6:
//				show_stus_linkedlist(hashtable);break;}}while(1);
}void menu(){printf("-----------------------------------------\n");printf("|\t\t学生管理系统            |\n");printf("-----------------------------------------\n");printf("|\t\t1、增加学生    \t\t|\n");printf("|\t\t2、显示学生信息    \t|\n");printf("|\t\t3、查找学生    \t\t|\n");printf("|\t\t4、修改学生信息    \t|\n");printf("|\t\t5、删除学生    \t\t|\n");printf("|\t\t0、退出    \t\t|\n");printf("----------------------------------------\n");
}

management.c

#include "linkedlist.h"bool login_status=false;
void login(){printf("=============登录=============\n");printf("用户：");char uname[256]={0};fgets(uname,sizeof(uname),stdin);uname[strlen(uname)-1]='\0';printf("密码：");char password[256]={0};fgets(password,sizeof(password)-1,stdin);password[strlen(password)-1]='\0';if(strcmp(uname,"wq")==0&&strcmp(password,"wq")==0){printf("登录成功^_^\n");login_status=true;}else{printf("用户或密码错误\n");}
}void create_hashtable(hash_t** hashtable){hash_t* p_hash=(hash_t*)malloc(sizeof(hash_t));if(NULL==p_hash){printf("malloc failure\n");return;}p_hash->n=0;for(int i=0;i<SIZE;i++){linkedlist_init(&(p_hash->item[i]));}*(hashtable)=p_hash;	
}uint32_t get_hashindex(char* id){uint32_t hashcode=0;while(*(id)!='\0'){hashcode+=*(id);id++;}return (uint32_t)(hashcode%SIZE);
}
void insert_stu(hash_t* hashtable){datatype_t* stu=(datatype_t*)malloc(sizeof(datatype_t));if(stu==NULL){printf("malloc failure\n");}printf("请输入：【学号，姓名，性别，年龄，分数】");scanf("%s %s %s %d %f",stu->id,stu->name,stu->gender,&(stu->age),&(stu->score));uint32_t res=get_hashindex(stu->id);linkedlist_insert_head(hashtable->item[res],stu);if(res){printf("添加成功\n");}else{printf("添加失败\n");}
}void show_stus(hash_t* p_hashtable){printf("------------------学生信息如下----------------------\n");printf("\tID\t姓名\t性别\t年龄\t成绩\t\n");for(int i=0;i<SIZE;i++){linkedlist_show(*(p_hashtable->item+i));}printf("----------------------------------------------------\n");
}void search_stu_by_id(hash_t* hashtable){printf("请输入学号：");char id[128]={0};while(getchar()!='\n');fgets(id,sizeof(id)-1,stdin);id[strlen(id)-1]='\0';uint32_t index=get_hashindex(id);search_data(hashtable->item[index],id);
}void del_stu_by_id(hash_t* hashtable){printf("请输入要删除的学生的学号：");char id[128]={0};while(getchar()!='\n');fgets(id,sizeof(id)-1,stdin);id[strlen(id)-1]='\0';uint32_t index=get_hashindex(id);bool res=linkedlist_remove_data(hashtable->item[index],id);if(res){printf("删除成功！\n");}else{printf("查无此人\n");}}
void modify_stu_by_id(hash_t* hashtable){printf("请输入修改学生的ID：");char id[128]={0};while(getchar()!='\n');fgets(id,sizeof(id)-1,stdin);id[strlen(id)-1]='\0';//根据ID获取哈希索引uint32_t index=get_hashindex(id);datatype_t* data=linkedlist_modify_stu(hashtable->item[index],id);if(data!=NULL){printf("修改学生信息成功");printf("ID\t姓名\t性别\t年龄\t成绩\t\n");printf("%s\t%s\t%s\t%d\t%.2f\t\n",data->id,data->name,data->gender,data->age,data->score);}else{printf("该%s对应学生不存在，修改学生信息失败\n",id);}
}void clear_hashtable(hash_t**p_hashtable){linkednode_t** arr=(*p_hashtable)->item;for(int i=0;i<SIZE;i++){linkedlist_clear(*(arr+i));}free(*p_hashtable);p_hashtable=NULL;
}

management.h

#ifndef __HEAD_MANAGEMENT_H__
#define __HEAD_MANAGEMENT_H__#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <errno.h>
#include <stdbool.h>
#include "linkedlist.h"#define SIZE 13typedef struct{char id[128];char name[128];char gender[64];uint32_t age;float score;
}datatype_t;typedef struct Node{datatype_t* data;struct Node* next;
}linkednode_t;typedef struct {linkednode_t* item[SIZE];int n;
}hash_t;//  登录状态
extern bool login_status;
extern void login();
extern void create_hashtable(hash_t**);
// 创建hash函数
extern uint32_t get_hashIndex(char*);
extern void insert_stu(hash_t*);
extern void show_stus(hash_t*);
extern void show_stus_linkedlist(hash_t*);
extern void search_stu_by_id(hash_t*);
extern void del_stu_by_id(hash_t*);
extern void modify_stu_by_id(hash_t*);
extern void clear_hashtable(hash_t**);
#endif

linkedlist.c

#include "linkedlist.h"void linkedlist_init(linkednode_t** p_dummyhead){                                         linkednode_t* p_node = (linkednode_t*)malloc(sizeof(linkednode_t));        if(p_node==NULL){                                        printf("malloc failure:%s\n",strerror(errno));   return;                                    }                                                        memset(p_node,0,sizeof(linkednode_t));                                                              p_node->next = NULL; *p_dummyhead = p_node;	
}// 添加的方法
bool linkedlist_insert_head(linkednode_t* p_dummyhead,datatype_t* p_data){//将data添加到链表的尾部// 1、封装成节点linkednode_t* p_node = (linkednode_t*)malloc(sizeof(linkednode_t));if(p_node==NULL){printf("malloc failure:%s\n",strerror(errno));return false;}memset(p_node,0,sizeof(linkednode_t));p_node->data = p_data;p_node->next = NULL;// 进行挂接p_node->next = p_dummyhead->next;p_dummyhead->next = p_node;return true;
}bool linkedlist_is_empty(linkednode_t* p_dummyhead){return p_dummyhead == NULL || p_dummyhead->next==NULL;
}bool linkedlist_remove_data(linkednode_t* p_dummyhead,const char* id){if(linkedlist_is_empty(p_dummyhead)){return false;}else{// 查找数据是否存在linkednode_t* pre = p_dummyhead;while(pre->next!=NULL){if(strcmp(id,pre->next->data->id)==0){linkednode_t* delnode = pre->next;pre->next = pre->next->next;free(delnode);delnode=NULL;return true;}pre=pre->next;}	return false;}
}void linkedlist_show(linkednode_t* p_dummyhead){linkednode_t* cur=p_dummyhead->next;while(cur!=NULL){printf("\t%s\t%s\t%s\t%d\t%.2f\n",cur->data->id,cur->data->name,cur->data->gender,cur->data->age,cur->data->score);cur= cur->next;}
}
void linkedlist_display(linkednode_t* p_dummyhead){linkednode_t* cur= p_dummyhead->next;while(cur!=NULL){printf("%s--->",cur->data->id);cur=cur->next;}printf("NULL\n");
}void search_data(linkednode_t* dummyhead,const char* id){if(dummyhead->next==NULL){printf("查无此人！\n");return;}linkednode_t* cur=dummyhead->next;while(cur != NULL){if(strcmp(cur->data->id,id) == 0){printf("ID\t姓名\t性别\t年龄\t成绩\t\n");printf("%-8s%-8s%-8s%-4d%-4f\n",cur->data->id,cur->data->name,cur->data->gender,cur->data->age,cur->data->score);return;}cur = cur->next;}if(cur == NULL){printf("找不到此人\n");return;}
}datatype_t* linkedlist_modify_stu(linkednode_t* p_dummyhead,const char* id){linkednode_t* cur=p_dummyhead->next;while(cur!=NULL){if(strcmp(cur->data->id,id)==0){printf("---------------修改学生信息------------------\n");printf("\t1.姓名\n");printf("\t2.性别\n");printf("\t3.年龄\n");printf("\t4.分数\n");printf("\t0.退出\n");printf("请选择：");int select;datatype_t* stu=cur->data;scanf("%d",&select);switch(select){case 1:while(getchar()!='\n');printf("姓名：");fgets(stu->name,sizeof(stu->name)-1,stdin);stu->name[strlen(stu->name)-1]='\0';break;case 2:while(getchar()!='\n');printf("性别：");fgets(stu->gender,sizeof(stu->gender)-1,stdin);stu->gender[strlen(stu->gender)-1]='\0';break;case 3:printf("年龄：");scanf("%d",&(stu->age));break;case 4:printf("成绩：");scanf("%f",&(stu->score));break;case 0:break;}return stu;}cur=cur->next;}return NULL;
}void linkedlist_clear(linkednode_t* p_dummyhead){linkednode_t* pre=p_dummyhead;while(pre->next!=NULL){linkednode_t* del=pre->next;pre->next=pre->next->next;free(del);del=NULL;}free(p_dummyhead);p_dummyhead=NULL;
}

linkedlist.h

#ifndef __HEAD_LINKED_LIST_H__
#define __HEAD_LINKED_LIST_H__#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#in#clude <stdbool.h>
#include <errno.h>
#include "management.h"extern bool linkedlist_insert_head(linkednode_t*, datatype_t*);
extern void linkedlist_init(linkednode_t**);
extern bool linkedlist_is_empty(linkednode_t*);
extern bool linkedlist_remove_data(linkednode_t*,const char*);
extern void linkedlist_show(linkednode_t*);
extern void linkedlist_display(linkednode_t*);
extern void search_data(linkednode_t*,const char*);
extern void del_data(linkednode_t*,const char*);
extern datatype_t*linkedlist_modify_stu(linkednode_t*,const char*);
extern void linkedlist_clear(linkednode_t*);
#endif