///////////////////////////////////////////////////////////////
////////////////////哈希表的設計與實現////////////////////////
/////////////////////////////軟件08-2?王??華/////////////////
/////////////////////////////軟件08-2?劉孟奇////////////////
#include
#include
#include
#include
#include?
#define?MAXSIZE??20??//電話薄記錄數量?
#define?MAX_SIZE?20????//人名的最大長度
#define?HASHSIZE?53????//定義表長??
#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];????//數據元素存儲基址
	int?count;?????????????????//當前數據元素個數
	int?size;??????????????????//當前容量
}HashTable;

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

Status?NUM_BER;?????//記錄的個數

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

void?ShowInformation（Record*?a）//顯示輸入的用戶信息
{	
	int?i;
	for（?i=0;i		printf（“\n第%d個用戶信息:\n?姓????名：%s\n?電話號碼：%s\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）;//復制字符串，不改變原字符串的大小寫
	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?pint?&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）{//建表，以人的姓名為關鍵字，建立相應的散列表
	????????????????????????????????????//若哈希地址沖突，進行沖突處理
	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記錄無法解決沖突“i+1）;//需要顯示沖突次數時輸出
				continue;
			}//無法解決沖突，跳入下一循環
		}
		H->elem[pp]=&（a[i]）;??//求得哈希地址，將信息存入
		H->count++;
		printf（“第%d個記錄沖突次數為%d。\n“i+1c）;//需要顯示沖突次數時輸出
	}
	printf（“\n建表完成!\n此哈希表容量為%d當前表內存儲的記錄個數為%d.\n“HASHSIZEH->count）;
	benGetTime（）;
}

void

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件?????823808??2009-12-22?13:04??課程設計-電話號碼查找系統\數據結構課程設計?劉孟奇.doc

?????文件?????822272??2009-12-22?13:04??課程設計-電話號碼查找系統\數據結構課程設計王華.doc

?????文件???????9341??2009-12-22?13:02??課程設計-電話號碼查找系統\課程設計--電話號碼查找系統.cpp

?????目錄??????????0??2009-12-22?16:51??課程設計-電話號碼查找系統

-----------?---------??----------?-----??----

??????????????1655421????????????????????4