电话号码查询系统（数据结构之哈希表）

2023-12-24 15:07| 来源: 网络整理| 查看: 265

哈希表

哈希表（Hash Table）是一种根据关键字直接访问内存存储位置的数据结构。通过哈希表，数据元素的存放位置和数据元素的关键字之间建立起某种对应关系，建立这种对应关系的函数称为哈希函数。

在这里插入图片描述 1.哈希函数的构造方法假设要存储的数据元素个数为n，设置一个长度为m（m≥n）的连续存储单元，分别以每个数据元素的关键字 Ki(0 Imfo* nextData;//利用链表法处理冲突 }HashTable[Max_num];

2.哈希函数

int HashFunction(Imfo Data){//哈希函数，构造储存地址 int s=0; s=(Data.num[3]-'0')+(Data.num[4]-'0')+(Data.num[5]-'0')+(Data.num[6]-'0')+(Data.num[7]-'0'); return s%47; }

3.初始化空哈希表

int InitHash(HashTable &s){//初始化一个空的哈希表 for(int i=0;i//初始化建立一个五位的哈希表 if(flag==0){ printf("未建立电话簿，请先建立！\n"); return ERROR; } printf("请输入~\n"); for(int i=0;i//向哈希表中插入元素 int k=HashFunction(*Data); Imfo*p=s[k].nextData; while(p){ if(!strcmp(p->num,Data->num)){ printf("%s %s 该号码已存在！不能录入系统！\n",Data->name,Data->num); return -1; } p=p->nextData; } Data->nextData=s[k].nextData; s[k].nextData=Data;//利用头接法将新节点链如哈希表 return OK; }

6.向哈希表中增加一个元素

int addOneHash(HashTable &s){//向电话簿中添加一个联系人 if(flag==0){ printf("未建立电话簿，请先建立！\n"); return ERROR; } Imfo*q=(Imfo*)malloc(sizeof(Imfo)); printf("输入联系人姓名："); scanf("%s",q->name); printf("输入联系人电话："); scanf("%s",q->num); int k=HashFunction(*q); Imfo*p=s[k].nextData; while(p){ if(!strcmp(p->num,q->num)){ printf("%s %s 该号码已存在！不能录入系统！\n",q->name,q->num); return -1; } p=p->nextData; } q->nextData=s[k].nextData; s[k].nextData=q; printf("添加成功！\n"); return OK; }

7.删除一个元素

int delOneHash(HashTable &s){//删除电话簿中一个联系人 if(flag==0){ printf("未建立电话簿，请先建立！\n"); return ERROR; } Imfo*q=(Imfo*)malloc(sizeof(Imfo)); Imfo*t=(Imfo*)malloc(sizeof(Imfo));; printf("输入联系人姓名："); scanf("%s",q->name); printf("输入联系人电话："); scanf("%s",q->num); int k=HashFunction(*q); Imfo*p=s[k].nextData; t=s[k].nextData; if(!t)printf("电话簿没有该联系人！\n"); if(!s[k].nextData->nextData&&!strcmp(s[k].nextData->num,q->num)){ s[k].nextData=NULL; printf("删除成功！\n"); return OK; }//该地址只有一个节点，s[k].nextData->nextData=null，且该节点就是需要删除的节点 else if(!s[k].nextData->nextData&&strcmp(s[k].nextData->num,q->num)){ printf("电话簿没有该联系人！\n"); return ERROR; }//该地址只有一个节点，s[k].nextData->nextData=null，但该节点不是需要删除的节点 if(s[k].nextData->nextData&&!strcmp(s[k].nextData->num,q->num)){ s[k].nextData=s[k].nextData->nextData; printf("删除成功！\n"); return OK; }//该地址不只有一个节点，s[k].nextData->nextData！=null，且该节点就是需要删除的节点 while(p){ if(!strcmp(p->num,q->num)){ break; } t=p; p=p->nextData; }//p为移动节点，用来做判断条件，t为p的前驱节点，用来删除p所用 if(!p){ printf("电话簿没有该联系人！\n"); return ERROR; } else{ if(!p->nextData)t->nextData=NULL;//如果需要查找的节点是该链最后一个，直接使t->nextData=NULL else t->nextData=p->nextData; free(p);//释放p printf("删除成功！\n"); } return OK; }

8.查询哈希表中的元素

int SearchHash(HashTable s){//根据输入的关键字，查询联系人信息，并打印 if(flag==0){ printf("未建立电话簿，请先建立！\n"); return ERROR; } Imfo T; printf("输入查询的电话号码："); scanf("%s",T.num); int k=HashFunction(T); Imfo*p=s[k].nextData; while(p){ if(!strcmp(p->num,T.num)){ printf("查找完毕！该联系人信息为：姓名：%s 电话号码：%s \n",p->name,p->num); return OK; } p=p->nextData; } printf("没有找到该联系人\n"); return ERROR; }

完整的代码：

#include #include #define OK 1 #define ERROR 0 #include #include using namespace std; #define Max_num 50 typedef struct Imfo{ char name[20]; char num[20]; Imfo* nextData; }Imfo; typedef struct node{ Imfo* nextData; }HashTable[Max_num]; int flag=0;//标记电话薄已经建立 int HashFunction(Imfo Data);//哈希函数，构造储存地址 int InitHash(HashTable &s);//初始化一个空的哈希表 int CreatHash(HashTable &s);//初始化建立一个五位的哈希表 int addHash(HashTable &s,Imfo* Data);//向哈希表中插入元素 int addOneHash(HashTable &s);//向电话簿中添加一个联系人 int delOneHash(HashTable &s);//删除电话簿中一个联系人 int SearchHash(HashTable s);//根据输入的关键字，查询联系人信息，并打印 int ModifyHash(HashTable &s);//改变联系人信息(需要先删除旧的信息在添加新的信息) int showHash(HashTable s);//打印哈希表 int OperateMenu();//建立菜单，提示操作代码 int main() { HashTable s; int i=1; while(i){ switch(OperateMenu()){ case 1: InitHash(s); break; case 2: CreatHash(s); break; case 3: showHash(s); break; case 4: SearchHash(s); break; case 5: addOneHash(s); break; case 6: delOneHash(s); break; case 7: ModifyHash(s); break; case 0: i=0; } } } int InitHash(HashTable &s){//初始化一个空的哈希表 for(int i=0;i//哈希函数，构造储存地址 int s=0; s=(Data.num[3]-'0')+(Data.num[4]-'0')+(Data.num[5]-'0')+(Data.num[6]-'0')+(Data.num[7]-'0'); return s%47; } int CreatHash(HashTable &s){//初始化建立一个五位的哈希表 if(flag==0){ printf("未建立电话簿，请先建立！\n"); return ERROR; } printf("请输入~\n"); for(int i=0;i//向哈希表中插入元素 int k=HashFunction(*Data); Imfo*p=s[k].nextData; while(p){ if(!strcmp(p->num,Data->num)){ printf("%s %s 该号码已存在！不能录入系统！\n",Data->name,Data->num); return -1; } p=p->nextData; } Data->nextData=s[k].nextData; s[k].nextData=Data;//利用头接法将新节点链如哈希表 return OK; } int SearchHash(HashTable s){//根据输入的关键字，查询联系人信息，并打印 if(flag==0){ printf("未建立电话簿，请先建立！\n"); return ERROR; } Imfo T; printf("输入查询的电话号码："); scanf("%s",T.num); int k=HashFunction(T); Imfo*p=s[k].nextData; while(p){ if(!strcmp(p->num,T.num)){ printf("查找完毕！该联系人信息为：姓名：%s 电话号码：%s \n",p->name,p->num); return OK; } p=p->nextData; } printf("没有找到该联系人\n"); return ERROR; } int addOneHash(HashTable &s){//向电话簿中添加一个联系人 if(flag==0){ printf("未建立电话簿，请先建立！\n"); return ERROR; } Imfo*q=(Imfo*)malloc(sizeof(Imfo)); printf("输入联系人姓名："); scanf("%s",q->name); printf("输入联系人电话："); scanf("%s",q->num); int k=HashFunction(*q); Imfo*p=s[k].nextData; while(p){ if(!strcmp(p->num,q->num)){ printf("%s %s 该号码已存在！不能录入系统！\n",q->name,q->num); return -1; } p=p->nextData; } q->nextData=s[k].nextData; s[k].nextData=q; printf("添加成功！\n"); return OK; } int delOneHash(HashTable &s){//删除电话簿中一个联系人 if(flag==0){ printf("未建立电话簿，请先建立！\n"); return ERROR; } Imfo*q=(Imfo*)malloc(sizeof(Imfo)); Imfo*t=(Imfo*)malloc(sizeof(Imfo));; printf("输入联系人姓名："); scanf("%s",q->name); printf("输入联系人电话："); scanf("%s",q->num); int k=HashFunction(*q); Imfo*p=s[k].nextData; t=s[k].nextData; if(!t)printf("电话簿没有该联系人！\n"); if(!s[k].nextData->nextData&&!strcmp(s[k].nextData->num,q->num)){ s[k].nextData=NULL; printf("删除成功！\n"); return OK; }//该地址只有一个节点，s[k].nextData->nextData=null，且该节点就是需要删除的节点 else if(!s[k].nextData->nextData&&strcmp(s[k].nextData->num,q->num)){ printf("电话簿没有该联系人！\n"); return ERROR; }//该地址只有一个节点，s[k].nextData->nextData=null，但该节点不是需要删除的节点 if(s[k].nextData->nextData&&!strcmp(s[k].nextData->num,q->num)){ s[k].nextData=s[k].nextData->nextData; printf("删除成功！\n"); return OK; }//该地址不只有一个节点，s[k].nextData->nextData！=null，且该节点就是需要删除的节点 while(p){ if(!strcmp(p->num,q->num)){ break; } t=p; p=p->nextData; }//p为移动节点，用来做判断条件，t为p的前驱节点，用来删除p所用 if(!p){ printf("电话簿没有该联系人！\n"); return ERROR; } else{ if(!p->nextData)t->nextData=NULL;//如果需要查找的节点是该链最后一个，直接使t->nextData=NULL else t->nextData=p->nextData; free(p);//释放p printf("删除成功！\n"); } return OK; } int ModifyHash(HashTable &s){//改变联系人信息(需要先删除旧的信息在添加新的信息) if(flag==0){ printf("未建立电话簿，请先建立！\n"); return ERROR; } if(!delOneHash(s))return ERROR; addOneHash(s); return OK; } int showHash(HashTable s){//打印哈希表 if(flag==0){ printf("未建立电话簿，请先建立！\n"); return ERROR; } int c=1; printf("电话号码全部信息为：\n"); for(int i=0;i printf("%d:姓名：%s 电话号码：%s\n",c++,s[i].nextData->name,s[i].nextData->num); Imfo*p=s[i].nextData->nextData; while(p){ printf("%d:姓名：%s 电话号码：%s\n",c++,p->name,p->num); p=p->nextData; } } } return OK; } int OperateMenu(){//建立菜单，提示操作代码 int num; printf(" *---------------------------------------*\n"); printf(" 1：创建一个空的电话薄！\n"); printf(" 2：初始化输入5个信息！\n"); printf(" 3：打印电话薄的全部信息！\n"); printf(" 4：查询联系人信息！\n"); printf(" 5：添加一个联系人信息！\n"); printf(" 6：删除一个联系人信息！\n"); printf(" 7：修改联系人的电话信息！\n"); printf(" 0:选择其他指令退出系统！\n"); printf(" *---------------------------------------*\n"); scanf("%d",&num); for(int i=0;;i++){ if(num7){printf("指令错误！请输入正确的指令~\n");return -1;} else if(num==0){return num;break;} else if(num==1){return num;break;} else if(num==2){return num;break;} else if(num==3){return num;break;} else if(num==4){return num;break;} else if(num==5){return num;break;} else if(num==6){return num;break;} else if(num==7){return num;break;} } }

【本文地址】

公司简介

联系我们