27数据结构课程设计通讯录、电话号码查询系统

《数据结构》课程设计报告学院（系）：班级：学生姓名：学号指导教师：2012年12月17日到2013年1月2日通讯录电话号码查询系统一、课程设计概述：本次数据结构课程设计共完成两个题：电话号码查询系统、通讯录。使用语言：C编译环境：VC6.0二、课程设计题目一[实验内容]电话号码查询系统[问题描述]设计散列表实现电话号码查找系统。[需求分析](1)设每个记录有下列数据项：电话号码、用户名、地址；(2)从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；(3)采用一定的方法解决冲突；(4)查找并显示给定电话号码的记录；(5)查找并显示给定用户名的记录。整个系统必须满足系统功能要求；设计不同的散列函数，比较冲突率；在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。[概要设计]voidgetin(Record*a)//键盘输入联系人的信息voidShowInformation(Record*a)//显示输入的用户信息Statuscollision(intp,int&c)//冲突处理函数，采用二次探测再散列法解决冲突voidCreateHash(HashTable*H,Record*a)//建表,若哈希地址冲突，进行冲突处理voidSearchHash(HashTable*H,int&c)//在通讯录里查找关键字voidSave()//保存voidmain_menu()[存储结构]typedefstruct{//记录NAname;NAtel;NAadd;}Record;typedefstruct{//哈希表Record*elem[HASHSIZE];//数据元素存储基址intcount;//当前数据元素个数intsize;//当前容量}HashTable;[流程图]voidmain_menu()voidgetinvoidvoidvoidStatusShowInformationCreateHashSearchHashcollision[详细设计]#includeiostream//cout,cin语句的头文件#includestdlib.h//清屏函数头文件：使用csl时调用system#includestring//字符串头文件#includestdio.h#includefstream#defineMAXSIZE100//电话薄记录的数量#defineMAX_SIZE50//用户名、电话号码、地址的最大长度#defineHASHSIZE400//定义表长#defineSUCCESS1//查找#defineUNSUCCESS-1#defineLENsizeof(HashTable)//哈希表的长度usingnamespacestd;typedefintStatus;//typedef用来定义类型的别名。此处用status作为int别名，目的表达int变量是一个状态变量。typedefcharNA[MAX_SIZE];//NA作为char的别名typedefstruct{//自定义一个记录用户名、电话号码、联系地址的结构体的别名recordNAname,tel,add,way;}Record;Recorda[HASHSIZE];typedefstruct{//散列表Record*elem[HASHSIZE];//数据元素存储地址intcount;//数据元素个数intsize;//容量}HashTable;Statuseq(NAx,NAy){//关键字比较，相等返回SUCCESS；否则返回UNSUCCESSif(strcmp(x,y)==0)//2个字符串的大小比较s1=s2，strcmp(s1,s2)==0;s1s2,strcmp(s1,s2)==1;s1s2,strcmp(s1,s2)==-1;returnSUCCESS;elsereturnUNSUCCESS;}StatusNUM_BER;//记录的个数voidgetin(Record*a){//键盘输入联系人的信息,Record*调用Record函数；a是参数cout请输入要添加的联系人的个数：\n;cinNUM_BER;inti;for(i=0;iNUM_BER;i++){cout请输入第i+1个记录的用户名:\n;cina[i].name;cout请输入第i+1个记录的电话号码:\n;cina[i].tel;cout请输入第i+1个记录的地址:\n;cina[i].add;}}voidShowInformation(Record*a)//显示输入的用户信息{inti;for(i=0;iNUM_BER;i++)cout\n第i+1个用户信息:\n姓名：a[i].name\n电话号码：a[i].tel\n联系地址：a[i].add\n--------\n;}longfold(NAs)//人名的折叠处理:将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址{char*p;longsum=0;NAss;strcpy(ss,s);//复制字符串，不改变原字符串的大小写strupr(ss);//将字符串ss转换为大写形式p=ss;while(*p!='\0')sum+=*p++;returnsum;}intHash1(NAstr){//哈希函数longn;intm;n=fold(str);//先将用户名进行折叠处理m=n%HASHSIZE;//折叠处理后的数，用除留余数法构造哈希函数returnm;//并返回模值}intHash2(NAstr){//哈希函数longn;intm;n=atoi(str);//把字符串转换成整型数.m=n%HASHSIZE;//用除留余数法构造哈希函数returnm;//并返回模值}Statuscollision(intp,int&c){//冲突处理函数，采用二次探测再散列法解决冲突inti,q;i=c/2+1;while(iHASHSIZE){if(c%2==0){c++;q=(p+i*i)%HASHSIZE;if(q=0)returnq;elsei=c/2+1;}else{q=(p-i*i)%HASHSIZE;c++;if(q=0)returnq;elsei=c/2+1;}}returnUNSUCCESS;}intsearchHash(HashTable*&H,NAkey,int&p,int&c,intway){if(way==1){p=Hash1(key);while(H-elem[p]!=NULL&&!eq(key,H-elem[p]-name))//若哈希地址冲突，进行冲突处理collision(p,++c);if(eq(key,H-elem[p]-name))return1;elsereturn0;}else{p=Hash2(key);while(H-elem[p]!=NULL&&!eq(key,H-elem[p]-tel))//若哈希地址冲突，进行冲突处理collision(p,++c);if(eq(key,H-elem[p]-tel))return1;elsereturn0;}}//建表,若哈希地址冲突，进行冲突处理voidCreateHash(HashTable*H,Record*a){cout\n〓〓〓〓〓〓建立散列表〓〓〓〓〓〓〓;cout\n⑴.以姓名建立散列表(再散列法解决冲突);cout\n⑵.以电话号码建立散列表(再散列法解决冲突);cout\n☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆;cout请输入选择:;intnum,i,p=-1,c;cinnum;for(i=0;iNUM_BER;i++){c=0;if(num==1){p=Hash1(a[i].name);while(H-elem[p]!=NULL&&!eq(a[i].name,H-elem[p]-name))//若哈希地址冲突，进行冲突处理collision(p,++c);}else{p=Hash2(a[i].tel);while(H-elem[p]!=NULL&&!eq(a[i].tel,H-elem[p]-tel))//若哈希地址冲突，进行冲突处理collision(p,++c);}H-elem[p]=a+i;//求得哈希地址，将信息存入H-count++;cout第i+1个记录冲突次数为c。\n;//需要显示冲突次数时输出}cout\n建表完成!\n此哈希表容量为HASHSIZE,当前表内存储的记录个数为H-count.\n;}//查找用户名和电话号码的记录；voidSearchHash(HashTable*H,int&c){//在通讯录里查找关键字，若查找成功，显示信息//c用来记录冲突次数,查找成功时显示冲突次数NAtype;intp;cout\n〓〓〓〓〓〓查找并显示用户信息记录〓〓〓〓〓〓〓;cout\n⑴.查找并显示给定用户名的记录;cout\n⑵.查找并显示给定电话号码的记录;cout\n☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆;cout请输入选择:;intnum;cinnum;switch(num){case1:cout\n请输入要查找的用户名：\n;cintype;searchHash(H,type,p,c,1);if(eq(type,H-elem[p]-name)==1){cout\n查找成功！以下是您需要要查找的信息：\n\n;cout姓名：H-elem[p]-name\n电话号码：H-elem[p]-tel\n联系地址：H-elem[p]-add\n;}elsecout\n对不起，该用户不存在\n;break;case2:cout\n请输入要查找电话号码：\n;cintype;searchHash(H,type,p,c,2);if(eq(type,H-elem[p]-tel)==1){cout\n查找成功！以下是您需要要查找的信息：\n\n;cout姓名：H-elem[p]-name\n电话号码：H-elem[p]-tel\n联系地址：H-elem[p]-add\n;}elsecout\n对不起，该用户不存在\n;break;default:cout输入错误，请重新输入!;}}voidSave(){//保存ifstreamin;ofstreamout;out.open(123.txt);printf(\n保存成功!);for(inti=0;iNUM_BER;i++){out姓名：a[i].name\n电话号码：a[i].tel\n联系地址：a[i].add\n;}return;}voidmain_menu(){intc,flag=1;////定义一个布尔型变量flag并初始化为真(true)HashTable*H;H=(HashTable*)malloc(LEN);for(inti=0;iHASHSIZE;i++)H-elem[i]=NULL;H-size=HASHSIZE;H-count=0;while(1){//while使电话查询系统执行后返回主菜单的界面system(cls);cout\n〓〓〓〓〓〓↖(^ω^)↗欢迎使用电话号码查找系统〓〓〓〓〓〓〓;cout\n⑴.添加用户信息;cout\n⑵.读取所有用户信息;cout\n⑶.建立散列表(再散列法解决冲突);cout\n⑷.查找并显示给定用户的记录;cout\n⑸.保存;cout\n⑹.退出;cout\n提示：进行4操作前请先进行3操作.否