- 1、本文档共38页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
沈阳航空航天大学课程设计报告
PAGE I
沈阳航空航天大学
课 程 设 计 报 告
课程设计名称:数据结构课程设计
课程设计题目: 基于Hash表的班级成员管理
目 录
TOC \o 1-3 \h \z \u
1 题目介绍和功能要求 h 1
1.1 题目介绍 h 1
1.2 功能要求 h 1
1.3 基本功能 h 1
2 系统功能模块结构图 h 2
2.1 系统功能结构框图 h 2
2.2 系统主要模块的功能说明 h 2
3 使用的数据结构的描述 h 4
3.1 数据结构设计 h 4
3.2 数据结构用法说明 h 4
4 函数的描述 h 5
4.1 主要函数设计 h 5
4.2 主要函数流程图 h 5
5程序测试和运行的结果 h 8
5.1 程序测试 h 8
5.2 运行结果 h 9
6参考文献 h 11
附 录(关键部分程序清单) h 12
沈阳航空航天大学课程设计报告
1 题目介绍和功能要求
1.1 题目介绍
针对本班成员以姓名为关键字设计一个Hash表,使得平均查找长度不超过R。
要求:
自行设计至少3中Hash函数;
每种Hash函数采用线性探测再散列和伪随机数探测再散列进行冲突处理;
针对本班成员给出每种Hash函数的平均查找长度。
建立一个确定的对应关系f,使每个关键字和结构中的一个唯一的存储位置相对应。在查找时,只要根据这个对应关系f找到给定值K的像f(K)所建立的表即为哈希表。
1.2 功能要求
1. 用三种方法创建哈希函数,分别为除留取余法,随机数法和分割法。
2. 当哈希地址产生冲突时,利用线性探测再散列和伪随机数探测再散列进行冲突处理得到新的哈希地址,并存入哈希表中。
3. 给出每个用户名的查找长度和该函数的平均查找长度,并比较哪种方法最好。
1.3 基本功能
CreateHashList() 建立Hash函数,并采用两种冲突处理方法进行操作。
SearchHash() 查找Hash表,将用户所输入的信息从Hash表中调出,并给出查找长度
沈阳航空航天大学课程设计报告
2 系统功能模块结构图
2.1 系统功能结构框图
创建Hash表
创建Hash表
哈希函数模块(除留取余)
哈希函数模块(随机数法)
哈希函数模块(分割法)
冲突处理模块
冲突处理模块
冲突处理模块
冲突处理模块
查找模块
冲突处理模块
冲突处理模块
查找模块
查找模块
图2.1 系统功能结构框图
2.2 系统主要模块的功能说明
哈希模块
CreateHashList();(adr为哈希地址)
初始化Hash表,并创建Hash函数,并将用户姓名添加至Hash表中。
除留取余法:adr=(DATALIST[i].k)%M;(将DATALIST[i].k所存的ASCII码除以M取余所得的哈希地址赋给adr)
随机函数法: srand(DATALIST[i].k);
int adr=rand()%L;(将DATALIST[i].k所存的ASCII码作为种子传入至srand函数中,并用rand函数产生L以内的随机值为哈希地址赋给adr)
分割法: change(DATALIST,A,i);
int adr=A[1]*10+A[2];( DATALIST[i].k所存的ASCII码利用change()函数分割开,并去第二个数字和第三个数字作为哈希地址赋给adr)
冲突处理模块
srand(姓名ASCII码);
d=(d+rand()%L)%M;
伪随机探测再散列
d=d+1;
线性探测再散列
查找模块
SearchHash();
查找用户输入姓名是否在Hash表中;
给出该姓名的查找长度和该Hash函数的平均查找长度。
沈阳航空航天大学课程设计报告 KEYWORDS \* MERGEFORMAT
3 使用的数据结构的描述
3.1 数据结构设计
建立一个确定的对应关系f,使每个关键字和结构中的一个唯一的存储位置相对应。在查找时,只要根据这个对应关系f找到给定值K的像f(K)为存储地址的结构体数组即为哈希表。
哈希表举例(平方取中法):
A B C …… Z 0 1 2 …… 9
01 02 03 32 60 61 62 71
记录
关键字
(关键字)2
哈希地址(217-29)
A
I
J
I0
P1
P2
您可能关注的文档
- 基于CAD和VBA地表移动观测站数据处理系统毕业论文.doc
- 基于CATIA支撑件的参数化设计毕业论文.doc
- 基于ca证书购物网站的建设及应用论文.doc
- 基于CC1010的温度传感器数据传送板设计本科毕业论文.doc
- 基于CC2540的蓝牙4.0模块与PC机通信设计毕业论文.doc
- 基于Cimatron软件平台的塑料模具设计毕业设计(论文).doc
- 基于CIP系列模式的物质输运模型的构建毕业论文.doc
- 基于Cisco系统的企业网IPSec_Vpn的设计与实现毕业设计论文.doc
- 基于CMM(三坐标测量机)的形状误差测量及MATLAB实现论文.doc
- 基于CMOS图像传感器的视觉导航智能小车设计毕业论文.doc
文档评论(0)