#include<iostream> //cout,cin语句的头文件

#include<stdlib.h> //清屏函数头文件：使用csl时调用system

#include //字符串头文件

#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{ // 自定义一个记录用户名、电话号码、联系地址的结构体的别名record

NA 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；否则返回UNSUCCESS

if(strcmp(x,y)==0)//2个字符串的大小比较s1=s2，strcmp(s1,s2) == 0; s1>s2, strcmp(s1,s2) == 1; s1strcmp(s1,s2) == -1;

return SUCCESS;

else

return 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<<"请输入第"<个记录的用户名:\n";

cin>>a[i].name;

cout<<"请输入第"<个记录的电话号码:\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第"<个用户信息:\n 姓 名："<i].name<<"\n 电话号码："<i].tel<<"\n 联系地址："<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;

else

return 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;

else

return 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<<"第"<个记录冲突次数为"<。\n";//需要显示冲突次数时输出

}

cout<<"\n建表完成!\n此哈希表容量为"<当前表内存储的记录个数为"<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<<"姓 名："<elem[p]->name<<"\n电话号码："<elem[p]->tel<<"\n联系地址："<elem[p]->add<<"\n";

}

else

cout<<"\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<<"姓 名："<elem[p]->name<<"\n电话号码："<elem[p]->tel<<"\n联系地址："<elem[p]->add<<"\n";

}

else

cout<<"\n对不起，该用户不存在 \n";

break;

default:

cout<<"输入错误，请重新输入!";

}

}

void Save(){ //保存

ifstream in;

ofstream out;

out.open("123.txt");

printf("\n保存成功!");

for(int i=0; ii++ ){

out<<"姓 名："<i].name<<"\n电话号码："<i].tel<<"\n联系地址："<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;

}