设计要求

设计以姓名为关键字的散列表（哈希表），实现通讯录查找系统，完成相应的建表和查表程序。

（1）设每个记录有下列数据项：用户名、电话号码、地址；

（2）从键盘输入各记录，分别以姓名为关键字建立散列表；

（3）人名可以采用汉语拼音形式。人名字符串转化为数字的方式自行决定。

（4）哈希函数用除留余数法构造，采用二次探测再散列法解决冲突；

（5）根据姓名查找，找到显示给定记录的电话号码和地址；找不到提示通讯录无此人。

（6）通讯录信息保存到文件。

#include <stdio.h>  
#include <stdlib.h>
#include <string.h>
#include <ctype.h> //用于实现toascii()函数
#include <windows.h> 
#include <conio.h>enum State {Empty, Active, Deleted} ;
//int hashsize[] = {31,67,137}; //哈希表容量递增表，一个合适的素数序列
typedef struct node  
{  //name为用户名，phone为电话号码，address为地址char name[20];char phone[15];char address[30];  enum State state ;  
} Node;  
typedef struct hashTable  
{  Node *array;//数据元素存储基址，动态分配数组int load;//当前数据元素个数int size;//hashsize[size]为当前容量  
}HashTable ;  //函数原型声明 
void doubleSpace(HashTable &H);int hash(HashTable &H,char name[]){//将人名字符串转化为ASCII码值求和，然后计算散列地址 int i = 1;int k =toascii(name[0]);while(name[i]!='\0'){k += toascii(name[i]);i++;}int key = k % H.size;   return key;
}bool isPrime (int n)  //判断n是否为素数 
{  if(n==2||n==3)return true;if(n==1||n%2==0)return false;for(int i=3;i*i<=n;i+=2)if(n%i==0)return false;return true;
}int nextPrime (int n)  //寻找大于或等于n的最小素数 
{  if(n % 2==0) ++n;while(!isPrime(n)) n += 2;return n; 
}int initializeTable (HashTable &H) //初始化散列表 
{int length = 30;H.size = nextPrime(length);H.array =(Node *)malloc(sizeof(Node *));H.load = 0; 
}bool insert (HashTable &H)  
{  char tname[18]; int pos,collisionNum = 0; //碰撞次数if(H.load*2>=H.size)doubleSpace(H);//如果数组已经半满，扩大空间 getchar();gets(tname);pos =hash(H,tname);  //计算散列地址 if(H.array[pos].state!=Active){ //找到空单元，插入 printf("请输入要添加的人的电话和地址\n");strcpy(H.array[pos].name,tname);gets(H.array[pos].phone);gets(H.array[pos].address);H.array[pos].state=Active;++H.load;//新插入一个元素，负载因子++ printf("添加成功!\n");return true;}else pos=(pos+2*(++collisionNum)-1)%H.size; //已存在则计算下一地址 return false;
}   void doubleSpace(HashTable &H){Node *tmp=H.array;int oldsize = H.size;H.size= nextPrime(oldsize*2);//找大于2倍表长的最小素数 H.load = 0;H.array =(Node *)malloc(sizeof(Node *));for(int i=0;i<oldsize;i++)if(tmp[i].state==Active)insert(H);free(tmp);
}bool remove (HashTable &H)  
{char tname[18]; int initPos,pos;int collisionNum = 0; //碰撞次数getchar();gets(tname);initPos = pos =hash(H,tname);do{//遍历整个数组寻找被删元素 if(H.array[pos].state==Empty)return false;//没找到 if(H.array[pos].state==Active)//找到 {H.array[pos].state=Deleted;--H.load;//元素被删除，负载因子-- printf("删除成功!\n");return true;}pos=(pos+2*(++collisionNum)-1)%H.size;}while(pos!=initPos);return false;
}  bool search (HashTable &H)
{   char tname[18];int pos,collisionNum = 0; //碰撞次数getchar();gets(tname);pos =hash(H,tname);if(H.array[pos].state==Empty) {//没找到 printf("该记录不存在!\n");return false;}if(H.array[pos].state==Active){if(strcmp(tname,H.array[pos].name)==0){printf("您所查找的信息：姓名：%s,电话：%s,地址：%s",H.array[pos].name,H.array[pos].phone,H.array[pos].address);return true;} else pos=(pos+2*(++collisionNum)-1)%H.size;}printf("该记录不存在!\n");return false;
}  void list(HashTable &H) //显示以姓名为关键字形成的列表
{int i;for(i=0;i<31;i++)if(H.array[i].state == Active)printf("姓名：%s,电话：%s,地址：%s\n",H.array[i].name,H.array[i].phone,H.array[i].address);
} void save(HashTable &H)//保存用户信息
{int i;FILE* fout;if((fout=fopen("output.txt","w"))!=NULL){for(i=0;i<31;i++)if(H.array[i].state == Active)fprintf(fout,"姓名：%s,电话：%s,地址：%s\n",H.array[i].name,H.array[i].phone,H.array[i].address);}fclose(fout);
}void Exit()
{printf("\nThank you for using this system!\n");printf("Press enter to exit...\n");getchar();exit(0);
}void DisplayMenu()
{system("cls");//每次显示主界面前先清屏 printf("**********欢迎进入121022班通讯录系统**********\n");printf("*          1.添加记录                         *\n");printf("*          2.删除记录                         *\n");printf("*          3.查找记录                         *\n");printf("*          4.显示记录                         *\n");printf("*          5.保存记录                         *\n");printf("*          6.退出系统                         *\n");printf("**********************************************\n");printf("请输入您想执行的功能对应的数字：");
}int main() {HashTable H;initializeTable(H);int option;while(1){DisplayMenu();scanf("%d",&option);switch(option){case 1:printf("请输入要添加的姓名：");insert(H);break;case 2:printf("请输入要删除的记录的姓名：");remove(H);break;case 3:printf("请输入要查询的姓名：");search(H);break;case 4:list(H);break;case 5:save(H);printf("已保存至\"output.txt\"中");break; case 6:Exit();return 0;}getch();}return 0;
}