一、要求：
【问题描述】
设计散列表实现电话号码查找系统。
【基本要求】
1)设每个记录有下列数据项：电话号码、用户名、地址；2)从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3)采用一定的方法解决冲突；4)查找并显示给定电话号码的记录；5)查找并显示给定用户名的记录。
【进一步完成内容】
1)系统功能的完善；2)设计不同的散列函数，比较冲突率；3)在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。
二、代码
头文件：Hash.h
#include <stdio.h>#include <stdlib.h>#include <string>#include <windows.h>#define MAXSIZE 20 //电话薄记录数量#define MAX_SIZE 20 //人名的最大长度#define HASHSIZE 53 //定义表长#define ok 1#define error -1#define LEN sizeof(HashTable)typedef int Status;typedef char NA[MAX_SIZE];typedef struct //记录{NA name;NA tel;NA add;} Record;typedef struct{//散列表Record *elem[HASHSIZE]; //数据元素存储基址int count;//当前数据元素个数int size; //当前容量} HashTable;Status eq(NA x,NA y){//关键字比较，相等返回1；否则返回-1if(strcmp(x,y)==0)return ok;else return error;}Status NUM_BER;//记录的个数
源文件：Hash.cpp
#include "stdio.h"#include "stdlib.h"#include "string"#include "windows.h"#include "Hash.h"void getin(Record* a){//键盘输入各人的信息printf("输入要添加的个数：\n");scanf("%d",&NUM_BER);int i;for(i=0; i<NUM_BER; i++){printf("请输入第%d个记录的用户名:\n",i+1);scanf("%s",a[i].name);printf("请输入%d个记录的电话号码:\n",i+1);scanf("%s",a[i].tel);printf("请输入第%d个记录的地址:\n",i+1);scanf("%s",a[i].add);}}void ShowInformation(Record* a) //显示输入的用户信息{int i;for( i=0; i<NUM_BER; i++)printf("\n第%d个用户信息:\n 姓名：%s\n 电话号码：%s\n 联系地址：%s\n",i+1,a[i].name,a[i].tel,a[i].add);}void Cls(Record* a){//完成清屏操作printf("*");system("cls");}long fold(NA s){//人名的折叠处理char *p;long sum=0;NA ss;strcpy(ss,s); //复制字符串，不改变原字符串的大小写strupr(ss);//将字符串ss转换为大写形式p=ss;while(*p!='\0')sum+=*p++;printf("\n表的地址总数%d",sum);return sum;}int Hash1(NA str){//姓名建表的散列函数long n;int m;n=fold(str);//先将用户名进行折叠处理m=n%HASHSIZE;//折叠处理后的数，用除留余数法构造散列函数return m; //并返回模值}int Hash2(NA str){//电话号码建表的散列函数long n;int m;n = atoi(str); //把字符串转换成整型的函数.m=n%HASHSIZE;//用除留余数法构造散列函数return m; //并返回模值}Status collision(int p,int &c){//冲突处理函数，采用二次探测再散列法解决冲突int i,q;i=c/2+1;while(i<HASHSIZE){if(c%2==0){c++;q=(p+i*i)%HASHSIZE;if(q>=0) return q;else i=c/2+1;}else{q=(p-i*i)%HASHSIZE;c++;if(q>=0) return q;else i=c/2+1;}}return error;}void CreateHash1(HashTable* H,Record* a){//建表，以人的姓名为关键字，建立相应的散列表，并解决相应的冲突int i,p=-1,c,pp;for(i=0; i<NUM_BER; i++){c=0;p=Hash1(a[i].name);pp=p;while(H->elem[pp]!=NULL){pp=collision(p,c);if(pp<0){printf("第%d记录无法解决冲突",i+1); //需要显示冲突次数时输出continue;}//无法解决冲突，跳入下一循环(即+1)}H->elem[pp]=&(a[i]); //求得散列地址，将信息存入H->count++;printf("第%d个记录冲突次数为%d。\n",i+1,c); //需要显示冲突次数时输出}printf("\n建表完成!\n此散列表容量为%d,当前表内存储的记录个数为%d.\n",HASHSIZE,H->count);}void SearchHash1(HashTable* H,int &c){//在通讯录里查找姓名关键字，若查找成功，显示信息//c用来显示冲突次数NA str;printf("\n请输入要查找记录的姓名：\n");scanf("%s",str);int p,pp;p=Hash1(str);pp=p;while((H->elem[pp]!=NULL)&&(eq(str,H->elem[pp]->name)==-1))pp=collision(p,c);if(H->elem[pp]!=NULL&&eq(str,H->elem[pp]->name)==1){printf("\n查找成功！\n查找过程冲突次数为%d．以下是您需要要查找的信息：\n\n",c);printf("姓 名：%s\n电话号码：%s\n联系地址：%s\n",H->elem[pp]->name,H->elem[pp]->tel,H->elem[pp]->add);}else printf("\n此人不存在，查找不成功!\n");}void CreateHash2(HashTable* H,Record* a){//建表，以电话号码为关键字，建立相应的散列表，并解决相应的冲突int i,p=-1,c,pp;for(i=0; i<NUM_BER; i++){c=0;p=Hash2(a[i].tel);pp=p;while(H->elem[pp]!=NULL){pp=collision(p,c);if(pp<0){printf("第%d记录无法解决冲突",i+1); //需要显示冲突次数时输出continue;} //无法解决冲突，跳入下一循环(即+1)}H->elem[pp]=&(a[i]); //求得散列地址，将信息存入H->count++;printf("第%d个记录冲突次数为%d。\n",i+1,c);//需要显示冲突次数时输出}printf("\n建表完成!\n此散列表容量为%d,当前表内存储的记录个数为%d.\n",HASHSIZE,H->count);}void SearchHash2(HashTable* H,int &c){//在通讯录里查找电话号码关键字，若查找成功，显示信息//c用来记录冲突次数,查找成功时显示冲突次数NA tele;printf("\n请输入要查找记录的电话号码：\n");scanf("%s",tele);int p,pp;p=Hash2(tele);pp=p;while((H->elem[pp]!=NULL)&&(eq(tele,H->elem[pp]->tel)==-1))pp=collision(p,c);if(H->elem[pp]!=NULL&&eq(tele,H->elem[pp]->tel)==1){printf("\n查找成功！\n查找过程冲突次数为%d．以下是您需要要查找的信息：\n",c);printf("姓 名：%s\n电话号码：%s\n联系地址：%s\n",H->elem[pp]->name,H->elem[pp]->tel,H->elem[pp]->add);}else printf("\n此人不存在，查找不成功!\n");}void Save(){//保存数据函数FILE *fp;if((fp=fopen("c:\test.txt", "w"))==NULL){printf("\nERROR opening customet file");}fclose(fp);}int main(int argc, char* argv[]){int c,flag=1;HashTable *H;H=(HashTable*)malloc(LEN);for(int i=0; i<HASHSIZE; i++)H->elem[i]=NULL;H->size=HASHSIZE;H->count=0;Record a[MAXSIZE];printf("欢迎使用电话号码查找系统 ");printf("\n 1. 添加用户信息");printf("\n 2. 读取所有用户信息 ");printf("\n 3. 以姓名建表 ");printf("\n 4. 以电话号码建表 ");printf("\n 5. 查找并显示给定用户名的记录 ");printf("\n 6. 查找并显示给定电话号码的记录 ");printf("\n 7. 清空 ");printf("\n 8. 保存 ");printf("\n 9. 退出程序 ");printf("\n 注意： ");printf("\n Ⅰ.进行5操作前 请先输出3");printf("\n Ⅱ.进行6操作前 请先输出4");printf("\n");printf("请输入你想要的操作：");printf("\n");while(1){int num;scanf("%d",&num);switch(num){case 1:getin(a);break;case 2:ShowInformation(a);break;case 3:CreateHash1(H,a); // 以姓名建立散列表break;case 4:CreateHash2(H,a); // 以电话号码建立散列表break;case 5:c=0;SearchHash1(H,c); //以姓名查找数据break;case 6:c=0;SearchHash2(H,c); //以电话号码查找数据break;case 7:Cls(a);break;case 8:Save();break;case 9:return 0;break;default:printf("输入错误，请重新输入!");printf("\n");}}system("pause");return 0;}
三、运行结果
