哈希表实现电话号码查询系统.doc

《哈希表实现电话号码查询系统.doc》由会员分享，可在线阅读，更多相关《哈希表实现电话号码查询系统.doc（9页珍藏版）》请在三一文库上搜索。

1、哈希表（散列表）的设计与实现【问题描述】 设计哈希表实现电话号码查找系统。【基本要求】 (1) 设每个记录有下列数据项：电话号码、用户名、地址； (2) 从键盘输入各记录，分别以电话号码为关键字建立散列表； (3)采用拉链法解决冲突； (4)查找并显示给定电话号码的记录； (5) 查找并显示给定用户名的记录。【选做内容】 (1)系统功能的完善； (2)设计不同的散列函数，比较冲突率； (3)在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。地址嫌麻烦没加，使用的时候要先新建一个空白的data.txt文件。/ hash.cpp : 定义控制台应用程序的入口点。/#i

2、nclude stdafx.h#include#includeusing namespace std;#define P 100#define Z 97#define MAX 100struct datachar name15;/存放姓名long num;/存放电话号码;typedef struct hashdatachar name15;long num;hashdata *next;*linklist;data hMAX;hashdata nhashMAX;hashdata nahashMAX;unsigned int BKDRHash(char *str)/字符串哈希值生成函数 unsi

3、gned int seed = 31; / 31 131 1313 13131 131313 etc. unsigned int hash = 0; while (*str) hash = hash * seed + (*str+); return (hash & 0x7FFFFFFF);unsigned int APHash(char *str)/字符串哈希值生成函数 unsigned int hash = 0; int i; for (i=0; *str; i+) if (i & 1) = 0) hash = (hash 3); else hash = (hash 5); return (

4、hash & 0x7FFFFFFF);int datanum(int j)/统计hMAX数组中有多少数据for(j=0;jP&hj.num!=NULL;j+)return j;void wdata()/新建电话簿数据文件for(int i=0;i1;i+)scanf(%s%d,&hi.name,&hi.num);FILE *fp;fp=fopen(data.txt,wb);fwrite(h,sizeof(struct data),1,fp);fclose(fp);void wpdata()/将hMAX的数据写入到文件当中int j=datanum(j);FILE *fp;fp=fopen(da

5、ta.txt,wb);fwrite(h,sizeof(struct data),j,fp);fclose(fp);void adata()/在电话簿中添加数据并写入文件for(int i=0;i1;i+)scanf(%s%d,&hi.name,&hi.num);FILE *fp;fp=fopen(data.txt,ab);fwrite(h,sizeof(struct data),1,fp);fclose(fp);void rdata()/读取文件中的电话簿数据FILE *fp;fp=fopen(data.txt,rb);fread(h,sizeof(struct data),P,fp);int

6、 j=datanum(j);printf(n编号 姓 名 电 话nn);for(int i=0;ij;i+)printf(%4d ,i+1);printf(%10s %10dn,hi.name,hi.num);fclose(fp);void ldata()/载入文件到hMAX数组当中FILE *fp;fp=fopen(data.txt,rb);fread(h,sizeof(struct data),P,fp);fclose(fp);void ddata(int n)/删除电话簿中数据if(n=0)return;ldata();int j=datanum(j),i;for(i=n;ij;i+)s

7、trcpy(hi-1.name,hi.name);hi-1.num=hi.num;hj-1.num=NULL;wpdata();void numhash(struct data sMAX)/按电话号码生成哈希表int k=0;int j=datanum(j);for(int i=0;iname,si.name);p-num=si.num;p-next=nhashk.next;nhashk.next=p;void fnumhash(long n)/按电话号码在哈希表中查找数据int k=0;k=n%Z;linklist p;p=&nhashk;if(p-num=n) printf(n姓 名 电

8、话n);printf(%6s %10dnn,p-name,p-num);elsewhile(p!=NULL)if(p-num=n)printf(n姓 名 电 话n);printf(%6s %10dnn,p-name,p-num);break;elseif(p-next=NULL)printf(n该号码不存在！nn);p=p-next;void namehash(data sMAX)/按姓名生成哈希表int k=0;int j=datanum(j);for(int i=0;iname,si.name);p-num=si.num;p-next=nahashk.next;nahashk.next=p

9、;void fnamehash(char str3)/按姓名在哈希表中查找数据int k=0;k=BKDRHash(str);k=k%Z;linklist p;p=&nahashk;if(APHash(str)=APHash(nahashk.name) printf(n姓 名 电 话n);printf(%6s %10dnn,p-name,p-num);elsewhile(p!=NULL)if(APHash(str)=APHash(p-name)printf(n姓 名 电 话n);printf(%6s %10dnn,p-name,p-num);break;elseif(p-next=NULL)p

10、rintf(n该姓名不存在！nn);p=p-next;void rnumhash()/输出按电话号码生成的哈希表printf(n编号 姓 名 电 话nn);for(int i=0;inext;while(p!=NULL)printf( -%10s %10d,p-name,p-num);p=p-next;printf(n);elseprintf(%4d,i);printf(%10s %10dn,nhashi.name,nhashi.num);elseprintf(%4d,i);printf(n);void rnamehash()/生成按姓名生成的哈希表printf(n编号 姓 名 电 话nn);

11、for(int i=0;inext;while(p!=NULL)printf( -%10s %10d,p-name,p-num);p=p-next;printf(n);elseprintf(%4d,i);printf(%10s %10dn,nahashi.name,nahashi.num);elseprintf(%4d,i);printf(n);int _tmain(int argc, _TCHAR* argv)int m;ldata();numhash(h);namehash(h);cout*电话号码查询系统*endlendl;printf(tttt1.电 话 簿ntttt2.按电话查找nt

12、ttt3.按姓名查找ntttt4.显示哈希表ntttt0.退 出nn);cout*endl;while(scanf(%d,&m)&m!=0)switch(m)case 1:int n;printf(n1.新 建n2.添 加n3.显 示n4.删 除n0.退 出n);while(scanf(%d,&n)&n!=0)switch(n)case 1: printf(n姓 名 电 话n);wdata();break;case 2: printf(n姓 名 电 话n);adata();break;case 3:rdata();break;case 4:int n;rdata();printf(n请输入编号

13、(0.退出删除):);scanf(%d,&n);ddata(n);break;printf(n1.新 建n2.添 加n3.显 示n4.删 除n0.退 出n);break;case 2:int num;/rnumhash();/ldata();/numhash(h);printf(请输入一个电话号码:);scanf(%d,&num);fnumhash(num);break;case 3:char name3;/rnamehash();/ldata();/namehash(h);printf(请输入一个姓名:);scanf(%s,name);fnamehash(name);break;case 4:int m;printf(1.按号码显示n2.按姓名显示n);scanf(%d,&m);if(m=1)rnumhash();elsernamehash();break;default:break;cout*电话号码查询系统*endlendl;printf(tttt1.电 话 簿ntttt2.按电话查找ntttt3.按姓名查找ntttt4.显示哈希表ntttt0.退 出nn);cout*endl;return 0;