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

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

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

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

4、以姓名為關(guān)鍵字檢索哈希表中的信息用鏈?zhǔn)椒ê驮俟７ń鉀Q沖突：int hash(string key) /以姓名或者 號碼的前四位運(yùn)算結(jié)果作為哈 /希碼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.得到輸入信息的哈希碼以后，將相應(yīng)的信息插入對應(yīng)的地址，若產(chǎn)生沖突，則循環(huán)到這個地址的最后一個節(jié)點(diǎn)，然后再將節(jié)點(diǎn)插入到這個位置，這樣就避免了沖突,在查

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、決沖突的常見方法，當(dāng)同義詞產(chǎn)生地址沖突時計(jì)算另一個哈希函數(shù)地址，知道沖突不再發(fā)生，這種方法不易產(chǎn)生聚義，但是增加了計(jì)算時間：int hash_agin(int numble,int key) /將關(guān)鍵字的前四位數(shù)經(jīng)過計(jì)算的結(jié)果 /模上一個定義的數(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ù)結(jié)構(gòu)，當(dāng)產(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àng)，減少程序因錯誤輸入而出現(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)試分析和測試結(jié)果1.用鏈?zhǔn)椒▽⒂脩粜畔⑻砑拥焦１恚?.以姓名為關(guān)鍵字檢索用戶信息:3.當(dāng)哈希表中不存在此項(xiàng)記錄時:4再哈希法將用戶信息添加到哈希表：5以姓名為檢索在哈希表中查找用戶信息:6.以 為檢索在哈希表中查詢信息:使用哈希表能在較短的時間內(nèi)查找出數(shù)據(jù)，程序

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

12、腦的能力，開始選擇一個合適的數(shù)據(jù)結(jié)構(gòu)，然后依據(jù)算法編碼，調(diào)試，最后得出正確結(jié)論，整個過程雖然遇到了很多問題，特別是指針的沖突，這樣在不知不覺中培養(yǎng)了我的耐性，“數(shù)據(jù)結(jié)構(gòu)與算法”課程是計(jì)算機(jī)專業(yè)的一門十分重要的核心基礎(chǔ)課程。這次的課程設(shè)計(jì)，拓廣了我解決實(shí)際問題的程序設(shè)計(jì)的思路，也培養(yǎng)了對于問題進(jìn)行深入探究的習(xí)慣。我更加深刻的體會到各種路由算法的特點(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.Rive

13、st, Clifford Stein著潘金貴，顧鐵成，李成法譯 第二版 機(jī)械工業(yè)出版社3. 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)(C語言版)(第2版) Ellis Horowitz，Sartaj Sahni，Susan Anderson-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ù)

14、上的難題，讓我能把系統(tǒng)做得更加完善。在此期間，我不僅學(xué)到了許多新的知識，而且也開闊了視野，提高了自己的設(shè)計(jì)能力。其次，我要感謝幫助過我的同學(xué)，他們也為我解決了不少我不太明白的設(shè)計(jì)商的難題。同時也感謝學(xué)院為我提供良好的做畢業(yè)設(shè)計(jì)的環(huán)境。最后再一次感謝所有在設(shè)計(jì)中曾經(jīng)幫助過我的良師益友和同學(xué)#include<iostream>#include<string>using namespace std;#define MAX 10000#define MOD 9873struct node /定義儲存學(xué)生信息的結(jié)構(gòu)體 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ù)要求用戶輸入正確的選項(xiàng) 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) /以名字為關(guān)鍵字查詢用戶信息 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) /以 為關(guān)鍵字查詢用戶信息 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() /分別以名字和 為關(guān)鍵字查詢用戶信息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<<"請輸入添