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

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

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

3、/查找長度HASH;2 .主要算法設(shè)計 1 姓名結(jié)構(gòu)體數(shù)組初始化 名字以拼音的形式夠成字符串，將字符串的各個字符所對應的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=&quo

4、t;fenghanzao"/馮漢棗 NameList5.py="fuzongkai"/付宗楷 NameList6.py="hujingbin"/胡勁斌 NameList7.py="huangjianwu"/黃建武 NameList8.py="lailaifa"/賴來發(fā) NameList9.py="lijiahao"/李嘉豪 NameList10.py="liangxiaocong"/梁曉聰 NameList11.py="linchunhua"/林

5、春華 NameList12.py="liujianhui"/劉建輝 NameList13.py="luzhijian"/盧志健 NameList14.py="luonan"/羅楠 NameList15.py="quegaoxiang"/闕高翔 NameList16.py="sugan"/蘇淦 NameList17.py="suzhiqiang"/蘇志強 NameList18.py="taojiayang"/陶嘉陽 NameList19.py="w

6、ujiawen"/吳嘉文 NameList20.py="xiaozhuoming"/肖卓明 NameList21.py="xujinfeng" /許金峰 NameList22.py="yanghaichun"/楊海春 NameList23.py="yeweixiong"/葉維雄 NameList24.py="zengwei"/曾瑋 NameList25.py="zhengyongbin"/鄭雍斌 NameList26.py="zhongminghua&qu

7、ot;/鐘明華 NameList27.py="chenliyan"/陳利燕 NameList28.py="liuxiaohui"/劉曉慧 NameList29.py="panjinmei"/潘金梅 for(i=0;i<NAME_NO;i+) s0=0; f=NameListi.py; for(r=0;*(f+r)!='0'r+) */將字符串的各個字符所對應的ASCII碼相加，所得的整數(shù)做為哈希表的關(guān)鍵字*/ s0=*(f+r)+s0; NameListi.k=s0; (2) 建立哈希表 1 用除留余數(shù)法構(gòu)建哈希

8、函數(shù) 2 用偽隨機探測再散列法處理沖突void CreateHashList() int i; for(i=0; i<HASH_LENGTH;i+) HashListi.py="" HashListi.k=0; HashListi.si=0; for(i=0;i<HASH_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;

9、 HashListadr.si=1; else /沖突 do d=(d+NameListi.k%10+1)%M; /偽隨機探測再散列法處理沖突 sum=sum+1; /查找次數(shù)加1 while (HashListd.k!=0); HashListd.k=NameListi.k; HashListd.py=NameListi.py; HashListd.si=sum+1; (3) 查找哈希表 在哈希表中進行查找，輸出查找的結(jié)果和關(guān)鍵字，并計算和輸出查找成功的平均查找長度void FindList() /查找 char name20=0; int s0=0,r,sum=1,adr,d; print

10、f("請輸入姓名的拼音:"); scanf("%s",name); for(r=0;r<20;r+) /求出姓名的拼音所對應的整數(shù)(關(guān)鍵字) s0+=namer; adr=s0%M; /使用哈希函數(shù) d=adr; if(HashListadr.k=s0) /分3種情況進行判斷 printf("n姓名:%s 關(guān)鍵字:%d 查找長度為: 1",HashListd.py,s0); else if (HashListadr.k=0) printf("無此記錄!"); else int g=0; do d=(d+s0%

11、10+1)%M; /偽隨機探測再散列法處理沖突 sum=sum+1; if(HashListd.k=0) printf("無此記錄! "); g=1; if(HashListd.k=s0) printf("n姓名:%s 關(guān)鍵字:%d 查找長度為:%d",HashListd.py,s0,sum); g=1; while(g=0); (4) 顯示哈希表 顯示哈希表的的格式： n地址t關(guān)鍵字tt搜索長度tH(key)t 姓名nvoid Display() int i; float average=0; printf("n地址t關(guān)鍵字tt搜索長度tH(

12、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 ",HashListi.k%M); printf("t %s ",HashListi.py); printf("n"); for(i=0;i<HASH_LENGTH;i+) average+=HashLi

13、sti.si; average/=NAME_NO; printf("n平均查找長度：ASL(%d)=%f n",NAME_NO,average); (5) 主函數(shù)設(shè)計void main()char ch1;InitNameList(); CreateHashList (); doprintf("D. 顯示哈希表nF. 查找nQ. 退出n請選擇： ");cin>>&ch1;switch(ch1)case 'D':Display(); cout<<endl;break;case 'F':Find

14、List();cout<<endl;break;case 'Q':exit(0);cout<<"come on !(y/n):"cin>>&ch1;while(ch1!='n'); 四. 編程環(huán)境：五調(diào)試報告及體會1.測試用例程序運行結(jié)果 程序運行后顯示如下: 1選擇D 查找 ， 顯示哈希表和平均查找長度，其中平均查找長度小于2，符合題目要求:2 選擇F 查找， 輸入要查找的人的姓名，假設(shè)存在那么顯示名字和對應的關(guān)鍵字以及查找長度；假設(shè)不存在那么顯示無此記錄：3選擇Q 退出 ， 如要繼續(xù)可按任意鍵：

15、 2.時間復雜度O(n)3經(jīng)驗和體會經(jīng)過這次課程設(shè)計的學習，讓我明白了編寫程序的思路是很重要的。在你編寫一個程序之前，如果你的腦袋里面沒有思路，根本就不可能編出好的程序。就算能編出程序來，相信編出的程序的邏輯性也不會很強，因為你是想到什么就編什么，不系統(tǒng)。因此在我們編程序之前一定要做好充分的準備，首先要理清自己的思路，然后再將思路分劃成幾個模塊，一塊一塊的編寫，最后再將所有的模塊聯(lián)系起來，組成一個完整的程序。在上機實驗之前，最好將程序編寫好在草稿紙上，這樣在編譯的時候也比擬有效率。其實在這次課程設(shè)計的過程中，我也遇到了很多難題。在種種的困難中，我明白了耐心在編寫程序時的重要性。如果你沒有耐心就

16、肯定編不出好的程序，特別是在調(diào)試的過程中。我們初次寫的程序在電腦上調(diào)試的時候也許會出項幾百個錯誤，這時候我們應該耐心的檢查出錯的地方和原因，并予以改正，而不是抱怨自己寫的程序太爛錯誤太多，就此放棄。相信再強的人也不可能一次就能編譯成功，總會有一些問題出現(xiàn)。其實只要有耐心，你就會發(fā)現(xiàn)，在你修改了一個錯誤之后，其它有的錯誤也會跟著消失，所以在編譯的時候一定要有耐心。這段時間的課程設(shè)計，我也認識到數(shù)據(jù)結(jié)構(gòu)是一門比擬難的課程，需要花很多的時間去練習和實踐。要想把這門課程學好學精不是一件容易的事，但是相信事在人為，只要肯下功夫就一定能學好。總的來說，這次程序設(shè)計讓我獲益匪淺，相信在以后的學習生活中我也能

17、從中獲得啟發(fā)。六. 用戶使用說明詳細視圖請參考調(diào)試報告程序運行初顯示如下:從中選擇需要做的操作，輸入對應的操作D、F、Q，并按回車，輸入錯誤時，會顯示“無此記錄！;正確時，顯示姓名，關(guān)鍵字以及查找長度。顯示“come on！<y/n>時，選擇y繼續(xù)回到初始菜單，選擇n退出程序。七測試結(jié)果輸入“chenliang輸出 “姓名：chenliang 關(guān)鍵字：937 查找長度為：1輸入“chenyuanhao輸出 “姓名：chenyuanhao 關(guān)鍵字：1171 查找長度為：1輸入“chengwenliang輸出 “姓名：chengwenliang 關(guān)鍵字：1370 查找長度為：1輸入“d

18、inglei輸出 “姓名：dinglei 關(guān)鍵字：732 查找長度為：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輸入“l(fā)ailaifa輸出 “姓名：lailaifa 關(guān)鍵字：819 查找長度為：1輸入“l(fā)ijiahao輸出 “姓名：lijiahao 關(guān)鍵字：833 查找長

19、度為：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ā)uonan輸出 “姓名：luonan 關(guān)鍵字：653 查找長度為：1輸入“quegaoxiang輸出 “姓名：quegaoxiang 關(guān)鍵字：1177 查找長度為：1輸入“sugan輸出 “姓名：sugan 關(guān)鍵字：