數(shù)據(jù)庫(kù)課程設(shè)計(jì)——哈希表設(shè)計(jì)

1、<p>　　《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)</p><p>　　題 目 哈希表設(shè)計(jì)_________</p><p>　　學(xué) 院 計(jì)算機(jī)學(xué)院 </p><p>　　專 業(yè) 網(wǎng)絡(luò)工程 </p><p>　　年級(jí)班別 11級(jí)（3）班 </p>

2、<p>　　學(xué) 號(hào) </p><p>　　學(xué)生姓名 </p><p>　　指導(dǎo)教師 </p><p>　　2013 年 6 月 28 日</p><p><b>　　一、需求分析<

3、;/b></p><p><b>　　1.任務(wù)和要求</b></p><p>　　（1） 針對(duì)某個(gè)集體中的人名設(shè)計(jì)一個(gè)哈希表，使得平均查找長(zhǎng)度不超過(guò)R，完成相應(yīng)的建立和查表程序。</p><p>　?。?）人名為漢語(yǔ)拼音形式，最長(zhǎng)不超過(guò)19個(gè)字符(如：莊雙雙 zhuangshuangshuang)。</p><p>

4、;　?。?） 假設(shè)待填入哈希表的人名有30個(gè)，平均查找長(zhǎng)度的上限為2。哈希表用除留余數(shù)法構(gòu)造，用偽隨機(jī)探測(cè)在散列法處理沖突。</p><p>　?。?） 在輸入人名過(guò)程中能自動(dòng)識(shí)別非法輸入，并給與非法輸入的反饋信息要求重新輸入。</p><p>　?。?）查找成功時(shí)，顯示姓名及關(guān)鍵字，并計(jì)算和輸出查找成功的平均查找長(zhǎng)度</p><p><b>　　2.運(yùn)行

5、環(huán)境</b></p><p>　?。?）WINDOW7系統(tǒng)</p><p>　　（2）Visual Studio 2012編譯環(huán)境</p><p><b>　　3.開(kāi)發(fā)工具</b></p><p><b>　　C++語(yǔ)言</b></p><p><b>

6、　　二、概要設(shè)計(jì)</b></p><p><b>　　1.設(shè)計(jì)思路</b></p><p>　　（1）創(chuàng)建姓名表和哈希表的結(jié)構(gòu)</p><p>　?。?）姓名（結(jié)構(gòu)體數(shù)組）初始化</p><p>　　用除留余數(shù)法構(gòu)件哈希函數(shù)</p><p>　　用偽隨機(jī)探測(cè)再散列法處理沖突</p

7、><p>　　(3)查找哈希表：在哈希表中進(jìn)行查找，輸出查找的結(jié)果和關(guān)鍵字，并輸出查找成功的平均查找長(zhǎng)度。</p><p><b>　?。?）顯示哈希表</b></p><p>　　2.主要數(shù)據(jù)結(jié)構(gòu)和函數(shù)</p><p>　　定義結(jié)構(gòu)體typedef struct HashList創(chuàng)建哈希表</p><p

8、>　　定義函數(shù)InitNameList()來(lái)對(duì)哈希表初始化</p><p>　　定義函數(shù)CreateHashList()建立哈希表</p><p>　　定義函數(shù)DisplayNamelist()顯示姓名表</p><p>　　定義函數(shù)DisplayHashList()顯示哈希表</p><p>　　定義函數(shù)FindName()查找輸入的

9、名字</p><p>　　定義主函數(shù)main（）來(lái)設(shè)計(jì)界面和輸出</p><p><b>　　三、詳細(xì)設(shè)計(jì)</b></p><p><b>　　1.存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)</b></p><p>　　typedef struct //姓名表</p><p><b>　　{

10、</b></p><p>　　char *py; //名字的拼音</p><p>　　int m; //拼音所對(duì)應(yīng)的 </p><p><b>　　}NAME;</b></p><p>　　NAME NameList[HASH_LEN]; //全局定義姓名表</p&

11、gt;<p>　　typedef struct //哈希表</p><p><b>　　{</b></p><p>　　char *py; //名字的拼音</p><p>　　int m; //拼音所對(duì)應(yīng)的ASCII總和</p><p>　　int si; //查找長(zhǎng)度</

12、p><p><b>　　}HASH;</b></p><p><b>　　2.主要算法</b></p><p>　?。?）姓名（結(jié)構(gòu)體數(shù)組）初始化</p><p>　　名字以拼音的形式夠成字符串，將字符串的各個(gè)字符所對(duì)應(yīng)的ASCII碼相加，所得的整數(shù)做為哈希表的關(guān)鍵字。</p><p

13、>　　/*-----------------姓名（結(jié)構(gòu)體數(shù)組）初始化----------------*/</p><p>　　void InitNameList() </p><p>　　{ char *f;</p><p>　　int r,s0,i;</p><p>　　NameList[0].py="

14、caizhilong";//蔡志龍</p><p>　　NameList[1].py="zengxiangjie";//曾祥杰</p><p>　　NameList[2].py="zengzhikun";//曾志坤</p><p>　　NameList[3].py="zengzhipeng";//

15、曾志鵬</p><p>　　NameList[4].py="chenjunhao";//陳俊豪</p><p>　　NameList[5].py="chenqiwei";//陳啟偉</p><p>　　NameList[6].py="chenxiaocong";//陳曉聰</p><p&

16、gt;　　NameList[7].py="chenzhaolong";//陳兆龍</p><p>　　NameList[8].py="dingyue";//丁越</p><p>　　NameList[9].py="dujingzhou";//杜徑舟</p><p>　　NameList[10].py=&qu

17、ot;duxinjie";//杜信杰</p><p>　　NameList[11].py="heyongjie";//何勇杰</p><p>　　NameList[12].py="houzhengzhi";//候正之</p><p>　　NameList[13].py="huangjinling"

18、;//黃錦玲</p><p>　　NameList[14].py="huangjin";//黃勁</p><p>　　NameList[15].py="huangweihao";//黃威豪</p><p>　　NameList[16].py="huangweidong";//黃煒東</p>&

19、lt;p>　　NameList[17].py="leizhenju";//雷振炬</p><p>　　NameList[18].py="lizhengxu";//李崢旭</p><p>　　NameList[19].py="linguangsheng";//林廣聲</p><p>　　NameList

20、[20].py="linyong";//林泳</p><p>　　NameList[21].py="linzhicong"; //林志聰</p><p>　　NameList[22].py="liuhaifeng";//劉海峰</p><p>　　NameList[23].py="lvhuican

21、g";//呂慧蒼</p><p>　　NameList[24].py="mashaobin";//馬少濱</p><p>　　NameList[25].py="mashuhong";//馬書(shū)鴻</p><p>　　NameList[26].py="paerhati";//帕爾哈提</p>

22、;<p>　　NameList[27].py="sunqinying";//孫秦英</p><p>　　NameList[28].py="wangbinbin";//王彬彬</p><p>　　NameList[29].py="wangnanjia";//王南佳</p><p>　　for (

23、i=0;i<NAME_LEN;i++) //將字符串的各個(gè)字符所對(duì)應(yīng)的ASCII碼相加，所得的整數(shù)做為哈希表的關(guān)鍵字</p><p><b>　　{</b></p><p><b>　　int s=0;</b></p><p>　　char *p=NameList[i].py;</p><p

24、>　　for (j=0;*(p+j)!='\0';j++) </p><p>　　s+=toascii(*(p+j));</p><p>　　NameList[i].m=s;</p><p><b>　　}</b></p><p><b>　　}</b>

25、</p><p><b>　?。?）.建立哈希表</b></p><p>　　/*-----------------------建立哈希表---------------------------------*/</p><p>　　void CreateHashList() //建立哈希表 </p><p><b&

26、gt;　　{</b></p><p>　　for(i=0;i<HASH_LEN;i++)</p><p><b>　　{</b></p><p>　　HashList[i].py="\0";</p><p>　　HashList[i].m =0;</p><p&g

27、t;　　HashList[i].si=0;</p><p><b>　　}</b></p><p>　　for(i=0;i<NAME_LEN;i++) </p><p><b>　　{</b></p><p>　　int sum=1,j=0;</p><p>　　int

28、 adr=(NameList[i].m)%P; //除留余數(shù)法 H(key)=key MOD p,p<=m</p><p>　　if(HashList[adr].si==0) //如果不沖突，將姓名表賦值給哈希表 </p><p><b>　　{</b></p><p>　　HashList[adr].m =NameList[

29、i].m;</p><p>　　HashList[adr].py=NameList[i].py; </p><p>　　HashList[adr].si=1; </p><p><b>　　}</b></p><p>　　else //如果沖突 </p>

30、;<p><b>　　{ </b></p><p>　　while(HashList[adr].si!=0)</p><p><b>　　{</b></p><p>　　adr=(adr+d[j++])%HASH_LEN; //偽隨機(jī)探測(cè)再散列法處理沖突 </p><p>

31、　　sum=sum+1; //查找次數(shù)加1</p><p><b>　　}</b></p><p>　　HashList[adr].m =NameList[i].m; //將姓名表復(fù)制給哈希表對(duì)應(yīng)的位置上</p><p>　　HashList[adr].py=NameList[i].py; </p>

32、<p>　　HashList[adr].si=sum; </p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void DisplayNamelist() //顯示姓名表<

33、;/p><p><b>　　{</b></p><p>　　printf("\n地址 \t\t 姓名 \t\t 關(guān)鍵字\n");</p><p>　　for (i=0;i<NAME_LEN;i++)</p><p>　　printf("%2d %18s \t\t %d \n",

34、i,NameList[i].py,NameList[i].m);</p><p><b>　　}</b></p><p>　　void DisplayHashList() // 顯示哈希表 </p><p><b>　　{</b></p><p>　　float asl=0.0;</

35、p><p>　　printf("\n\n 地址 \t\t 姓名 \t\t 關(guān)鍵字 \t 搜索長(zhǎng)度\n"); //顯示的格式</p><p>　　for (i=0;i<HASH_LEN;i++)</p><p><b>　　{ </b></p><p>　　printf("%2d %1

36、8s \t\t %d \t\t %d\n",i,HashList[i].py,HashList[i].m,HashList[i].si);</p><p>　　asl+=HashList[i].si;</p><p><b>　　}</b></p><p>　　asl/=NAME_LEN;

37、 //求得ASL</p><p>　　printf("\n\n平均查找長(zhǎng)度：ASL(%d)=%f \n",NAME_LEN,asl);</p><p><b>　　}</b></p><p><b>　?。?）查找哈希表</b></p><p>　　void FindName

38、() //查找 </p><p><b>　　{ </b></p><p>　　char name[20]={0};</p><p>　　int s=0,sum=1,adr;</p><p>　　printf("\n請(qǐng)輸入想要查找的姓名的拼音:"); </p><p>

39、;　　scanf("%s",name);</p><p>　　for (j=0;j<20;j++) //求出姓名的拼音所對(duì)應(yīng)的ASCII作為關(guān)鍵字</p><p>　　s+=toascii(name[j]);</p><p>　　adr=s%P; //除留余數(shù)法</p>&l

40、t;p><b>　　j=0;</b></p><p>　　if(HashList[adr].m==s&&!strcmp(HashList[adr].py,name)) //分3種情況進(jìn)行判斷，并輸出超找結(jié)果</p><p>　　printf("\n姓名:%s 關(guān)鍵字:%d 查找長(zhǎng)度為: 1\n",Ha

41、shList[adr].py,s);</p><p>　　else if (HashList[adr].m==0)</p><p>　　printf("沒(méi)有想要查找的人!\n");</p><p><b>　　else</b></p><p><b>　　{</b></p&

42、gt;<p><b>　　while(1)</b></p><p><b>　　{</b></p><p>　　adr=(adr+d[j++])%HASH_LEN; //偽隨機(jī)探測(cè)再散列法處理沖突 </p><p>　　sum=sum+1;

43、 //查找次數(shù)加1</p><p>　　if(HashList[adr].m==0)</p><p><b>　　{</b></p><p>　　printf("沒(méi)有想要查找的人!\n");</p><p><b>　　break;</b></p&

44、gt;<p><b>　　}</b></p><p>　　if(HashList[adr].m==s&&!strcmp(HashList[adr].py,name))</p><p><b>　　{</b></p><p>　　printf("\n姓名:%s 關(guān)鍵字:%d 查

45、找長(zhǎng)度為:%d\n",HashList[adr].py,s,sum);</p><p><b>　　break;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b><

46、;/p><p><b>　　}</b></p><p><b>　　（4）主函數(shù)的設(shè)計(jì)</b></p><p>　　void main() //主函數(shù)</p><p><b>　　{</b></p><p><b>　　c

47、har a;</b></p><p>　　srand((int)time(0)); </p><p>　　for(i=0;i<30;i++) //用隨機(jī)函數(shù)求得偽隨機(jī)數(shù)列d[i]（在1到50之間）</p><p>　　d[i]=1+(int)(HASH_LEN*rand()/(RAND_MAX+1.0));<

48、/p><p>　　InitNameList(); </p><p>　　CreateHashList(); </p><p>　　puts(" 哈希表設(shè)計(jì)");//顯示菜單欄</p><p>　　start:

49、 </p><p>　　puts("\n*--------------------菜單欄-----------------------*");</p><p>　　puts(" \t\t\t 1. 顯示姓名表");</p><p>　　puts("

50、; \t\t\t 2. 顯示哈希表");</p><p>　　puts(" \t\t\t 3. 查找");</p><p>　　puts(" \t\t\t 4. 退出");</p><p>　　puts("*--------------------------------------------------

51、--*"); </p><p><b>　　restart:</b></p><p>　　printf("\n\t請(qǐng)選擇:"); </p><p>　　scanf("%s",&a);</p><p>　　switch(a)

52、 //根據(jù)選擇進(jìn)行判斷，直到選擇退出時(shí)才可以退出</p><p><b>　　{</b></p><p><b>　　case '1':</b></p><p>　　DisplayNamelist();</p><p><b>　　break;</b

53、></p><p><b>　　case '2':</b></p><p>　　DisplayHashList();</p><p><b>　　break;</b></p><p><b>　　case '3':</b></p>

54、;<p>　　FindName();</p><p><b>　　break;</b></p><p><b>　　case '4':</b></p><p><b>　　exit(0);</b></p><p><b>　　break;

55、</b></p><p><b>　　default:</b></p><p>　　printf("\n請(qǐng)輸入正確的選擇!\n");</p><p>　　goto restart;</p><p><b>　　}</b></p><p>　　g

56、oto start;</p><p><b>　　}</b></p><p>　　四、調(diào)試分析實(shí)驗(yàn)截圖</p><p><b>　　1.測(cè)試用例</b></p><p>　　（1）程序運(yùn)行后顯示如下：</p><p>　?。?）顯示姓名表（選擇1）</p>&l

57、t;p>　?。?）顯示哈希表（選擇2）</p><p>　　平均查找長(zhǎng)度小于2，符合題目要求</p><p>　?。?）查找哈希表（選擇3）</p><p>　　輸入要查找的人的姓名，若存在則顯示名字和對(duì)應(yīng)的關(guān)鍵字以及查找長(zhǎng)度；若不存在則顯示無(wú)此記錄：</p><p>　　例1：輸入想要查找的姓名的拼音：linguangsheng（林廣

58、聲）</p><p>　　例2：輸入想要查找的姓名的拼音：mashuhong（馬書(shū)鴻）</p><p>　?。?）退出（選擇4）</p><p><b>　　五、用戶手冊(cè)</b></p><p>　　1.本程序的運(yùn)行環(huán)境為DOS操作系統(tǒng)，執(zhí)行項(xiàng)目為：Namehash。</p><p>　　2.進(jìn)入

59、執(zhí)行程序后，顯示的用戶界面如下：</p><p>　　3.用戶可以根據(jù)界面顯示選擇操作：</p><p><b>　　選擇1：顯示姓名表</b></p><p><b>　　選擇2：顯示哈希表</b></p><p>　　選擇3：查找拼音姓名對(duì)應(yīng)的哈希表位置</p><p>

60、<b>　　選擇4：退出程序</b></p><p><b>　　六、測(cè)試結(jié)果</b></p><p>　　輸入“caizhilong”</p><p>　　輸出 “姓名：caizhilong 關(guān)鍵字：1064 查找長(zhǎng)度為：1”</p><p>　　輸入“zengxiangjie”<

61、/p><p>　　輸出 “姓名：zengxiangjie 關(guān)鍵字：1283 查找長(zhǎng)度為：1”</p><p>　　輸入“zengzhikun”</p><p>　　輸出 “姓名：zengzhikun 關(guān)鍵字：1101 查找長(zhǎng)度為：1”</p><p>　　輸入“zengzhipeng”</p><p>

62、　　輸出 “姓名：zengzhipeng 關(guān)鍵字：1193 查找長(zhǎng)度為：1”</p><p>　　輸入“chenjunhao”</p><p>　　輸出 “姓名：chenjunhao 關(guān)鍵字：1059 查找長(zhǎng)度為：1”</p><p>　　輸入“chenqiwei”</p><p>　　輸出 “姓名：chenqiwei

63、 關(guān)鍵字：957 查找長(zhǎng)度為：1”</p><p>　　輸入“chenxiaocong”</p><p>　　輸出 “姓名：chenxiaocong 關(guān)鍵字：1270 查找長(zhǎng)度為：1”</p><p>　　輸入“chenzhaolong”</p><p>　　輸出 “姓名：chenzhaolong 關(guān)鍵字：1280 查找

64、長(zhǎng)度為：1”</p><p>　　輸入“dingyue”</p><p>　　輸出 “姓名：dingyue 關(guān)鍵字：757 查找長(zhǎng)度為：1”</p><p>　　輸入“dujingzhou”</p><p>　　輸出 “姓名：dujingzhou 關(guān)鍵字：1095 查找長(zhǎng)度為：2”</p><p>

65、　　輸入“duxinjie”</p><p>　　輸出 “姓名：duxinjie 關(guān)鍵字：864 查找長(zhǎng)度為：1”</p><p>　　輸入“heyongjie”</p><p>　　輸出 “姓名：heyongjie 關(guān)鍵字：962 查找長(zhǎng)度為：1”</p><p>　　輸入“houzhengzhi”</p>

66、<p>　　輸出 “姓名：houzhengzhi 關(guān)鍵字：1203 查找長(zhǎng)度為：1”</p><p>　　輸入“huangjinling”</p><p>　　輸出 “姓名：huangjinling 關(guān)鍵字：1278 查找長(zhǎng)度為：2”</p><p>　　輸入“huangjin”</p><p>　　輸出 “姓

67、名：huangjin 關(guān)鍵字：852 查找長(zhǎng)度為：1”</p><p>　　輸入“huangweihao”</p><p>　　輸出 “姓名：huangweihao 關(guān)鍵字：1168 查找長(zhǎng)度為：1”</p><p>　　輸入“huangweidong”</p><p>　　輸出 “姓名：huangweidong 關(guān)鍵字

68、：1280 查找長(zhǎng)度為：1”</p><p>　　輸入“l(fā)eizhenju”</p><p>　　輸出 “姓名：leizhenju 關(guān)鍵字：974 查找長(zhǎng)度為：2”</p><p>　　輸入“l(fā)izhengxu”</p><p>　　輸出 “姓名：lizhengxu 關(guān)鍵字：990 查找長(zhǎng)度為：1”</p>

69、<p>　　輸入“l(fā)ingguangsheng”</p><p>　　輸出 “姓名：linguangsheng 關(guān)鍵字：1386 查找長(zhǎng)度為：1”</p><p>　　輸入“l(fā)inyong”</p><p>　　輸出 “姓名：linyong 關(guān)鍵字：768 查找長(zhǎng)度為：1”</p><p>　　輸入“l(fā)inzhic

70、ong”</p><p>　　輸出 “姓名：linzhicong 關(guān)鍵字：1077 查找長(zhǎng)度為：7”</p><p>　　輸入“l(fā)iuhaifeng”</p><p>　　輸出 “姓名：liuhaifeng 關(guān)鍵字：1052 查找長(zhǎng)度為：2”</p><p>　　輸入“l(fā)vhuicang”</p><p

71、>　　輸出 “姓名：lvhuicang 關(guān)鍵字：961 查找長(zhǎng)度為：1”</p><p>　　輸入“mashaobin”</p><p>　　輸出 “姓名：mashaobin 關(guān)鍵字：946 查找長(zhǎng)度為：1”</p><p>　　輸入“mashuhong”</p><p>　　輸出 “姓名：mashuhong

72、關(guān)鍵字：970 查找長(zhǎng)度為：7”</p><p>　　輸入“paerhati”</p><p>　　輸出 “姓名：paerhati 關(guān)鍵字：846 查找長(zhǎng)度為：1”</p><p>　　輸入“sunqinying”</p><p>　　輸出 “姓名：sunqinying 關(guān)鍵字：1109 查找長(zhǎng)度為：2”</p&

73、gt;<p>　　輸入“wangbinbin”</p><p>　　輸出 “姓名：wangbinbin 關(guān)鍵字：1055 查找長(zhǎng)度為：1”</p><p>　　輸入“wangnanjia”</p><p>　　輸出 “姓名：wangnanjia 關(guān)鍵字：1054 查找長(zhǎng)度為：4”</p><p><b&