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

2、法建立哈希表，然后用戶輸入用戶信息，分別以上述確定的方法分別以用戶名為檢索以及以以電話號碼為檢索將用戶信息添加到哈希表,.當添加一定量的用戶信息后，用戶接著輸入用戶名或者電話號碼分別以用戶名或者電話號碼的方式從以用戶名或電話號碼為檢索的哈希表查找用戶信息.程序用鏈表的方式存儲信息以及構造哈希表。具體流程圖如下所示：三：詳細設計（含代碼分析）1.程序描述:本程序以要求使用哈希表為工具快速快速查詢學生信息，學生信息包括電話號碼、用戶名、地址；用結構體存儲structnodestringphone;/電話號碼stringname;/姓名stringaddress;/地址node*next;/鏈接下一

3、個地址的指針;2具體步驟1 .要求主要用在哈希法解決沖突，并且至少嘗試用兩種方法解決沖突，定義兩個指針數組存儲信息node*infor_phoneMAX;node*infor_nameMAX;前者以電話號碼為關鍵字檢索哈希表中的信息，后者以姓名為關鍵字檢索哈希表中的信息用鏈式法和冉哈希法解決沖突:以姓名或者電話號碼的前四位運算結果作為哈希碼inthash(stringkey)/intresult=1,cur=0,i;if(key.size()<=4)i=key.size()-1;elsei=4;for(;i>=0;i-)cur=keyi-'0'result=resu

4、lt*9+cur;result%=(MOD);returnresult;)2 .得到輸入信息的哈希碼以后，將相應的信息插入對應的地址，若產生沖突，則循環到這個地址的最后一個節點，然后再將節點插入到這個位置，這樣就避免了沖突,在查找的時候便可直接找到這個地址然后快速的查找到信息：voidadd_infor_phone(stringphone,stringname,stringaddress)(intvalue=hash(phone);node*infor=build_infor(phone,name,address);if(infor_phonevalue=NULL)infor_phoneval

5、ue=infor;else(node*cur=infor_phonevalue;while(cur->next)cur=cur->next;cur->next=infor;)3 .再哈希法也是解決沖突的常見方法，當同義詞產生地址沖突時計算另一個哈希函數地址，知道沖突不再發生，這種方法不易產生聚義，但是增加了計算時間：inthash_agin(intnumble,intkey)/將關鍵字的前四位數經過計算的結果/模上一個定義的數然后返回的數字為returnnumble%key;/哈希碼)intcreate(stringkey)intresult=1,cur=0,i;if(key

6、.size()<=4)i=key.size()-1;elsei=4;for(;i>=0;i-)(cur=keyi-'0'result=result*9+cur;returnresult;4 .同樣用鏈表為儲存信息的數據結構，當產生沖突時，將模數減去一然后再尋找地址直到不再產生沖突：voidadd_infors(stringphone,stringname,stringaddress)(intnumble_phone=create(phone),key=MOD,pos_phone,pos_name;while(infor_phonepos_phone=hash_agi

7、n(numble_phone,key)!=NULL)key-;key=MOD;intnumble_name=create(name);while(infor_namepos_name=hash_agin(numble_name,key)!=NULL)key-;node*inforphone=newnode;node*inforname=newnode;inforphone->name=inforname->name=name;inforphone->phone=inforname->phone=phone;inforphone->address=inforname

8、->address=address;inforphone->next=inforname->next=NULL;infor_phonepos_phone=inforphone;infor_namepos_name=inforname;5 .幫主函數boolusersayyes(),返回一個bool值，要求用戶輸入一個正確的選項，減少程序因錯誤輸入而出現的問題：boolusersayyes()(stringsig;boolcontinu=true;cout<<"請輸入(N/n)或(Y/y),(N/n)代表退出,(Y/y)代表繼續:"；while(

9、cin>>sig&&(sig!="Y"&&sig!="y")&&(sig!="N"&&sig!="n")cout<<"輸入錯誤，請重新輸入！"<<endl;returnsig="Y"|sig="y"四調試分析和測試結果1.用鏈式法將用戶信息添加到哈希表：請施入姓名：aliouminsi請輸入電話號珥二請輸入地址;請癡人姓名：xiedi埴題人電話號鯉=1314

10、2157894二百輸入地址=yunnan請鋤人姓名=i請輸入電話黃坤H47589421S6請輸入地垃二tEainl附2 .以姓名為關鍵字檢索用戶信息人要供查找的信:xiediQj-hijl£i>：yLinnan請憫入N/n或代表退出代表繼續:y用物人要供查茨的信息代號=我表電話號碼.2代表姓名:2逋鋤人要快當我的信息：tan9vei姓:白：tangwei電話feilt-1ianhe3 .當哈希表中不存在此項記錄時4 .再哈希法將用戶信息添加到哈希表:'E:課程設計Debug課程設V-哈希表*exe"U4曲y-

11、SSil.C-e3一數2>人名第型的生口區何加S<1添一電入入入二和和.一和j切青青青青主j人姓名：xieguang入電話茸他1347HM5689?人地ilE'henan京人-姓名=zhouron9St入電話甘碼豈52457895681入地址：beijing京人姓名：xiaoyan總入電話黑馬入地址:giiAHQfdong加人姓名:zhouchaa才入電話照人一地11£：he加i5 .以姓名為檢索在哈希表中查找用戶信息請諭入3或2代表姓名.<2代表電話：工隔輸入要查找的信息、:xla.0yan：xiaosr

12、an電話：1S84789s621itJjllE：guangdonsr請領人或<V/y>.<N/n>代表退出八丫/»代表繼續7諳輸入6或2,5代表姓名4<2代表電話"請輸入要查找的信息:NJwucho小丁-zlioticliao電話ehei6 .以電話為檢索在哈希表中查詢信息請痂入H/n或T/”,3小代表退出，“£代表繼續3請麻入1或2,1代表姓名“2代表電話二2通循人要查找的信息nS145789456姓名：zhouchao電fe±lt：hebei請茄入H/n或代表退出，代表

13、繼續：y請輸入【或2),<1>代表姓名“2代表電話：2遭物人要查找的信息門5847895621姓名：xiaovn電話"5847895621Jteilt：gjuangdong使用哈希表能在較短的時間內查找出數據，程序的結果基本和理論相符合。五，總結通過做這個課程設計，使我們對如何去解決分析一個沒有接觸過的問題有深刻的認識，我們開始對題目有很多誤解，根本沒有思路，經過老師的幾次講解和我們自己很多的討論，最終把問題進行轉換，老師的要求是為了一個映射關系，我們找到了一個算法，算法和公式是可以相互轉換的，在這個過程我們發現自己的程序有很多問題，經過我們不斷對算法進行修改使得我們的程

14、序運行的更快。哈希表的設計與實現這一算法始終圍繞怎樣解決沖突和怎樣快速查找數據為目的，要求用在哈希法和鏈式法設計和實現哈希表，經過查閱資料請教同學問題漸漸的變得清晰，在分析問題，思考問題和解決問題的過程中，很大程度上培養了我們的動手和動腦的能力，開始選擇一個合適的數據結構，然后依據算法編碼，調試，最后得出正確結論，整個過程雖然遇到了很多問題，特別是指針的沖突，這樣在不知不覺中培養了我的耐性，數據結構與算法”課程是計算機專業的一門十分重要的核心基礎課程。這次的課程設計，拓廣了我解決實際問題的程序設計的思路，也培養了對于問題進行深入探究的習慣。我更加深刻的體會到各種路由算法的特點，以及性能的優劣。

15、為我今后專業課程的學習奠定了堅實的理論基礎！6 .參考文獻；1 .數據結構嚴蔚敏，吳偉明（c語言版）清華大學出版社2 .算法導論Thoms.H.Cormen,CharlesE.Leiserson,RonaldL.Rivest,CliffordStein著潘金貴，顧鐵成，李成法譯第二版機械工業出版社3 .數據結構基礎（C語言版）（第2版）日lisHorowitz,SartajSahni,SusanAnderson-Freed著朱仲濤譯清華大學出版社4 .數據結構與算法分析：C語言描述（英文版.第2版）MarkAllenWeiss著機械工業出版社5 .算法之道鄒恒明（第2版）機械工業出版社7 .致

16、謝在這次課程設計的撰寫過程中，我得到了許多人的幫助。首先我要感謝我的老師在課程設計上給予我的指導、提供給我的支持和幫助，這是我能順利完成這次報告的主要原因，更重要的是老師幫我解決了許多技術上的難題，讓我能把系統做得更加完善。在此期間，我不僅學到了許多新的知識，而且也開闊了視野，提高了自己的設計能力。其次，我要感謝幫助過我的同學，他們也為我解決了不少我不太明白的設計商的難題。同時也感謝學院為我提供良好的做畢業設計的環境。最后再一次感謝所有在設計中曾經幫助過我的良師益友和同學8 .附錄#include<iostream>#include<string>usingnamesp

17、acestd;#defineMAX10000#defineMOD9873structnode/定義儲存學生信息的結構體stringphone;stringname;stringaddress;node*next;node*infor_phoneMAX;/node*infor_nameMAX;voidinit()/for(inti=0;i<MAX;i+)infor_phonei=NULL;infor_namei=NULL;boolusersayyes()/存放信息的指針數組初始化初始化指針數組幫助函數要求用戶輸入正確的選項stringsig;boolcontinu=true;cout<

18、;<"請輸入(N/n)或(Y/y),(N/n)代表退出,(Y/y)代表繼續:"while(cin>>sig&&(sig!="Y"&&sig!="y")&&(sig!="N"&&sig!="n")cout<<"輸入錯誤，請重新輸入!"<<endl;returnsig="Y"|sig="y"/冉哈希法inthash_agin(intnu

19、mble,intkey)/冉哈希法獲得地址的函數returnnumble%key;intcreate(stringkey)intresult=1,cur=0,i;if(key.size()<=4)i=key.size()-1;elsei=4;for(;i>=0;i-)cur=keyi-'0'result=result*9+cur;returnresult;voidadd_infors(stringphone,stringname,stringaddress)/再希法添加用戶信息到哈希表intnumble_phone=create(phone),key=MOD,pos

20、_phone,pos_name;while(infor_phonepos_phone=hash_agin(numble_phone,key)!=NULL)key-;key=MOD;intnumble_name=create(name);while(infor_namepos_name=hash_agin(numble_name,key)!=NULL)key-;node*inforphone=newnode;node*inforname=newnode;inforphone->name=inforname->name=name;inforphone->phone=inforna

21、me->phone=phone;inforphone->address=inforname->address=address;inforphone->next=inforname->next=NULL;infor_phonepos_phone=inforphone;infor_namepos_name=inforname;voidfind_byname(stringname)/以名字為關鍵字查詢用戶信息intnumble_name=create(name),key=MOD,pos_name;while(true)pos_name=hash_agin(numble_

22、name,key);if(infor_namepos_name=NULL)cout<<"不存在你要查找的信息！"<<endl;cout<<""<<endl;return;if(infor_namepos_name->name=name)cout<<"姓名:"cout<<infor_namepos_name->name<<endl;cout<<"電話:"；cout<<infor_namepos_na

23、me->phone<<endl;cout<<"地址:"；cout<<infor_namepos_name->address<<endl;cout<<""<<endl;return;key-;voidfind_byphone(stringphone)/以電話為關鍵字查詢用戶信息intnumble_phone=create(phone),key=MOD,pos_phone;while(true)pos_phone=hash_agin(numble_phone,key);if(

24、infor_phonepos_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->phone

25、<<endl;cout<<"地址:"；cout<<infor_phonepos_phone->address<<endl;cout<<""<<endl;return;key-;voidfind()stringsig,infor;cout<<"請輸入(1)或(2),(1)代表姓名，(2)代表電話:"while(cin>>sig&&(sig!="1"&&sig!="2"

26、;)cout<<"輸入錯誤，請重新輸入!"<<endl;cout<<"請輸入要查找的信息：”；cin>>infor;if(sig="1")find_byname(infor);elsefind_byphone(infor);/鏈表法inthash(stringkey)/鏈表法獲得哈希碼intresult=1,cur=0,i;if(key.size()<=4)i=key.size()-1;elsei=4;for(;i>=0;i-)cur=keyi-'0'result=re

27、sult*9+cur;result%=(MOD);returnresult;node*build_infor(stringphone,stringname,stringaddress)/存儲用戶信息到哈希表node*information=newnode;information->phone=phone;information->name=name;information->address=address;information->next=NULL;returninformation;voidadd_infor_phone(stringphone,stringname

28、,stringaddress)(intvalue=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;voidadd_infor_name(stringphone,stringname,stringaddress)(intvalue=hash(name);node*info

29、r=build_infor(phone,name,address);if(infor_namevalue=NULL)infor_namevalue=infor;else(node*cur=infor_namevalue;while(cur->next)cur=cur->next;cur->next=infor;voidfindinfor()/分別以名字和電話為關鍵字查詢用戶信息(stringinfor;intsig,pos;cout<<"請輸入要供查找的信息代號:1代表電話號碼，2代表姓名：”；while(cin>>sig&&

30、(sig!=1&&sig!=2)cout<<"輸入錯誤，請重新輸入！"<<endl;cout<<"請輸入要供查找的信息："；cin>>infor;if(sig=1)(boolflag=true;pos=hash(infor);node*cur=infor_phonepos;while(cur)(if(cur->phone=infor)(cout<<"姓名:"<<cur->name<<endl;cout<<&quo

31、t;電話:"<<cur->phone<<endl;cout<<"地址:"<<cur->address<<endl;flag=false;break;)cur=cur->next;)if(flag)cout<<"不存在要查找的記錄!"<<endl;cout<<""<<endl;)elseif(sig=2)(boolflag=true;pos=hash(infor);node*cur=infor_name

32、pos;while(cur)(if(cur->name=infor)(cout<<"姓名:"<<cur->name<<endl<<"電話:"<<cur->phone<<endl<<"地址:"<<cur->address<<endl;flag=false;break;cur=cur->next;if(flag)cout<<"不存在要查找的記錄！"<<endl;cout<<""<<endl;else(cout<<"輸入錯誤，請重新輸入:"<<endl;cout<<""<<endl;findinfor();v