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

1、1、 問題描述針對某個集體(比如你所在的班級)中的“人名”設(shè)計一個哈希表，使得平均查找長度均不超過R,完成相應(yīng)的建表和查表順序。2、 基本要求假設(shè)人名為中國人姓名的漢語拼音形式。待填入哈希表的人名共有30個，取平均查找長度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用偽隨機(jī)探測再散列法處理沖突。3、 概要設(shè)計1 .構(gòu)造結(jié)構(gòu)體：typedefstruct。；2 .姓名表的初始化：voidInitNameTable();3 .建立哈希表：voidCreateHashTable();4 .顯示姓名表：voidDisplayNameTable();5 .姓名查找：voidFindName();6 .主函數(shù)：

2、voidmain()；4、 詳細(xì)設(shè)計1 .姓名表的初始化voidInitNameTable()(NameTable0.py="louyuhong"NameTable1.py="shenyinghong"NameTable2.py="wangqi"NameTable3.py="zhuxiaotong"NameTable4.py="zhataotao"NameTable5.py="chenbinjie"NameTable6.py="chenchaoqun"Na

3、meTable7.py="chencheng"NameTable8.py="chenjie"NameTable9.py="chenweida"NameTable10.py="shanjianfeng"NameTable11.py="fangyixin"NameTable12.py="houfeng"NameTable13.py="hujiaming"NameTable14.py="huangjiaju"NameTable15.py=&q

4、uot;huanqingsong”;NameTable16.py="jianghe"NameTable17.py="jinleicheng"NameTable18.py="libiao"NameTable19.py="liqi"NameTable20.py="lirenhua"NameTable21.py="liukai"NameTable22.py="louhanglin"NameTable23.py="luchaoming"Name

5、Table24.py="luqiuwei"NameTable25.py="panhaijian"NameTable26.py="shuxiang"NameTable27.py="suxiaolei"NameTable28.py="sunyubo"NameTable29.py="wangwei"for(i=0;i<NAME_LEN;i+)將字符串的各個字符所對應(yīng)的ASCII碼相加，所得的整數(shù)做為哈希表的關(guān)桎字ints=0;char*p=NameTablei.py;for(

6、j=0;*(p+j)!='0'j+)s+=toascii(*(p+j);NameTablei.m=s;2 .建立哈希表voidCreateHashTable()for(i=0;i<HASH_LEN;i+)HashTablei.py="0"HashTablei.m=0;HashTablei.si=0;for(i=0;i<NAME_LEN;i+)intsum=1,j=0;intadr=(NameTablei.m)%P;/除留余數(shù)法H(key)=keyMODp,p<=mif(HashTableadr.si=0)/如果不沖突，將姓名表賦值給哈希表H

7、ashTableadr.m=NameTablei.m;HashTableadr.py=NameTablei.py;HashTableadr.si=1;)else/如果沖突(while(HashTableadr.si!=0)(adr=(adr+dj+)%HASH_LEN;/偽隨機(jī)探測再散列法處理沖突sum=sum+1;/查找次數(shù)加1)HashTableadr.m=NameTablei.m;/將姓名表復(fù)制給哈希表對應(yīng)的位置上HashTableadr.py=NameTablei.py;HashTableadr.si=sum;)3 .顯示姓名表與哈希表voidDisplayNameTable()(pr

8、intf("n地址tt姓名tt關(guān)鍵字n");for(i=0;i<NAME_LEN;i+)printf("%2d%18stt%dn",i,NameTablei.py,NameTablei.m);voidDisplayHashTable()(floatasl=0.0;printf("nn地址tt姓名tt關(guān)鍵字t搜索長度n");顯示的格式for(i=0;i<HASH_LEN;i+)(printf("%2d%18stt%dtt%dn",i,HashTablei.py,HashTablei.m,HashTable

9、i.si);asl+=HashTablei.si;)asl/=NAME_LEN;/求得ASLprintf("nn平均查找長度：ASL(%d)=%fn",NAME_LEN,asl);)4 .姓名查找voidFindName()(charname20=0;ints=0,sum=1,adr;printf("n請輸入想要查找的姓名的拼音：")；scanf("%s",name);for(j=0;j<20;j+)/求出姓名的拼音所對應(yīng)的ASCII作為關(guān)鍵字s+=toascii(namej);adr=s%P;/除留余數(shù)j=0;if(HashT

10、ableadr.m=s&&!strcmp(HashTableadr.py,name)/分3種情況進(jìn)行判斷，并輸出超找結(jié)果printf("n姓名:%s關(guān)鍵字:%d查找長度為：1n",HashTableadr.py,s);elseif(HashTableadr.m=0)printf("沒有想要查找的人!n");elsewhile(1)adr=(adr+dj+)%HASH_LEN;/偽隨機(jī)探測再散列法處理沖突sum=sum+1;/查找次數(shù)加1if(HashTableadr.m=0)printf("沒有想要查找的人!n");b

11、reak;if(HashTableadr.m=s&&!strcmp(HashTableadr.py,name)printf("n姓名:%s關(guān)鍵字:d查找長度為：dn",HashTableadr.py,s,sum);break;5、 測試結(jié)果c:我的文君i.C-FreeYTenip法命名l.ejce一表表豺虻除一得示示找出一號顯顯看一退一-1234請選擇:工地址姓名關(guān)鍵字Qlouyuhongi10021shenyinghong12972叫angqiE，73ghuMiaoton9121G4zhataotao?715chenbinjie10396chenchaoq

12、uiinii11657chenchengi9318chenjiie7269chenwe93610shanjianfeng12&0E1fangfyixio?7312houfeng748I：,'.d：懂的文若C-FeeVTemp侏命名1.exer?chenueida93610shanjianfeng126011fangyixin97312houfeng74813hujiaming95614huangjiaju106215huanqingsong129816jianghe72617jinleicheng115218libiao62419liqi431Q0lii'enhua85

13、6Elliukai639Q2louhancflin1073E3luchaoming1063Q4luqiuwei885panhaijian1043shuxiang871G7suxiaolei979Q8sunsFLibo789G9wangwei7541063H856104343172h1039754關(guān)鍵字wangweichenhinjiejlanghechenjiesunyuboc：4：我的文若工干已用161叩球命名1.田（©87國姓名liqipanhaiJiaiolirenhuaihuangjiajuluchaomingilouyulionghujianinor0援察長度BQ10012

14、111002211000012六、實(shí)驗(yàn)環(huán)境C-Free七、源程序代碼/time用到的頭文件/隨機(jī)數(shù)用到的頭文件/toascii()用到的頭文件#include<stdio.h>#include<time.h>#include<stdlib.h>查找姓名時比較用的頭文件/哈希表的長度小于哈希表長度的P/姓名表的長度#include<ctype.h>#include<string.h>/# defineHASH_LEN50# defineP47/# defineNAME_LEN30typedefstruct/姓名表char*py;/名字的

15、拼音intm;/拼音所對應(yīng)的NAME;NAMENameTableHASH_LEN;/全局定義姓名表typedefstruct/哈希表char*py;/名字的拼音intm;/拼音所對應(yīng)的ASCII總和intsi;/查找長度HASH;HASHHashTableHASH_LEN;/全局定義哈希表intd30,i,j;/全局定義隨機(jī)數(shù)，循環(huán)用的i、jvoidInitNameTable()/姓名表的初始化NameTable0.py="louyuhong"NameTable1.py="shenyinghong"NameTable2.py="wangqi&q

16、uot;NameTable3.py="zhuxiaotong”;NameTable4.py="zhataotao”;NameTable5.py="chenbinjie”;NameTable6.py="chenchaoqun”;NameTable7.py="chencheng"NameTable8.py="chenjie"NameTable9.py="chenweida"NameTable10.py="shanjianfeng"NameTable11.py="fang

17、yixin"NameTable12.py="houfeng"NameTable13.py="hujiaming"NameTable14.py="huangjiaju"NameTable15.py="huanqingsong"NameTable16.py="jianghe"NameTable17.py="jinleicheng"NameTable18.py="libiao"NameTable19.py="liqi"NameTab

18、le20.py="lirenhua"NameTable21.py="liukai"NameTable22.py="louhanglin"NameTable23.py="luchaoming"NameTable24.py="luqiuwei"NameTable25.py="panhaijian”;NameTable26.py="shuxiang"NameTable27.py="suxiaolei"NameTable28.py="sunyu

19、bo"NameTable29.py="wangwei"for(i=0;i<NAME_LEN;i+)/將字符串的各個字符所對應(yīng)的ASCII碼相加，所得的整數(shù)做為哈希表的關(guān)鍵字ints=0;char*p=NameTablei.py;for(j=0;*(p+j)!='0'j+)s+=toascii(*(p+j);NameTablei.m=s;voidCreateHashTable()/建立哈希表for(i=0;i<HASH_LEN;i+)HashTablei.py="0"HashTablei.m=0;HashTablei.

20、si=0;for(i=0;i<NAME_LEN;i+)intsum=1,j=0;intadr=(NameTablei.m)%P;/除留余數(shù)法H(key)=keyMODp,p<=mif(HashTableadr.si=0)/如果不沖突，將姓名表賦值給哈希表HashTableadr.m=NameTablei.m;HashTableadr.py=NameTablei.py;HashTableadr.si=1;else/如果沖突while(HashTableadr.si!=0)adr=(adr+dj+)%HASH_LEN;/偽隨機(jī)探測再散列法處理沖突sum=sum+1;/查找次數(shù)加1將姓名

21、表復(fù)制給哈希表對應(yīng)的位置上HashTableadr.m=NameTablei.m;/HashTableadr.py=NameTablei.py;HashTableadr.si=sum;voidDisplayNameTable()/顯示姓名表(printf("n地址tt姓名tt關(guān)鍵字n");for(i=0;i<NAME_LEN;i+)printf("%2d%18stt%dn",i,NameTablei.py,NameTablei.m);)voidDisplayHashTable()/顯示哈希表(floatasl=0.0;printf("nn

22、地址tt姓名tt關(guān)鍵字t搜索長度n");顯示的格式for(i=0;i<HASH_LEN;i+)(printf("%2d%18stt%dtt%dn",i,HashTablei.py,HashTablei.m,HashTablei.si);asl+=HashTablei.si;)asl/=NAME_LEN;/求得ASLprintf("nn平均查找長度：ASL(%d)=%fn",NAME_LEN,asl);)voidFindName()/查找charname20=0;ints=0,sum=1,adr;printf("n請輸入想要查找的

23、姓名的拼音：")；scanf("%s",name);for(j=0;j<20;j+)/求出姓名的拼音所對應(yīng)的ASCII作為關(guān)鍵字s+=toascii(namej);adr=s%P;/除留余數(shù)法j=0;if(HashTableadr.m=s&&!strcmp(HashTableadr.py,name)/分3種情況進(jìn)行判斷，并輸出超找結(jié)果printf("n姓名:s關(guān)鍵字:d查找長度為：1n",HashTableadr.py,s);elseif(HashTableadr.m=0)printf("沒有想要查找的人!n");elsewhile(1)adr=(adr+dj+)%HASH_LEN;/偽隨機(jī)探測再散列法處理沖突sum=sum+1;/查找次數(shù)加1if(HashTableadr.m=0)printf("沒有想要查找的人