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

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

2、able();5. 姓名查找：void FindName();6. 主函數(shù)：void main();四、詳細(xì)設(shè)計1. 姓名表的初始化void InitNameTable()NameTable0.py="louyuhong"NameTable1.py="shenyinghong”;NameTable2.py="wangqi”;NameTable3.py="zhuxiaotong”;NameTable4.py="zhataotao”;NameTable5.py="chenbinjie”;NameTable6.py="c

3、henchaoqun”;NameTable7.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="huanqingsong”;

4、NameTable16.py="jianghe”;NameTable17.py="jinleicheng”;NameTable18.py="libiao”;NameTable19.py="liqi”;NameTable20.py="lirenhua”;NameTable21.py="liukai”;NameTable22.py="louhanglin”;NameTable23.py="luchaoming”;NameTable24.py="luqiuwei”;NameTable25.py="pa

5、nhaijian”;NameTable26.py="shuxiang”;NameTable27.py="suxiaolei”;NameTable28.py="sunyubo”;NameTable29.py="wangwei"for (i=0;i<NAME_LEN;i+) /得的整數(shù)做為哈希表的關(guān)鍵字(int s=0;char *p=NameTablei.py;for (j=0;*(p+j)!='0'j+)s+=toascii(*(p+j);NameTablei.m=s;2. 建立哈希表void CreateHashTabl

6、e()(for(i=0;i<HASH_LEN;i+)(HashTablei.py="0”;HashTablei.m =0;HashTablei.si=0;for(i=0;i<NAME_LEN;i+)(int sum=1,j=0;int adr=(NameTablei.m)%P; /將字符串的各個字符所對應(yīng)的ASCII碼相加，所除留余數(shù)法 H(key)=key MOD p,p<=m如果不沖突，將姓名表賦值給哈希表if(HashTableadr.si=0) /HashTableadr.m =NameTablei.m;HashTableadr.py=NameTablei.

7、py;HashTableadr.si=1;else/如果沖突(while(HashTableadr.si!=0)偽隨機探測再散列法處查找次數(shù)加1將姓名表復(fù)制給哈希表(adr=(adr+dj+)%HASH_LEN; /理沖突sum=sum+1;/HashTableadr.m =NameTablei.m; /對應(yīng)的位置上HashTableadr.py=NameTablei.py;HashTableadr.si=sum;3. 顯示姓名表與哈希表void DisplayNameTable()(printf("n 地址 tt 姓名 tt 關(guān)鍵字 n");for (i=0;i<N

8、AME_LEN;i+)printf("%2d %18stt %d n”,i,NameTablei.py,NameTablei.m);void DisplayHashTable()float asl=0.0;printf("nn地址tt 姓名tt 關(guān)鍵字t搜索長度n"); / 顯示的格式for (i=0;i<HASH_LEN;i+)printf("%2d %18s tt %dtt %dn”,i,HashTablei.py,HashTablei.m,HashTablei.si);asl+=HashTablei.si;asl/=NAME_LEN;/求得

9、ASLprintf("nn平均查找長度：ASL(%d)=%f n”,NAME_LEN,asl);4. 姓名查找void FindName()char name20=0;int s=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(HashTableadr.m=s&&!strcmp(HashTableadr.py,name)

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

11、leadr.py,name)printf("n姓名:%s關(guān)鍵字:%d查找長度為:%dn",HashTableadr.py,s,sum);break;i村選擇h巾，-hlxw d:哉的文檔'C-FreeVTemp 5R命名 1. exe12-34567890121 1 tI12 3 4一表表 霉 斡示昇找出 T顯顯查退五、測試結(jié)果姓名關(guān)鍵字lo usiuhQ n 91002sheninglioiiig1297gngqi647huxiaotoog121&zhataotao971chenbinjie1039chenchaoquo1165chenchengi931c

12、henJie726chenwe id«936shanj ianfeng12G0fangixin973houfeng748d：成的文檔C-FreeT emp5|c 命名 1. exer?chenue ida936keshanj ianf eng1260kifangyixin973h.2houfeng748h.3hujiaming956h.4huangj iaju1062h.5huanqingsong1298卜6jianghe726k?jin leicheng1152kslibiao624k?liqi431holirenhua856hiliukai639B2louhancflin1073

13、S3luchaoming1063B4luqiuwei885hspanhaij ian1043shuxiang871E7suxiaolei979B8sunsFLibo789E9wangwei754e d:我的文檔'OFreeYTenipr未命名 ILesce地址0123456789011213456 ?89 012姓缶wangweighenbinjie jlangheliqi panhaij iaio lirenhuchhiiangf jiaju luchaoiningi louyuhong huj iamingrchenjiesunyubo關(guān)鍵字075410394311043lets1

14、0631002搜索長度001001201110&11000012六、實驗環(huán)境C-Free七、源程序代碼#include<stdio.h>char *py;/名字的拼音int m;/拼音所對應(yīng)的NAME;NAME NameTableHASH_LEN;/全局定義姓名表typedef struct /哈希表char *py; /名字的拼音int m; /拼音所對應(yīng)的ASCII總和int si; /查找長度HASH;HASH HashTableHASH_LEN;/全局定義哈希表int d30,i,j; /全局定義隨機數(shù)，循環(huán)用的i、j#include<time.h>/t

15、ime用到的頭文件#include<stdlib.h>/隨機數(shù)用到的頭文件#include<ctype.h>/toascii()用到的頭文件#include<string.h>/查找姓名時比較用的頭文件#define HASH_LEN 50/哈希表的長度#define P 47/小于哈布表長度的#define NAME_LEN 30/姓名表的長度typedef struct /姓名表Pvoid InitNameTable() /姓名表的初始化NameTable0.py="louyuhong”;NameTable1.py="shenying

16、hong”;NameTable2.py="wangqi”;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

17、.py="fangyixin”;NameTable12.py="houfeng”;NameTable13.py="hujiaming”;NameTable14.py="huangjiaju”;NameTable15.py="huanqingsong”;NameTable16.py="jianghe”;NameTable17.py="jinleicheng”;NameTable18.py="libiao”;NameTable19.py="liqi”;NameTable20.py="lirenhua

18、”;NameTable21.py="liukai”;NameTable22.py="louhanglin”;NameTable23.py="luchaoming”;NameTable24.py="luqiuwei”;NameTable25.py="panhaijian”;NameTable26.py="shuxiang”;NameTable27.py="suxiaolei”;NameTable28.py="sunyubo”;NameTable29.py="wangwei”;for (i=0;i<NA

19、ME_LEN;i+) /將字符串的各個字符所對應(yīng)的ASCII碼相加，所得的整數(shù)做為哈希表的關(guān)鍵字int s=0;char *p=NameTablei.py;for (j=0;*(p+j)!='0'j+)s+=toascii(*(p+j);NameTablei.m=s;void CreateHashTable() /建立哈希表for(i=0;i<HASH_LEN;i+)HashTablei.py="0”;HashTablei.m =0;HashTablei.si=0;for(i=0;i<NAME_LEN;i+)int sum=1,j=0;int adr=(N

20、ameTablei.m)%P; /除留余數(shù)法 H(key)=key MOD p,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; /偽隨機探測再散列法處理沖突sum=sum+1;/查找次數(shù)加1HashTableadr.m =NameTablei.m; /將姓名表復(fù)制給哈希表 對應(yīng)的位置上

21、HashTableadr.py=NameTablei.py;HashTableadr.si=sum;void DisplayNameTable() / 顯示姓名表(printf("n 地址 tt 姓名 tt 關(guān)鍵字 n");for (i=0;i<NAME_LEN;i+)printf("%2d %18s tt %d n”,i,NameTablei.py,NameTablei.m);void DisplayHashTable()/ 顯示哈希表(float asl=0.0;printf("nn地址tt 姓名tt 關(guān)鍵字t搜索長度n"); /顯示

22、的格式for (i=0;i<HASH_LEN;i+)(printf("%2d %18s tt %dtt %dn”,i,HashTablei.py,HashTablei.m,HashTablei.si);asl+=HashTablei.si;asl/=NAME_LEN;/求得 ASLprintf("nn平均查找長度：ASL(%d)=%f n”,NAME_LEN,asl);void FindName() / 查找(char name20=0;int s=0,sum=1,adr;printf("n請輸入想要查找的姓名的拼音：，scanf("%s”,nam

23、e);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);else if (HashTableadr.m=0)printf("沒有想要查找的人!n");else (while(1)(adr=(adr+dj+)%HASH_LEN; /偽隨機探測再散列法處理沖突sum=sum+1;/查找次數(shù)加1if(HashTableadr.m=0)(printf(沒有想要查找的人!n");break;if(HashTabl