数据结构课程设计报告

《数据结构》课程设计

哈希表实现电话号码查询系统

一 目的

利用《数据结构》课程的相关知识完成一个具有一定难度的综合设计题目，利用C/C++语言进行程序设计，并规范地完成课程设计报告。通过课程设计，巩固和加深对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的理解；掌握现实复杂问题的分析建模和解决方法（包括问题描述、系统分析、设计建模、代码实现、结果分析等）；提高利用计算机分析解决综合性实际问题的基本能力。

二 需求分析

1、 程序的功能

1)

读取数据

① 读取原电话本存储的电话信息。

② 读取系统随机新建电话本存储的电话信息。 2)

查找信息

① 根据电话号码查询用户信息。 ② 根据姓名查询用户信息。 3)

存储信息

查询无记录的结果存入记录文档。

2、 输出形式

1) 数据文件“old.txt”存放原始电话号码数据。

2) 数据文件“new.txt”存放有系统随机生成的电话号码文件。 3) 数据文件“out.txt”存放未查找到的电话信息。 4) 查找到相关信息时显示姓名、地址、电话号码。

3、 初步测试计划

1) 从数据文件“old.txt”中读入各项记录，或由系统随机产生各记录，并且把记录保存

到“new.txt”中 。

2) 分别采用伪随机探测再散列法和再哈希法解决冲突。 3) 根据姓名查找时显示给定姓名用户的记录。 4) 根据电话号码查找时显示给定电话号码的用户记录。

xxxx大学xxxx学院xxxx专业 学号： xxxxxxx 姓名 ：jenery6 1

《数据结构》课程设计

5) 将没有查找的结果保存到结果文件Out.txt中。

6) 系统以菜单界面工作，运行界面友好，演示程序以用户和计算机的对话方式进行。

三 概要设计

1、 子函数功能

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)

//在没有找到时输出未找到的记录，打开文件out.txt并将记录储存在文档中 void Outhash(int key) //输出哈希表中的记录 void Rafile()

//随机生成数据，并将数据保存在new.txt void Init_HashTable(char*fname,int n) //建立哈希表

int Search_by_name(string name) //根据姓名查找哈希表中的记录 int Search_by_phone(string phone) //根据电话号码查找哈希表中的记录

xxxx大学xxxx学院xxxx专业 学号： xxxxxxx 姓名 ：jenery6 2

《数据结构》课程设计

2、 函数调用图

main()Refile()init-hashtable()init-hashtable-by-name()init-hashtable-by-phone()Seach-by-name()Seach-by-phone()Coiiision-random()Collision-rehash()Outhash()xxxx大学xxxx学院xxxx专业 学号： xxxxxxx 姓名 ：jenery6 3

《数据结构》课程设计

四 详细设计

1、 主函数流程图

开始选择数据来源21建“new.txt”选择查找方式12姓名查找电话号码查找12021输入姓名显示哈希表0显示哈希表输入电话号码无此记录显示信息无此记录显示信息0写入“out.txt”写入“out.txt”

结束

2、 “伪随机探测再散列处理冲突”伪代码

若对应位置上已经存在其他数据，则新的关键字=（原关键字+伪随机数）% 哈希表长。

若新的位置上也存在其他数据，则用伪随机序列的下一个数求新的关键字，直到找到合适的位置。

3、 “再哈希法处理冲突”伪代码

用“折叠法”将电话号码的ASCII码值定义为关键字，分别为前四位、中四位、后三位。

xxxx大学xxxx学院xxxx专业 学号： xxxxxxx 姓名 ：jenery6 4