#include
#include?
#include
#include
#include?
#include?

using?namespace?std;

#define?MAXSIZE??20??//電話薄記錄數(shù)量?
#define?MAX_SIZE?20????//人名的最大長(zhǎng)度
#define?HASHSIZE?53????//定義表長(zhǎng)??
#define?SUCCESS?1
#define?UNSUCCESS?-1
#define?LEN?sizeof（HashTable）
typedef?int?Status;
typedef?char?NA[MAX_SIZE];

typedef?struct{//記錄
	NA?name;
	NA?tel;
	NA?add;
}Record;

typedef?struct{//哈希表
	Record?*elem[HASHSIZE];????//數(shù)據(jù)元素存儲(chǔ)基址
	int?count;?????????????????//當(dāng)前數(shù)據(jù)元素個(gè)數(shù)
	int?size;??????????????????//當(dāng)前容量
}HashTable;

Status?eq（NA?xNA?y）{//關(guān)鍵字比較，相等返回SUCCESS；否則返回UNSUCCESS
	if（strcmp（xy）==0）
		return?SUCCESS;
	else?return?UNSUCCESS;
}

Status?NUM_BER;?????//記錄的個(gè)數(shù)
HashTable?*H;

void?getin（Record*?a）{//鍵盤(pán)輸入各人的信息
	printf（“輸入要添加的個(gè)數(shù)：\n“）;
	scanf（“%d“&NUM_BER）;
	int?i;?
	for（i=0;i		
		printf（“請(qǐng)輸入第%d個(gè)記錄的用戶名:\n“i+1）;
		scanf（“%s“a[i].name）;
		printf（“請(qǐng)輸入%d個(gè)記錄的電話號(hào)碼:\n“i+1）;
		scanf（“%s“a[i].tel）;
		printf（“請(qǐng)輸入第%d個(gè)記錄的地址:\n“i+1）;
		scanf（“%s“a[i].add）;?????????//gets（str2）;??????
	}
}

void?ShowInformation（Record*?a）//顯示輸入的用戶信息
{?
	int?i;
	for（?i=0;i		printf（“\n第%d個(gè)用戶信息:\n?姓????名：%s\n?電話號(hào)碼：%s\n?聯(lián)系地址：%s\n“i+1a[i].namea[i].tela[i].add）;?
}???????????????????????????????????

void?Cls（Record*?a）{
	printf（“*“）;?
????system（“cls“）;
}
long?fold（NA?s）{//人名的折疊處理
	char?*p;
	long?sum=0;
	NA?ss;
	strcpy（sss）;//復(fù)制字符串，不改變?cè)址拇笮?xiě)
	strupr（ss）;//將字符串ss轉(zhuǎn)換為大寫(xiě)形式
	p=ss;
	while（*p!=‘\0‘）
		sum+=*p++;
	printf（“\nsum====================%d“sum）;?
	return?sum;
}

int?Hash1（NA?str）{//哈希函數(shù)
	long?n;
	int?m;
	n=fold（str）;//先將用戶名進(jìn)行折疊處理
	m=n%HASHSIZE;?????//折疊處理后的數(shù)，用除留余數(shù)法構(gòu)造哈希函數(shù)
	return?m;???//并返回模值
}


int?Hash2（NA?str）{//哈希函數(shù)
	long?n;
	int?m;
	n?=?atoi（str）;//把字符串轉(zhuǎn)換成整型數(shù).
	m=n%HASHSIZE;?????//用除留余數(shù)法構(gòu)造哈希函數(shù)
	return?m;???//并返回模值
}

Status?collision（int?pint?&c）{//沖突處理函數(shù)，采用二次探測(cè)再散列法解決沖突
	int?iq;
	i=c/2+1;
	while（i		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;
}
void?benGetTime（）;
void?CreateHash1（HashTable*?HRecord*?a）{//建表，以人的姓名為關(guān)鍵字，建立相應(yīng)的散列表
	//若哈希地址沖突，進(jìn)行沖突處理
	benGetTime（）;
	int?ip=-1cpp;?????????????????
	for（i=0;i		c=0;
		p=Hash1（a[i].name）;
		pp=p;
		while（H->elem[pp]!=NULL）?{
			pp=collision（pc）;
			if（pp<0）{
				printf（“第%d記錄無(wú)法解決沖突“i+1）;//需要顯示沖突次數(shù)時(shí)輸出
				continue;
			}//無(wú)法解決沖突，跳入下一循環(huán)
		}
		H->elem[pp]=&（a[i]）;??//求得哈希地址，將信息存入
		H->count++;
		printf（“第%d個(gè)記錄沖突次數(shù)為%d。\n“i+1c）;//需要顯示沖突次數(shù)時(shí)輸出
	}
	printf（“\n建表完成!\n此哈希表容量為%d當(dāng)前表內(nèi)存儲(chǔ)的記錄個(gè)數(shù)為%d.\n“HASHSIZEH->count）;
	benGetTime（）;
}

void?SearchHash1（HashTable*?Hint?&c）{//在通訊錄里查找姓名關(guān)鍵字，若查找成功，顯示信息
	//c用來(lái)記錄沖突次數(shù)查找成功時(shí)顯示沖突次數(shù)
	benGetTime（）;
	NA?str;
	printf（“\n請(qǐng)輸入要查找記錄的姓名：\n“）;
	scanf（“%s“str）;
	int?ppp;
	p=Hash1