哈希表实现电话号码查询系统 数据结构课程设计报告.docx

哈希表实现电话号码查询系统
一目的
利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目,利用C/C++语言进行程序设计,并规范地完成课程设计报告。通过课程设计,巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解;掌握现实复杂问题的分析建模和解决方法(包括问题描述、系统分析、设计建模、代码实现、结果分析等);提高利用计算机分析解决综合性实际问题的基本能力。
二需求分析
程序的功能
读取数据
读取原电话本存储的电话信息。
读取系统随机新建电话本存储的电话信息。
查找信息
根据电话号码查询用户信息。
根据姓名查询用户信息。
存储信息
查询无记录的结果存入记录文档。
输出形式
数据文件“”存放原始电话号码数据。
数据文件“”存放有系统随机生成的电话号码文件。
数据文件“”存放未查找到的电话信息。
查找到相关信息时显示姓名、地址、电话号码。
初步测试计划
从数据文件“”中读入各项记录,或由系统随机产生各记录,并且把记录保存到“”中。
分别采用伪随机探测再散列法和再哈希法解决冲突。
根据姓名查找时显示给定姓名用户的记录。
根据电话号码查找时显示给定电话号码的用户记录。
。
系统以菜单界面工作,运行界面友好,演示程序以用户和计算机的对话方式进行。
三概要设计
子函数功能
int Collision_Random(int key,int i)
//伪随机数探量观测再散列法处理冲突
void Init_HashTable_by_name(string name,string phone,string address)
//以姓名为关键字建立哈希表
int Collision_Rehash(int key,string str)
//再哈希法处理冲突
void Init_HashTable_by_phone(string name,string phone,string address)
//以电话号码为关键字建立哈希表
void Outfile(string name,int key)
//在没有找到时输出未找到的记录,
void Outhash(int key)
//输出哈希表中的记录
void Rafile()
//随机生成数据,
void Init_HashTable(char*fname,int n)
//建立哈希表
int Search_by_name(string name)
//根据姓名查找哈希表中的记录
int Search_by_phone(string phone)
//根据电话号码查找哈希表中的记录
函数调用图
四详细设计
主函数流程图

“伪随机探测再散列处理冲突”伪代码
若对应位置上已经存在其他数据,则新的关键字=(原关键字+伪随机数)% 哈希表长。
若新的位置上也存在其他数据,则用伪随机序列的下一个数求新的关键字,直到找到合适的位置。
“再哈希法处理冲突”伪代码
用“折叠法”将电话号码的ASCII码值定义为关键字,分别为前四位、中四位、后三位。
再用“除留余数法”求的新的关键字=原关键字%哈希表长。
“以姓名为关键字建立哈希表”伪代码
用“除留余数法”将姓名的ASCII码值定义为关键字。
若对应位置上存在其他数据,则调用伪随机处理冲突,然后将数据存入哈希表。
“以电话号码为关键字建立哈希表”伪代码
用“除留余数法”将电话号码的ASCII码值定义为关键字。
若对应位置上存在其他数据,则调用再哈希处理冲突。
然后将数据存入哈希表。
五调试分析
1、程序的关键是掌握文件的相关操作、哈希函数的创建和运用、伪随机法处理冲突、再哈希法处理冲突等。在编程的过程中,出现了很多问题,如文件无法正常打开、程序进入死循环、无法实现文件的写入操作、忘了添加头文件等错误。修改后程序运行正确。
2、创建“”内容用子函数来实现,但是原数据是从“”文件中读取的,刚开始不知道怎样实现二者之间的选择,在同学和参考书的帮助下终于得到解决。
3、关于伪随机和再哈希的相关内容觉得很难懂,看了很久参考书才有所了解
六测试结果
根据姓名查找
姓名查找成功
姓名查找失败
哈希表
根据电话号码查找
电话号码输入错误
电话号码查询成功
电话号码查询失败
七用户使用说明
选择数据来源
根据提示信息进行操作,选择已存在的“”文件中的数据或系统当前自