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

實驗六：存儲管理、查找和排序題目：哈希表設(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 DisplayNameTable()；5. 姓名查找：void FindName()；6. 主函數(shù)：void main()； 四、 詳細設(shè)計1. 姓名表的初始化void InitNameTable() NameTable0.py=louyuhong; NameTable1.py=shenyinghong; 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.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; 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;iNAME_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; 2. 建立哈希表 void CreateHashTable() for(i=0;iHASH_LEN;i+) HashTablei.py=0; HashTablei.m =0; HashTablei.si=0; for(i=0;iNAME_LEN;i+) int sum=1,j=0; int adr=(NameTablei.m)%P; /除留余數(shù)法 H(key)=key MOD p,p=m if(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ù)加1 HashTableadr.m =NameTablei.m; /將姓名表復(fù)制給哈希表對應(yīng)的位置上 HashTableadr.py=NameTablei.py; HashTableadr.si=sum; 3. 顯示姓名表與哈希表 void DisplayNameTable() printf(n地址 tt 姓名 tt 關(guān)鍵字n); for (i=0;iNAME_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); /顯示的格式 for (i=0;iHASH_LEN;i+) printf(%2d %18s tt %d tt %dn,i,HashTablei.py,HashTablei.m,HashTablei.si); asl+=HashTablei.si; asl/=NAME_LEN; /求得ASL printf(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;j20;j+) /求出姓名的拼音所對應(yīng)的ASCII作為關(guān)鍵字 s+=toascii(namej); adr=s%P; /除留余數(shù)法 j=0; if(HashTableadr.m=s&!strcmp(HashTableadr.py,name) /分3種情況進行判斷，并輸出超找結(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ù)加1 if(HashTableadr.m=0) printf(沒有想要查找的人!n); break; if(HashTableadr.m=s&!strcmp(HashTableadr.py,name) printf(n姓名:%s 關(guān)鍵字:%d 查找長度為:%dn,HashTableadr.py,s,sum); break; 五、 測試結(jié)果六、 實驗環(huán)境C-Free七、 源程序代碼 #include#include /time用到的頭文件#include /隨機數(shù)用到的頭文件#include /toascii()用到的頭文件#include /查找姓名時比較用的頭文件#define HASH_LEN 50 /哈希表的長度 #define P 47 /小于哈希表長度的P#define NAME_LEN 30 /姓名表的長度 typedef struct /姓名表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、jvoid InitNameTable() /姓名表的初始化 NameTable0.py=louyuhong; NameTable1.py=shenyinghong; 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.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;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;iNAME_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;iHASH_LEN;i+) HashTablei.py=0; HashTablei.m =0; HashTablei.si=0; for(i=0;iNAME_LEN;i+) int sum=1,j=0; int adr=(NameTablei.m)%P; /除留余數(shù)法 H(key)=key MOD p,p=m if(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ù)加1 HashTableadr.m =NameTablei.m; /將姓名表復(fù)制給哈希表對應(yīng)的位置上 HashTableadr.py=NameTablei.py; HashTableadr.si=sum; void DisplayNameTable() /顯示姓名表 printf(n地址 tt 姓名 tt 關(guān)鍵字n); for (i=0;iNAME_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); /顯示的格式 for (i=0;iHASH_LEN;i+) printf(%2d %18s tt %d tt %dn,i,HashTablei.py,HashTablei.m,HashTablei.si); asl+=HashTablei.si; asl/=NAME_LEN; /求得ASL printf(nn平均查找長度：ASL(%d)=%f n,NAME_LEN,asl);void FindName() /查找 char name20=0; int s=0,sum=1,adr; printf(n請輸入想要查找的姓名的拼音:); scanf(%s,name); for (j=0;j20;j+) /求出姓名的拼音所對應(yīng)的ASCII作為關(guān)鍵字 s+=toascii(namej); adr=s%P; /除留余數(shù)法 j=0; if(HashTableadr.m=s&!strcmp(HashTableadr.py,name) /分3種情況進行判斷，并輸出超找結(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ù)加1 if(HashTableadr.m=0) printf(沒有想要查找的人!n); break; if(HashTableadr.m=s&!strcmp(HashTabl