哈希表設計-數(shù)據(jù)結構課程設計

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

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

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

4、udetoii()用到的頭文件#include查找姓名時比較用的頭文件#defineHASH_LEN50哈希表的長度#defineP47小于哈希表長度的P#defineNAME_LEN30姓名表的長度typedefstruct姓名表py名字的拼音intm拼音所對應的NAMENAMENameTable[HASH_LEN]全局定義姓名表typedefstruct哈希表py名字的拼音山東科技大學學生課程設計山東科技大學學生課程設計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偽隨機探測再散列法處理沖突sum=sum1查找次數(shù)加1HashTable[adr].m=NameTable[i].m將姓名表復制給哈希表對應的位置上HashTable[adr].py=NameTable[i].pyHashTable[adr].si=sumvoidDisplayN

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