數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-基于hash表的班級(jí)成員管理

上傳人：奔*** IP屬地：河北更新時(shí)間：2024-03-01 格式：doc 頁(yè)數(shù)：21 大?。?99.50KB 人氣指數(shù)：12 舉報(bào) 版權(quán)申訴

2023年全國(guó)碩士研究生考試考研英語(yǔ)一試題真題（含答案詳解+作文范文）_第1頁(yè)

已閱讀1頁(yè)，還剩20頁(yè)未讀，繼續(xù)免費(fèi)閱讀

版權(quán)說(shuō)明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、　　課程設(shè) 計(jì) 報(bào) 告　　課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)　　課程設(shè)計(jì)題目：基于Hash表的班級(jí)成員管理　　院（系）：計(jì)算機(jī)學(xué)院　　專業(yè)：

2、班級(jí)：　　學(xué) 號(hào)： 　　姓名： 　　指導(dǎo)教師： 　　目錄</p&

3、gt;　　1 題目介紹和功能要求1　　1.1 題目介紹1　　1.2 功能要求1　　1.3 基本功能1　　2 系統(tǒng)功能模塊結(jié)構(gòu)圖2　　2.1 系統(tǒng)功能結(jié)構(gòu)框圖2&l

4、t;p>　　2.2 系統(tǒng)主要模塊的功能說(shuō)明2　　3 使用的數(shù)據(jù)結(jié)構(gòu)的描述4　　3.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)4　　3.2 數(shù)據(jù)結(jié)構(gòu)用法說(shuō)明4　　4 函數(shù)的描述5　　4.1主要函數(shù)設(shè)計(jì)5&l

5、t;p>　　4.2 主要函數(shù)流程圖5　　5程序測(cè)試和運(yùn)行的結(jié)果8　　5.1 程序測(cè)試8　　5.2 運(yùn)行結(jié)果9　　6參考文獻(xiàn)11　　附錄（關(guān)鍵部分程序清單）12</

6、p>　　1 題目介紹和功能要求　　1.1 題目介紹　　針對(duì)本班成員以姓名為關(guān)鍵字設(shè)計(jì)一個(gè)Hash表，使得平均查找長(zhǎng)度不超過(guò)R。　　要求：　　自行設(shè)計(jì)至少3中Hash

7、函數(shù)；　　每種Hash函數(shù)采用線性探測(cè)再散列和偽隨機(jī)數(shù)探測(cè)再散列進(jìn)行沖突處理；　　針對(duì)本班成員給出每種Hash函數(shù)的平均查找長(zhǎng)度。　　建立一個(gè)確定的對(duì)應(yīng)關(guān)系f，使每個(gè)關(guān)鍵字和結(jié)構(gòu)中的一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)。在查找時(shí)，只要根據(jù)這個(gè)對(duì)應(yīng)關(guān)系f找到給定值K的像f（K）所建立的表即為哈希表。&l

8、t;p>　　1.2 功能要求　　1.用三種方法創(chuàng)建哈希函數(shù)，分別為除留取余法，隨機(jī)數(shù)法和分割法。　　2.當(dāng)哈希地址產(chǎn)生沖突時(shí)，利用線性探測(cè)再散列和偽隨機(jī)數(shù)探測(cè)再散列進(jìn)行沖突處理得到新的哈希地址，并存入哈希表中。　　3.給出每個(gè)用戶名的查找長(zhǎng)度和該函數(shù)的平均查找長(zhǎng)

9、度，并比較哪種方法最好。　　1.3 基本功能　　CreateHashList()建立Hash函數(shù)，并采用兩種沖突處理方法進(jìn)行操作。　　SearchHash()查找Hash表，將用戶所輸入的信息從Hash表中調(diào)出

10、，并給出查找長(zhǎng)度　　2 系統(tǒng)功能模塊結(jié)構(gòu)圖　　2.1 系統(tǒng)功能結(jié)構(gòu)框圖　　圖2.1 系統(tǒng)功能結(jié)構(gòu)框圖　　2.2 系統(tǒng)主要模塊的功能說(shuō)明　　哈希模塊

11、　CreateHashList()；（adr為哈希地址）　　初始化Hash表，并創(chuàng)建Hash函數(shù)，并將用戶姓名添加至Hash表中。　　除留取余法：adr=(DATALIST[i].k)%M;（將DATALIST[i].k所存的ASCII碼除以M取余所得的哈希地址賦給adr）　　隨機(jī)函數(shù)法: srand(DATAL

12、IST[i].k);　　int adr=rand()%L;(將DATALIST[i].k所存的ASCII碼作為種子傳入至srand函數(shù)中，并用rand函數(shù)產(chǎn)生L以內(nèi)的隨機(jī)值為哈希地址賦給adr)　　分割法: change(DATALIST,A,i);　　int adr=A[1]*10+A[2];( DATALIS

13、T[i].k所存的ASCII碼利用change()函數(shù)分割開(kāi)，并去第二個(gè)數(shù)字和第三個(gè)數(shù)字作為哈希地址賦給adr)　　沖突處理模塊　　srand(姓名ASCII碼);　　d=(d+rand()%L)%M;　　偽隨機(jī)探測(cè)

14、再散列　　d=d+1;　　線性探測(cè)再散列　　查找模塊　　SearchHash();　　查找用戶輸

15、入姓名是否在Hash表中；　　給出該姓名的查找長(zhǎng)度和該Hash函數(shù)的平均查找長(zhǎng)度。　　3 使用的數(shù)據(jù)結(jié)構(gòu)的描述　　3.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)　　建立一個(gè)確定的對(duì)應(yīng)關(guān)系f，使每個(gè)關(guān)鍵字和結(jié)構(gòu)中的一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)。在查找時(shí)，只要根據(jù)這個(gè)對(duì)應(yīng)關(guān)系f找到給定值K的像f（K）

16、為存儲(chǔ)地址的結(jié)構(gòu)體數(shù)組即為哈希表。　　哈希表舉例（平方取中法）：　　A B C ……Z 0 1 2 …… 9　　01 02 0332 60 61 62 71　　表3.1 哈希表</p&

17、gt;　　3.2 數(shù)據(jù)結(jié)構(gòu)用法說(shuō)明　　取關(guān)鍵字平方后的中間幾位為哈希地址。這是一種比較常用的構(gòu)造哈希函數(shù)的方法。通常在選定哈希函數(shù)時(shí)不一定能知道關(guān)鍵字的全部情況，取其中哪幾位也不一定合適，而一個(gè)數(shù)平方后的中間幾位數(shù)和數(shù)的每一位都相關(guān)，由此使隨即分布的關(guān)鍵字得到的哈希地址也是隨即的。取的位數(shù)由表長(zhǎng)決定。如表3.1列出了一些標(biāo)識(shí)符及它們的哈希地址。&l

18、t;p>　　4 函數(shù)的描述　　主要函數(shù)設(shè)計(jì)　　Input ()；　　作用：將用戶姓名換算成ASCII碼。　　CreateHashList()；<

19、/p>　　作用：將用戶名輸入至哈希表中，并用兩種沖突處理方法進(jìn)行沖突處理。　　SearchHash();　　作用：將用戶輸入的用戶名在哈希表中進(jìn)行查找，并給出查找結(jié)果和查找長(zhǎng)度，和該函數(shù)的平均查找長(zhǎng)度。　　Print ()；

20、　　作用：打印出程序的主菜單和界面。　　Change();　　作用: 將用戶姓名的ASCII碼分割為多個(gè)數(shù)字并存入數(shù)組中。　　4.2 主要函數(shù)流程圖　　CreateHashList()；<

21、;p>　　圖4.2.1創(chuàng)建函數(shù)流程圖 　　SearchHash();　　圖4.2.2查找函數(shù)流程圖 　　5程序測(cè)試和運(yùn)行的結(jié)果　　5.1 程序測(cè)試　　程序開(kāi)始菜單：&l

22、t;/b>　　圖5.1.1 一號(hào)菜單圖 　　輸入1或者2；　　圖5.1.2 二號(hào)菜單圖　　輸入1；　　圖5.1.3查找圖</

23、b>　　輸入2；　　圖5.1.4平均查找圖　　5.2 運(yùn)行結(jié)果　　給出3組數(shù)據(jù)，每組數(shù)據(jù)29個(gè)用戶名，分別用三種哈希函數(shù)和兩種沖突處理方法進(jìn)行操作，結(jié)果如圖：<

24、p>　　1.數(shù)據(jù)1：　　除留取余法：　　線性探測(cè)再散列：　　偽隨機(jī)數(shù)探測(cè)再散列：　　隨機(jī)數(shù)法：

25、;　　線性探測(cè)再散列：　　偽隨機(jī)數(shù)探測(cè)再散列：　　分割法：　　線性探測(cè)再散列：　　偽隨機(jī)數(shù)探測(cè)再散列：<p

26、>　　2.數(shù)據(jù)2：　　除留取余法：　　線性探測(cè)再散列：　　偽隨機(jī)數(shù)探測(cè)再散列：　　隨機(jī)數(shù)法：

27、　　線性探測(cè)再散列：　　偽隨機(jī)數(shù)探測(cè)再散列：　　分割法：　　線性探測(cè)再散列：　　偽隨機(jī)數(shù)探測(cè)再散列：<p&

28、gt;　　3.數(shù)據(jù)3：　　除留取余法：　　線性探測(cè)再散列：　　偽隨機(jī)數(shù)探測(cè)再散列：　　隨機(jī)數(shù)法：

29、　　線性探測(cè)再散列：　　偽隨機(jī)數(shù)探測(cè)再散列：　　分割法：　　線性探測(cè)再散列：　　偽隨機(jī)數(shù)探測(cè)再散列：<p&g

30、t;　　結(jié)論：經(jīng)比較可知，分割法所建立的哈希函數(shù)平均查找長(zhǎng)度最短。　　6參考文獻(xiàn)　　[1] 高富平，張楚 . 電子商務(wù)法［M］. 北京：北京大學(xué)出版社，2002　　[2] Huang S C，Huang Y M，Shieh S M．Vibration and stabilit

31、y of a rotating shaft containing a transerse crack［J］, J Sound and Vibration，1993，162（3）：387－401．　　[3]譚浩強(qiáng)著. C程序設(shè)計(jì)（第三版）. 北京: 清華大學(xué)出版社,2005　　[4]數(shù)據(jù)結(jié)構(gòu): C語(yǔ)言版 /嚴(yán)蔚敏,吳偉明編著.—北京:清華大學(xué)出版社,20

32、07　　附錄（關(guān)鍵部分程序清單）　　#include<stdio.h>　　#include<stdlib.h>　　#include<string.h>　　#define L 50

33、 //哈希表的長(zhǎng)度 　　#define RAND_MAX 10 //隨機(jī)數(shù)范圍　　#define M 47 //除留取余數(shù)值　　#define NAME_NO 29 //人名的個(gè)數(shù)　　#define SUCCESS 1</p&g

34、t;　　#define UNSUCESS 0　　#define ElemType char　　typedef structHash//哈希表　　{　　ElemType *data;

35、　　int s;//查找長(zhǎng)度　　int k;//當(dāng)前姓名的ASCII碼　　}Hash;Hash hlist[L];　　typedef structDATE//班級(jí)成員　　{ char *data;//姓名

36、;　　int k;//姓名ASCII碼　　}DATA;DATE DATALIST[NAME_NO];　　void input() //姓名（結(jié)構(gòu)體數(shù)組）初始化 　　{ char *m;　　int r,s0,i;</

37、p>　　DATALIST[0].data="hudi";　　DATALIST[1].data="lijing";　　DATALIST[2].data="peiting";　　DATALIST[3].data="yin

38、hang";　　DATALIST[4].data="liulu";　　DATALIST[5].data="lishengnan";　　DATALIST[6].data="cuililong";　　DAT

39、ALIST[7].data="songchongyuan";　　DATALIST[8].data="xiejinhua";　　DATALIST[9].data="mashuangmin";　　DATALIST[10].data="wangjin

40、g";　　DATALIST[11].data="qiyueyu";　　DATALIST[12].data="gaozhiwei";　　DATALIST[13].data="fuzedong";　　DAT

41、ALIST[14].data="shidailong";　　DATALIST[15].data="sujun";　　DATALIST[16].data="zhangxinglei";　　DATALIST[17].data="liuyang&qu

42、ot;;　　DATALIST[18].data="liushuxin";　　DATALIST[19].data="fengkunkun";　　DATALIST[20].data="suzheng";　　DATAL

43、IST[21].data="sunjianwei";　　DATALIST[22].data="mengbaiyu";　　DATALIST[23].data="yushaolong";　　DATALIST[24].data="lishaolun&

44、quot;;　　DATALIST[25].data="zhangkuo";　　DATALIST[26].data="wangdanran";　　DATALIST[27].data="lizhanying";　　D

45、ATALIST[28].data="yangjun"; 　　for(i=0;i<NAME_NO;i++)　　{ 　　s0=0;　　m=DATALIST[i].data;

46、　　for(r=0;*(m+r)!='\0';r++) 　　s0=*(m+r)+s0;　　DATALIST[i].k=s0;　　} 　　}

47、　　int CreateHashList() //建立哈希表 　　{ 　　int i,num,sum;　　printf("請(qǐng)選擇沖突處理方法\n");　　printf(

48、"1.線性探測(cè)再散列\(zhòng)n");　　printf("2.偽隨機(jī)數(shù)探測(cè)再散列\(zhòng)n");　　scanf("%d",&num);　　switch(num)　　{</p&

49、gt;　　case 1:{　　for(i=0;i<L;i++)//哈希表的初始化　　{ 　　hlist[i].data="";　　hlist[i

50、].k=0;　　hlist[i].s=0;　　}　　for(i=0;i<L;i++)　　{ 　　sum=0;

51、;　　int adr=(DATALIST[i].k)%M; //哈希函數(shù)（除留取余）　　if(i==NAME_NO)　　break;　　int d=adr;　　if(hlist[adr].s

52、==0) 　　{ 　　hlist[adr].k=DATALIST[i].k;　　hlist[adr].data=DATALIST[i].data;　　hlist[adr].s=1;//此處已有數(shù)據(jù)

53、　　}　　else 　　{ 　　do　　{ </p&

54、gt;　　d=d+1; //線性探測(cè)再散列法處理沖突 　　sum=sum+1; //查找次數(shù)加1 　　}while (hlist[d].s!=0);　　hlist[d].k=DATALIST[i].k;<

55、;p>　　hlist[d].data=DATALIST[i].data;　　hlist[d].s=sum+1;　　}　　}　　return 1;<

56、/p>　　}break;　　case 2:{　　for(i=0;i<L;i++)//哈希表的初始化　　{ 　　hlist

57、[i].data="";　　hlist[i].k=0;　　hlist[i].s=0;　　}　　for(i=0;i<L;i++)　　{ </

58、b>　　sum=0;　　int adr=(DATALIST[i].k)%M; //哈希函數(shù)　　if(i==NAME_NO)　　break;　　in

59、t d=adr;　　if(hlist[adr].s==0) 　　{ 　　hlist[adr].k=DATALIST[i].k;　　hlist[adr].data=DATALIST[i].data;<

60、;p>　　hlist[adr].s=1;//此處已有數(shù)據(jù)　　}　　else 　　{ 　　do</p

61、>　　{ 　　srand(DATALIST[i].k);　　d=(d+rand()%L)%M; //偽隨機(jī)數(shù)探測(cè)再散列法處理沖突 　　sum=sum+1; //查找次數(shù)加1 </p&g

62、t;　　}while (hlist[d].s!=0);　　hlist[d].k=DATALIST[i].k;　　hlist[d].data=DATALIST[i].data;　　hlist[d].s=sum+1;　　}</b&

63、gt;　　}　　return 2;　　}break;　　}

64、　}　　int SearchHash1(char *name,Hash hlist[],int *k) //k為查找次數(shù),線性探測(cè)查找　　{　　int s0=0,r,n=1;　　for(r=0;*(name+r)!

65、='\0';r++) 　　s0=*(name+r)+s0;　　int adr=s0%M;　　if(stricmp(hlist[adr].data,name)==0)　　{　　*

66、k=hlist[adr].s;　　return SUCCESS;　　}　　else　　{　　whi

67、le(1)　　{　　if(n>L||strlen(hlist[adr].data)==0)　　return UNSUCESS;　　adr=adr+1;

68、;　　n++;　　if(stricmp(hlist[adr].data,name)==0)　　{　　*k=hlist[adr].s;　　return SUCCESS;<

69、;b>　　}　　}　　}　　}　　int SearchHash2(char *name,Hash hlist[],int *k) /

70、/k為查找次數(shù),偽隨機(jī)數(shù)探測(cè)查找　　{　　int s0=0,r,n=1; //n為初始查找長(zhǎng)度　　for(r=0;*(name+r)!='\0';r++) 　　s0=*(name+r)+s0;</p&g

71、t;　　int adr=s0%M;　　if(stricmp(hlist[adr].data,name)==0)　　{　　*k=hlist[adr].s;　　return SUCCESS;&

72、lt;p>　　}　　else　　{　　while(1)　　{</p&g

73、t;　　if(n>L||strlen(hlist[adr].data)==0)　　return UNSUCESS;　　srand(s0);　　adr=(adr+rand()%L)%M;　　n++;<

74、;/p>　　if(stricmp(hlist[adr].data,name)==0)　　{　　*k=hlist[adr].s;　　return SUCCESS;　　}&

75、lt;/p>　　}　　}　　}　　void print()　　{&l

76、t;p>　　printf("%*******************************************\n");　　printf("****\n");　　printf("****\n");　　printf(&quo

77、t;**哈希表**\n");　　printf("****\n");　　printf("****\n");　　printf("****\n");　　printf(&

78、quot;******************************************\n");　　}　　void main()　　{　　char name[20];int re

79、sult=0,m,n;int k;int i=1; //m判斷選擇探測(cè)方法　　float c=0,d;　　while(1)　　{　　lp:print();

80、;　　printf("請(qǐng)選擇：\n");　　input();　　m=CreateHashList();　　printf("請(qǐng)選擇：\n");　　printf("1.查找姓名\n&quo

81、t;);　　printf("2.顯示該哈希函數(shù)的平均查找長(zhǎng)度\n");　　printf("3.退到上級(jí)\n");　　scanf("%d",&n);　　switch(n)

82、;　　{　　case 1:{　　if(m==1)　　{　　printf(&qu

83、ot;請(qǐng)輸入姓名\n");　　scanf("%s",name);　　result=SearchHash1(name,hlist,&k);　　if(result==1)　　{

84、　　printf("查找成功\n");　　printf("查找長(zhǎng)度為%d\n",k);　　}　　else　　printf("查找

85、失敗\n");　　}　　if(m==2)　　{　　printf("請(qǐng)輸入姓名\n");

86、　　scanf("%s",name);　　result=SearchHash2(name,hlist,&k);　　if(result==1)　　{　　printf("查找成功\n");&

87、lt;/p>　　printf("查找長(zhǎng)度為%d\n",k);　　}　　else　　printf("查找失敗\n");<b&

88、gt;　　}　　}break;　　case 2:{　　d=0;　　for(i=0;i<L;i++)<p

89、>　　d+=hlist[i].s;　　c=d/NAME_NO;　　printf("平均查找長(zhǎng)度為%f\n",c);　　}break;　　case 3:{

90、;　　system("cls");　　goto lp;　　}break;　　}　　}</b&

眾賞文庫(kù)> 全部分類> 畢業(yè)設(shè)計(jì)

溫馨提示

1. 本站所有資源如無(wú)特殊說(shuō)明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽，若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間，僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請(qǐng)與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-基于hash表的班級(jí)成員管理

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-基于hash表的班級(jí)成員管理

文檔簡(jiǎn)介

溫馨提示

最新文檔

評(píng)論

免費(fèi)下載