c语言课程设计
- 格式:doc
- 大小:1.48 MB
- 文档页数:26
课程设计说明书课程名称软件课程设计
教学部工学一部
专业电子信息工程
班级 B
学号 B
学生姓名
指导教师白玉
2010年6月
哈希表设计
目录
摘要 (1)
1绪论 (1)
2系统分析................................................................................... 错误!未定义书签。
2.1功能需求 (1)
2.2数据需求 (1)
2.3性能需求 (1)
3总体设计 (1)
3.1任务书 (1)
3.2系统设计方案....................................................................错误!未定义书签。
3.3流程图 (3)
4测试 (11)
5结论 (11)
6结束语 (11)
参考文献 (11)
附录1-用户手册 (12)
附录2-源程序 (16)
摘要
随着科技的发展,为了方便人们查询信息,在众多的信息中筛选出自己所需要的,我们需要对它们进行编码。例如,在进行查询成绩单时,为了在众多人的成绩表中迅速的找到自己或他人的成绩,我们需要对它们进行编码并建表,然后就能在程序中进行查表了。
关键词:哈希表编码。
1绪论
随着信息技术的飞速发展,我们需要很快捷的查找我们所要的信息。合理的哈希表设计系统已成为必不可少的查询系统之一。该题目要求待填入哈希表的人名共有30个,取平均查找长度的上限为2。哈希函数用除留余数法构造,用开放定址法处理冲突。如果随机函数自行构造,则应首先调整好随机函数,使其分布均匀。人名的长度不超过19个字符,可对过长的人名先作折叠处理。
2 系统分析
2.1 功能需求
(1)初始化哈夫曼链表。
(2)输入要编码的字符。
(3)打印编码。
(4)打印哈夫曼树。
2.2数据需求
通过对30个人名的编译,能够迅速查到所需信息。
2.3 性能需求
在运行本程序时只要按照正确的操作方法不会出现无法运行的情况,系统稳定性好,安全,可靠。反应速度快速。性能安全可靠,稳定性强,不会出现重复编码的现象。并能在大量信息中迅速找出所需信息。
3总体设计
3.1任务书
针对某个集体(比如你所在的班级)中的“人名”设计一个哈希表,使得平均查找长度不超过2,完成相应的建表和查表程序。
假设人名为中国人姓名的汉语拼音形式。待填入哈希表的人名共有30个,取平均查找长度的上限为2。
哈希函数用除留余数法构造,用开放定址发处理冲突。如果随即函数自行构造,则应首先调整好随即函数,使其分布均匀。人名的长度均不超过19个字符(最长人名如:庄双双 zhuangshuangshuang)。可对过长的人名先作折叠处理。
3.2系统设计方案
抽象数据类型定义
数据结构ADT Tree {
数据对象D:D是具有相同特性的数据元素的集合
数据关系R:若D为空集,则成为空树;
若D仅含一个数据元素,则R为空集,否则R={H},H是如下二元关系:(1)在D中存在惟一的称为根的数据元素root,它在关系H下无前驱;
(2)若D-{root}的一个划分D1,D2,…,Dm(m>0),对任意j≠k(1≤j,k ≤m)有Dj∩Dk=Φ,且对任意的i(1≤i≤m),惟一存在数据元素Xi∈Di,有<root,Xi>∈H;
(3)对应于D-{root}的划分,H-{<root,X1>,…,<root,Xm>}有惟一的一个划分H1,H2, …,Hm(m>0),对任意j≠k(1≤j,k≤m)有Dj∩Dk=Φ,且对任意的i(1≤i ≤m),Hi是Di上的二元关系,(Di,{Hi})是一棵符合定义的树,称为根root的子树。
基本操作P:
InitTree(&T);
操作结果:构造空树T。
DestroyTree(&T);
初始条件:树T的存在。
操作结果:销毁树T。
CreateTree(&T,definition);
初始条件:definition给出树T的定义。
操作结果:按definition构建树T。
ClearTree(&T);
初始条件:树T存在。
操作结果:将树T清为空树。
TreeEmpty(T);
初始条件:树T的存在。
操作结果:若T为空树,则返回TRUE,否则FALSE。
}ADT Tree
3.3流程图
图1 求赫夫曼编码流程图
图2 select函数流程图
图3 算法6.12流程图
图4 编码函数流程图
图5 译码函数流程图
图6 打印编码的函数流程图
图7 初始化赫夫曼链表流程图
4 测试
软件测试是软件生存期中的一个重要阶段,是软件质量保证的关键步骤从用户的角度来看,普遍希望通过软件测试暴露软件中隐藏的错误和缺陷,所以软件测试应该是“为了发现错误而执行程序的过程”。或者说,软件测试应该根据软件开发各阶段的规格说明和程序的内部结构而精心设计一批测试用例(即输入数据及其预期的输出结果),并利用这些测试用例去运行程序,以发现程序错误或缺陷。过度测试则会浪费许多宝贵的资源。到测试后期,即使找到了错误,然而付出了过高的代价。
5结论
经过这一段时间的程序设计,该课设任务书中的内容基本达到。并且比任务书要求更高。在此程序中哈希函数用除留余数法构造,用开放定址法处理冲突,此程序还需要更为深入的研发,在假期时间争取做到更好。
6结束语
C语言综合训练顺利完成,题目所要求的功能也都一一实现。通过这段时间的辛苦工作,使我懂得了有付出就有回报,只要你肯努力就一定能攻克困难。虽然在这次C语言综合训练中我遇了我没有学过的知识,但是我积极的上图书馆,上网查资料,一一攻克了难题。因此我希望学校能够经常的举行这样的综合训练,这样能够让我们扩大自己的视野,培养积极动脑,积极动手的好习惯。
参考文献
[1] 谭浩强.C语言程序设计(第三版).清华大学出版社,2007
[2]姜灵芝,余健.C语言课程设计案例精编.清华大学出版社,2008
[3] 网上相关资料
[4] 吴伟民,严蔚敏.数据结构. 清华大学出版社,2008
[5] 王晓东,数据结构与算法设计.电子工业出版社,2002