版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、哈希表实验报告 实习报告 题目:设计一个哈希表,完成相应的建表和查表程序 班级:1503013 姓名:李睿元 学号完成日期:2021.12.04 一、 需求分析 1. 假设人名为中国人名的汉语拼音形式; 2. 待填入哈希表的姓名共有 30 个,去平均查找长度的上限为 2; 3. 哈希函数用除留余数法构造,用伪随机探测再散列法处理冲突; 4. 取读者周围较熟悉的 30 个人的姓名。 二、 概要设计 1. 抽象数据类型的定义: (1)人名数据表: typedef struct node char name20; int key; node,nodelistmax; (2)
2、哈希表: typedef struct hashtable char* name; int key; int conflict_time; hashtablehashlen; (3)变量: #define p 61/随机数值 #define max 30/人数 #define hashlen 61/哈希表长 2. 主要函数的实现: (1)哈希函数: int hash(int key) (2)关键字获得: int getkey(char str) (3)文件流中读取姓名: void getname(nodelist l,int i,file* fp) (4)哈希表的初始化: void initi
3、alhashtable(hashtable ht) (5)伪随机探测序列的生成: void creatconfilctarray(int n) (6)哈希表的生成: void creathashtable(hashtable ht,nodelist l,int* n) (7)哈希表的查询: void searchhashtable(hashtable ht,int* n,char get_name) 三、 详细设计 #include stdio.h #include stdlib.h #include string.h #define p 61/随机数值 #define max 30/人数 #
4、define hashlen 61/哈希表长 typedef struct node char name20; int key; node,nodelistmax; typedef struct hashtable char* name; int key; int conflict_time; hashtablehashlen; int hash(int key) return key%p; int getkey(char str) int t=0; char *s=str; while(*s) t += *s; s+; return t; void getname(nodelist l,in
5、t i,file* fp) /* printf(请以拼音形式输入第%d 个姓名:,i); scanf(%s,l); li.key=getkey(l); */ fscanf(fp,%s,l); li.key=getkey(l); /printf(n); void initialhashtable(hashtable ht) int n=0; while(nhashlen) htn.conflict_time=0; =null; htn.key=0; n+; void creatconfilctarray(int n) / n=(in
6、t*)malloc(50*sizeof(int); int i=0,j=0; while(i50) ni=rand()%(hashlen+1); for(;ji;j+) if(ni=nj) j=0; ni=rand()%(hashlen+1); continue; i+; void creathashtable(hashtable ht,nodelist l,int* n) / creatconfilctarray(n); int i=0; int t; while(imax) t=hash(li.key); if(htt.conflict_time=0) =l;
7、htt.conflict_time+; htt.key=li.key; printf(姓名:%s key 值:%d 表内存储位置:%dn,l,li.key,t); else int m=0; int d=(t+nm)%hashlen; while(htd.conflict_time!=0) htd.conflict_time+; m+; d=(t+nm)%hashlen; =l; htd.conflict_time+; htd.key=li.key; printf(姓名:%s key 值:%d 表内存储位置:%dn,l,li.key,d);
8、i+; void searchhashtable(hashtable ht,int* n,char get_name) /printf(请输入要查询的姓名:); /char get_name20; int p=-1; int s_time=1; / scanf(%s,get_name); int h,k; int t; k=getkey(get_name); t=h=hash(k); while(1) /*if(hth.conflict_time=0hth.key!=k) printf(表中未找到无此人!n); break; else if(hth.key=k) printf(已找到%s,表内
9、存储位置:%dn,get_name,h); break; else p+; h=np; */ if(=null) printf(表中未找到无此人!n); break; else if(strcmp(,get_name)=0) printf(已找到%s,表内存储位置:%d,查找次数:%dn,get_name,h,s_time); break; else p+; h=(t+np)%hashlen; s_time+; int main() / printf(请输入建表所需的三十个人名!n); int i,j; nodelist l; hashtable ht; ini
10、tialhashtable(ht); char get_name20=0; int rand_n50; creatconfilctarray(rand_n); file* fp; fp=fopen(name.txt,r); for(i=0;i30;i+) getname(l,i,fp); fclose(fp); creathashtable(ht,l,rand_n); printf(n); printf(-哈希表建表完成-); printf(n); while(1) get_name20=0; printf(请输入要查找的人名(输入"*'表示结束程序):); scanf(%s
11、,get_name); printf(关键字:%d ,getkey(get_name); if(strcmp(get_name,*)=0) break; searchhashtable(ht,rand_n,get_name); return 0; 四、 调试分析 1. 哈希表可以在理想情况下不经过任何比较,一次存取就能得到所查记录; 2. 除留余数法对于 p 的选择很重要,经过分析后的选择是 p 为小于等于 m 的最大素数,最终选择了 61; 3. 伪随机探测再散列相较于线性探测再散列或二次探测再散能有效的防止二次堆积。 五、 用户手册 1. 本程序的运行环境为 windows 操作系统,执行文件为 hashtable.exe; 2. 本程序的输入的名字存储在 name.txt 文件中; 3. 程序进入后已经完成哈希表的构建并进行展示,用户只需进行相应的查找; 六、 测试数据 1. 挑选表中已有的十个姓
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 冀教版七年级上册第5章一元一次方程5.3.1用合并同类项法解方程课件数学
- 高中物理-探究电磁感应的产生条件课件-新人教版选修3
- 九上下册物理新人教版十五章-两种电荷公开课教案教学设计课件测试卷练习卷课时同步训练练习公开课教案课件
- 高中语文-第22课-荷花淀第2课时同步教学课件-粤教版必修3
- 高一语文上册《我的空中楼阁》课件-人教版第一册
- 智慧水务平台整体建设方案
- 六年级下册数学第2课时-数的认识(2)公开课教案教学设计课件公开课教案课件
- 冀教版八年级下册《Lesson 6 Stories about Spring》同步练习卷
- 冀教版七年级下册Lesson 21 What Is Your Club Type同步练习
- 护理交接班程序应用
- 国开2024年秋季《形势与政策》大作业答案
- 仙家送钱表文-文字打印版
- 污水管顶管施工方案(附计算)
- JJG 695-2019 硫化氢气体检测仪检定规程(高清版)
- 实验室专业术语中英文翻译对照
- 《水利水电建设工程验收规程》SL223
- NumPy数值计算基础PPT课件
- 绿化工程施工PPT课件
- 变更通知单(ECN) 模板
- 设计素描完整PPT课件
- 热水循环泵选型手册
评论
0/150
提交评论