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

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

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

3、構(gòu)體數(shù)組)初始化名字以拼音的形式夠成字符串，將字符串的各個(gè)字符所對(duì)應(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"/賴來(lái)發(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"蘇志強(qiáng)NameList18.py="taojiayang"/陶嘉陽(yáng)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;*/將字符串的各個(gè)字符所對(duì)應(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)用偽隨機(jī)探測(cè)再散列法處理沖突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;偽隨機(jī)探測(cè)再散列法處理沖突sum=sum+1;查找次數(shù)加1while(Has

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

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

11、ashListd.py,s0,sum);g=1;while(g=0);(4)顯示哈希表顯示哈希表的的格式：n地址t關(guān)鍵字tt搜索長(zhǎng)度tH(key)t姓名nvoidDisplay()inti;floataverage=0;printf("n地址t關(guān)鍵字tt搜索長(zhǎng)度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平均查找長(zhǎng)度：ASL(%d)=%fn",NAME_NO,average);(5)主函數(shù)設(shè)計(jì)voidmain()charch1;InitNameList();CreateHashList();doprintf("D.顯示哈希表nF.查找nQ.退出n請(qǐng)選擇："

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)試報(bào)告及體會(huì)1 .測(cè)試用例程序運(yùn)行結(jié)果程序運(yùn)行后顯示如下：哈希t哈希表設(shè)_計(jì)5計(jì)11於g處.e

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

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

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

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

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

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

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

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