课程设计报告--散列表的设计与实现

《课程设计报告--散列表的设计与实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称《数据结构》课题名称散列表的设计与实现专业计算机科学与技术班级10计本2班学号10012101；10012104姓名项阳徐旭东联系方式15056583551；15056560835指导教师江家宝目录1、数据结构课程设计任务书１1.1、题目１1.2、要求１2、总体设计１2.1、功能模块设计１2.2、所有功能模块的流程图１3、详细设计１3.1、程序中所采用的数据结构及存储结构的说明１3.2、算法的设计思想２3.3、稀疏矩阵各种运算的性质变换２4、调试与测试：２4.1、调试方法与步骤：２4.2、测试结果的分析

2、与讨论：３4.3、测试过程中遇到的主要问题及采取的解决措施：３5、时间复杂度的分析：４6、源程序清单和执行结果４7、C程序设计总结８8、致谢８9、参考文献８1、数据结构课程设计任务书1.1、题目散列表的设计与实现1.2、要求1)设每个记录有下列数据项：电话号码、用户名、地址；2)从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3)采用一定的方法解决冲突；4)查找并显示给定电话号码的记录；5)查找并显示给定用户名的记录。【进一步完成内容】1)系统功能的完善；2)设计不同的散列函数，比较冲突率；3)在散列函数确定的前提下，尝试各种不同类型处理冲突的

3、方法，考察平均查找长度的变化。2、总体设计2.1、功能模块设计根据课程设计题目的功能要求，各个功能模块的组成框图如下：2.2、所有功能模块的流程图以号码为关键字的Hash()函数流程图取整型num[2]赋给key结束Key=key%20Key=key+(int)num[i]i++i从3开始取num[i]!=0开始以姓名为关键字的Hash()函数流程图取整型name[0]赋给key2结束Key2=key%20Key2+=name[i]i++i从0开始取name[i]不为空开始添加结点信息流程图:利用用户名为关键字插入拉链法处理冲突调用hash()函数调用ha

4、sh()函数Newname指向newphoneNewphone=input()结束申请新的结点newphone,newname即新的号码和名字开始申请专利开始按姓名查找流程图:q不为空结束输出无记录输出相应记录q=q->nextq不为空调用hash()函数中新结点q指向phone[key]->next开始按号码查找流程图:开始调用hash2()函数中新结点q指向phone[key]->nextq不为空q=q->nextq不为空输出无记录输出相应记录结束主程序流程图开始Main()初始化散列链表（1）并为其动态分配内存空间初始化散列链表（2）并为其动态分配内

5、存空间Menu（）主菜单输入选择选择1选６选7查找号码find()查找用户find2()输出结果输出结果选择2选择0选择3选择4选择5进行姓名散列list2()姓名散列结果添加记录apend()退出系统return0进行号码散列list()清空creat();creat2()列表已清空号码散列结果结束3、详细设计首先定义结点结构体类型，在链地址法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成，链地址法结点结构如图：name[8]num[11]address[20]nex

6、t其中name[8]和num[11]是分别为以电话号码和用户名为关键字域（key），存放关键字；address[20]为结点的数据域(data)，用来存储用户的地址信息。next指针是用来指向下一个结点的地址。unsignedintkey和unsignedintkey2分别被定义为电话号码和用户名关键字。程序的主要模块如下：************************程序部分源代码*************************3.1建立节点structnode{charname[8],address[20];charnum[11];node*nex

7、t;};typedefnode*pnode;//typedeftypedefnode*mingzi;node**phone;node**nam;node*a;3.2对散列函数的定义本程序要设计两个hash（）函数，分别对应电话号码和用户名。本设计中对散列函数选择的是除留余数法，即对关键字进行模运算，将运算结果所得的余数作为关键字（或结点）的存储地址，即H（key）=keymodp,本设计中p取20,然后将计算出来的数作为该结点的地址赋给key。具体方法如下：以电话号码为关键字建立哈希函数hash(charnum[11])。以用户名为关键字建立哈希函数has

8、h2(charname[8])。利用强制类型转换，将用户名的每一个