散列表的設(shè)計與實現(xiàn)報告

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目：散列表的設(shè)計與實現(xiàn)專業(yè)：計算機(jī)科學(xué)與技術(shù)指導(dǎo)教師：李竹林姓名：劉朋飛( 1060309014004)何 偉( 1060309014042)需求分析:1. 任務(wù)需求：設(shè)計散列表實現(xiàn)電話號碼查找系統(tǒng)；2. 功能需求：設(shè)每個記錄有下列數(shù)據(jù)項：電話號碼、用戶名、地址；.從鍵盤輸入各記錄，分別以電話號碼和用戶名為關(guān)鍵字建立散列表；.采用一定的方法解決沖突；查找并顯示給定電話號碼的記錄；.查找并顯示給定用戶名的記錄；3. 其他功能：系統(tǒng)功能的完善；.設(shè)計不同的散列函數(shù)，比較沖突率；.在散列函數(shù)確定的前提下，嘗試各種不同類型處理沖突的方法，考察平均查找長 度的變化；總體設(shè)計：1.系統(tǒng)功

2、能設(shè)計：定義電話本記錄數(shù)量( MAXSIZE )、表長(HASHSIZE )、姓名長度(MAX_SIZE)以 及結(jié)構(gòu)體typedef struct 的內(nèi)容，構(gòu)造兩個哈希函數(shù)hashl和hash2。功能示意圖：功能示意圖2. 系統(tǒng)功能設(shè)計：增加系統(tǒng)功能如下 : 添加用戶信息 ; 讀取所有用戶信息 ; 以姓名建立哈希表 ;以電話 號碼建立哈希表 ; 查找并顯示給定用戶名的記錄 ; 查找并顯示給定電話號碼的記錄 清屏以及保存功能；處理流程示意圖：開始1r進(jìn)入錄入系統(tǒng)1r獲得關(guān)鍵子key用Hashl(key)計算地址處理流程圖3. 功能模塊設(shè)計： . 運用 main 函數(shù)輸出電話本信息系統(tǒng)的整體界面，

3、在調(diào)試運行后如下：適輸入一*任勞選坂巧itit.養(yǎng)野誥 n-F世 足 的盤履塞 心簣右耳顯 序 細(xì)戢竝富吏 也沖左.-.-燼小I: I:出出請徹扎一/唯勞選壩.利用添加功能void getin(Record* a)實現(xiàn)用戶信息的錄入，在調(diào)試運行后如下:=? Etwfrmi i r5yfl( (叭十電 ts-Xt eb DI 匚眉匸呼is 輸兀 _ PE界矍舔!1*fr.人昭輔如的叮第,苗暢人烯丄平記錄闔用戶容I亦*“謚輸人弟1個記素溝冃話號拒:Ibl 丄 23 峙!*VH恒愉人和芥記K杓吐址“歸入染1-1H5?.囲用戶各 lny伯希i h茸士于記予溝丸譙尸社=諂陸入弟工個I存旳噸址：nn 1匸

4、利用哈希函數(shù) CREATEHASH1.2來構(gòu)造哈希表并用 Status collision函數(shù)的相應(yīng)功能來查找并解決沖突：H5-M(3第；!個記菲沖笑-攵皺為嶷 耳粉2 .為前黃內(nèi)存第詢計無滄梵粉”2CT1 IG211272HTiWisuai.實迎U戶出話號血戊產(chǎn)西適輸入一*任勞選坂巧I枝迎快用電活弓渦生代朿橫I? ?潢 沖 屮轉(zhuǎn) 昭.市l(wèi)td.ltd. fifi -n-nI I -IDIb-IDIb b bTMTM*.*.佶疥一疋逗 F.=F.=丿咕坪治昭 衣有耳號妊-?.亡總?cè)使?# *加W?W?廿申ialt出*“應(yīng)J;JNolhlir1J;JNolhlir1謂啟空艮En 利用void S

5、earchHash1(HashTable* H,int &c)在通訊錄里查找姓名關(guān)鍵字，若查找成功，顯示信息，c用來記錄沖突次數(shù)，查找成功時顯示沖突次數(shù)：g EVaPul c*十出凸姑再菲Jvroic-ctsLICDeixifiJLL.t-Me査我據(jù)沖笑窩數(shù)為筍丄您需旻要站？罷目 I 2 ia.DEBftlft2fiinK13S9三、詳細(xì)設(shè)計與實現(xiàn)部分:定義頭文件及基本屬性#in clude#in clude#in clude#in clude#in clude #define MAXSIZE 20/電話薄記錄數(shù)量#define MAX_SIZE 20/人名的最大長度#define HASHS

6、IZE 53/ 定義表長#define SUCCESS 1#define UNSUCCESS -1#define LEN sizeof(HashTable)typedef int Status;typedef char NAMAX_SIZE;定義結(jié)構(gòu)體typedef struct 記錄AT T 、沖 中眸 .1.1 JLflnrJLflnrF=“F=“ 亠-n7ln7l中豈 4 4出出審.?!先先1=11=11 1TITI$箱6 6 6 6講進(jìn)利用void SearchHash1(HashTable* H,int &c)在通訊錄里查找姓名關(guān)鍵字，若查找成功，顯示信息，c用來記錄沖突次數(shù)，查找成

7、功時顯示沖突次數(shù)：NA n ame;NA tel;NA add;Record;typedef struct 哈希表Record *elemHASHSIZE;/ 數(shù)據(jù)元素存儲基址UNSUCCESSint count; / 當(dāng)前數(shù)據(jù)元素個數(shù)int size; / 當(dāng)前容量HashTable;關(guān)鍵字比較功能的實現(xiàn)Status eq(NA x,NA y)關(guān)鍵字比較，相等返回SUCCES；否則返回if(strcmp(x,y)=0)return SUCCESS;else return UNSUCCESS;記錄個數(shù)功能的實現(xiàn)Status NUM_BER; /記錄的個數(shù)輸入信息功能void getin(Rec

8、ord* a)/ 鍵盤輸入各人的信息coutNUM_BER;int i; for(i=0;iNUM_BER;i+)cout 請輸入第 i+1;cout 請輸入第 i+1ai.tel;cout 請輸入第 i+1ai.add;/gets(str2);?顯示輸入信息的實現(xiàn)void ShowInformation(Record* a)/ 顯示輸入的用戶信息電話號碼：int i;for( i=0;iNUM_BER;i+)coutn 第 i+1 個 用 戶 信 息 :n 姓名 ： nai.teln 聯(lián)系地址： ai.addn;清屏功能的實現(xiàn)void Cls(Record* a)

9、cout*;system(cls);long fold(NA s)/ 人名的折疊處理char *p;long sum=0;NA ss;strcpy(ss,s);/ 復(fù)制字符串，不改變原字符串的大小寫strupr(ss);/ 將字符串 ss 轉(zhuǎn)換為大寫形式p=ss;while(*p!=0)sum+=*p+;coutnsum=sum;return sum;構(gòu)造哈希函數(shù)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

10、 Hash2(NA str)/ 哈希函數(shù)long n;int m;n = atoi(str);/ 把字符串轉(zhuǎn)換成整型數(shù) .m=n%HASHSIZE; / 用除留余數(shù)法構(gòu)造哈希函數(shù)return m; / 并返回模值沖突處理函數(shù)，用于解決沖突Status collision(int p,int &c)/ 沖突處理函數(shù)，采用二次探測再散列法解決沖突int i,q;i=c/2+1;while(i=0) return q;else i=c/2+1;elseq=(p-i*i)%HASHSIZE;c+;if(q=0) return q;else i=c/2+1;return UNSUCCESS;void b

11、enGetTime();void CreateHash1(HashTable* H,Record* a)/ 建表，以人的姓名為關(guān)鍵字，建立相應(yīng)的散列表benGetTime();int i,p=-1,c,pp;for(i=0;ielempp!=NULL) pp=collision(p,c);if(pp0)cout第i+1elempp=&(ai); / 求得哈希地址，將信息存入H-count+;cout第i+1個記錄沖突次數(shù)為c.n;需要顯示沖突次數(shù)時輸出coutn建表完成!n此哈希表容量為HASHSIZE當(dāng)前表內(nèi) 存儲的記 錄個數(shù)為 count.n;benGetTime();查找功能的實現(xiàn)voi

12、d SearchHash1(HashTable* H,int &c)/ 在通訊錄里查找姓名關(guān)鍵字， 若查找成功， 顯示信息 benGetTime();NA str;coutstr;int p,pp;p=Hash1(str);pp=p;while(H-elempp!=NULL)&(eq(str,H-elempp-name)=-1)pp=collision(p,c);if(H-elempp!=NULL&eq(str,H-elempp-name)=1)coutn查找成功！ n查找過程沖突次數(shù)為c.以下是您需要要查找的信息：nn;cout 姓 名： elempp-namen 電話號碼： elempp-

13、teln 聯(lián)系地址： elempp-addn;else coutn 此人不存在，查找不成功 !n;benGetTime();void benGetTime()SYSTEMTIME sys;GetLocalTime( &sys );coutsys.wYearsys.wMonthsys.wDaysys.wHoursys.wMinutesys.wSecondsys.wMilli seconds; void CreateHash2(HashTable* H,Record* a)/ 建表，以電話號碼為關(guān)鍵字，建立相應(yīng)的散列表 benGetTime();int i,p=-1,c,pp;for(i=0;ie

14、lempp!=NULL) pp=collision(p,c);if(pp0)cout第i+1elempp=&(ai);/求得哈希地址，將信息存入H-count+;cout第i+1個記錄沖突次數(shù)為c。 n;/需要顯示沖突次數(shù)時輸出coutn建表完成!n此哈希表容量為HASHSIZE當(dāng)前表內(nèi)存儲的記 錄個數(shù)為 count.n;benGetTime();void SearchHash2(HashTable* H,int &c)/ 在通訊錄里查找電話號碼關(guān)鍵字， 若查找成功， 顯示 信息benGetTime();NA tele;couttele;int p,pp;p=Hash2(tele);pp=p;

15、 while(H-elempp!=NULL)&(eq(tele,H-elempp-tel)=-1)pp=collision(p,c);if(H-elempp!=NULL&eq(tele,H-elempp-tel)=1)coutn 查找成功！ n 查找過程沖突次數(shù)為 c 以下是您需要要查找的信息：nn;cout姓 名：elempp-namen 電話號碼：elempp-teln 聯(lián)系地址: elempp-addn;else coutn 此人不存在，查找不成功 !n;benGetTime();存盤功能的實現(xiàn)：void Save()FILE *fp;if(fp=fopen(c:test.txt, w)

16、=NULL)printf(nERROR opening customet file);fclose(fp);主界面功能的實現(xiàn)：int main(int argc, char* argv)int c,flag=1;HashTable *H;H=(HashTable*)malloc(LEN);for(int i=0;ielemi=NULL;H-size=HASHSIZE;H-count=0;Record aMAXSIZE;while (1)coutn|-:coutn|歡迎使用電話號碼查找系統(tǒng)丨”；coutn廠= = = = = = = = = = = = = = = = = = = = = = =

17、 = = = = = =coutn 哈希表的設(shè)計與實現(xiàn)；coutn|【1】. 添加用戶信息|；coutn|【2】. 讀取所有用戶信息|；coutn1【3 .以姓名建立哈希表 ( 再哈希法解決沖突)1;coutn1【4 .以電話號碼建立哈希表 (再哈希法解決沖突)1;coutn1【5 .查找并顯示給定用戶名的記錄1;coutn1 【6 .查找并顯示給定電話號碼的記錄1;coutn1【7 .清屏1;coutn1 【8 .保存1;coutn1【9 .退出程序1;coutn1溫馨提示：1;coutn丨進(jìn)行5操作前請先輸出3;coutn1n.進(jìn)行6 操作前 請先輸出 41;coutn匚coutn;cou

18、t;coutnum;switch(num)case 1: getin(a); break;case 2: ShowInformation(a); break;case 3:CreateHash1(H,a); /* 以姓名建立哈希表 */ break;case 4:CreateHash2(H,a); /* 以電話號碼建立哈希表 */ break;case 5:c=0;SearchHash1(H,c); break;case 6:c=0;SearchHash2(H,c); break;case 7:Cls(a);break;case 8:Save(); break;case 9:return 0;break;default:cout 你輸錯了，請重新輸入 !;coutn;system(pause);return 0;四、程序測試1、程序經(jīng)測試后大部分功能正常