哈希表的設(shè)計與實現(xiàn)數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計報告

1、合肥學(xué)院計算機科學(xué)與技術(shù)系課程設(shè)計報告2009 2010 學(xué)年第二學(xué)期課程 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計名稱哈希表的設(shè)計與實現(xiàn)學(xué)生姓名王東東學(xué)號0804012030專業(yè)班級08計本（2)指導(dǎo)教師王昆侖、李貫虹2010 年 5 月課程設(shè)計目的“數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計”是計算機科學(xué)與技術(shù)專業(yè)學(xué)生的集中實踐性環(huán)節(jié)之一，是學(xué)習(xí)“數(shù)據(jù)結(jié)構(gòu)與算法”理論和實驗課程后進(jìn)行的一次全面的綜合練習(xí)。其目的是要達(dá)到理論與實際應(yīng)用相結(jié)合，提高學(xué)生組織數(shù)據(jù)及編寫程序的能力，使學(xué)生能夠根據(jù)問題要求和數(shù)據(jù)對象的特性，學(xué)會數(shù)據(jù)組織的方法，把現(xiàn)實世界中的實際問題在計算機內(nèi)部表示出來并用軟件解決問題，培養(yǎng)良好的程序設(shè)計技能。 一、 問題

2、分析和任務(wù)定義1、 問題分析 要完成如下要求：設(shè)計哈希表實現(xiàn) 號碼查詢系統(tǒng)。實現(xiàn)本程序需要解決以下幾個問題：（1） 如何定義一個包括 號碼、用戶名、地址的節(jié)點。（2） 如何以 號碼和用戶名為關(guān)鍵字建立哈希表。（3） 用什么方法解決沖突。（4） 如何查找并顯示給定 號碼的記錄。（5） 如何查找并顯示給定用戶名的記錄。2 任務(wù)定義 1、由問題分析知，本設(shè)計要求分別以 號碼和用戶名為關(guān)鍵字建立哈希表，z在此基礎(chǔ)上實現(xiàn)查找功能。本實驗是要我們分析怎么樣很好的解決散列問題，從而建立一比較合理的哈希表。由于長度無法確定，并且如果采用線性探測法散列算法，刪除結(jié)點會引起“信息丟失”的問題。所以采用鏈地址法散列

3、算法。采用鏈地址法，當(dāng)出現(xiàn)同義詞沖突時，可以使用鏈表結(jié)構(gòu)把同義詞鏈接在一起，即同義詞的存儲地址不是散列表中其他的空地址。 根據(jù)問題分析，我們可以定義有3個域的節(jié)點，這三個域分別為 號碼char num30，姓名char name30，地址char address30。這種類型的每個節(jié)點對應(yīng)鏈表中的每個節(jié)點，其中 號碼和姓名可分別作關(guān)鍵字實現(xiàn)哈希表的創(chuàng)建。 二、 數(shù)據(jù)結(jié)構(gòu)的選擇和概要設(shè)計1、數(shù)據(jù)結(jié)構(gòu)的選擇數(shù)據(jù)結(jié)構(gòu)：散列結(jié)構(gòu)。散列結(jié)構(gòu)是使用散列函數(shù)建立數(shù)據(jù)結(jié)點關(guān)鍵詞與存儲地址之間的對應(yīng)關(guān)系，并提供多種當(dāng)數(shù)據(jù)結(jié)點存儲地址發(fā)生“沖突”時的處理方法而建立的一種數(shù)據(jù)結(jié)構(gòu)。散列結(jié)構(gòu)基本思想，是以所需存儲的結(jié)

4、點中的關(guān)鍵詞作為自變量，通過某種確定的函數(shù)H（稱作散列函數(shù)或者哈希函數(shù)）進(jìn)行計算，把求出的函數(shù)值作為該結(jié)點的存儲地址，并將該結(jié)點或結(jié)點地址的關(guān)鍵字存儲在這個地址中。散列結(jié)構(gòu)法（簡稱散列法）通過在結(jié)點的存儲地址和關(guān)鍵字之間建立某種確定的函數(shù)關(guān)系H，使得每個結(jié)點（或關(guān)鍵字）都有一個唯一的存儲地址相對應(yīng)。當(dāng)需要查找某一指定關(guān)鍵詞的結(jié)點時，可以很方便地根據(jù)待查關(guān)鍵字K計算出對應(yīng)的“映像”H(K)，即結(jié)點的存儲地址。從而一次存取便能得到待查結(jié)點，不再需要進(jìn)行若干次的比較運算，而可以通過關(guān)鍵詞直接計算出該結(jié)點的所在位置。2、概要設(shè)計 （1）、哈希表的定義結(jié)點的數(shù)據(jù)類型：struct node /定義 姓名

5、 地址 號碼 char name30;char address30; char num30; node * next; ; ElemNode; （2）、哈希地址的計算以姓名為關(guān)鍵字的哈希地址計算：從取得的姓名第二個字母開始，取ASCII碼累加，對30求余得所求哈希地址以 號碼為關(guān)鍵字的哈希地址計算：從號碼第二位開始，將所有號碼累加之后對30求模得哈希地址 （3）、拉鏈法鏈地址法：在散表結(jié)構(gòu)存放在指針指向的單元中。鏈地址法在解決沖突時，使用鏈表結(jié)構(gòu)把同義詞鏈接在一起，即同義詞的存儲地址不是散列表中其他的空地址。采用C語言定義如下：#define Max_length 100Typedef str

6、uct int key; ElemType data; ElemNode *next;ElemNode;Typedef struct ElemNode *first;ElemHeader,HashTableMax_length;所有的同義詞構(gòu)成一個單鏈表，再由一個表頭節(jié)點指向這個單鏈表的第一個節(jié)點。這些鏢頭節(jié)點組成一個一維數(shù)組，即散列表。數(shù)組元素的下標(biāo)對應(yīng)由散列函數(shù)求出的散列地址。拉鏈法處理沖突的散列表結(jié)構(gòu)and army breeze buy 1boy 2 egg each 5hash 8（4）鏈地址法查找結(jié)點的算法思想 a、根據(jù)查找節(jié)點的關(guān)鍵字算出哈希地址b、在散列地址所指向的單鏈表中依次

7、尋找節(jié)點 c、如果找到，輸出節(jié)點的信息；否則提示沒有找到三、 詳細(xì)設(shè)計和編碼 主流程圖。Main ()初始化散列鏈表1并為其動態(tài)分配內(nèi)存空間初始化散列鏈表2并為其動態(tài)分配內(nèi)存空間Menu（）主菜單輸入選擇選擇1選9選8查找號碼find_num()mm()查找用戶find2_name)輸出結(jié)果輸 出結(jié)果選擇2選擇0選擇3選擇4選擇5進(jìn)行姓名散列l(wèi)ist2()姓名散列結(jié)果添加記錄 apend()退出系統(tǒng)return 0進(jìn)行號碼散列 list()清空creat();creat2()列表已清空號碼散列結(jié)果結(jié) 束開 始以號碼為關(guān)鍵字的Hash()函數(shù)流程圖取整型num2賦給key結(jié)束Key=key%20

8、Key=key+(int) numii+i從3開始取numi!=0開 始以姓名為關(guān)鍵字的Hash()函數(shù)流程圖取整型name0賦給key2結(jié)束Key2=key%20Key2+=nameii+i從0開始取namei不為空 開 始添加結(jié)點信息流程圖:利用用戶名為關(guān)鍵字插入拉鏈法處理沖突調(diào)用hash()函數(shù)調(diào)用hash()函數(shù)Newname指向newphoneNewphone=input()結(jié)束申請新的結(jié)點newphone,newname即新的號碼和名字開始申請專利開始 按姓名查找流程圖:q不為空結(jié)束輸出無記錄輸出相應(yīng)記錄q=q-nextq 不為空調(diào)用hash()函數(shù)中新結(jié)點q指向phonekey-

9、next開始按號碼查找流程圖:開始調(diào)用hash2()函數(shù)中新結(jié)點q指向phonekey-nextq 不為空q=q-nextq不為空輸出無記錄輸出相應(yīng)記錄結(jié)束編碼1、建立節(jié)點struct node /定義 姓名 地址 號碼 char name30;char address30; char num30; node * next; ; typedef node* pnode; /聲明了已有數(shù)據(jù)類型的兩個指針變量typedef node* mingzi; node *phone; node *nam;2、定義哈希函數(shù)這里我們需要定義兩個哈希函數(shù)，一個以 號碼為關(guān)鍵字，另一個以姓名ASCII之和求模之后

10、的值為關(guān)鍵字。主要方法為將 號碼從第二位開始逐一累加并將所得結(jié)果對30求模得哈希地址；第二種則是將姓名字符進(jìn)行強制類型轉(zhuǎn)換之后得ASCII碼相加對30求模得哈希地址。=求哈希地址源代碼=void hash(char num30) /哈希函數(shù) /將運算的結(jié)果所得的余數(shù)作為節(jié)點的存儲地址 int i = 1; key=(int)num0; while(numi!=NULL) key+=(int)numi; i+; key=key%30; void hash2(char name30) /哈希函數(shù) /將運算的結(jié)果所得的余數(shù)作為節(jié)點的存儲地址 int i = 1; key2=(int)name0; w

11、hile(namei!=NULL) key2+=(int)namei; i+; key2=key2%30; =（3）、添加節(jié)點接下來就是每個節(jié)點的建立，添加結(jié)點，利用鏈地址法解決沖突。建立結(jié)點應(yīng)包括動態(tài)申請內(nèi)存空間。向結(jié)點中輸入信息。同時將結(jié)點中的next指針等于NULL。添加結(jié)點，首先需要利用哈希函數(shù)計算出地址即關(guān)鍵字，然后將所得數(shù)據(jù)插入到鏈表中。=動態(tài)申請內(nèi)存空間=void create_phone() /新建節(jié)點 int i; phone=new pnode30; for(i=0;inext=NULL; void create2_num() /新建節(jié)點 int i; nam=new mi

12、ngzi30; for(i=0;inext=NULL; =添加節(jié)點=int apend() /添加節(jié)點 node *newphone; node *newname; newphone=input(); newname=newphone; newphone-next=NULL; newname-next=NULL; hash(newphone-num); /先計算號碼的key hash2(newname-name); /姓名的key2 newphone-next = phonekey-next;/把該key的號碼鏈接到原來的號碼的后一節(jié)點上 phonekey-next=newphone; new

13、name-next = namkey2-next; /把該key的姓名鏈接到原來的號碼的后一節(jié)點上 namkey2-next=newname; return 0; =（4）、查找節(jié)點=void find_num(char num30) /按號碼查找用戶信息 hash(num); node *q=phonekey-next; while(q!= NULL) if(strcmp(num,q-num)=0) break; q=q-next; if(q) coutname_ address_numendl; else cout無此記錄next; while(q!= NULL) if(strcmp(na

14、me,q-name)=0) break; q=q-next; if(q) coutname_ address_numendl; else cout無此記錄endl; =（5）輸出哈希表=void list_num() /以號碼為關(guān)鍵字顯示列表 int i; node *p; for(i=0;inext; while(p) coutname_address_numnext; void list2_nam() /以姓名為關(guān)鍵字顯示列表 int i; node *p; for(i=0;inext; while(p) coutname_address_numnext; =（6）主函數(shù) main（）四、

15、 上機調(diào)試1、在調(diào)試的時候，出現(xiàn)了無法查找姓名或者 號碼相同的用戶的信息 當(dāng)查找姓名相同或者號碼相同的用戶時，就會出現(xiàn)死循環(huán) 原先代碼如下=部分代碼=while(q!= NULL)if(strcmp(num,q-num)=0)break;q=q-next;if(q)coutname_ address_numendl;else cout無此記錄next; while(q!= NULL) if(strcmp(num,q-num)=0) coutname_ address_numnext; if(flag=0) cout無此記錄endl; =先前出現(xiàn)問題是因為break語句結(jié)束語句指能查找一個節(jié)點，

16、改進(jìn)之后可以實現(xiàn)功能2、文件的操作在這個程序中沒有能成功實現(xiàn)，故在最后階段，刪除了這一功能。3、程序中經(jīng)常會出現(xiàn)程序調(diào)試過程中常會出現(xiàn)一些小錯誤，如i,j混淆少括號少分號等小問題都可以按照提示找到，然后改正。測試結(jié)果及分析（1）主界面：（2）添加記錄（3）查找記錄a、通過姓名查找姓名不重復(fù)的結(jié)點b、通過姓名查找姓名重復(fù)的結(jié)點c、通過 號碼查找結(jié)點d、結(jié)點不存在結(jié)點不存在時，輸出的數(shù)據(jù)為空（4）姓名散列以姓名為關(guān)鍵字查找結(jié)點，輸出數(shù)據(jù)（5）、號碼散列（6）清空記錄（7）退出系統(tǒng)用戶使用說明添加數(shù)據(jù)不能大于30個數(shù)， 號碼為字符型。進(jìn)入后按照程序界面提示可以進(jìn)行對數(shù)據(jù)的添加、查找以及按姓名和按 號

17、碼兩種不同方式的散列。本程序在運行時有輔助信息提示，可以十分容易的上手，關(guān)鍵信息均通過鍵盤錄入。 參考文獻(xiàn)1 王昆侖，李紅. 數(shù)據(jù)結(jié)構(gòu)與算法. 北京：中國鐵道出版社，2007.2 譚浩強，張基溫. C語言程序設(shè)計教程. 3版. 北京：高等教育出版社，2007.八、 附錄#include #include string.husing namespace std; #define NULL 0 unsigned int key; /所需存儲的節(jié)點中的無符號關(guān)鍵字作為自變量unsigned int key2; struct node /定義 姓名 地址 號碼 char name30;char add

18、ress30; char num30; node * next; ; typedef node* pnode; /聲明了已有數(shù)據(jù)類型的兩個指針變量typedef node* mingzi; node *phone; node *nam; void hash(char num30) /哈希函數(shù) /將運算的結(jié)果所得的余數(shù)作為節(jié)點的存儲地址 int i = 1; key=(int)num0; while(numi!=NULL) key+=(int)numi; i+; key=key%30; void hash2(char name30) /哈希函數(shù) /將運算的結(jié)果所得的余數(shù)作為節(jié)點的存儲地址 int

19、 i = 1; key2=(int)name0; while(namei!=NULL) key2+=(int)namei; i+; key2=key2%30; node* input() /輸入節(jié)點 node *one; one = new node; one-next=NULL; cout輸入姓名：one-name; cout輸入地址：one-address; cout輸入 ：one-num; return one; int apend() /添加節(jié)點 node *newphone; node *newname; newphone=input(); newname=newphone; new

20、phone-next=NULL; newname-next=NULL; hash(newphone-num); /先計算號碼的key hash2(newname-name); /姓名的key2 newphone-next = phonekey-next;/把該key的號碼鏈接到原來的號碼的后一節(jié)點上 phonekey-next=newphone; newname-next = namkey2-next; /把該key的姓名鏈接到原來的號碼的后一節(jié)點上 namkey2-next=newname; return 0; void create_phone() /新建節(jié)點 int i; phone=n

21、ew pnode30; for(i=0;inext=NULL; void create2_num() /新建節(jié)點 int i; nam=new mingzi30; for(i=0;inext=NULL; void list_num() /以號碼為關(guān)鍵字顯示列表 int i; node *p; for(i=0;inext; while(p) coutname_address_numnext; void list2_nam() /以姓名為關(guān)鍵字顯示列表 int i; node *p; for(i=0;inext; while(p) coutname_address_numnext; void fi

22、nd_num(char num30) /按號碼查找用戶信息 int flag;hash(num); node *q=phonekey-next; while(q!= NULL) if(strcmp(num,q-num)=0) coutname_ address_numnext; if(flag=0) cout無此記錄next; while(q!= NULL) if(strcmp(name,q-name)=0) coutname_ address_numnext; if(flag=0) cout無此記錄endl; void menu() /菜單 couttt*endl; /cout endl;cout endl;cout endl;couttt 歡迎來到哈希 簿系統(tǒng) endl; cout en