《哈希表设计数据结构优秀课程设计》由会员分享，可在线阅读，更多相关《哈希表设计数据结构优秀课程设计（10页珍藏版）》请在金锄头文库上搜索。
1、实习 6、哈希表设计一、需求分析1. 问题描述针对某个集体比方你所在班级中“人名”设计一个哈希表，使得平均查找长度均不超出R，完成对应建表和查表次序。2. 根底要求假设人名为中国人姓名汉语拼音形式。待填入哈希表人名共有30 个，取平均查找长度上限为 2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。3. 测试数据取读者四周较生疏 30 个人姓名。4. 实现提示假设随机数自行构造，那么应首先调整好随机函数，使其分布均匀。人名长度均不超出 19 个字符最长人名如：庄双双Zhuang Shuangshuang。字符取码方法可直接利用 C 语言中toascii 函数，并可先对过长人名先作折叠
2、处理。二、概要设计ADT Hash 数据对象 D：D 是含有一样特征数据元素集合。各数据元素均含有类型一样，可唯一标识数据元素关键字。数据关系R：数据元素同属一个集合。InitNameTable()操作结果：初始化姓名表。CreateHashTable()操作结果：建立哈希表。DisplayNameTable()操作结果：显示姓名表。DisplayHashTable()操作结果：显示哈希表。FindName()操作结果：查找姓名。ADT Hash三、具体设计源代码使用C 语言 #include#include/time 用到头文件#include/随机数用到头文件#include/toasci
3、i()用到头文件#include/查找姓名时比较用头文件#define HASH_LEN 50/哈希表长度#define P 47/小于哈希表长度 P #define NAME_LEN 30/姓名表长度typedef struct/姓名表char *py;/名字拼音 int m;/拼音所对应NAME;NAME NameTableHASH_LEN;/全局定义姓名表typedef struct/哈希表char *py;/名字拼音int m;/拼音所对应 ASCII 总和int si;/查找长度HASH;HASH HashTableHASH_LEN;/全局定义哈希表int d30,i,j;/全局定义
4、随机数,循环用 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“; NameTable9.py=“sunha
5、ohao“; 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=“xu
6、nwenwen“; 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“;f
7、or (i=0;iNAME_LEN;i+)/将字符串各个字符所对应 ASCII 码相加，所得整数做为哈希表关键字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)
8、%P;/除留余数法 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;/查找次数加 1位置上HashTableadr.m =NameTablei.m;/将姓名表复制给哈希表对应HashTableadr.py=Na
9、meTablei.py; HashTableadr.si=sum;void DisplayNameTable()/显示姓名表printf(“n 地址 tt 姓名 tt 关键字n“); for (i=0;iNAME_LEN;i+)printf(“%2d %18s tt%dn“,i,NameTablei.py,NameTablei.m);void DisplayHashTable()/ 显示哈希表float asl=0.0;printf(“nn 地址 tt 姓名 tt 关键字 t 搜寻长度n“); /显示格式for (i=0;iHASH_LEN;i+)printf(“%2d %18s tt%dtt
10、%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“,name);getchar();for (j=0;j20;j+)/求出姓名拼音所对应 ASCII 作为关键字s+=toascii(namej);adr=
11、s%P;/除留余数法j=0;if(HashTableadr.m=s&!strcmp(HashTableadr.py,name) /分 3 种状况进展判定，并输出超找结果printf(“n 姓名:%s关键字:%d查找长度为: 1n“,HashTableadr.py,s); else if (HashTableadr.m=0)printf(“没有想要查找人!n“);elsewhile(1)adr=(adr+dj+)%HASH_LEN;/伪随机探测再散列法处理冲突sum=sum+1;/查找次数加 1 if(HashTableadr.m=0)printf(“没有想要查找人!n“); break;if(
12、HashTableadr.m=s&!strcmp(HashTableadr.py,name)printf(“n 姓名:%s关键字:%d查找长度为:%dn“,HashTableadr.py,s,sum);break;int main()/主函数char c; int a=1;srand(int)time(0);for(i=0;i30;i+)/用随机函数求得伪随机数列 di在 1 到 50 之间di=1+(int)(HASH_LEN*rand()/(RAND_MAX+1.0);InitNameTable();CreateHashTable();printf(“*n“);printf(“*n“);p
13、rintf(“*哈希表设计*n“);printf(“*printf(“*A: 显示姓名表B:显示哈希表*n“);*n“);printf(“*printf(“*C: 查找D:退出*n“);*n“);printf(“*n“);printf(“*n“); while(a)printf(“n 请选择:“);scanf(“%c“,&c); getchar();switch(c)/依据选择进展判定，直到选择退出时才能够退出case ”A”:case ”a”:DisplayNameTable(); break;case ”B”:case ”b”:DisplayHashTable(); break;case ”C”:case ”c”:FindName(); break;case ”D”:case ”d”:a=0;break; default:printf(“n 请输入正确选择!n“); break;return 0;四
