數(shù)據(jù)結(jié)構(gòu)課程設(shè)計哈希表設(shè)計

1、題目學(xué)院專業(yè)班級姓名指導(dǎo)教師哈希表設(shè)計計算機科學(xué)與技術(shù)計算機科學(xué)與技術(shù)目錄TOC o 1-5 h z HYPERLINK l bookmark2 o Current Document 1問題描述3 HYPERLINK l bookmark4 o Current Document 問題描述3 HYPERLINK l bookmark6 o Current Document 大體要求3 HYPERLINK l bookmark8 o Current Document 測試數(shù)據(jù)3 HYPERLINK l bookmark10 o Current Document 實現(xiàn)分析3 HYPERLINK l

2、bookmark12 o Current Document 3程序設(shè)計4存儲結(jié)構(gòu)設(shè)計4函數(shù)模塊7程序流程圖7 HYPERLINK l bookmark14 o Current Document 調(diào)試報告9 HYPERLINK l bookmark16 o Current Document 調(diào)試中的問題9 HYPERLINK l bookmark18 o Current Document 對設(shè)計和編碼的討論和分析9 HYPERLINK l bookmark20 o Current Document 程序運行結(jié)果10 HYPERLINK l bookmark22 o Current Documen

3、t 體會和體會11感受和體會11 HYPERLINK l bookmark24 o Current Document 對算法改良的方式13 HYPERLINK l bookmark26 o Current Document 哈希表和源程序13 HYPERLINK l bookmark28 o Current Document 哈希表13 HYPERLINK l bookmark30 o Current Document 源程序15課程設(shè)計任務(wù)書學(xué)生姓名：專業(yè)班級：班指導(dǎo)教師：工作單位：運算機科學(xué)系題目:哈希表設(shè)計初始條件：針對某個集體（比如你所在的班級）中的“人名”設(shè)計一個哈希表，使得平均查找

4、長度不超過R,完成相應(yīng)的建表和查表程序。假設(shè)人名為中國人姓名的漢語拼音形式。待填入哈希表的人名共有30個，取平均查找長度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用偽隨機探測再散列發(fā)處置沖突。測試用例見題集p166。要求完成的要緊任務(wù):（包括課程設(shè)計工作量及其技術(shù)要求，和說明書撰寫等具體要求）課程設(shè)計報告按學(xué)校規(guī)定格式用A4紙打?。〞鴮懀?yīng)包括如下內(nèi)容：一、問題描述簡述題目要解決的問題是什么。2、設(shè)計存儲結(jié)構(gòu)設(shè)計、要緊算法設(shè)計（用類C語言或用框圖描述）、測試用例設(shè)計；3、調(diào)試報告調(diào)試進程中碰到的問題是如何解決的；對設(shè)計和編碼的討論和分析。4、體會和體會（包括對算法改良的假想）5、附源程序清單和

5、運行結(jié)果。源程序要加注釋。若是題目規(guī)定了測試數(shù)據(jù)，那么運行結(jié)果要包括這些測試數(shù)據(jù)和運行輸出，6、設(shè)計報告、程序不得彼此剽竊和拷貝；假設(shè)有類似，那么所有類似者成績均為0分。時刻安排：一、第19周完成。二、7月1日14：00到計算中心檢查程序、交課程設(shè)計報告、源程序（CD盤）。指導(dǎo)教師簽名：年月日系主任（或責(zé)任教師）簽名：年月日課程設(shè)計報告書1問題描述問題描述針對某個集體（比如你所在的班級）中的“人名”設(shè)計一個哈希表，使得平均查找長度不超過R,完成相應(yīng)的建表和查表程序。大體要求假設(shè)人名為中國人姓名的漢語拼音形式。待填入哈希表的人名共有30個，取平均查找長度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用偽

6、隨機探測再散列發(fā)處置沖突。測試數(shù)據(jù)取自己班級成員的名字作為測試數(shù)據(jù)，成立一個相關(guān)哈希表，并計算平均查找長度，完成查詢。2.實現(xiàn)分析（1）針對某個集體中的人名設(shè)計一個哈希表，使得平均查找長度不超過R，完成相應(yīng)的成立和查表程序。（2）人名為漢語拼音形式，最長不超過19個字符（如：莊雙雙zhuangshuangshuang）。（3）假設(shè)待填入哈希表的人名有30個，平均查找長度的上限為2。哈希表用除留余數(shù)法構(gòu)造，用偽隨機探測在散列法處置沖突。（4）若是隨機函數(shù)自行構(gòu)造，那么應(yīng)第一調(diào)整好隨機函數(shù)，使其散布均勻。字符的取碼方式可直接利用C語言中的toascii函數(shù)，并可對太長人名先進行折疊處置。（5）查找

7、成功時，顯示姓名及關(guān)鍵字，并計算和輸出查找成功的平均查找長度。3程序設(shè)計存儲結(jié)構(gòu)設(shè)計依照哈希函數(shù)可唯一確信一個記錄的地址，在理想情形下，記錄就能夠夠依照那個存儲地址進行存儲。因此哈希表的存儲結(jié)構(gòu)能夠是鏈表和線性表，但一樣情形下選擇線性表進行存儲。本次課程設(shè)計用到的存儲結(jié)構(gòu)如下：typedefstructchar*name;ame=fanxu;NameL=jiangyong;NameL=guyuze;NameL=liuzhenhai;NameL=chenang;NameL=caoyandong;NameLi

8、=yangchenchen;NameL=shenjin;NameL=puping;NameL=luhaibo;NameL=renchao;NameL=wangshichuang;NameL=guoqihui;NameL=chengkang;NameL=wangyuesong;NameL=liangfangping;NameL=wangxufeng;NameL=heji

9、e;NameL=yangyiming;NameL=wushengping;NameL=yangchaoqin;NameL=wulinfeng;NameL=xiehongwei;NameL=liushuo;NameL=yijiabin;NameL=xuhaiyang;NameL=yangwenjuan;NameL=chenjunyan；NameL=wangjiaxin;NameL

10、=chenwan;for(i=0;ivNAMENO;i+)sO=O;f=NameL;for(r=0;*(f+r)!=0;r+)/*哈希地址方法：將字符串的各個字符所對應(yīng)的ASCII碼相加，所得的整數(shù)作為哈希表的關(guān)鍵字*/s0=*(f+r)+s0;NameListi.k=sO;成立哈希表用除留余數(shù)法構(gòu)建哈希函數(shù)用偽隨機探測再散列法處置沖突構(gòu)建哈希函數(shù)voidCreateHashList()的實現(xiàn)：voidCreateHashList()inti;for(i=0;ivHASH_LENGTH;i+)HashListi.py=;HashListi.k=0;Hash

11、Listi.si=0;for(i=O;ivHASH_LENGTH;i+)intsum=0;intadr=(NameListi.k)%M;i=0)=NameListi.k;HashListadr.py=NameListi.py;HashListadr.si=1;else%10+1)%M;!=0);HashListd.k=NameListi.k;HashListd.py=NameListi.py;HashListd.si=sum+1;查找哈希表假設(shè)查找成功，那么輸出姓名、關(guān)鍵字和查找長度；查找失敗，那么返回相應(yīng)的失敗信息。查找函數(shù)voidFindList()的實現(xiàn)：voidFindList()=s

12、0)y,s0);else訐(HashListadr.k=0)printf(無此記錄!)；elseintg=0；dod=(d+s0%10+l)%M;=0)printf(無此記錄！)；g=1；if(HashListd.k=s0)printf(n姓名:%s關(guān)鍵字:%d查找長度為:d,HashListd.py,s0,sum);g=1;while(g=0);3)顯示哈希表顯示哈希表的的格式：n地址t關(guān)鍵字tt搜索長度tH(key)t姓名n顯示哈希表的函數(shù)voidDisplay()的：voidDisplay。;printf(tt%d,HashListi.si);printf(tt%d,HashListi.

13、k%M);printf(t%s,HashListi.py);printf(n);for(i=0;ivHASH_LENGTH;i+)average+=HashListi.si;average/=NAME_NO;printf(n平均查找長度：ASL(%d)=%fn,NAME_NO,average);(4)主函數(shù)設(shè)計voidmain()charch1;InitNameList();CreateHashList();doprintf(D.顯示哈希表nF.查找nQ.退出n請選擇：“)；cin&ch1;switch(ch1)caseD:Display();coutvvendl;break;caseF:Fi

14、ndList();coutvvendl;break;caseQ:exit(O);coutvvcomeon!(y/n):;cinwhile(chl!=n);函數(shù)模塊模塊挪用關(guān)系主函數(shù)模塊輸出模塊查找模塊哈希表模塊姓名初始化模程序流程圖本次程序流程圖如下Q調(diào)試報告調(diào)試中的問題通過對哈希表的研究后，即進行程序的設(shè)計和編碼；將原程序編好后，通過編譯，有如下幾個問題：在聲明了結(jié)構(gòu)體NAME后，最開始結(jié)構(gòu)體內(nèi)的charname20用來寄存姓名拼音，最長為20位；經(jīng)分析，name表示所存姓名拼音的首地址，無需再申明具體的數(shù)組長度來寄存姓名拼音，如此增加了系統(tǒng)的開銷，最后改成char*name，對寄存姓名拼音

15、時直接對name賦值，系統(tǒng)直接依照字符數(shù)組來寄存姓名拼音，而寄存長度沒有固定。成立哈希表的函數(shù)：voidCreateHashList()中，若是碰到?jīng)_突后，在dowhile()；語句中，利用偽隨機探測再散列法處置沖突，沒執(zhí)行一次就要將記錄查找長度的sum增加一次，在那個循環(huán)執(zhí)行完后，即找到一個不沖突的地址來寄存姓名拼音，通過自習(xí)分析，現(xiàn)在的查找長度需要加1，即將原先的語句HashListd.si=sum;改成HashListd.si=sum+1;現(xiàn)在的HashListd.si才是正確的查找長度。main函數(shù)中的dowhile()語句中，最開始while()語句是：while(a!=Nlla!=

16、n)通過度析，在用戶需要退出時，不論輸入a=N仍是a=n，都將繼續(xù)循環(huán)；通過自習(xí)試探，最終將while()語句改成：while(a=Ylla=y)，如此就實現(xiàn)了用戶的選擇。對設(shè)計和編碼的討論和分析算法采納結(jié)構(gòu)體和數(shù)組來存儲數(shù)據(jù)，利用除留余數(shù)法取得哈希地址，利用為隨機序列法來處置沖突，姓名拼音的關(guān)鍵字為字符串的各個字符所對應(yīng)的ASCII碼相加，所得的整數(shù)。求哈希地址時模為51，哈希表的總長度為50，而實際名字只有30個，因此有20個地址空間被空閑著，這浪費了必然的內(nèi)存。算法的時刻復(fù)雜度為：O(n)。平均查找長度為：裝填因子為：30/50=程序運行結(jié)果通過對程序錯誤的修改后，程序執(zhí)行，通過度析，程

17、序運行結(jié)果正確，知足題目要求！運行結(jié)果要緊截圖如下：程序開始后，初始界面為:84700011910736777081093408106497S10G272408755171383974107501072107301010011101111141131682626180121816G131110H0請選擇:yijiabinFzCDocumentsandSettingsAdministrato”莫面S據(jù)結(jié)構(gòu)諜設(shè)嗆希表潘眄DebugHash,79446i00321040175402i關(guān)鍵字0搜索長度1姓名uang.itaxinltuzhenhaichenJunyanxuhaiyanguangshic

18、huangheJieguaqihuichenangfwangxufmnmuulinfeng1ymngyiminmchengkangguyuneliushuorenchaoi/anuenjuanluhaibochenuanxtehonguei000039264748邨350B0003437結(jié)果顯示，平均查找長度為，符合題設(shè)要求！選擇Y繼續(xù)后選擇F查找查找成功結(jié)果為：繼色毛乩退岀次g-顯下哈希表P-杳找Q-退出請迭擇；F.請輸入姓名的拼音:pupring姓:pupinq關(guān)悻字=69杳棧長度為：1Y繼妹乩退出：.查找失敗結(jié)果為：V音-拼出丈口F名t-N.押姓錄續(xù)魴擇A記續(xù)繃顯選輸此繼體會和體會感受和

19、體會數(shù)據(jù)結(jié)構(gòu)這門課程是運算機專業(yè)一門基礎(chǔ)性學(xué)科，重要性可見一斑，學(xué)好這門課程對以后人一輩子的進展具有深遠的阻礙。而數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計即是對學(xué)習(xí)成效的查驗。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計不僅能夠鍛煉咱們獨立試探問題、解決問題的能力，而且能夠培育咱們的整體性思維的能力；通過課程設(shè)計，使我了解了很多數(shù)據(jù)結(jié)構(gòu)的經(jīng)典問題和經(jīng)典算法，加深了對數(shù)據(jù)結(jié)構(gòu)的再熟悉，鞏固了數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)性知識，比如：存儲結(jié)構(gòu)、數(shù)據(jù)查找、哈希表的設(shè)計和查找、算法分析等。哈希表是依照關(guān)鍵碼值而直接進行訪問的數(shù)據(jù)結(jié)構(gòu)，它把關(guān)鍵碼值通過哈希函數(shù)映射到表中一個地址來存儲記錄，以加速查找的速度。哈希函數(shù)的構(gòu)造方式有：直接尋址法、數(shù)字分析法、平方取中法、折

20、疊法、隨機數(shù)法、除留余數(shù)法等；關(guān)于地址沖突要進行解決，要緊解決沖突的的方式有：開放尋址法（線性探測再散列、二次探測再散列、偽隨機探測再散列）、再散列法、鏈地址法、成立一個公共溢出區(qū)等。查找進程中，關(guān)鍵碼的比較次數(shù)，取決于產(chǎn)生沖突的多少，產(chǎn)生的沖突少，查找效率就高，產(chǎn)生的沖突多，查找效率就低。因此，阻礙產(chǎn)生沖突多少的因素，也確實是阻礙查找效率的因素。阻礙產(chǎn)生沖突多少有以下三個因素：散列函數(shù)是不是均勻、處置沖突的方式、散列表的裝填因子。通過查找相關(guān)資料還了解了聞名的hash算法：MD4、MD五、SHA-1及其他。哈希表的要緊用途為：文件校驗、數(shù)字簽名、鑒權(quán)協(xié)議等。這也是關(guān)于以后繼續(xù)研究數(shù)據(jù)結(jié)構(gòu)所必

21、需了解的知識。這次課程設(shè)計，我明白了關(guān)于編寫程序，解題的思路尤其重要。在編寫程序之前，若是沒有比較清楚的思路，全然不可能編出好的程序。就算馬馬虎虎的編出來，程序的邏輯性、健壯性、完善性、合理性也可不能很強。在編程之前，咱們應(yīng)反復(fù)研究題目要求，對題目涉及的情形進行比較充分的分析，以便編寫出加倍符合題意的程序；第二要充分考慮各類臨界情形，對一些錯誤的輸入進行處置。因此在咱們編程序之前必然要做好充分的預(yù)備，第一要理清自己的思路，然后再將思路分劃成幾個模塊，逐塊的寫好算法，最后再將所有的模塊有機的聯(lián)系起來，組成一個完整的程序。在成功通過編譯的情形下，對程序運行的結(jié)果進行系統(tǒng)的分析，查驗其正確性，若是有

22、錯誤，應(yīng)當(dāng)即去分析源程序的邏輯錯誤，直到取得正確的結(jié)果。在這次課程設(shè)計的進程中，我也碰到了很多難題。在各類的困難中，我明白了在編寫程序時要有耐心。若是你沒有耐心，即便再好的算法思路也可不能取得專門好的表達，專門是在調(diào)試的進程中，關(guān)于各類各樣的錯誤，要專門的有耐心去自習(xí)分析緣故，專門是一些大體的語法錯誤，不能一看到錯誤很多就亂了陣腳，更不能輕易的舍棄，半途而廢。比如在調(diào)試中沒有概念某些變量的錯誤、大體的輸入輸犯錯誤、數(shù)據(jù)選取不合理的錯誤、變量名前后不一的錯誤、函數(shù)返回值的錯誤等等。其實只要有耐心，你就會發(fā)覺，在你修改了一個錯誤以后，其它有的錯誤也會隨著消失，因此在編譯的時候必然要有耐心。數(shù)據(jù)結(jié)構(gòu)

23、是一門比較難的課程，需要花很多的時刻去不斷地練習(xí)和實踐。要想把這門課程學(xué)勤學(xué)精并非一件容易的事，專門是一些經(jīng)典算法，是幾十年前人聰慧的結(jié)晶，關(guān)于初學(xué)者的明白得和應(yīng)用有必然的難度；可是事在人為，只要肯下功夫，便必然能夠?qū)W好。總的來講，這次程序設(shè)計讓我獲益匪淺，相信在以后的學(xué)習(xí)生活中我也能從中取得啟發(fā)。對算法改良的方式本次哈希表的設(shè)計采納的存儲結(jié)構(gòu)為順序存儲，如此的存儲結(jié)構(gòu)簡單易操作，可是必需實現(xiàn)給定存儲大小，如此無益于動態(tài)操作，在題目許諾的情形下，能夠采納鏈式存儲結(jié)構(gòu)，從而實現(xiàn)動態(tài)存儲；對關(guān)鍵字的選取還能夠依照各個姓名的字母表的順序等方式，哈希地址的除留余數(shù)法的模還能夠是其他的接近表長的素數(shù)，解

24、決沖突的偽隨機序列取余的模長也能夠是其他的接近表長的素數(shù)；本次哈希表的總長度為50，而實際只用到了30個，還余下20個空閑地址被白白浪費了，能夠在知足題目要求的情形下適當(dāng)?shù)倪x取小一點的總表長。哈希表和源程序哈希表通過度析，最后取得的哈希表如下：搜索長度地址存儲內(nèi)容關(guān)鍵字H(key)10(null)0011wangjiaxin1072112liuzhenhai1073243(null)0014chenjunyan1075415xuhaiyang974516wangshichuang1383617hejie517718guoqihui87580900110chenang72410111wangxu

25、feng108211212wulinfeng9756113yangyiming1084130140001500116chengkang9341601700118guyuze6811801900220liushuo7771202100122renchao7362202300424yangwenjuan11911802500126luhaibo74026227chenwan74026328xiehongwei107980290003000131yijiabin847310320003300134wangyuesong120734135yangchenchen125935136fanxu546361

26、37shenjin7513703800139caoyandong1059390400004100042000430004400245liangfangping136539346wushengping119926147puping65947148jiangyong96648249yangchaoqin117048源程序整個程序的源代碼為：#includev#includev#include#defineHASH_LENGTH50ame=fanxu;NameL=jiangyong;NameL=guyuze;NameL=liuzhenhai;Na

27、meL=chenang;NameL=caoyandong;NameL=yangchenchen;NameL=shenjin;NameL=puping;NameL=luhaibo;NameL=renchao;NameL=wangshichuang;NameL=guoqihui;NameL=chengkang;NameL=wangyuesong;NameL=liangfan

28、gping;NameL=wangxufeng;NameL=hejie;NameL=yangyiming;NameL=wushengping;NameL=yangchaoqin;NameL=wulinfeng;NameL=xiehongwei;NameL=liushuo;NameL=yijiabin;NameL=xuhaiyang;NameL=yangwenjuan;NameLi

29、=chenjunyan;NameL=wangjiaxin;NameL=chenwan;for(i=0;ivNAME_NO;i+)s0=0;f=NameL;for(r=0;*(f+r)!=0;r+)/*哈希地址方法：將字符串的各個字符所對應(yīng)的ASCII碼相力口，所得的整數(shù)做為哈希表的關(guān)鍵字*/sO=*(f+r)+sO;NameListi.k=sO;voidCreateHashList()ame=;HashListi.k=O;HashListi.si=0;for(i=0;ivHASH_LENGTH;i+)intsum=0;intadr=(NameListi.k)%M;i=0)=NameListi.k;HashL=NameL;Hash