哈希表的設(shè)計(jì)與實(shí)現(xiàn)------課程設(shè)計(jì)報(bào)告(共21頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上一 : 需求分析問題描述：設(shè)計(jì)哈希表實(shí)現(xiàn)電話號(hào)碼查詢系統(tǒng)?；疽?、設(shè)每個(gè)記錄有下列數(shù)據(jù)項(xiàng)：電話號(hào)碼、用戶名、地址2、從鍵盤輸入各記錄，分別以電話號(hào)碼和用戶名為關(guān)鍵字建立哈希表；3、采用再哈希法解決沖突；4、查找并顯示給定電話號(hào)碼的記錄；5、查找并顯示給定用戶名的記錄。6、在哈希函數(shù)確定的前提下，嘗試各種不同類型處理沖突的方法（至少兩種），考察平均查找長度的變化。二: 概要設(shè)計(jì)進(jìn)入主函數(shù),用戶輸入1或者2,進(jìn)入分支選擇結(jié)構(gòu):選1:以鏈?zhǔn)椒椒ń⒐１?選2:以再哈希的方法建立哈希表,然后用戶輸入用戶信息,分別以上述確定的方法分別以用戶名為檢索以及以以電話號(hào)碼為檢索將

2、用戶信息添加到哈希表,.當(dāng)添加一定量的用戶信息后,用戶接著輸入用戶名或者電話號(hào)碼分別以用戶名或者電話號(hào)碼的方式從以用戶名或電話號(hào)碼為檢索的哈希表查找用戶信息.程序用鏈表的方式存儲(chǔ)信息以及構(gòu)造哈希表。 具體流程圖如下所示:主函數(shù)輸入1輸入2鏈?zhǔn)椒?gòu)造哈希表表再哈希法構(gòu)造哈希表輸入用戶信息輸入用戶信息分別以電話和姓名為檢索將信息存儲(chǔ)到哈希表分別以電話和姓名為檢索將信息存儲(chǔ)到哈希表輸入1輸入2輸入1輸入2以電話為索引查找用戶信息輸入電 話輸 入姓 名輸入電 話輸 入姓 名以姓名為索引查找用戶信息以電話為索引查找用戶信息以姓名為索引查找用戶信息 程序結(jié)束三: 詳細(xì)設(shè)計(jì)（含代碼分析）1. 程序描述: 本

3、程序以要求使用哈希表為工具快速快速查詢學(xué)生信息，學(xué)生信息包括電話號(hào)碼、用戶名、地址；用結(jié)構(gòu)體存儲(chǔ)struct node string phone; /電話號(hào)碼string name; /姓名string address;/地址node *next; /鏈接下一個(gè)地址的指針;2具體步驟1. 要求主要用在哈希法解決沖突，并且至少嘗試用兩種方法解決沖突，定義兩個(gè)指針數(shù)組存儲(chǔ)信息node *infor_phoneMAX; node *infor_nameMAX;前者以電話號(hào)碼為關(guān)鍵字檢索哈希表中的信息，后者以姓名為關(guān)鍵字檢索哈希表中的信息用鏈?zhǔn)椒ê驮俟７ń鉀Q沖突：int hash(string ke

4、y) /以姓名或者電話號(hào)碼的前四位運(yùn)算結(jié)果作為哈 /希碼int result=1,cur=0,i;if(key.size()=0;i-)cur=keyi-0;result=result*9+cur;result%=(MOD);return result;2.得到輸入信息的哈希碼以后，將相應(yīng)的信息插入對(duì)應(yīng)的地址，若產(chǎn)生沖突，則循環(huán)到這個(gè)地址的最后一個(gè)節(jié)點(diǎn)，然后再將節(jié)點(diǎn)插入到這個(gè)位置，這樣就避免了沖突,在查找的時(shí)候便可直接找到這個(gè)地址然后快速的查找到信息:void add_infor_phone(string phone,string name,string address)int value=h

5、ash(phone); node *infor=build_infor(phone,name,address);if(infor_phonevalue=NULL)infor_phonevalue=infor;else node *cur=infor_phonevalue;while(cur-next) cur=cur-next; cur-next=infor;3. 再哈希法也是解決沖突的常見方法，當(dāng)同義詞產(chǎn)生地址沖突時(shí)計(jì)算另一個(gè)哈希函數(shù)地址，知道沖突不再發(fā)生，這種方法不易產(chǎn)生聚義，但是增加了計(jì)算時(shí)間：int hash_agin(int numble,int key) /將關(guān)鍵字的前四位數(shù)經(jīng)過計(jì)

6、算的結(jié)果 /模上一個(gè)定義的數(shù)然后返回的數(shù)字為 return numble%key; /哈希碼int create(string key) int result=1,cur=0,i; if(key.size()=0;i-) cur=keyi-0; result=result*9+cur; return result;4. 同樣用鏈表為儲(chǔ)存信息的數(shù)據(jù)結(jié)構(gòu)，當(dāng)產(chǎn)生沖突時(shí)，將模數(shù)減去一然后再尋找地址直到不再產(chǎn)生沖突：void add_infors(string phone,string name,string address) int numble_phone=create(phone),key=MO

7、D,pos_phone,pos_name; while(infor_phonepos_phone=hash_agin(numble_phone,key)!=NULL) key-; key=MOD; int numble_name=create(name); while(infor_namepos_name=hash_agin(numble_name,key)!=NULL) key-; node *inforphone=new node; node *inforname=new node; inforphone-name=inforname-name=name; inforphone-phone

8、=inforname-phone=phone; inforphone-address=inforname-address=address; inforphone-next=inforname-next=NULL; infor_phonepos_phone=inforphone; infor_namepos_name=inforname;5 .幫主函數(shù)bool usersayyes()，返回一個(gè)bool值，要求用戶輸入一個(gè)正確的選項(xiàng)，減少程序因錯(cuò)誤輸入而出現(xiàn)的問題:bool usersayyes() string sig; bool continu=true; coutsig&(sig!=Y&s

9、ig!=y)&(sig!=N&sig!=n) cout輸入錯(cuò)誤,請(qǐng)重新輸入!endl; return sig=Y|sig=y;四 調(diào)試分析和測試結(jié)果1.用鏈?zhǔn)椒▽⒂脩粜畔⑻砑拥焦１恚?.以姓名為關(guān)鍵字檢索用戶信息:3.當(dāng)哈希表中不存在此項(xiàng)記錄時(shí):4再哈希法將用戶信息添加到哈希表：5以姓名為檢索在哈希表中查找用戶信息:6.以電話為檢索在哈希表中查詢信息:使用哈希表能在較短的時(shí)間內(nèi)查找出數(shù)據(jù)，程序的結(jié)果基本和理論相符合。五，總結(jié)通過做這個(gè)課程設(shè)計(jì)，使我們對(duì)如何去解決分析一個(gè)沒有接觸過的問題有深刻的認(rèn)識(shí)，我們開始對(duì)題目有很多誤解，根本沒有思路，經(jīng)過老師的幾次講解和我們自己很多的討論，最終把問題進(jìn)行

10、轉(zhuǎn)換，老師的要求是為了一個(gè)映射關(guān)系，我們找到了一個(gè)算法，算法和公式是可以相互轉(zhuǎn)換的，在這個(gè)過程我們發(fā)現(xiàn)自己的程序有很多問題，經(jīng)過我們不斷對(duì)算法進(jìn)行修改使得我們的程序運(yùn)行的更快。哈希表的設(shè)計(jì)與實(shí)現(xiàn)這一算法始終圍繞怎樣解決沖突和怎樣快速查找數(shù)據(jù)為目的，要求用在哈希法和鏈?zhǔn)椒ㄔO(shè)計(jì)和實(shí)現(xiàn)哈希表，經(jīng)過查閱資料請(qǐng)教同學(xué)問題漸漸的變得清晰，在分析問題，思考問題和解決問題的過程中，很大程度上培養(yǎng)了我們的動(dòng)手和動(dòng)腦的能力，開始選擇一個(gè)合適的數(shù)據(jù)結(jié)構(gòu)，然后依據(jù)算法編碼，調(diào)試，最后得出正確結(jié)論，整個(gè)過程雖然遇到了很多問題，特別是指針的沖突，這樣在不知不覺中培養(yǎng)了我的耐性，“數(shù)據(jù)結(jié)構(gòu)與算法”課程是計(jì)算機(jī)專業(yè)的一門十分

11、重要的核心基礎(chǔ)課程。這次的課程設(shè)計(jì)，拓廣了我解決實(shí)際問題的程序設(shè)計(jì)的思路，也培養(yǎng)了對(duì)于問題進(jìn)行深入探究的習(xí)慣。我更加深刻的體會(huì)到各種路由算法的特點(diǎn)，以及性能的優(yōu)劣。為我今后專業(yè)課程的學(xué)習(xí)奠定了堅(jiān)實(shí)的理論基礎(chǔ)！六.參考文獻(xiàn);1. 數(shù)據(jù)結(jié)構(gòu) 嚴(yán)蔚敏，吳偉明（c語言版）清華大學(xué)出版社2. 算法導(dǎo)論 Thoms.H.Cormen , Charles E.Leiserson , Ronald L.Rivest, Clifford Stein著潘金貴，顧鐵成，李成法譯 第二版 機(jī)械工業(yè)出版社3. 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)(C語言版)(第2版) Ellis Horowitz，Sartaj Sahni，Susan And

12、erson-Freed 著 朱仲濤譯 清華大學(xué)出版社4. 數(shù)據(jù)結(jié)構(gòu)與算法分析：C語言描述(英文版.第2版) Mark Allen Weiss 著 機(jī)械工業(yè)出版社 5. 算法之道 鄒恒明 (第2版) 機(jī)械工業(yè)出版社七.致謝在這次課程設(shè)計(jì)的撰寫過程中，我得到了許多人的幫助。首先我要感謝我的老師在課程設(shè)計(jì)上給予我的指導(dǎo)、提供給我的支持和幫助，這是我能順利完成這次報(bào)告的主要原因，更重要的是老師幫我解決了許多技術(shù)上的難題，讓我能把系統(tǒng)做得更加完善。在此期間，我不僅學(xué)到了許多新的知識(shí)，而且也開闊了視野，提高了自己的設(shè)計(jì)能力。其次，我要感謝幫助過我的同學(xué)，他們也為我解決了不少我不太明白的設(shè)計(jì)商的難題。同時(shí)也

13、感謝學(xué)院為我提供良好的做畢業(yè)設(shè)計(jì)的環(huán)境。最后再一次感謝所有在設(shè)計(jì)中曾經(jīng)幫助過我的良師益友和同學(xué)八.附錄#include#includeusing namespace std;#define MAX 10000#define MOD 9873struct node /定義儲(chǔ)存學(xué)生信息的結(jié)構(gòu)體 string phone;string name;string address;node *next;node *infor_phoneMAX; /存放信息的指針數(shù)組node *infor_nameMAX;void init() /初始化初始化指針數(shù)組for(int i=0;iMAX;i+)infor_ph

14、onei=NULL;infor_namei=NULL;bool usersayyes() /幫助函數(shù)要求用戶輸入正確的選項(xiàng) string sig; bool continu=true; coutsig&(sig!=Y&sig!=y)&(sig!=N&sig!=n) cout輸入錯(cuò)誤,請(qǐng)重新輸入!endl; return sig=Y|sig=y;/再哈希法int hash_agin(int numble,int key) /再哈希法獲得地址的函數(shù) return numble%key;int create(string key) int result=1,cur=0,i; if(key.size(

15、)=0;i-) cur=keyi-0; result=result*9+cur; return result;void add_infors(string phone,string name,string address) /再希法添/加用戶信息到哈希表 int numble_phone=create(phone),key=MOD,pos_phone,pos_name; while(infor_phonepos_phone=hash_agin(numble_phone,key)!=NULL) key-; key=MOD; int numble_name=create(name); while(

16、infor_namepos_name=hash_agin(numble_name,key)!=NULL) key-; node *inforphone=new node; node *inforname=new node; inforphone-name=inforname-name=name; inforphone-phone=inforname-phone=phone; inforphone-address=inforname-address=address; inforphone-next=inforname-next=NULL; infor_phonepos_phone=inforph

17、one; infor_namepos_name=inforname;void find_byname(string name) /以名字為關(guān)鍵字查詢用戶信息 int numble_name=create(name),key=MOD,pos_name; while(true) pos_name=hash_agin(numble_name,key); if(infor_namepos_name=NULL) cout不存在你要查找的信息!endl;cout-name=name) cout姓名:; coutnameendl; cout電話:;coutphoneendl;cout地址:;coutaddr

18、essendl;cout-endl; return ; key-; void find_byphone(string phone) /以電話為關(guān)鍵字查詢用戶信息 int numble_phone=create(phone),key=MOD,pos_phone; while(true) pos_phone=hash_agin(numble_phone,key); if(infor_phonepos_phone=NULL) cout不存在你要查找的信息!endl;cout-phone=phone) cout姓名:; coutnameendl; cout電話:;coutphoneendl;cout地

19、址:;coutaddressendl;cout-endl; return ; key-; void find() string sig,infor; coutsig&(sig!=1&sig!=2) cout輸入錯(cuò)誤,請(qǐng)重新輸入!endl; coutinfor; if(sig=1) find_byname(infor); else find_byphone(infor);/鏈表法int hash(string key) /鏈表法獲得哈希碼 int result=1,cur=0,i; if(key.size()=0;i-) cur=keyi-0; result=result*9+cur; resu

20、lt%=(MOD); return result;node * build_infor(string phone,string name,string address) /存儲(chǔ)用戶信息到哈希表node *information=new node; information-phone=phone;information-name=name;information-address=address;information-next=NULL;return information;void add_infor_phone(string phone,string name,string address)

21、int value=hash(phone); node *infor=build_infor(phone,name,address);if(infor_phonevalue=NULL)infor_phonevalue=infor;else node *cur=infor_phonevalue;while(cur-next) cur=cur-next; cur-next=infor;void add_infor_name(string phone,string name,string address) int value=hash(name);node *infor=build_infor(ph

22、one,name,address);if(infor_namevalue=NULL)infor_namevalue=infor;elsenode *cur=infor_namevalue;while(cur-next) cur=cur-next; cur-next=infor;void findinfor() /分別以名字和電話為關(guān)鍵字查詢用戶信息string infor;int sig,pos; coutsig&(sig!=1&sig!=2) cout輸入錯(cuò)誤,請(qǐng)重新輸入!endl;coutinfor; if(sig=1) bool flag=true; pos=hash(infor); node * cur=infor_phonepos; while(cur) if(cur-phone=infor) cout姓名:nameendl;cout電話:phoneendl;cout地址:addressnext; if(flag) cout不存在要查找的記錄!endl; cout