哈希表设计-数据结构课程设计_第1页
哈希表设计-数据结构课程设计_第2页
哈希表设计-数据结构课程设计_第3页
哈希表设计-数据结构课程设计_第4页
哈希表设计-数据结构课程设计_第5页
已阅读5页,还剩3页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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/随机数用到的头文件#

3、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_

4、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; Name

5、Table9.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、各个字符所对应的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)=

8、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=NameTab

9、lei.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

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请输入想要查找的姓名的拼音:);scanf(%s,name);getchar(); for (j=0;j20;j+)/求出姓名的拼音所对应的ASCII作为关键字 s+=toascii(namej); adr=s%

11、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;

12、 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:

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论