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

1、課程設(shè)計課程名稱數(shù)據(jù)結(jié)構(gòu)題目名稱哈希表設(shè)計學(xué)生學(xué)院計算機學(xué)院專業(yè)班級07級網(wǎng)絡(luò)工程2班學(xué)號3207007022學(xué)生姓名劉曉慧指導(dǎo)教師楊勁濤2009年6月28日一,問題描述1問題描述針對某個集體(比如你所在的班級)中的“人名”設(shè)計一個哈希表，使得平均查找長度不超過R,完成相應(yīng)的建表和查表程序。2.基本要求假設(shè)人名為中國人姓名的漢語拼音形式。待填入哈希表的人名共有30個，取平均查找長度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用偽隨機探測再散列發(fā)處理沖突。二.需求分析(1)針對某個集體中的人名設(shè)計一個哈希表，使得平均查找長度不超過R,完成相應(yīng)的建立和查表程序。(2)人名為漢語拼音形式，最長不超過19個

2、字符(如：莊雙雙zhuangshuangshuang)。(3)假設(shè)待填入哈希表的人名有30個，平均查找長度的上限為2。哈希表用除留余數(shù)法構(gòu)造，用偽隨機探測在散列法處理沖突。(4)在輸入人名過程中能自動識別非法輸入，并給與非法輸入的反饋信息要求重新輸入。(5)查找成功時，顯示姓名及關(guān)鍵字，并計算和輸出查找成功的平均查找長度三.程序設(shè)計1 .存儲結(jié)構(gòu)設(shè)計typedefstructchar*py;/名字的拼音intk;/拼音所對應(yīng)的整數(shù)NAME;typedefstruct/哈希表char*py;/名字的拼音intk;/拼音所對應(yīng)的整數(shù)intsi;/查找長度HASH;2 .主要算法設(shè)計(1) 姓名(結(jié)

3、構(gòu)體數(shù)組)初始化名字以拼音的形式夠成字符串，將字符串的各個字符所對應(yīng)的ASCII碼相加,所得的整數(shù)做為哈希表的關(guān)鍵字。voidInitNameList()char*f;intr,s0,i;NameList0.py="chenliang"/陳亮NameList1.py="chenyuanhao"/陳元浩NameList2.py="chengwenliang"/程文亮NameList3.py="dinglei"丁磊NameList4.py="fenghanzao"/馮漢棗NameList5.py=&

4、quot;fuzongkai"/付宗楷NameList6.py="hujingbin"/胡勁斌NameList7.py="huangjianwu"/黃建武NameList8.py="lailaifa"/賴來發(fā)NameList9.py="lijiahao"李嘉豪NameList10.py="liangxiaocong"/梁曉聰NameList11.py="linchunhua"/林春華NameList12.py="liujianhui"/劉建輝Na

5、meList13.py="luzhijian"盧志健NameList14.py="luonan"/羅楠NameList15.py="quegaoxiang"/闕高翔NameList16.py="sugan"/蘇漁NameList17.py="suzhiqiang"蘇志強NameList18.py="taojiayang"/陶嘉陽NameList19.py="wujiawen"/吳嘉文NameList20.py="xiaozhuoming"

6、;/肖卓明NameList21.py="xujinfeng"/許金峰NameList22.py="yanghaichun"/楊海春NameList23.py="yeweixiong"葉維雄NameList24.py="zengwei"/曾瑋NameList25.py="zhengyongbin"/鄭雍斌NameList26.py="zhongminghua"/鐘明華NameList27.py="chenliyan"/陳利燕NameList28.py=&qu

7、ot;liuxiaohui"/劉曉慧NameList29.py="panjinmei"/潘金梅for(i=0;i<NAME_NO;i+)s0=0;*/將字符串的各個字符所對應(yīng)的ASCII碼相加，所f=NameListi.py;for(r=0;*(f+r)!=''0'r+)得的整數(shù)做為哈希表的關(guān)鍵字*/s0=*(f+r)+s0;NameListi.k=s0;)(2) 建立哈希表(1)用除留余數(shù)法構(gòu)建哈希函數(shù)(2)用偽隨機探測再散列法處理沖突voidCreateHashList()inti;for(i=0;i<HASH_LENGTH

8、;i+)HashListi.py=""HashListi.k=0;HashListi.si=0;)for(i=0;i<HASH_LENGTH;i+)intsum=0;intadr=(NameListi.k)%M;哈希函數(shù)intd=adr;if(HashListadr.si=0)如果不沖突HashListadr.k=NameListi.k;HashListadr.py=NameListi.py;HashListadr.si=1;)else沖突dod=(d+NameListi.k%10+1)%M;偽隨機探測再散列法處理沖突sum=sum+1;查找次數(shù)加1while(Has

9、hListd.k!=0);HashListd.k=NameListi.k;HashListd.py=NameListi.py;HashListd.si=sum+1;(3) 查找哈希表在哈希表中進行查找，輸出查找的結(jié)果和關(guān)鍵字，并計算和輸出查找成功的平均查找長度voidFindList()/查找charname20=0;ints0=0,r,sum=1,adr,d;printf("請輸入姓名的拼音：")；scanf("%s",name);for(r=0;r<20;r+)求出姓名的拼音所對應(yīng)的整數(shù)(關(guān)鍵字)s0+=namer;adr=s0%M;/使用哈希

10、函數(shù)d=adr;if(HashListadr.k=s0)分3種情況進行判斷printf("n姓名:%s關(guān)鍵字:%d查找長度為：1",HashListd.py,s0);elseif(HashListadr.k=0)printf("無此記錄!");elseintg=0;dod=(d+s0%10+1)%M;/偽隨機探測再散列法處理沖突sum=sum+1;if(HashListd.k=0)printf("無此記錄！");g=1;if(HashListd.k=s0)printf("n姓名:%s關(guān)鍵字:%d查找長度為：d",H

11、ashListd.py,s0,sum);g=1;while(g=0);(4)顯示哈希表顯示哈希表的的格式：n地址t關(guān)鍵字tt搜索長度tH(key)t姓名nvoidDisplay()inti;floataverage=0;printf("n地址t關(guān)鍵字tt搜索長度tH(key)t姓名n");顯示的格式for(i=0;i<50;i+)printf("%d",i);printf("t%d",HashListi.k);printf("tt%d",HashListi.si);printf("tt%d"

12、;,HashListi.k%M);printf("t%s",HashListi.py);printf("n");for(i=0;i<HASH_LENGTH;i+)average+=HashListi.si;average/=NAME_NO;printf("n平均查找長度：ASL(%d)=%fn",NAME_NO,average);(5)主函數(shù)設(shè)計voidmain()charch1;InitNameList();CreateHashList();doprintf("D.顯示哈希表nF.查找nQ.退出n請選擇："

13、);cin>>&ch1;switch(ch1)case'D':Display();cout<<endl;break;case'F':FindList();cout<<endl;break;case'Q':exit(0);cout<<"comeon!(y/n):"cin>>&ch1;while(ch1!='n');四.編程環(huán)境:VC+6.0五.調(diào)試報告及體會1 .測試用例程序運行結(jié)果程序運行后顯示如下：哈希t哈希表設(shè)_計5計11於g處.e

14、xe,顯示哈希表-查找選擇;(1)選擇D查找，顯示哈希表和平均查找長度，其中平均查找長度小于2,符合題目要求：Q"F：'哈希1哈希表設(shè)計Xlhbw'HaBli.金力h.退出懵選擇;址t012345678901234FO6787012345&78?0123456789批IS1Z34J67871111111111222222222233333333334444444444關(guān)鍵字搜索長度116720211771Htkey>姓名37yliunZquesaoxian873000011089761118B17108109613799749588819955g1057

15、054212?57328741W63Q0095597401298107183397410740£53117171339100037chensrwenliantr8lluxiAohui9z&n9wci18huanfjianwii0IBsuHhiqianH心015歲Eu電±xzLnng18liangxiaoconff34xujinFeng18hujinbin020lallaifft15chenlxvan023fenffhAhzao025sun26zhongmijnsfliua27dinglei28uujiftuen29taojiayans(00ISpanjinnei34

16、Fuzonsfkai029zhefigyonsfhin37linehuahua34lijifthao34lushijian40liujianliui42luonan49chenipufinliao44chen1-ian945xiaozhuoiDins000平均查找長度：ASL<30>=1omenn，4/n=(2)選才?F查找，輸入要查找的人的姓名，若存在則顯示名字和對應(yīng)的關(guān)鍵字以及查找長度；若不存在則顯示無此記錄：D.顯小哈希表F.4-退出請選擇：F請輸入姓名的拼音：Uuxiaohui姓名二liicciaoluii關(guān)鍵字:1晚查找長度為：1cotiteonf<y/n>：

17、yBl顯小哈希表F.查卓Q1退出請選*F請輸入姓名的拼音:xadssd無巡記錄，comeon*<y/n>：(3)選擇Q退出，如要繼續(xù)可按任意鍵:corfon，y/r»>：yD.顯小哈希表F.查找Q.退出請選南Qrressanykeytocontinue2 .時間復(fù)雜度O(n)3 .經(jīng)驗和體會經(jīng)過這次課程設(shè)計的學(xué)習(xí)，讓我明白了編寫程序的思路是很重要的。在你編寫一個程序之前，如果你的腦袋里面沒有思路，根本就不可能編出好的程序。就算能編出程序來，相信編出的程序的邏輯性也不會很強，因為你是想到什么就編什么，不系統(tǒng)。因此在我們編程序之前一定要做好充分的準(zhǔn)備，首先要理清自己的思

18、路，然后再將思路分劃成幾個模塊，一塊一塊的編寫，最后再將所有的模塊聯(lián)系起來，組成一個完整的程序。在上機實驗之前，最好將程序編寫好在草稿紙上，這樣在編譯的時候也比較有效率。其實在這次課程設(shè)計的過程中，我也遇到了很多難題。在種種的困難中，我明白了耐心在編寫程序時的重要性。如果你沒有耐心就肯定編不出好的程序，特別是在調(diào)試的過程中。我們初次寫的程序在電腦上調(diào)試的時候也許會出項幾百個錯誤，這時候我們應(yīng)該耐心的檢查出錯的地方和原因，并予以改正，而不是抱怨自己寫的程序太爛錯誤太多，就此放棄。相信再強的人也不可能一次就能編譯成功，總會有一些問題出現(xiàn)。其實只要有耐心，你就會發(fā)現(xiàn)，在你修改了一個錯誤之后，其它有的

19、錯誤也會跟著消失，所以在編譯的時候一定要有耐心。這段時間的課程設(shè)計，我也認識到數(shù)據(jù)結(jié)構(gòu)是一門比較難的課程，需要花很多的時間去練習(xí)和實踐。要想把這門課程學(xué)好學(xué)精不是一件容易的事，但是相信事在人為，只要肯下功夫就一定能學(xué)好?？偟膩碚f，這次程序設(shè)計讓我獲益匪淺，相信在以后的學(xué)習(xí)生活中我也能從中獲得啟發(fā)。六.用戶使用說明詳細視圖請參考調(diào)試報告程序運行初顯示如下通選畫F請輸入姓名的拼音門iuxiaohui姓名:liuxianhui關(guān)鍵字二108y查找長度為二1從中選擇需要做的操作，輸入對應(yīng)的操作D、F、Q,并按回車，輸入錯誤時,會顯示“無此記錄！”；正確時，顯示姓名，關(guān)鍵字以及查找長度。0-顯不哈希表F

20、.宜找9-退出coneonffyZn>：y口.顯示哈希表P.查找請選擇，F(xiàn)請祠人姓名的拼音無此記錄，U-退出coneon!<y/n>：顯示“comeon!<y/n>"時，選擇y繼續(xù)回到初始菜單，選擇n退出程序七.測試結(jié)果輸入“chenliang”輸出姓名：chenliang關(guān)鍵字：937查找長度為：1”輸入“chenyuanhao”輸出姓名：chenyuanhao關(guān)鍵字：1171查找長度為：1”輸入“chengwenliang”輸出姓名：chengwenliang關(guān)鍵字：1370查找長度為：1輸入“dinglei輸出姓名：dinglei關(guān)鍵字：732查找

21、長度為：1”輸入“fenghanzao”輸出姓名：fenghanzao關(guān)鍵字：1057查找長度為：1”輸入“fuzongkai”輸出姓名：fuzongkai關(guān)鍵字：974查找長度為：1”輸入“hujingbin”輸出姓名：hujingbin關(guān)鍵字：958查找長度為：1”輸入“huangjianwu”輸出姓名：huangjianwu關(guān)鍵字：1185查找長度為：1”輸入"lailaifa”輸出姓名：lailaifa關(guān)鍵字：819查找長度為：1”輸入“l(fā)ijiahao”輸出姓名：lijiahao關(guān)鍵字：833查找長度為：2”輸入“l(fā)iangxiaocong”輸出姓名：liangxiaocong關(guān)鍵字：1379查找長度為：1"輸入“l(fā)inchunhua”輸出姓名：linchunhua關(guān)鍵字：1071查找長度為：1”輸入“l(fā)iujianhui”輸出姓名：liujianhui關(guān)鍵字：1074查找長度為：1”輸入“l(fā)uzhijian”輸出姓名：luzhijian關(guān)鍵字：974查找長度為：2”輸入“l(fā)uon