《数据结构》课程设计报告
目录
1.需求分析..................................................................................................................... 1
1.1问题描述.......................................................................................................... 1 1.2需求分析.......................................................................................................... 1 2.概要设计..................................................................................................................... 2
2.1设计的内容...................................................................................................... 2 2.2设计的数据结构选择..................................................................................... 2
2.2.1.开放定址法........................................................................................... 4 2.2.2.链地址法............................................................................................... 5
3.详细设计..................................................................................................................... 6
3.1.涉及的知识点.................................................................................................. 6 3.2.详细的设计思路.............................................................................................. 6
3.2.1算法的基本思路描述........................................................................... 6 3.2.2 算法的设计.......................................................................................... 6 3.2.3程序的总流程图................................................................................... 7
4.编码............................................................................................................................. 9
4.1常量的定义...................................................................................................... 9 4.2数据结构定义.................................................................................................. 9 5.各个模块功能上机测试........................................................................................... 12
5.1口令测试（进入系统的条件）.................................................................... 20 5.2录入计信系各教师的信息............................................................................ 21 5.3显示系统中教师的信息................................................................................ 21 5.4查找教师的信息（以姓名）........................................................................ 22 5.5查找教师的信息（以电话号码）................................................................ 23 5.6删除教师的信息............................................................................................ 23 5.7修改教师的信息............................................................................................ 24 6.小结........................................................................................................................... 24 参考文献...................................................................................................................... 25
《数据结构》课程设计报告
1.需求分析
1.1问题描述
本程序要完成一个实现计算机与信息工程系教师通信录查询系统，能够完成教师信息的录入、查找、删除、增添功能。要求采用散列表实现计信系教师查询系统，并考虑解决散列冲突的方法。
通过对任务的分配，实现本程序需要解决以下几个问题： ?设每个记录有下列数据项：电话号码、用户名、地址；
? 从键盘输入各记录，分别以电话号码、姓名为关键字建立散列表； ? 采用二次探测再散列法解决冲突； ?查找并显示给定电话号码的记录； ?查找并显示给定姓名的记录；
?对教师信息进行相关添、删、修等操作； ?通信录信息文件保存；
?要求人机界面友好，使用图形化界面；
1.2需求分析
（1）程序所需要达到的功能：是通过创建哈希表，实现通信录的创建，并通过哈希表的插入和查找使通信录可以进行姓名、电话、地址的添加和相应的查找。 （2）输入的形式和输入值的范围：姓名地址均使用汉语拼音全拼形式，电话使用数字，记录的添加不会超过系教师的总人数。
（3）输出的形式：若输出整个哈希表内容，则按照哈希表的每一项所对应输入内容后，将整个记录表直接输出；若单个查找，则只会出现查找时对应的记录内容。
（4）测试数据：输入的记录个数应该小于设定的教师的记录数量（<20），输入的记录姓名的汉语拼音的长度也应小于设定的姓名的最大长度(<20)，只要在规定的输入范围内输入都能得到想要的结果。
1
《数据结构》课程设计报告
2.概要设计
2.1设计的内容
Menu()的功能： 显示提示选单。 Key()的功能： 口令测试。 Create()的功能： 创建新的通讯录。
Search()的功能： 查询某人的信息，如果找到了，则显示该人的信息，如果没有则提示通 讯录中没有此人的信息，并返回选单。
Alter()的功能： 修改某人的信息，如果未找到要修改的人，则提示通讯录中没有此人的信息，并返回选单。
Delete()的功能： 删除某人的信息，如果未找到要删除的人，则提示通讯录中没有此人的信息，并返回选单。
List()的功能： 显示通讯录中的所有记录。
Save()的功能： 保存通讯录中的所有记录到指定文件中。
2.2设计的数据结构选择
存储教师的记录时，若在存储位置和其关键字之间建立某种确定的对应关系?,使得每个关键字和存储结构中一个唯一的存储位置相对应，那么在进行查找时，根据这个对应关系?就可以找到给定值K的像?(K）。若存储结构中存在关键字和K相?等的记录，则必定在f（K）的存储位置上，由此不需要进行比较便可直接找到所查记录。这个对应关系?称为哈希（Hash）函数或散列函数。按照以上思路建立的表称为哈希表或散列表。该程序设计主要考察散列表的建立、查找、删除和修改 ，系统的功能模块图如图1所示。
散列表一旦建立，进行查找时就可以用给定的关键字和建立散列表时所采用的哈希函数直接在给定的表中进行查找。然而，由于集合中各记录关键字的聚会可能在一个很大的范围内，所以，即使当集合中记录的个数不是很多时，也很难选取一个合适的哈希函数H能够保证对于任意不同的ki和kj。有H(Ki)?H(Kj)。
2
《数据结构》课程设计报告
当Ki?Kj，而H(Ki)?H(Kj)的现象称为冲突现象。当发生冲突时，必须采用适当的方法来解决冲突。
因此，构造哈希函数和建立解决冲突的方法是建立哈希表的两大任务。 选取一个合适的不大于哈希表长的正整数P，用P去除关键字K，所得的余数作为其哈希地址，即H（K）＝K mod P，这种方法称为除余法哈希函数。除余法是一种简单且行之有效的构造哈希函数的方法。实践证明，当P取小于哈希表长的最大质数时，产生哈希函数较好。所以本程序设计采用的是除余法哈希函数。
系统功能添加教师记录显示教师记录查找教师记录删除教师记录修改教师记录根据姓名查找根据电话号码以姓名创建哈希函数以电话号码创建哈希函数
图 1系统功能图
解决冲突的方法有两大类，即开放定址法和链地址法。
3
《数据结构》课程设计报告
2.2.1.开放定址法
开放定址法又分为线性探查法、二次探查法和双重散列法。开放定址法解决冲突的基本思想是：使用某种方法在散列表中形成一 个探查序列，沿着此序列逐个单元进行查找，直到找到一个空闲的单元时将新结点存入其中。假设散列表空间为T[0....m-1]，散列函数为H（key），开放定址法的一般形式为：其中为增量序列，m为散列表长。h0?H(key)hi?(H(key)?di)%m(0?i?m?1)，
为初始探查地址（假设d0＝0），后续的探查地址依次是h1,h2,...，hm?1。 （1）线性探查法
线性探查法的基本思想是：将散列表T[0...m-1]看成一个循环向量，若初始探查的地址为d（即H(key）=d），那么，后续探查地址的序列为：d+1,d+2,....,m-1,0,1,....,d-1。也就是说，探查时从地址d开始，首先探查T[d]，然后依次探查T[d+1],....,T[m-1],此后又循环到T[0],T[1],...,T[d-1]。若当前探查单元为空，则将关键字key写入空单元；若不为空则继续后序地址探查，直到遇到空单元插入关键字，若探查到T[d-1]时仍未发现空单元，则插入失败（表满） （2）二次探查法
二次探查法的探查序列为：hi?(H(key)?i2)%m,0?i?m?1，也就是说，探查从地址d开始，先探查T[d],然后再依次探查T[d?12],T[d?22],....。 （3）双重散列法
双重散列法的探查序列为：hi?(H(key)?i*H1(key))%m(0?i?m?1),即探查序列为：d?H(key),(d?1*H1(key))%m,(d?2*H1(key))%m,....。
4