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

1、一 : 需求分析2三: 詳細設計（含代碼分析）41.程序描述:42具體步驟4四 調(diào)試分析和測試結果7五，總結9六.參考文獻;10七.致謝10八.附錄10一 : 需求分析問題描述：設計哈希表實現(xiàn) 號碼查詢系統(tǒng)?；疽?、設每個記錄有下列數(shù)據(jù)項： 號碼、用戶名、地址2、從鍵盤輸入各記錄，分別以 號碼和用戶名為關鍵字建立哈希表；3、采用再哈希法解決沖突；4、查找并顯示給定 號碼的記錄；5、查找并顯示給定用戶名的記錄。6、在哈希函數(shù)確定的前提下，嘗試各種不同類型處理沖突的方法（至少兩種），考察平均查找長度的變化。二: 概要設計進入主函數(shù),用戶輸入1或者2,進入分支選擇結構:選1:以鏈式方法建立哈希表

2、,選2:以再哈希的方法建立哈希表,然后用戶輸入用戶信息,分別以上述確定的方法分別以用戶名為檢索以及以以 號碼為檢索將用戶信息添加到哈希表,.當添加一定量的用戶信息后,用戶接著輸入用戶名或者 號碼分別以用戶名或者 號碼的方式從以用戶名或 號碼為檢索的哈希表查找用戶信息.程序用鏈表的方式存儲信息以及構造哈希表。 具體流程圖如下所示:主函數(shù)輸入1輸入2鏈式法構造哈希表表再哈希法構造哈希表輸入用戶信息輸入用戶信息分別以 和姓名為檢索將信息存儲到哈希表分別以 和姓名為檢索將信息存儲到哈希表輸入1輸入2輸入1輸入2以 為索引查找用戶信息輸入電 話輸 入姓 名輸入電 話輸 入姓 名以姓名為索引查找用戶信息以

3、 為索引查找用戶信息以姓名為索引查找用戶信息 程序結束三: 詳細設計（含代碼分析）1. 程序描述: 本程序以要求使用哈希表為工具快速快速查詢學生信息，學生信息包括 號碼、用戶名、地址；用結構體存儲struct node string phone; / 號碼string name; /姓名string address;/地址node *next; /鏈接下一個地址的指針;2具體步驟1. 要求主要用在哈希法解決沖突，并且至少嘗試用兩種方法解決沖突，定義兩個指針數(shù)組存儲信息node *infor_phoneMAX; node *infor_nameMAX;前者以 號碼為關鍵字檢索哈希表中的信息，后者

4、以姓名為關鍵字檢索哈希表中的信息用鏈式法和再哈希法解決沖突：int hash(string key) /以姓名或者 號碼的前四位運算結果作為哈 /希碼int result=1,cur=0,i;if(key.size()<=4)i=key.size()-1;else i=4;for(;i>=0;i-)cur=keyi-'0'result=result*9+cur;result%=(MOD);return result;2.得到輸入信息的哈希碼以后，將相應的信息插入對應的地址，若產(chǎn)生沖突，則循環(huán)到這個地址的最后一個節(jié)點，然后再將節(jié)點插入到這個位置，這樣就避免了沖突,在查

5、找的時候便可直接找到這個地址然后快速的查找到信息:void add_infor_phone(string phone,string name,string address)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;3. 再哈希法也是解

6、決沖突的常見方法，當同義詞產(chǎn)生地址沖突時計算另一個哈希函數(shù)地址，知道沖突不再發(fā)生，這種方法不易產(chǎn)生聚義，但是增加了計算時間：int hash_agin(int numble,int key) /將關鍵字的前四位數(shù)經(jīng)過計算的結果 /模上一個定義的數(shù)然后返回的數(shù)字為 return numble%key; /哈希碼int create(string key) int result=1,cur=0,i; if(key.size()<=4) i=key.size()-1; else i=4; for(;i>=0;i-) cur=keyi-'0' result=result*9

7、+cur; return result;4. 同樣用鏈表為儲存信息的數(shù)據(jù)結構，當產(chǎn)生沖突時，將模數(shù)減去一然后再尋找地址直到不再產(chǎn)生沖突：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(inf

8、or_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;

9、 infor_phonepos_phone=inforphone; infor_namepos_name=inforname;5 .幫主函數(shù)bool usersayyes()，返回一個bool值，要求用戶輸入一個正確的選項，減少程序因錯誤輸入而出現(xiàn)的問題:bool usersayyes() string sig; bool continu=true; cout<<"請輸入(N/n)或(Y/y),(N/n)代表退出,(Y/y)代表繼續(xù):" while(cin>>sig&&(sig!="Y"&&sig!

10、="y")&&(sig!="N"&&sig!="n") cout<<"輸入錯誤,請重新輸入!"<<endl; return sig="Y"|sig="y"四 調(diào)試分析和測試結果1.用鏈式法將用戶信息添加到哈希表：2.以姓名為關鍵字檢索用戶信息:3.當哈希表中不存在此項記錄時:4再哈希法將用戶信息添加到哈希表：5以姓名為檢索在哈希表中查找用戶信息:6.以 為檢索在哈希表中查詢信息:使用哈希表能在較短的時間內(nèi)查找出數(shù)據(jù)，程序

11、的結果基本和理論相符合。五，總結通過做這個課程設計，使我們對如何去解決分析一個沒有接觸過的問題有深刻的認識，我們開始對題目有很多誤解，根本沒有思路，經(jīng)過老師的幾次講解和我們自己很多的討論，最終把問題進行轉換，老師的要求是為了一個映射關系，我們找到了一個算法，算法和公式是可以相互轉換的，在這個過程我們發(fā)現(xiàn)自己的程序有很多問題，經(jīng)過我們不斷對算法進行修改使得我們的程序運行的更快。哈希表的設計與實現(xiàn)這一算法始終圍繞怎樣解決沖突和怎樣快速查找數(shù)據(jù)為目的，要求用在哈希法和鏈式法設計和實現(xiàn)哈希表，經(jīng)過查閱資料請教同學問題漸漸的變得清晰，在分析問題，思考問題和解決問題的過程中，很大程度上培養(yǎng)了我們的動手和動

12、腦的能力，開始選擇一個合適的數(shù)據(jù)結構，然后依據(jù)算法編碼，調(diào)試，最后得出正確結論，整個過程雖然遇到了很多問題，特別是指針的沖突，這樣在不知不覺中培養(yǎng)了我的耐性，“數(shù)據(jù)結構與算法”課程是計算機專業(yè)的一門十分重要的核心基礎課程。這次的課程設計，拓廣了我解決實際問題的程序設計的思路，也培養(yǎng)了對于問題進行深入探究的習慣。我更加深刻的體會到各種路由算法的特點，以及性能的優(yōu)劣。為我今后專業(yè)課程的學習奠定了堅實的理論基礎！六.參考文獻;1. 數(shù)據(jù)結構 嚴蔚敏，吳偉明（c語言版）清華大學出版社2. 算法導論 Thoms.H.Cormen , Charles E.Leiserson , Ronald L.Rive

13、st, Clifford Stein著潘金貴，顧鐵成，李成法譯 第二版 機械工業(yè)出版社3. 數(shù)據(jù)結構基礎(C語言版)(第2版) Ellis Horowitz，Sartaj Sahni，Susan Anderson-Freed 著 朱仲濤譯 清華大學出版社4. 數(shù)據(jù)結構與算法分析：C語言描述(英文版.第2版) Mark Allen Weiss 著 機械工業(yè)出版社 5. 算法之道 鄒恒明 (第2版) 機械工業(yè)出版社在這次課程設計的撰寫過程中，我得到了許多人的幫助。首先我要感謝我的老師在課程設計上給予我的指導、提供給我的支持和幫助，這是我能順利完成這次報告的主要原因，更重要的是老師幫我解決了許多技術

14、上的難題，讓我能把系統(tǒng)做得更加完善。在此期間，我不僅學到了許多新的知識，而且也開闊了視野，提高了自己的設計能力。其次，我要感謝幫助過我的同學，他們也為我解決了不少我不太明白的設計商的難題。同時也感謝學院為我提供良好的做畢業(yè)設計的環(huán)境。最后再一次感謝所有在設計中曾經(jīng)幫助過我的良師益友和同學#include<iostream>#include<string>using namespace std;#define MAX 10000#define MOD 9873struct node /定義儲存學生信息的結構體 string phone;string name;string

15、 address;node *next;node *infor_phoneMAX; /存放信息的指針數(shù)組node *infor_nameMAX;void init() /初始化初始化指針數(shù)組for(int i=0;i<MAX;i+)infor_phonei=NULL;infor_namei=NULL;bool usersayyes() /幫助函數(shù)要求用戶輸入正確的選項 string sig; bool continu=true; cout<<"請輸入(N/n)或(Y/y),(N/n)代表退出,(Y/y)代表繼續(xù):" while(cin>>sig

16、&&(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)

17、 int result=1,cur=0,i; if(key.size()<=4)ize()-1; else i=4; for(;i>=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_a

18、gin(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=inforname->phone=phone; inforphone->

19、address=inforname->address=address; inforphone->next=inforname->next=NULL; infor_phonepos_phone=inforphone; 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_name

20、pos_name=NULL) cout<<"不存在你要查找的信息!"<<endl;cout<<"-"<<endl;return; if(infor_namepos_name->name=name) cout<<"姓名:" cout<<infor_namepos_name->name<<endl; cout<<" :"cout<<infor_namepos_name->phone<<

21、;endl;cout<<"地址:"cout<<infor_namepos_name->address<<endl;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_ph

22、onepos_phone=NULL) cout<<"不存在你要查找的信息!"<<endl;cout<<"-"<<endl;return; if(infor_phonepos_phone->phone=phone) cout<<"姓名:" cout<<infor_phonepos_phone->name<<endl; cout<<" :"cout<<infor_phonepos_phone->

23、phone<<endl;cout<<"地址:"cout<<infor_phonepos_phone->address<<endl;cout<<"-"<<endl; return ; key-; void find() string sig,infor; cout<<"請輸入(1)或(2),(1)代表姓名,(2)代表 :" while(cin>>sig&&(sig!="1"&&sig!

24、="2") cout<<"輸入錯誤,請重新輸入!"<<endl; cout<<"請輸入要查找的信息:" cin>>infor; if(sig="1") find_byname(infor); else find_byphone(infor);/鏈表法int hash(string key) /鏈表法獲得哈希碼 int result=1,cur=0,i; if(key.size()<=4) i=key.size()-1; else i=4; for(;i>=

25、0;i-) cur=keyi-'0' result=result*9+cur; result%=(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 infor

26、mation;void add_infor_phone(string phone,string name,string address)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 p

27、hone,string name,string address) int value=hash(name);node *infor=build_infor(phone,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; cout<

28、<"請輸入要供查找的信息代號:1代表 號碼,2代表姓名:"while(cin>>sig&&(sig!=1&&sig!=2) cout<<"輸入錯誤,請重新輸入!"<<endl;cout<<"請輸入要供查找的信息:"cin>>infor; if(sig=1) bool flag=true; pos=hash(infor); node * cur=infor_phonepos; while(cur) if(cur->phone=info

29、r) cout<<"姓名:"<<cur->name<<endl;cout<<" :"<<cur->phone<<endl;cout<<"地址:"<<cur->address<<endl;flag=false;break; cur=cur->next; if(flag) cout<<"不存在要查找的記錄!"<<endl; cout<<"-&q

30、uot;<<endl;else if(sig=2) bool flag=true; pos=hash(infor); node * cur=infor_namepos; while(cur) if(cur->name=infor) cout<<"姓名:"<<cur->name<<endl<<" :"<<cur->phone<<endl<<"地址:"<<cur->address<<endl;fl

31、ag=false;break; cur=cur->next; if(flag) cout<<"不存在要查找的記錄!"<<endl; cout<<"-"<<endl;elsecout<<"輸入錯誤,請重新輸入:"<<endl;cout<<"-"<<endl; findinfor();void hash_frist() int numble; string phone,name,address,sig; init(); cout<<"請輸入添