哈希表数据结构课程设计

1、数学与计算机学院课程设计说明书课 程 名 称: 数据结构-课程设计 课 程 代 码: 8404181 题 目: 哈希表的设计与实现 年级/专业/班: 2009级软件工程3班 学 生 姓 名: 张加发 学 号: 开 始 时 间: 2011 年 06 月 20 日完 成 时 间: 2011 年 06 月 29 日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总 分（100）指导教师签名： 年 月 日数 据 结 构 课 程 设 计 任 务 书学院名称： 数学与计算机学院 课程代码： 8404181 专 业： 软件工程 年 级： 2009级 一、设计

2、题目哈希表的设计与实现二、主要内容设计哈希表实现电话号码查找系统，要求如下：1)设每个记录有下列数据项：电话号码、用户名、地址；2)从键盘输入各记录，分别以电话号码和用户名为关键字建立哈希表（要求设计两种以上不同的散列函数）；3)采用两种以上的方法解决冲突；4)查找并显示给定电话号码的记录；5)查找并显示给定用户名的记录。三、具体要求及应提交的材料1每个同学以自己的学号和姓名建一个文件夹，如：“”。里面应包括：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）、任务书和课程设计说明书的电子文档。2打印的课程设计说明书（注意：在封面后夹入打印的“任务书”以后再装订）。四、主要技

3、术路线提示哈希表的操作。构造散列函数的方法较多，常用直接定址法、数字分析法、平方取中法、折叠法、除留余数法等，解决冲突的方法也较多，常用：开放定址法、链地址法等。五、进度安排共计两周时间，建议进度安排如下：选题，应该在上机实验之前完成需求分析、概要设计可分配4学时完成详细设计可分配4学时调试和分析可分配10学时。2学时的机动，可用于答辩及按教师要求修改课程设计说明书。注：只用课内上机时间一般不能完成设计任务，所以需要学生自行安排时间做补充。六、推荐参考资料1苏仕华等编著，数据结构课程设计，机械工业出版社，20072严蔚敏等编著，数据结构（C语言版），清华大学出版社，20033严蔚敏等编著，数据

4、结构题集（C语言版），清华大学出版社，2003指导教师 签名日期 年 月 日系 主 任 审核日期 年 月 日摘 要 分析了对线性表、栈、队列、字符串、树、图、查找、排序等理论知识的应用，对现实复杂问题的分析建模和解决方法！分析了针对系统的需求所要执行的解决方法的可行性，正确性。完成系统前需要进行问题描述、系统分析、设计建模、代码实现、调试修改，结果分析。设计哈希表实现电话号码查询系统是利用哈希表实现电话系统的快速查询，程序实现哈希表建表和查表，并实现对没有查找到的内容进行记录。利用编程实现电话号码查询系统，该系统具有录入联系人的姓名，电话号码，住址信息，查询联系人，保存记录以及清空记录，并且实

5、现利用散列显示联系人信息，包括姓名散列和电话号码散列。关键词：哈希表; 散列; 排序；联系人；电话号码 目 录 1需求分析12开发及运行平台23 概要设计34 详细设计55 调试分析166 测试结果187 结论22参考文献231需求分析（1）输入的形式和输入值的范围： 数据的输入在屏幕中进行，所输入的数据的格式为：姓名，住址，电话号码。用户使用时显示菜单，用户输入菜单选项完成操作。（2）输出的形式： 查找的结果显示在屏幕上，未被查找到的内容输出相应的提示信息。用户需要时，将哈希表显示在屏幕上。（3）程序所能达到的功能： 根据用户的要求，输入联系人的姓名，电话号码。住址，分别以姓名和电话号码作为

6、关键字生成哈希表。生成哈希表后用户可以根据相应的关键字进行数据的查找，若查找到对应的数据则将数据输出屏幕，若没有查找到对应的数据则将输出提示信息表示未找到联系人。在用户选择哈希表时，显示完整的哈希表。程序使用文字菜单的友好界面，在数据输入时对输入内容进行范围控制。（4）测试数据：在电脑屏幕中输入记录，令程序读入并分别以姓名和电话号码做为关键字生成哈希表，查找记录中原有的记录，查看输出数据，查找记录中没有的记录输出提示信息，查看整个哈希表的数据。清除所有的记录后再次输入信息查询，屏幕输出未查找到的提示信息，若录入新的信息后，可保存信息，查询，散列联系人信息。2开发及运行平台硬件：微型计算机。软件

7、：VC+6.0。具体操作如下：新建工程，添加相应的源文件，再编译，链接，执行！3 概要设计1.数据类型定义结构体类型存储每条记录。struct node /建节点 char name8; /用于存放姓名char address20; /用于存放地址char num11; /用于存放电话号码 node * next; ;2.主程序流程创建存放记录的结构体数组查找记录，分别可选择姓名查询和电话号码查询姓名散列号码散列清空记录保存记录选择退出系统3.各函数功能 int apend()； /添加节点 void create()； /新建电话号码的节点 void create2()； /新建姓名的节点

8、void find(char num11)； /通过电话号码查找用户信息 void find2(char name8)； /通过姓名查找用户信息 void hash(char num11)； /哈希函数，号码散列 void hash2(char name8)； /哈希函数，姓名散列 node* input()； /输入用户信息 void list()； /通过姓名查找显示用户信息 void list2() /通过电话号码查找显示列表4 详细设计4.1数据类型定义 struct node /建节点 char name8,address20; char num11; ; node * next;

9、/定义结构体1. 主要算法 /实现添加姓名，电话号码，住址的新的内存空间模块儿 int apend() node *newphone; node *newname; newphone=input(); newname=newphone; newphone->next=NULL; newname->next=NULL; hash(newphone->num); hash2(newname->name); newphone->next = phonekey->next; phonekey->next=newphone; newname->next =

10、 namkey2->next; namkey2->next=newname; return 0; / 新建电话号码节点函数void create() int i; phone=new pnode20; for(i=0;i<20;i+) phonei=new node; phonei->next=NULL; /新建名字节点函数void create2() int i; nam=new mingzi20; for(i=0;i<20;i+) nami=new node; nami->next=NULL; /通过电话号码查找用户信息函数void find(char

11、num11) hash(num); node *q=phonekey->next; while(q!= NULL) if(strcmp(num,q->num)=0) break; q=q->next; if(q) cout<<q->name<<" "<<q->address<<" "<<q->num<<endl; else cout<<"无此记录"<<endl; /通过姓名查找用户信息函数void fin

12、d2(char name8) hash2(name); node *q=namkey2->next; while(q!= NULL) if(strcmp(name,q->name)=0) break; q=q->next; if(q) cout<<q->name<<" "<<q->address<<" "<<q->num<<endl; else cout<<"无此记录"<<endl; / 哈希函数，用于电

13、话号码的散列功能void hash(char num11) int i = 3; key=(int)num2; while(numi!=NULL) key+=(int)numi; i+; key=key%20; /哈希函数，用于姓名的散列功能void hash2(char name8) int i = 1; key2=(int)name0; while(namei!=NULL) key2+=(int)namei; i+; key2=key2%20; /输入函数，用于输入用户的姓名，电话号码，住址node* input() /输入节点 node *temp; temp = new node; t

14、emp->next=NULL; cout<<" 请输入姓名："<<endl; cin>>temp->name; cout<<" 请输入地址："<<endl; cin>>temp->address; cout<<" 请输入电话："<<endl; cin>>temp->num; return temp; /显示列表函数，用于显示通过电话号码查找到的用户信息void list() int i; node *p;

15、 for(i=0;i<20;i+) p=phonei->next; while(p) cout<<p->name<<" "<<p->address<<" "<<p->num<<endl; p=p->next; /显示列表函数，用于显示通过姓名查找到的用户信息void list2() int i; node *p; for(i=0;i<20;i+) p=nami->next; while(p) cout<<p->name

16、<<" "<<p->address<<" "<<p->num<<endl; p=p->next; /菜单函数，实现客户选择菜单进行系统操作void menu() cout<<"= 欢迎进入设计哈希表查询电话号码系统 ="<<endl; cout<<endl;cout<<"- 0. 添加记录-"<<endl; cout<<"- 1. 查找记录-"&l

17、t;<endl; cout<<"- 2. 姓名散列-"<<endl; cout<<"- 3. 号码散列-"<<endl; cout<<"- 4. 清空记录-"<<endl; cout<<"- 5. 保存记录-"<<endl; cout<<"- 6. 退出系统-"<<endl;cout<<endl; cout<<"请输入你的选择（0，1，2

18、，3，4，5，6）"<<endl;2. 函数流程图图一 哈希函数实现姓名散列图二 哈希函数实现电话号码散列图三 输入函数图四 电话号码节点创建函数图五 姓名节点创建函数图六 通过电话查找显示函数图七 通过姓名查找显示函数图八 姓名查找函数图九 电话号码查找函数图十 保存用户信息函数图十一 主函数5 调试分析内容包括：1.测试环境在Windows 7环境下的Microsoft Visual C+ 6.02.模块调试 写入数据时，对数据的内容的控制需要特别注意。要注意其字符组合模式，比如生成名字是应该只有字幕，生成电话号码是应该只有数字，还要注意生成字符组合的长度限制，比如电话号码应该是11位，这可以在循环语句中进行控制。在哈希含查找时要注意取余的除数的一致，这是哈希表成立的关键点。3.复杂度分析 使用哈希表存储记录，在执行查找是可以快捷的进行查找。选用在哈希法和为随机探测再散列法。程序设定的哈希标长为50，文件数据长