哈希表设计-数据结构课程设计.pdf

山东科技大学学生课程设计山东科技大学学生课程设计实习实习 6 6、哈希表设计、哈希表设计一、一、需求分析需求分析1.问题描述问题描述针对某个集体（比如你所在的班级）中的“人名”设计一个哈希表，使得平均查找长度均不超过 R，完成相应的建表和查表顺序。2.基本要求基本要求假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有 30 个，取平均查找长度的上限为 2。哈希函数用除留余数法构造，用伪随机探测再散列法处理冲突。3.测试数据测试数据取读者周围较熟悉的 30 个人的姓名。4.实现提示实现提示 如果随机数自行构造，则应首先调整好随机函数，使其分布均匀。人名的长度均不超过 19 个字符（最长的人名如：庄双双（Zhuang Shuangshuang）。字符的取码方法可直接利用 C 语言中的 toascii 函数，并可先对过长的人名先作折叠处理。二、概要设计二、概要设计ADT Hash 数据对象 D：D 是具有相同特征的数据元素的集合。各数据元素均含有类型相同，可唯一标识数据元素的关键字。数据关系 R：数据元素同属一个集合。InitNameTable()操作结果：初始化姓名表。CreateHashTable()操作结果：建立哈希表。DisplayNameTable()操作结果：显示姓名表。DisplayHashTable()操作结果：显示哈希表。FindName()操作结果：查找姓名。ADT Hash三、详细设计（源代码）三、详细设计（源代码）（使用 C 语言）#include#include/time 用到的头文件#include/随机数用到的头文件#include/toascii()用到的头文件#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;/全局定义随机数,循环用的 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=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;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+)/将字符串的各个字符所对应的 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)%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=NameTablei.py;HashTableadr.si=sum;void DisplayNameTable()/显示姓名表 printf(n 地址 tt 姓名 tt 关键字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 关键字 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 请输入想要查找的姓名的拼音:);scanfs,name);getchar();for(j=0;j20;j+)/求出姓名的拼音所对应的 ASCII 作为关键字 s+=toascii(namej);adr=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);else while(1)adr=(adr+dj+)%HASH_LEN;/伪随机探测再散列法处理冲突 sum=sum+1;/查找次数加 1 if(HashTableadr.m=0)printf(没有想要查找的人!n);break;if(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);printf(*哈希表设计 *n);printf(*n);printf(*A:显示姓名表 B:显示哈希表 *n);printf(*n);printf(*C:查找 D:退出 *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;四、调试分析四、调试分析编译环境为编译环境为 CodeBlocks。山东科技大学学生课程设计山东科技大学学生课程设计山东科技大学学生课程设计山东科技大学学生课程设计山东科技大学学生课程设计山东科技大学学生课程设计