《程序设计与算法综合训练》设计报告项目五.doc

程序设计与算法综合训练设计报告项目五学号：E11514062 姓名：孙祺 年级： 2015级 专 业：计算机科学与技术项目名称：通讯录查询系统的设计与实现 完成日期：2016年7月4日1需求分析在该部分中根据设计题目的要求，充分地分析和理解问题，叙述系统的功能要求，明确问题要求做什么？限制条件是什么？1问题描述：为某个单位建立一个员工通讯录管理系统，可以方便查询每一个员工的电话与地址。设计散列表存储，设计并实现通讯录查找系统。2基本要求（1）每个记录有下列数据项：电话号码、用户名、地址；（2）从键盘输入各记录，分别以电话号码为关键字建立散列表；（3）采用二次探测再散列法解决冲突；（4）查找并显示给定电话号码的记录；（5）通讯录信息文件保存。（6）按照题意要求独立进行设计，设计结束后按要求写出设计报告。2概要设计说明本程序中用到的所有抽象数据类型的定义。主程序的流程以及各程序模块之间的层次(调用)关系。 (1) 数据结构 在拉链法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成，链地址法结点结构如图：(2) name16num11address20next(3) 其中name16和num11是分别为以电话号码和用户名为关键字域，存放关键字；address20(4) 为结点的数据域，用来存储用户的地址。Next指针是用来指向下一个结点的地址。主要算法的流程图如下：(5) 初始化散列链表（1）并为其动态分配内存空间(6) 初始化散列链表（2）并为其动态分配内存空间19I开始建立新结点temp把tempnext赋为空输入信息结束开始i=0i20p-phoneinextp!=null输入结点信息p=pnext结束i+开始取整型numi给key从3开始取i值Numi!=0Key=key+(int)numii+Key=key%20结束开始取整型name0给key2从0开始取i值namei!=0Key2+=nameii+Key2=key2%20结束开始申请新的结点newphone newnameNewphone=input()Newname指向 newphone调用HASH函数调用HASH2函数拉链法处理冲突用户名为关键字输入信息结束开始申请新结点q指向phonekeynextq不为空q=qnextq不为空输出记录输出结点信息结束调用HASH函数N(2)程序模块1. 输入节点信息 ，建立结点，并将结点的next指针指空2. 添加节点3.哈希函数4. 在以电话号码为关键字的哈希表中查找用户信息5. 保存用户信息6.主函数(3) 各模块之间的调用关系以及算法设计3. 详细设计首先定义结点结构体类型，在拉链法中，每个结点对应一个链表结点，它由三个域组成，而由于该程序需要分别用电话号码和用户名为关键字建立哈希表，所以该链表结点它是由四个域组成 name16num11address20next其中name16和num11是分别为以电话号码和用户名为关键字域，存放关键字；address20为结点的数据域，用来存储用户的地址。next指针是用来指向下一个结点的地址。#include 用来输入/输出文件流类包含的文件是fstream。unsigned int key由于题目要求以电话号码为关键字，所以在此设计的关键字。其次，设计hash（）函数，以电话号码为关键字建立哈希函数hash(char num11)。哈希函数的主旨是将电话号码的十一位数字全部加起来，然后在对20求余。将计算出来的数作为该结点的地址赋给key。以用户名为关键字建立哈希函数hash2(char name8)。利用强制类型转换，将用户名的每一个字母的ASCLL码值相加并且除以20后的余数。将计算出来的数作为该结点的地址赋给key2。再次，建立结点，并添加结点，利用拉链法解决冲突。建立结点应包括动态申请内存空间。向结点中输入信息。同时将结点中的next指针等于null。添加结点，首先需要利用哈希函数计算出地址即关键字，其次将该结点插入以关键字为地址的链表后，以电话号码为关键字调用void hash(char num11)函数，并且将结点插入对应的散列链表中。并且，需要建立散列链表的函数，动态申请一定的空间，用于动态申请散列链表。void create()用来动态创建以电话号码为关键字的链表数组。同样，需要显示链表的函数，利用for循环和while语句将表中信息按要求输出来。想要实现查找功能，同样需要查找函数，以电话号码为关键字，首先，需要利用hash函数来计算出地址。再依次对比，比较其电话号码是否相同。如果找不到与之对应相同的，则输出“无记录”。哈希函数void hash(char num11) int i = 3; key=(int)num2; while(numi!=NULL) key+=(int)numi; i+; key=key%20; void hash2(char name16) int i = 1; key2=(int)name0; while(namei!=NULL) key2+=(int)namei; i+; key2=key2%20; 查找函数void find(char num11) hash(num); node *q=phonekey-next; while(q!= NULL) if(strcmp(num,q-num)=0) break; q=q-next; if(q) printf(%s,q-name); printf(%s,q-address); printf(%s,q-num); else printf(无此记录n); void find2(char name16) hash2(name); node *q=namkey2-next; while(q!= NULL) if(strcmp(name,q-name)=0) break; q=q-next; if(q) printf(%s,q-name); printf(%s,q-address); printf(%s,q-num); else printf(无此记录n); 保存函数void save() int i; node *p; for(i=0;inext; while(p) fstream iiout(fq, ios:out); iioutname_address_numnext; 读取函数void Load() system(CLS); ifstream inFile; inFile.open(fq); string str; if(inFile.is_open() while(!inFile.eof() getline(inFile, str, n); cout str endl; inFile.close(); getchar();4. 测试与分析5. 总结本次实验存在以下几个问题：1.对于文件的保存和读取存在问题；2,本次实验中，对于文件的保存需要每次保存只能保存一个6. 附录#include #include #include using namespace std;FILE *fq; #define NULL 0 unsigned int key; unsigned int key2;int *p; struct node char name16,address20; char num11; node * next; ; typedef node* pnode; typedef node* mingzi; node *phone; node *nam; node *a; void hash(char num11) int i = 3; key=(int)num2; while(numi!=NULL) key+=(int)numi; i+; key=key%20; void hash2(char name16) int i = 1; key2=(int)name0; while(namei!=NULL) key2+=(int)namei; i+; key2=key2%20; node* input() node *temp; temp = new node; temp-next=NULL; printf(输入姓名：n); scanf(%s,temp-name);printf(输入地址：n); scanf(%s,temp-address);printf(输入电话：n); scanf(%s,temp-num);return temp; 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 = namkey2-next; namkey2-next=newname; return 0; void create() int i; phone=new pnode20; for(i=0;inext=NULL; void create2() int i; nam=new mingzi20; for(i=0;inext=NULL; void list() int i; node *p; for(i=0;inext; while(p) printf(%s,p-name); printf(%s,p-address); printf(%s,p-num); p=p-next; void list2() int i; node *p; for(i=0;inext; while(p) printf(%s,p-name); printf(%s,p-address); printf(%s,p-num); p=p-next; void find(char num11) hash(num); node *q=phonekey-next; while(q!= NULL) if(strcmp(num,q-num)=0) break; q=q-next; if(q) printf(%s,q-name); printf(%s,q-address); printf(%s,q-num); else printf(无此记录n); void find2(char name16) hash2(name); node *q=namkey2-next; while(q!= NULL) if(strcmp(name,q-name)=0) break; q=q-next; if(q) printf(%s,q-name); printf(%s,q-address); printf(%s,q-num); else printf(无此记录n); void save() int i; node *p; for(i=0;inext; while(p) fstream iiout(fq, ios:out); iioutname_address_numnext; void Load() system(CLS); ifstream inFile; inFile.open(fq); string str; if(inFile.is_open() while(!inFile.eof() getline(inFile, str, n); cout str endl; inFile.close(); getchar();int main() int n;char num11; char name16; create(); create2(); doprintf(*员工通讯录*n);printf( 1.添加记录n);printf( 2.号码散列n);printf( 3.查找记录n);printf( 4.清空记录n);printf( 5.保存记录n);printf( 6.读取记录n);printf( 7.退出系统n);printf(*n);printf(请输入要进行的操作：);scanf(%d,&n);switch(n)case 1:printf(请输入要添加的内容:n); apend(); break;case 2:printf(姓名散列结果:n);list2();printf(号码散列结果:n);list(); break; case 3:printf(输入 “1 ”姓名查询，输入“2”号码查询n);int a; scanf(%d,&a); if(a=2) printf(请输入电话号码: