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

哈希表散列表的设计与实现

【问题描述】

设计哈希表实现电话号码查找系统。

【基本要求】

(1)设每个记录有下列数据项 电话号码、用户名、地址

(2)从键盘输入各记录分别以电话号码为关键字建立散列表

(3)采用拉链法解决冲突

(4)查找并显示给定电话号码的记录

(5)查找并显示给定用户名的记录。

【选做内容】

(1)系统功能的完善

(2)设计不同的散列函数 比较冲突率

(3)在散列函数确定的前提下尝试各种不同类型处理冲突的方法考察平均查找长度的变化。

地址嫌麻烦没加使用的时候要先新建一个空白的data.txt文件。

//hash.cpp:定义控制台应用程序的入口点。

//

#include"stdafx.h"

#include<stdio.h>

#include<iostream>using namespace std;

#define P 100

#define Z 97

#define MAX 100struct data{char name[15];//存放姓名long num;//存放电话号码

};typedef struct hashdata{char name[15];long num;hashdata*next;

}*linklist;data h[MAX];hashdata nhash[MAX];hashdata nahash[MAX];

unsigned int BKDRHash(char*str)//字符串哈希值生成函数{unsigned 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<<7)^(*str++)^(hash>>3));}else

{hash^=(~((hash<<11)^(*str++)^(hash>>5)));}

}return(hash&0x7FFFFFFF);

}int datanum(int j)//统计h[MAX]数组中有多少数据

{for(j=0;j<P&&h[j].num!=NULL;j++){}return j;

}void wdata()//新建电话簿数据文件

{for(int i=0;i<1;i++)

{s canf("%s%d",&h[i].name,&h[i].num);

}

FILE*fp;fp=fop en("data.txt","wb");fwrite(h,sizeof(struct data),1,fp);fclose(fp);

}void wpdata()//将h[MAX]的数据写入到文件当中{int j=datanum(j);

FILE*fp;fp=fop en("data.txt","wb");fwrite(h,sizeof(struct data),j,fp);fclose(fp);

}void adata()//在电话簿中添加数据并写入文件{for(int i=0;i<1;i++)

{s canf("%s%d",&h[i].name,&h[i].num);}

FILE*fp;fp=fop en("data.txt","ab");fwrite(h,sizeof(struct data),1,fp);fclose(fp);

}void rdata()//读取文件中的电话簿数据

{

FILE*fp;fp=fop en("data.txt","rb");fread(h,sizeof(struct data),P,fp);int j=datanum(j);printf("\n编号 姓 名 电 话\n\n");for(int i=0;i<j;i++)

{printf("%4d ",i+1);printf("%10 s%10 d\n",h[i].name,h[i].num);}fclose(fp);

}void ldata()//载入文件到h[MAX]数组当中

{

FILE*fp;fp=fop en("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;i<j;i++)

{strcpy(h[i-1].name,h[i].name);h[i-1].num=h[i].num;

}h[j-1].num=NUL L;wpdata();

}void numhash(struct data s[MAX])//按电话号码生成哈希表{int k=0;int j=datanum(j);for(int i=0;i<j;i++)

{k=s[i].num%Z;i f(nha sh[k].num==NULL){strcpy(nha s h[k].name,s[i].name);nha sh[k].num=s[i].num;nhash[k].next=NULL;

}else{linklist p;p=(linklist)malloc(sizeof(hashdata));strcpy(p->name,s[i].name);p->num=s[i].num;p->next=nha sh[k].next;nhash[k].next=p;

}

}

}void fnumhash(long n)//按电话号码在哈希表中查找数据{int k=0;k=n%Z;linklist p;p=&nha s h[k];i f(p->num==n){printf("\n姓 名 电 话\n");

printf("%6 s%10d\n\n",p->name,p->num);}else{while(p!=NULL){i f(p->num==n){printf("\n姓 名 电 话\n");printf("%6 s%10d\n\n",p->name,p->num);break;}else{if(p->next==NULL){printf("\n该号码不存在 \n\n");}p=p->next;}

}

}

}void namehash(data s[MAX])//按姓名生成哈希表

{int k=0;int j=datanum(j);for(int i=0;i<j;i++)

{k=BKDRHash(s[i].name);k=k%Z;if(nahash[k].num==NULL){strcpy(naha sh[k].name,s[i].name);naha sh[k].num=s[i].num;nahash[k].next=NULL;

}else{linklist p;p=(linklist)malloc(sizeof(hashdata));strcpy(p->name,s[i].name);p->num=s[i].num;p->next=nahash[k].next;nahash[k].next=p;

}

}

}void fnamehash(char str[3])//按姓名在哈希表中查找数据{int k=0;k=BKDRHash(str);k=k%Z;linklist p;p=&nahash[k];if(APHash(str)==APHash(nahash[k].name)){

printf("\n姓 名 电 话\n");printf("%6 s%10 d\n\n",p->name,p->num);}else{while(p!=NULL){if(APHash(str)==APHash(p->name)){printf("\n姓 名 电 话\n");printf("%6 s%10d\n\n",p->name,p->num);break;}else{if(p->next==NULL){printf("\n该姓名不存在 \n\n");}p=p->next;

}

}

}

}void rnumhash()//输出按电话号码生成的哈希表

{printf("\n编号 姓 名 电 话\n\n");for(int i=0;i<MAX;i++)

{i f(nha sh[i].num!=NULL){if(nhash[i].next!=NULL){printf("%4d",i);printf("%10 s%10 d",nha s h[i].name,nha sh[i].num);linklist p;p=&nha sh[i];p=p->next;while(p!=NULL){printf(" ->%10 s%10d",p->name,p->num);p=p->next;

}printf("\n");

}else{printf("%4d",i);printf("%10 s%10 d\n",nhash[i].name,nhash[i].num);

}}else{printf("%4d",i);printf("\n");

}

}

}

void rnamehash()//生成按姓名生成的哈希表

{printf("\n编号 姓 名 电 话\n\n");for(int i=0;i<MAX;i++)

{i f(naha s h[i].num!=NULL){if(nahash[i].next!=NULL){printf("%4d",i);printf("%10 s%10d",nahash[i].name,nahash[i].num);linklist p;p=&nahash[i];p=p->next;while(p!=NULL){printf(" ->%10 s%10d",p->name,p->num);p=p->next;

}printf("\n");

}else{printf("%4d",i);printf("%10 s%10 d\n",nahash[i].name,nahash[i].num);

}}else{printf("%4d",i);printf("\n");

}

}

}int_tmain(int argc,_TCHAR*argv[])

{int m;ldata();numhash(h);namehash(h);

<"*******************************电 话 号 码 查 询 系 统

*******************************"<<printf("\t\t\t\t 1.电话簿\n\t\t\t\t2.按电话查找\n\t\t\t\t3.按姓名查找\n\t\t\t\t4.显示哈希表\n\t\t\t\t0.退出\n\n");cout<<"********************************************************************

**********"<<endl;while((scanf("%d",&m))&&m!=0){switch(m)

{case 1:

int n;printf("\n 1.新建\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请输入编号(0.退出删除):");s canf("%d",&n);ddata(n);break;

}printf("\n 1.新建\n2.添加\n3.显示\n4.删除\n0.退出\n");

}break;case 2:int num;

//rnumha s h();

//ldata();

//numha s h(h);printf("请输入一个电话号码:");s c anf("%d",&num);fnumh a s h(num);break;case 3:char name[3];

//rnamehas h();

//ldata();

//namehash(h);printf("请输入一个姓名:");s canf("%s",name);fnamehash(name);break;case 4:int m;printf("1.按号码显示\n2.按姓名显示\n");s canf("%d",&m);if(m==1){rnumh a s h();}else

{rnamehash();}break;de fault:break;

}

<"*******************************电 话 号 码 查 询 系 统

*******************************"<<printf("\t\t\t\t 1.电话簿\n\t\t\t\t2.按电话查找\n\t\t\t\t3.按姓名查找\n\t\t\t\t4.显示哈希表\n\t\t\t\t0.退出\n\n");cout<<"********************************************************************

**********"<<endl;

}return 0;

}