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

1、實(shí)習(xí)6、哈希表設(shè)計(jì)一、 需求分析1. 問題描述針對(duì)某個(gè)集體（比如你所在的班級(jí)）中的“人名”設(shè)計(jì)一個(gè)哈希表，使得平均查找長度均不超過r，完成相應(yīng)的建表和查表順序。2. 基本要求假設(shè)人名為中國人姓名的漢語拼音形式。待填入哈希表的人名共有30個(gè)，取平均查找長度的上限為2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用偽隨機(jī)探測(cè)再散列法處理沖突。3. 測(cè)試數(shù)據(jù)取讀者周圍較熟悉的30個(gè)人的姓名。4. 實(shí)現(xiàn)提示 如果隨機(jī)數(shù)自行構(gòu)造，則應(yīng)首先調(diào)整好隨機(jī)函數(shù)，使其分布均勻。人名的長度均不超過19個(gè)字符（最長的人名如：莊雙雙（zhuang shuangshuang）。字符的取碼方法可直接利用c語言中的toascii函數(shù)，并可先對(duì)

2、過長的人名先作折疊處理。二、概要設(shè)計(jì)adt hash 數(shù)據(jù)對(duì)象d：d是具有相同特征的數(shù)據(jù)元素的集合。各數(shù)據(jù)元素均含有類型相同，可唯一標(biāo)識(shí)數(shù)據(jù)元素的關(guān)鍵字。數(shù)據(jù)關(guān)系r：數(shù)據(jù)元素同屬一個(gè)集合。initnametable()操作結(jié)果：初始化姓名表。createhashtable()操作結(jié)果：建立哈希表。displaynametable()操作結(jié)果：顯示姓名表。displayhashtable()操作結(jié)果：顯示哈希表。findname()操作結(jié)果：查找姓名。adt hash三、詳細(xì)設(shè)計(jì)（源代碼）（使用c語言）#include#include/time用到的頭文件#include/隨機(jī)數(shù)用到的頭文件#i

3、nclude/toascii()用到的頭文件#include/查找姓名時(shí)比較用的頭文件#define hash_len 50/哈希表的長度#define p 47/小于哈希表長度的p#define name_len 30/姓名表的長度typedef struct/姓名表 char *py; /名字的拼音 int m; /拼音所對(duì)應(yīng)的name;name nametablehash_len; /全局定義姓名表typedef struct/哈希表 char *py; /名字的拼音 int m; /拼音所對(duì)應(yīng)的ascii總和 int si; /查找長度hash;hash hashtablehash_l

4、en; /全局定義哈希表int d30,i,j; /全局定義隨機(jī)數(shù),循環(huán)用的i、jvoid initnametable()/姓名表的初始化 nametable0.py=caowukui; nametable1.py=langzhijie; nametable2.py=dongshuliang; nametable3.py=qiuhouyang; nametable4.py=zhangxu; nametable5.py=duhuan; nametable6.py=fanqing; nametable7.py=songxiaofei; nametable8.py=dutongtong; namet

5、able9.py=sunhaohao; nametable10.py=shanjianfeng; nametable11.py=wangbaoshan; nametable12.py=houfeng; nametable13.py=hujiaming; nametable14.py=jiangkaiqiang; nametable15.py=xuyang; nametable16.py=lvdelu; nametable17.py=shenjinfeng; nametable18.py=xuhui; nametable19.py=hanle; nametable20.py=xunwenwen;

6、 nametable21.py=chenhongcong; nametable22.py=zhangyanyan; nametable23.py=nieyanshun; nametable24.py=haopengcheng; nametable25.py=yuhaiyuan; nametable26.py=shuxiang; nametable27.py=sunyingjie; nametable28.py=wangbo; nametable29.py=zhaoqing; nametable30.py=zhangshengqian;for (i=0;iname_len;i+) /將字符串的各

7、個(gè)字符所對(duì)應(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)=k

8、ey 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; /偽隨機(jī)探測(cè)再散列法處理沖突 sum=sum+1; /查找次數(shù)加1 hashtableadr.m =nametablei.m; /將姓名表復(fù)制給哈希表對(duì)應(yīng)的位置上 hashtableadr.py=nametabl

9、ei.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 %

10、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請(qǐng)輸入想要查找的姓名的拼音:);scanf(%s,name);getchar(); for (j=0;j20;j+)/求出姓名的拼音所對(duì)應(yīng)的ascii作為關(guān)鍵字 s+=toascii(namej); adr=s%p

11、; /除留余數(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;/偽隨機(jī)探測(cè)再散列法處理沖突 sum=sum+1; /查找次數(shù)加1 if(hashtableadr.m=0) printf(沒有想要查找的人!n); break;

12、if(hashtableadr.m=s&!strcmp(hashtableadr.py,name) printf(n姓名:%s 關(guān)鍵字:%d 查找長度為:%dn,hashtableadr.py,s,sum); break; int main()/主函數(shù) char c; int a=1; srand(int)time(0); for(i=0;i30;i+)/用隨機(jī)函數(shù)求得偽隨機(jī)數(shù)列di（在1到50之間） di=1+(int)(hash_len*rand()/(rand_max+1.0); initnametable(); createhashtable(); printf(*n); printf(* *n); printf(* 哈希表設(shè)計(jì) *n); printf(* *n); printf(* a: 顯示姓名表 b: 顯示哈希表 *n); printf(* *n); printf(* c: 查找 d: 退出 *n); printf(* *n); printf(*n); while(a) printf(n請(qǐng)選擇:); scanf(%c,&c); getchar(); switch(c)/根據(jù)選擇進(jìn)行判斷，直到選擇退出時(shí)才可以退出 case a: case a: