#include<iostream> //cout,cin语句的头文件#include<stdlib.h> //清屏函数头文件：使用csl时调用system#include<string> //字符串头文件#include<stdio.h>#include<fstream>#define MAXSIZE 100 //电话薄记录的数量#define MAX_SIZE 50 //用户名、电话号码、地址的最大长度#define HASHSIZE 400 //定义表长#define SUCCESS 1 //查找#define UNSUCCESS -1#define LEN sizeof(HashTable) // 哈希表的长度using namespace std;typedef int Status;//typedef用来定义类型的别名。

此处用status作为int别名，目的表达int 变量是一个状态变量。

typedef char NA[MAX_SIZE]; //NA作为char的别名typedef struct{ // 自定义一个记录用户名、电话号码、联系地址的结构体的别名recordNA name,tel,add,way;}Record;Record a[HASHSIZE];typedef struct{ //散列表Record *elem[HASHSIZE]; //数据元素存储地址int count; //数据元素个数int size; //容量}HashTable;Status eq(NA x,NA y){ //关键字比较，相等返回SUCCESS；否则返回UNSUCCESSif(strcmp(x,y)==0)//2个字符串的大小比较s1=s2，strcmp(s1,s2) == 0; s1>s2, strcmp(s1,s2) == 1; s1<s2, strcmp(s1,s2) == -1;return SUCCESS;elsereturn UNSUCCESS;}Status NUM_BER; //记录的个数void getin(Record* a){ // 键盘输入联系人的信息,Record*调用Record函数；a是参数cout<<"请输入要添加的联系人的个数：\n";cin>>NUM_BER;int i;for(i=0;i<NUM_BER;i++){cout<<"请输入第"<<i+1<<"个记录的用户名:\n";cin>>a[i].name;cout<<"请输入第"<<i+1<<"个记录的电话号码:\n";cin>>a[i].tel;cout<<"请输入第"<<i+1<<"个记录的地址:\n";cin>>a[i].add;}}void ShowInformation(Record* a)//显示输入的用户信息{int i;for( i=0;i<NUM_BER;i++)cout<<"\n第"<<i+1<<"个用户信息:\n 姓名："<<a[i].name<<"\n 电话号码："<<a[i].tel<<"\n 联系地址："<<a[i].add<<"\n--------\n";}long fold(NA s) //人名的折叠处理:将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址{char *p;long sum=0;NA ss;strcpy(ss,s);//复制字符串，不改变原字符串的大小写strupr(ss);//将字符串ss转换为大写形式p=ss;while(*p!='\0')sum+=*p++;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 UNSUCCESS;}int searchHash( HashTable * &H, NA key, int &p, int &c ,int way ){if( way == 1 ){p=Hash1( key );while(H->elem[p]!=NULL && !eq( key, H->elem[p]->name ) )//若哈希地址冲突，进行冲突处理collision( p ,++c );if( eq( key, H->elem[p]->name ) )return 1;elsereturn 0;}else{p=Hash2( key );while(H->elem[p]!=NULL && !eq( key, H->elem[p]->tel ) )//若哈希地址冲突，进行冲突处理collision( p ,++c );if( eq( key, H->elem[p]->tel ) )return 1;elsereturn 0;}}// 建表,若哈希地址冲突，进行冲突处理void CreateHash(HashTable* H ,Record* a){cout<<"\n 〓〓〓〓〓〓建立散列表〓〓〓〓〓〓〓";cout<<"\n ⑴. 以姓名建立散列表(再散列法解决冲突) ";cout<<"\n ⑵. 以电话号码建立散列表(再散列法解决冲突) ";cout<<"\n ☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆";cout<<"请输入选择:";int num,i,p=-1,c;cin>>num;for(i=0;i<NUM_BER;i++){c=0;if( num==1 ){p=Hash1( a[i].name );while(H->elem[p]!=NULL && !eq( a[i].name, H->elem[p]->name ) )//若哈希地址冲突，进行冲突处理collision( p ,++c );}else{p=Hash2( a[i].tel );while(H->elem[p]!=NULL && !eq( a[i].tel, H->elem[p]->tel ) )//若哈希地址冲突，进行冲突处理collision( p ,++c );}H->elem[p]=a+i; //求得哈希地址，将信息存入H->count++;cout<<"第"<<i+1<<"个记录冲突次数为"<<c<<"。

\n";//需要显示冲突次数时输出}cout<<"\n建表完成!\n此哈希表容量为"<<HASHSIZE<<",当前表内存储的记录个数为"<<H->count<<".\n";}// 查找用户名和电话号码的记录；void SearchHash ( HashTable* H,int &c){//在通讯录里查找关键字，若查找成功，显示信息//c用来记录冲突次数,查找成功时显示冲突次数NA type;int p;cout<<"\n 〓〓〓〓〓〓查找并显示用户信息记录〓〓〓〓〓〓〓";cout<<"\n ⑴. 查找并显示给定用户名的记录";cout<<"\n ⑵. 查找并显示给定电话号码的记录";cout<<"\n ☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆";cout<<"请输入选择:";int num;cin>>num;switch(num){case 1:cout<<"\n请输入要查找的用户名：\n";cin>>type;searchHash( H, type, p, c, 1);if( eq( type, H->elem[p]->name )==1){cout<<"\n查找成功！以下是您需要要查找的信息：\n\n";cout<<"姓名："<<H->elem[p]->name<<"\n电话号码："<<H->elem[p]->tel<<"\n 联系地址："<<H->elem[p]->add<<"\n";}elsecout<<"\n对不起，该用户不存在\n";break;case 2:cout<<"\n请输入要查找电话号码：\n";cin>>type;searchHash( H, type, p, c, 2);if( eq( type, H->elem[p]->tel )==1){cout<<"\n查找成功！以下是您需要要查找的信息：\n\n";cout<<"姓名："<<H->elem[p]->name<<"\n电话号码："<<H->elem[p]->tel<<"\n 联系地址："<<H->elem[p]->add<<"\n";}elsecout<<"\n对不起，该用户不存在\n";break;default:cout<<"输入错误，请重新输入!";}}void Save(){ //保存ifstream in;ofstream out;out.open("123.txt");printf("\n保存成功!");for(int i=0; i<NUM_BER; i++ ){out<<"姓名："<<a[i].name<<"\n电话号码："<<a[i].tel<<"\n联系地址："<<a[i].add<<"\n";}return;}void main_menu(){int c,flag=1;////定义一个布尔型变量flag并初始化为真(true)HashTable *H;H=(HashTable*)malloc(LEN);for(int i=0;i<HASHSIZE;i++)H->elem[i]=NULL;H->size=HASHSIZE;H->count=0;while (1){ // while使电话查询系统执行后返回主菜单的界面system("cls");cout<<"\n 〓〓〓〓〓〓↖(^ω^)↗欢迎使用电话号码查找系统〓〓〓〓〓〓〓";cout<<"\n ⑴. 添加用户信息";cout<<"\n ⑵. 读取所有用户信息";cout<<"\n ⑶. 建立散列表(再散列法解决冲突) ";cout<<"\n ⑷. 查找并显示给定用户的记录";cout<<"\n ⑸. 保存";cout<<"\n ⑹. 退出";cout<<"\n 提示：进行4操作前请先进行3操作 .否则无法查找成功!";cout<<"\n ☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆";cout<<"\n\n请选择：";int num;cin>>num;switch(num){case 1:getin(a);system("pause");break;case 2:ShowInformation(a);system("pause");break;case 3:CreateHash (H,a); /* 建立散列表*/system("pause");break;case 4:c=0;SearchHash (H,c);system("pause");break;case 5:Save();system("pause");break;case 6:return ;break;default:cout<<"输入错误，请重新输入!";cout<<"\n";}}}int main(int argc, char* argv[]){main_menu();//执行结束后清屏，显示主菜单return 0;}。