设计要求

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

（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;
}