哈希表实验报告

第1页数据结构课程设计报告院系：专业：班级：学号：姓名：教师：时间：第2页目录一、设计要求......................................3㈠、问题描述.............................................3㈡、需求分析.............................................3一、概要设计.....................................3㈠、存储结构设计..........................................3㈡、系统功能设计..........................................4三、模块设计.......................................6㈠、模块设计..............................................6㈡、系统子程序及功能设计..................................6㈢、函数主要调用关系图....................................6四、详细设计.......................................7五、系统实现......................................13㈠、源代码.........................................13㈡、调试分析.......................................31㈢、输出界面.......................................45六、设计总结......................................46第3页一、设计要求㈠、问题描述设计散列表实现电话号码查找系统(1)设每个记录有下列数据项：电话号码、用户名、地址；(2)从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；(3)采用一定的方法解决冲突；(4)查找并显示给定电话号码的记录；(5)查找并显示给定用户名的记录。㈡、需求分析（1）用record结构体表示联系人的基本资料姓名、电话和地址等，用HashTable结构体构造哈希表；（2）在创建联系人时从键盘输入记录存储在record结构体数组中，分别用两个哈希函数以电话号码和姓名为关键字将record首地址存入哈希表中，方便添加、删除、修改和查找；（3）采用二次探测再散列法解决冲突，如果无法解决冲突则显示冲突并进行下一操作；（4）查找到指定记录后通过HashTable结构体指针指向record中的记录并打印出来。二、概要设计㈠、存储结构设计联系人记录定义：typedefstructpepole{charname[Max_name]];//姓名chartele[Max_tele];//电话charadd[Max_add];//地址}Record;因为电话号码查询系统的查找功能比较多，相对于链表数组查找更方便快速，当然这样就会存在数组扩容的问题。可以使用realloc，但是realloc并不保证调整后的内存空间和原来的内存空间保持同一内存地址,相反，realloc返回的指针很可能指向一个新的地址，之前的内容会被删掉。所以必须将realloc的返回值重新复值给指向哈希表的指针。哈希表定义：typedefstruct第4页{Record*elem[HASHSIZE];//数据元素存储地址intsize;//哈希表容量intcount;//哈希表当前存储量}HashTable;㈡、系统功能设计总流程图：部分算法流程图：电话号码查询系统创建联系人建立哈希表电话号码哈希表姓名哈希表添加联系人查找联系人显示联系人删除联系人修改联系人显示联系人删除联系人查找联系人修改联系人添加联系人第5页解决冲突：哈希查找：开始i=c/2+1iHASHSIZE哈希地址=0冲突次数是否为偶数？冲突次数加一计算哈希地址（+i*i）返回哈希地址YYY冲突次数加一计算哈希地址（-i*i）N发生冲突，重置iNN返回False开始输入要查询的电话号码或者姓名通过哈希函数获得关键字的KEY哈希表KEY不为空且与关键字不同解决冲突返回冲突次数和KEY地址Y哈希表KEY为空且关键字相同输出联系人信息输出查无此人NY结束结束第6页三、模块设计㈠、模块设计本程序共用包含三个模块：主程序模块、创建哈希表模块和增删改除运算模块。其调用关系如图：㈡、系统子程序及功能设计本程序共设置17个子程序，各子程序的函数名及功能说明如下;1、voidMenu();//菜单2、voidCreate(Record*record);//创建新的通讯录3、voidCreateHash1(HashTable*H,Record*record);//以姓名为关键字，建立相应的哈希表4、voidCreateHash2(HashTable*H,Record*record);//以姓名为关键字，建立相应的哈希表5、intHash1(charname[]);//哈希函数(姓名)6、intHash2(chartele[]);//哈希函数(电话号码)7、voidAdd(Record*record);//添加联系人8、voidDelete(HashTable*H,int&c);//删除联系人9、voidAlter(HashTable*H,int&c);//修改联系人10、voidSearchHash1(HashTable*H,int&c);//在通讯录里查找姓名关键字，并打印出来11、voidSearchHash2(HashTable*H,int&c);//在通讯录里查找电话号码关键字，并打印出来12、intcollision(intp,int&c);//冲突处理函数，用于解决冲突13、inteq(charx[],chary[]);//关键字比较14、voidShow(Record*record);//显示通讯录15、voidLoad();//读取通讯录16、voidSave(HashTable*H);//保存通讯录17、voidQuit();//退出㈢函数主要调用关系图主程序模块创建哈希表模块增删改除模块NMenu()Main()所有子函数第7页四、详细设计系统主要子程序详细设计(1)主函数设计模块intmain(intargc,char*argv[]){while(en!=11){switch(en){调用相应函数执行相应操作，并输出操作结果}}判断哈希表是否满，若满则扩容return0;}(2)创建通讯录voidCreate(Record*record){system(CLS);//调用DOS命令CLS能够清屏FILE*fp1,*fp2;//定义指向文件的指针if((fp1=fopen(record.txt,r))!=NULL)//如果存在文件，打开文件，只读{fclose(fp1);}//关闭文件else{//如果不存在文件，创建一个record.txt文件fp2=fopen(record.txt,w);//以写的方式打开文件fclose(fp2);}//关闭文件cout\t\t通讯录创建成功！endl;cout\t\t输入要添加的个数：;cinnum;for(inti=0;inum;i++){//从键盘输入联系人信息intii=0;cout\n\t\t请输入第i+1个记录的姓名（不超过4个字）：;cinrecord[i].name;//保存在record结构体数组中for(intj=0;ji&&i0;j++){//每次输入姓名后判断是否重复if(eq(record[j].name,record[i].name)==1){cout\t\t第j+1个和第i+1个联系人重复！请重新输入：;coutendl;//一旦重复，提示重复并请求重新输入ii=1;//标示有重复，中断其余的信息输入i--;}}//同时删去刚刚输入的信息if(ii==0){//表示没有重复元素，可以继续输入cout\t\t请输入第i+1个记录的电话号码（不超过12个数字）：;cinrecord[i].tele;第8页cout\t\t请输入第i+1个记录的地址（不超过10个字）：;cinrecord[i].add;}}cout\t\t添加成功！endl;}(3)建立哈希表voidCreateHash1(HashTable*H,Record*record){//以姓名为关键字，建立相应的哈希表system(CLS);//调用DOS命令CLS能够清屏inti,p=-1,c,pp;for(i=0;inum;i++){c=0;//定义冲突次数初值为0p=Hash1(record[i].name);//获得关键字的哈希表地址pp=p;while(H-elem[pp]!=NULL){//若哈希表地址不为空pp=collision(p,c);//解决冲突if(pp0){//返回值为负，冲突无法解决cout第i+1记录无法解决冲突endl;//显示第几次冲突无法解决continue;//无法解决冲突，跳入下一循环}}H-elem[pp]=&(record[i]);//求得哈希地址，将信息存入哈希表中H-count++;//同时哈希表计数器加一cout第i+1个记录冲突次数为c.\n;}//需要显示冲突次数时输出cout哈希表（姓名）组建完成！endl;cout此哈希表容量为HASHSIZEendl;cout当前哈希表存储记录个数为H-countendl;cout\n请按ENTER进入添加通讯录菜单endl;}(4)解决冲突intcollision(intp,int&c)//参数p为哈希表中的存储位置，&c为二次探测增量地址，每次不变为0{//冲突处理函数，采用二次探测再散列法解决冲突inti,q;i=c/2+1;while(iHASHSIZE){if(c%2==0)//偶数加上i的平方{c++;q=(p+i*i)%HASHSIZE;if(q=0)returnq;//返回哈希地址elsei=c/2+1;//发生冲突，重置i}else//奇数减去i的平方{q=(p-i*i)%HASHSIZE;第9页c++;if(q=0)returnq;//返回哈希地址elsei=c/2+1;//发生冲突，重置i}}returnFAILURE;//无法解决冲突，返回failure}(5)查找voidSearchHash1(HashTable*H,int&c){//在通讯录里查找姓名关键字，若查找成功，显示信息system(CLS);charname[10];cout\n\t\t请输入要查找记录的姓名：;cinname;intp,pp;p=Hash1(name);//将关键字转换得到其哈希地址pp=p;while((H-elem[pp]!=NULL)&&(eq(name,H-elem[pp]-name)==0))pp=collision(p,c);//如果此哈希地址不为空且姓名不相同，则继续寻找直到哈希地址为空或者姓名相同if((H-elem[pp]!=NULL)&&(eq(name,H-elem[pp]-name)==1)){//哈希地址不为空且姓名相同，说明找到了cout\t\t查找成功！\n\t\t查找过程冲突次数为c．\n\n\t\t以下是您需要要查找的信息：\n;cout\t\t姓名：H-elem[pp]-nameendl;cout\t\t电话号码：H-elem[pp]-teleendl;cout\t\t联系