數(shù)據(jù)結(jié)構(gòu)實(shí)驗(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 日一問題描述1問題描述針對(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、表程序。（2）人名為漢語(yǔ)拼音形式，最長(zhǎng)不超過(guò)19個(gè)字符(如：莊雙雙 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ì)typedef struct char *py; /名字的拼音 int k; /拼音所對(duì)應(yīng)的整數(shù)NAME; typedef struct /哈希表 char *py; /名字的拼音 int k;

3、 /拼音所對(duì)應(yīng)的整數(shù) int si; /查找長(zhǎng)度HASH;2 .主要算法設(shè)計(jì) （1） 姓名（結(jié)構(gòu)體數(shù)組）初始化 名字以拼音的形式夠成字符串，將字符串的各個(gè)字符所對(duì)應(yīng)的ASCII碼相加，所得的整數(shù)做為哈希表的關(guān)鍵字。void InitNameList() char *f; int r,s0,i; NameList0.py=chenliang;/陳亮 NameList1.py=chenyuanhao;/陳元浩 NameList2.py=chengwenliang;/程文亮 NameList3.py=dinglei;/丁磊 NameList4.py=fenghanzao;/馮漢棗 NameList5

4、.py=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;/劉建輝 NameList13.py=luzhijian;/盧志健 NameList14.py=luonan;/羅楠 NameList15.py=quegaoxi

5、ang;/闕高翔 NameList16.py=sugan;/蘇淦 NameList17.py=suzhiqiang;/蘇志強(qiáng) NameList18.py=taojiayang;/陶嘉陽(yáng) NameList19.py=wujiawen;/吳嘉文 NameList20.py=xiaozhuoming;/肖卓明 NameList21.py=xujinfeng; /許金峰 NameList22.py=yanghaichun;/楊海春 NameList23.py=yeweixiong;/葉維雄 NameList24.py=zengwei;/曾瑋 NameList25.py=zhengyongbin;/鄭雍

6、斌 NameList26.py=zhongminghua;/鐘明華 NameList27.py=chenliyan;/陳利燕 NameList28.py=liuxiaohui;/劉曉慧 NameList29.py=panjinmei;/潘金梅 for(i=0;iNAME_NO;i+) s0=0; f=NameListi.py; for(r=0;*(f+r)!=0;r+) */將字符串的各個(gè)字符所對(duì)應(yīng)的ASCII碼相加，所得的整數(shù)做為哈希表的關(guān)鍵字*/ s0=*(f+r)+s0; NameListi.k=s0; (2) 建立哈希表 （1） 用除留余數(shù)法構(gòu)建哈希函數(shù) （2） 用偽隨機(jī)探測(cè)再散列法處

7、理沖突void CreateHashList() int i; for(i=0; iHASH_LENGTH;i+) HashListi.py=; HashListi.k=0; HashListi.si=0; for(i=0;iHASH_LENGTH;i+) int sum=0; int adr=(NameListi.k)%M; /哈希函數(shù) int d=adr; if(HashListadr.si=0) /如果不沖突 HashListadr.k=NameListi.k; HashListadr.py=NameListi.py; HashListadr.si=1; else /沖突 do d=(d

8、+NameListi.k%10+1)%M; /偽隨機(jī)探測(cè)再散列法處理沖突 sum=sum+1; /查找次數(shù)加1 while (HashListd.k!=0); HashListd.k=NameListi.k; HashListd.py=NameListi.py; HashListd.si=sum+1; (3) 查找哈希表 在哈希表中進(jìn)行查找，輸出查找的結(jié)果和關(guān)鍵字，并計(jì)算和輸出查找成功的平均查找長(zhǎng)度void FindList() /查找 char name20=0; int s0=0,r,sum=1,adr,d; printf(請(qǐng)輸入姓名的拼音:); scanf(%s,name); for(r

9、=0;r20;r+) /求出姓名的拼音所對(duì)應(yīng)的整數(shù)(關(guān)鍵字) s0+=namer; adr=s0%M; /使用哈希函數(shù) d=adr; if(HashListadr.k=s0) /分3種情況進(jìn)行判斷 printf(n姓名:%s 關(guān)鍵字:%d 查找長(zhǎng)度為: 1,HashListd.py,s0); else if (HashListadr.k=0) printf(無(wú)此記錄!); else int g=0; do d=(d+s0%10+1)%M; /偽隨機(jī)探測(cè)再散列法處理沖突 sum=sum+1; if(HashListd.k=0) printf(無(wú)此記錄! ); g=1; if(HashListd.

10、k=s0) printf(n姓名:%s 關(guān)鍵字:%d 查找長(zhǎng)度為:%d,HashListd.py,s0,sum); g=1; while(g=0); (4) 顯示哈希表 顯示哈希表的的格式： n地址t關(guān)鍵字tt搜索長(zhǎng)度tH(key)t 姓名nvoid Display() int i; float average=0; printf(n地址t關(guān)鍵字tt搜索長(zhǎng)度tH(key)t 姓名n); /顯示的格式 for(i=0; i50; i+) printf(%d ,i); printf(t%d ,HashListi.k); printf(tt%d ,HashListi.si); printf(tt%d

11、 ,HashListi.k%M); printf(t %s ,HashListi.py); printf(n); for(i=0;i&ch1;switch(ch1)case D:Display(); coutendl;break;case F:FindList();coutendl;break;case Q:exit(0);cout&ch1;while(ch1!=n); 四. 編程環(huán)境：VC+6.0五調(diào)試報(bào)告及體會(huì)1.測(cè)試用例程序運(yùn)行結(jié)果 程序運(yùn)行后顯示如下: （1）選擇D 查找 ， 顯示哈希表和平均查找長(zhǎng)度，其中平均查找長(zhǎng)度小于2，符合題目要求:（2） 選擇F 查找， 輸入要查找的人的姓名，

12、若存在則顯示名字和對(duì)應(yīng)的關(guān)鍵字以及查找長(zhǎng)度；若不存在則顯示無(wú)此記錄：（3）選擇Q 退出 ， 如要繼續(xù)可按任意鍵： 2.時(shí)間復(fù)雜度O(n)3經(jīng)驗(yàn)和體會(huì)經(jīng)過(guò)這次課程設(shè)計(jì)的學(xué)習(xí)，讓我明白了編寫程序的思路是很重要的。在你編寫一個(gè)程序之前，如果你的腦袋里面沒有思路，根本就不可能編出好的程序。就算能編出程序來(lái)，相信編出的程序的邏輯性也不會(huì)很強(qiáng)，因?yàn)槟闶窍氲绞裁淳途幨裁矗幌到y(tǒng)。因此在我們編程序之前一定要做好充分的準(zhǔn)備，首先要理清自己的思路，然后再將思路分劃成幾個(gè)模塊，一塊一塊的編寫，最后再將所有的模塊聯(lián)系起來(lái)，組成一個(gè)完整的程序。在上機(jī)實(shí)驗(yàn)之前，最好將程序編寫好在草稿紙上，這樣在編譯的時(shí)候也比較有效率。其

13、實(shí)在這次課程設(shè)計(jì)的過(guò)程中，我也遇到了很多難題。在種種的困難中，我明白了耐心在編寫程序時(shí)的重要性。如果你沒有耐心就肯定編不出好的程序，特別是在調(diào)試的過(guò)程中。我們初次寫的程序在電腦上調(diào)試的時(shí)候也許會(huì)出項(xiàng)幾百個(gè)錯(cuò)誤，這時(shí)候我們應(yīng)該耐心的檢查出錯(cuò)的地方和原因，并予以改正，而不是抱怨自己寫的程序太爛錯(cuò)誤太多，就此放棄。相信再?gòu)?qiáng)的人也不可能一次就能編譯成功，總會(huì)有一些問題出現(xiàn)。其實(shí)只要有耐心，你就會(huì)發(fā)現(xiàn)，在你修改了一個(gè)錯(cuò)誤之后，其它有的錯(cuò)誤也會(huì)跟著消失，所以在編譯的時(shí)候一定要有耐心。這段時(shí)間的課程設(shè)計(jì)，我也認(rèn)識(shí)到數(shù)據(jù)結(jié)構(gòu)是一門比較難的課程，需要花很多的時(shí)間去練習(xí)和實(shí)踐。要想把這門課程學(xué)好學(xué)精不是一件容易的

14、事，但是相信事在人為，只要肯下功夫就一定能學(xué)好?？偟膩?lái)說(shuō)，這次程序設(shè)計(jì)讓我獲益匪淺，相信在以后的學(xué)習(xí)生活中我也能從中獲得啟發(fā)。六. 用戶使用說(shuō)明詳細(xì)視圖請(qǐng)參考調(diào)試報(bào)告程序運(yùn)行初顯示如下:從中選擇需要做的操作，輸入對(duì)應(yīng)的操作D、F、Q，并按回車，輸入錯(cuò)誤時(shí)，會(huì)顯示“無(wú)此記錄！”;正確時(shí)，顯示姓名，關(guān)鍵字以及查找長(zhǎng)度。顯示“come on！”時(shí)，選擇y繼續(xù)回到初始菜單，選擇n退出程序。七測(cè)試結(jié)果輸入“chenliang”輸出 “姓名：chenliang 關(guān)鍵字：937 查找長(zhǎng)度為：1”輸入“chenyuanhao”輸出 “姓名：chenyuanhao 關(guān)鍵字：1171 查找長(zhǎng)度為：1”輸入“che

15、ngwenliang”輸出 “姓名：chengwenliang 關(guān)鍵字：1370 查找長(zhǎng)度為：1”輸入“dinglei輸出 “姓名：dinglei 關(guān)鍵字：732 查找長(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”輸入“l(fā)ailaifa”輸出 “姓名

16、：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ā)uonan”輸出 “姓名：luonan 關(guān)鍵字：653

17、 查找長(zhǎng)度為：1”輸入“quegaoxiang”輸出 “姓名：quegaoxiang 關(guān)鍵字：1177 查找長(zhǎng)度為：1”輸入“sugan”輸出 “姓名：sugan 關(guān)鍵字：542 查找長(zhǎng)度為：1”輸入“suzhiqiang”輸出 “姓名：suzhiqiang 關(guān)鍵字：1091 查找長(zhǎng)度為：2”輸入“taojiayang”輸出 “姓名：taojiayang 關(guān)鍵字：1063 查找長(zhǎng)度為：1”輸入“wujiawen”輸出 “姓名：wujiawen 關(guān)鍵字：874 查找長(zhǎng)度為：1”輸入“xiaozhuoming”輸出 “姓名：xiaozhuoming 關(guān)鍵字：1314 查找長(zhǎng)度為：1”輸入“xujinfeng”輸出 “姓名：xujinfeng 關(guān)鍵字：974 查找長(zhǎng)度為：7”輸入“yanghaichun”輸出 “姓名：yanghaichun 關(guān)鍵字：1167 查找長(zhǎng)度為：2”輸入“yeweixiong”輸出 “姓名：yeweixiong 關(guān)鍵字：1096 查找長(zhǎng)度為：1”輸入“zengwei”輸出 “姓名：zengwei 關(guān)鍵字：761 查找長(zhǎng)度為