哈希表的設計與實現(xiàn)------課程設計報告(共21頁)

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

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

3、程序以要求使用哈希表為工具快速快速查詢學生信息，學生信息包括電話號碼、用戶名、地址；用結(jié)構體存儲struct node string phone; /電話號碼string name; /姓名string address;/地址node *next; /鏈接下一個地址的指針;2具體步驟1. 要求主要用在哈希法解決沖突，并且至少嘗試用兩種方法解決沖突，定義兩個指針數(shù)組存儲信息node *infor_phoneMAX; node *infor_nameMAX;前者以電話號碼為關鍵字檢索哈希表中的信息，后者以姓名為關鍵字檢索哈希表中的信息用鏈式法和再哈希法解決沖突：int hash(string ke

4、y) /以姓名或者電話號碼的前四位運算結(jié)果作為哈 /希碼int result=1,cur=0,i;if(key.size()=0;i-)cur=keyi-0;result=result*9+cur;result%=(MOD);return result;2.得到輸入信息的哈希碼以后，將相應的信息插入對應的地址，若產(chǎn)生沖突，則循環(huán)到這個地址的最后一個節(jié)點，然后再將節(jié)點插入到這個位置，這樣就避免了沖突,在查找的時候便可直接找到這個地址然后快速的查找到信息: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. 再哈希法也是解決沖突的常見方法，當同義詞產(chǎn)生地址沖突時計算另一個哈希函數(shù)地址，知道沖突不再發(fā)生，這種方法不易產(chǎn)生聚義，但是增加了計算時間：int hash_agin(int numble,int key) /將關鍵字的前四位數(shù)經(jīng)過計

6、算的結(jié)果 /模上一個定義的數(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. 同樣用鏈表為儲存信息的數(shù)據(jù)結(jié)構，當產(chǎn)生沖突時，將模數(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()，返回一個bool值，要求用戶輸入一個正確的選項，減少程序因錯誤輸入而出現(xiàn)的問題:bool usersayyes() string sig; bool continu=true; coutsig&(sig!=Y&s

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

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

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

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

13、感謝學院為我提供良好的做畢業(yè)設計的環(huán)境。最后再一次感謝所有在設計中曾經(jīng)幫助過我的良師益友和同學八.附錄#include#includeusing namespace std;#define MAX 10000#define MOD 9873struct node /定義儲存學生信息的結(jié)構體 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ù)要求用戶輸入正確的選項 string sig; bool continu=true; coutsig&(sig!=Y&sig!=y)&(sig!=N&sig!=n) cout輸入錯誤,請重新輸入!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) /以名字為關鍵字查詢用戶信息 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) /以電話為關鍵字查詢用戶信息 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輸入錯誤,請重新輸入!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) /存儲用戶信息到哈希表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() /分別以名字和電話為關鍵字查詢用戶信息string infor;int sig,pos; coutsig&(sig!=1&sig!=2) cout輸入錯誤,請重新輸入!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