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

1、題目學(xué)院專業(yè)班級姓名指導(dǎo)教師哈希表設(shè)計(jì)計(jì)算機(jī)科學(xué)與技術(shù)計(jì)算機(jī)科學(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 實(shí)現(xiàn)分析3 HYPERLINK l

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

3、t 體會(huì)和體會(huì)11感受和體會(huì)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è)計(jì)任務(wù)書學(xué)生姓名：專業(yè)班級：班指導(dǎo)教師：工作單位：運(yùn)算機(jī)科學(xué)系題目:哈希表設(shè)計(jì)初始條件：針對某個(gè)集體（比如你所在的班級）中的“人名”設(shè)計(jì)一個(gè)哈希表，使得平均查找

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

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

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

7、成功時(shí)，顯示姓名及關(guān)鍵字，并計(jì)算和輸出查找成功的平均查找長度。3程序設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)依照哈希函數(shù)可唯一確信一個(gè)記錄的地址，在理想情形下，記錄就能夠夠依照那個(gè)存儲(chǔ)地址進(jìn)行存儲(chǔ)。因此哈希表的存儲(chǔ)結(jié)構(gòu)能夠是鏈表和線性表，但一樣情形下選擇線性表進(jìn)行存儲(chǔ)。本次課程設(shè)計(jì)用到的存儲(chǔ)結(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+)/*哈希地址方法：將字符串的各個(gè)字符所對應(yīng)的ASCII碼相加，所得的整數(shù)作為哈希表的關(guān)鍵字*/s0=*(f+r)+s0;NameListi.k=sO;成立哈希表用除留余數(shù)法構(gòu)建哈希函數(shù)用偽隨機(jī)探測再散列法處置沖突構(gòu)建哈希函數(shù)voidCreateHashList()的實(shí)現(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()的實(shí)現(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è)計(jì)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)試報(bào)告調(diào)試中的問題通過對哈希表的研究后，即進(jìn)行程序的設(shè)計(jì)和編碼；將原程序編好后，通過編譯，有如下幾個(gè)問題：在聲明了結(jié)構(gòu)體NAME后，最開始結(jié)構(gòu)體內(nèi)的charname20用來寄存姓名拼音，最長為20位；經(jīng)分析，name表示所存姓名拼音的首地址，無需再申明具體的數(shù)組長度來寄存姓名拼音，如此增加了系統(tǒng)的開銷，最后改成char*name，對寄存姓名拼音

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

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

17、序運(yùn)行結(jié)果正確，知足題目要求！運(yùn)行結(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ù)繃顯選輸此繼體會(huì)和體會(huì)感受和

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

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

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

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

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

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

25、feng108211212wulinfeng9756113yangyiming1084130140001500116chengkang9341601700118guyuze6811801900220liushuo7771202100122renchao7362202300424yangwenjuan11911802500126luhaibo74026227chenwan74026328xiehongwei107980290003000131yijiabin847310320003300134wangyuesong120734135yangchenchen125935136fanxu546361

26、37shenjin7513703800139caoyandong1059390400004100042000430004400245liangfangping136539346wushengping119926147puping65947148jiangyong96648249yangchaoqin117048源程序整個(gè)程序的源代碼為：#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+)/*哈希地址方法：將字符串的各個(gè)字符所對應(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