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

1、山東科技大學(xué)學(xué)生課程設(shè)計(jì)山東科技大學(xué)學(xué)生課程設(shè)計(jì)實(shí)習(xí)實(shí)習(xí)6、哈希表設(shè)計(jì)、哈希表設(shè)計(jì)一、一、需求分析需求分析1.問題描述問題描述針對(duì)某個(gè)集體（比如你所在的班級(jí)）中的“人名”設(shè)計(jì)一個(gè)哈希表，使得平均查找長(zhǎng)度均不超過R，完成相應(yīng)的建表和查表順序。2.基本要求基本要求假設(shè)人名為中國(guó)人姓名的漢語拼音形式。待填入哈希表的人名共有30個(gè)，取平均查找長(zhǎng)度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用偽隨機(jī)探測(cè)再散列法處理沖突。3.測(cè)試數(shù)據(jù)測(cè)試數(shù)據(jù)取讀者周圍較

2、熟悉的30個(gè)人的姓名。4.實(shí)現(xiàn)提示實(shí)現(xiàn)提示如果隨機(jī)數(shù)自行構(gòu)造，則應(yīng)首先調(diào)整好隨機(jī)函數(shù)，使其分布均勻。人名的長(zhǎng)度均不超過19個(gè)字符（最長(zhǎng)的人名如：莊雙雙（ZhuangShuangshuang））。字符的取碼方法可直接利用C語言中的toii函數(shù)，并可先對(duì)過長(zhǎng)的人名先作折疊處理。二、概要設(shè)計(jì)二、概要設(shè)計(jì)ADTHash數(shù)據(jù)對(duì)象D：D是具有相同特征的數(shù)據(jù)元素的集合。各數(shù)據(jù)元素均含有類型相同，可唯一標(biāo)識(shí)數(shù)據(jù)元素的關(guān)鍵字。數(shù)據(jù)關(guān)系R：數(shù)據(jù)元素同屬一個(gè)

3、集合。InitNameTable()操作結(jié)果：初始化姓名表。CreateHashTable()操作結(jié)果：建立哈希表。DisplayNameTable()操作結(jié)果：顯示姓名表。DisplayHashTable()操作結(jié)果：顯示哈希表。FindName()操作結(jié)果：查找姓名。ADTHash三、詳細(xì)設(shè)計(jì)（源代碼）三、詳細(xì)設(shè)計(jì)（源代碼）（使用C語言）#include#includetime用到的頭文件#include隨機(jī)數(shù)用到的頭文件#incl

4、udetoii()用到的頭文件#include查找姓名時(shí)比較用的頭文件#defineHASH_LEN50哈希表的長(zhǎng)度#defineP47小于哈希表長(zhǎng)度的P#defineNAME_LEN30姓名表的長(zhǎng)度typedefstruct姓名表py名字的拼音intm拼音所對(duì)應(yīng)的NAMENAMENameTable[HASH_LEN]全局定義姓名表typedefstruct哈希表py名字的拼音山東科技大學(xué)學(xué)生課程設(shè)計(jì)山東科技大學(xué)學(xué)生課程設(shè)計(jì)HashTa

5、ble[i].py=“0“HashTable[i].m=0HashTable[i].si=0f(i=0iNAME_LENi)intsum=1j=0intadr=(NameTable[i].m)%P除留余數(shù)法H(key)=keyMODpp=mif(HashTable[adr].si==0)如果不沖突，將姓名表賦值給哈希表HashTable[adr].m=NameTable[i].mHashTable[adr].py=NameTable[i

6、].pyHashTable[adr].si=1else如果沖突while(HashTable[adr].si!=0)adr=(adrd[j])%HASH_LEN偽隨機(jī)探測(cè)再散列法處理沖突sum=sum1查找次數(shù)加1HashTable[adr].m=NameTable[i].m將姓名表復(fù)制給哈希表對(duì)應(yīng)的位置上HashTable[adr].py=NameTable[i].pyHashTable[adr].si=sumvoidDisplayN

7、ameTable()顯示姓名表printf(“n地址tt姓名tt關(guān)鍵字n“)f(i=0iNAME_LENi)printf(“%2d%18stt%dn“iNameTable[i].pyNameTable[i].m)voidDisplayHashTable()顯示哈希表floatasl=0.0printf(“nn地址tt姓名tt關(guān)鍵字t搜索長(zhǎng)度n“)顯示的格式f(i=0iHASH_LENi)printf(“%2d%18stt%dtt%dn“