哈希表实现号码查询实验报告

华北电力大学实验报告||实验名称哈希表课程名称数据结构||专业班级：学生姓名：学号：成绩：指导教师：实验日期：华北电力大学实验报告第页共页一、实验目的（1）掌握哈希表的基本操作。（2）掌握插入、删除、查找等运算，能够灵活应用这种数据存储结构。二、实验内容及要求1.实验要求设计哈希表实现电话号码查询系统。设计程序完成以下要求：（1）设每个记录有下列数据项：电话号码、用户名、地址；（2）从键盘输入各记录，以电话号码为关键字建立哈希表（至少要有12个以上的记录，哈希表的长度为8）；（3）采用链地址法解决冲突；（4）显示建立好的哈希表，对于学有余力的同学可以实现哈希表的查找。2.实验说明：（1）采用除留余数法进行哈希表的散列，即以电话号码作为主关键字，将电话号码的11位相加，按照模7取余；（2）解决冲突用链地址法。3.实验数据：（1）姓名：张三电话号码：[phone]地址：保定（2）姓名：李四电话号码：[phone]地址：石家庄……三、实验仪器与设备计算机，记事本，visualC++6.0四、问题分析与系统设计系统描述：设计哈希表实现电话号码查询系统。其中，电话号码的每个记录有三个数据项：电话号码、用户名和地址；以电话号码为关键字建立哈希表；假定哈希表的长度为8，采用链地址法解决冲突。处理信息：1.采用除留余数法进行哈希表的散列，即以电话号码为主关键字，将电话号码的11位相加，按照模7取余；2.解决冲突用链地址法。功能设计：1.通过哈希表的构造存储电话号码的相关信息；2.能够遍历哈希表，显示所有数据；3.通过电话号码查找哈希表，显示与该电话号码有关的所有信息；通过姓名查找哈希表，显示与该姓名有关的所有信息；算法设计：采用除留余数法进行哈希表的散列，解决冲突用链地址法。华北电力大学实验报告第页共页1.定义哈希表节点的结构体，包括数据域和指针域。#definelength8//lengthofliststructlist//list{structnode*lnext;//pointarecord}lis[length];structnode//recordnode{charname[8],address[20];charnum[11];structnode*next;};2.以电话号码为关键字，用除留余数法进行哈希表的散列，对7取模获得哈希地址。inthash(structnoderecord)//getkeybynum{intkey=0;for(inti=0;i11;i++){key=key+(int)(record.num[i]-'0');}key=key%7;returnkey;}3.插入电话记录。voidcreatenode()//createoraddanewnode{structnode*temp=newnode;temp-next=NULL;printf(请输入姓名:\n);scanf(%s,temp-name);printf(输入电话：\n);scanf(%s,temp-num);printf(输入地址：\n);scanf(%s,temp-address);intk=hash(*temp);structlist*p=&lis[k];if(p-lnext!=NULL)temp-next=p-lnext;p-lnext=temp;4.按电话号码查找记录。读入要查找的电话号码，计算得到哈希地址，在相应的哈希地址中寻找匹配节点，若找到，则输出节点信息，否则，提示未找到相关信息。华北电力大学实验报告第页共页voidfind(charnu[])//findtheinfoofanodebynum{intkey=0,a=1;for(inti=0;i11;i++){key=key+(int)(nu[i]-'0');}key=key%7;structnode*q=lis[key].lnext;while(q!=NULL){for(inti=0;i11;i++){if(nu[i]==q-num[i]){a=0;continue;}else{a=1;break;}}if(a==0){printf(Key:%d\n,key);printf(姓名:%s\t地址:%s\t电话:%s\n,q-name,q-address,q-num);break;}elseq=q-next;}if(a==1)printf(无此记录\n);}//的信息，则提示用户。}5.按电话号码删除记录。读入要删除的电话号码，计算得到哈希地址，在相应的哈希地址中寻找匹配节点，若找到，则删除节点信息，否则，提示未找到相关信息。voiddeletenode(charnu[]){intkey=0,a=1;for(inti=0;i11;i++)华北电力大学实验报告第页共页{key=key+(int)(nu[i]-'0');}key=key%7;structnode*q=lis[key].lnext;structnode*p=newnode;if(q==NULL)printf(无此记录\n);else{for(inti=1;;i++){for(intj=0;j11;j++){if(nu[j]==q-num[j]){a=0;continue;}else{a=1;break;}}if(a==0){if(i==1)lis[key].lnext=q-next;p-next=q-next;q=NULL;deleteq;printf(节点已删除\n);break;}else{p=q;q=q-next;}if(q==NULL)break;}if(a==1)printf(信息不存在\n);}华北电力大学实验报告第页共页}6.输出所有的信息。voidshowlist()//showlist{for(inti=0;ilength;i++){structnode*q=lis[i].lnext;printf(Key:%d\n,i);if(!q)printf(norecordnow\n);while(q){printf(%s\t%s\t%s\n,q-name,q-address,q-num);q=q-next;}}}五、实验结果输入电话号码信息，将电话记录存入电话号码查询系统中。然后进行号码查找，删除和显示，结果如下：华北电力大学实验报告第页共页六、总结与体会运用到的知识：1.哈希表的构造；2.哈希表的散列；3.哈希表的冲突处理方法；4.哈希表的查找；华北电力大学实验报告第页共页5.邻接表的构造。遇到的问题：哈希地址的求取，以及冲突的解决。解决方法：哈希地址以电话号码为关键字，将电话号码的11位相加，对7取模得到哈希地址。七、实验代码#includestdio.h#includestring.h#includeiostream.h#definelength8//lengthofliststructlist//list{structnode*lnext;//pointarecord}lis[length];structnode//recordnode{charname[8],address[20];charnum[11];structnode*next;};inthash(structnoderecord)//getkeybynum{intkey=0;for(inti=0;i11;i++){key=key+(int)(record.num[i]-'0');}key=key%7;returnkey;}voidcreatenode()//createoraddanewnode{structnode*temp=newnode;temp-next=NULL;printf(请输入姓名:\n);scanf(%s,temp-name);printf(输入电话：\n);scanf(%s,temp-num);printf(输入地址：\n);scanf(%s,temp-address);intk=hash(*temp);structlist*p=&lis[k];if(p-lnext!=NULL)temp-next=p-lnext;p-lnext=temp;华北电力大学实验报告第页共页}voidshowlist()//showlist{for(inti=0;ilength;i++){structnode*q=lis[i].lnext;printf(Key:%d\n,i);if(!q)printf(norecordnow\n);while(q){printf(%s\t%s\t%s\n,q-name,q-address,q-num);q=q-next;}}}voidfind(charnu[])//findtheinfoofanodebynum{intkey=0,a=1;for(inti=0;i11;i++){key=key+(int)(nu[i]-'0');}key=key%7;structnode*q=lis[key].lnext;while(q!=NULL){for(inti=0;i11;i++){if(nu[i]==q-num[i]){a=0;continue;}else{a=1;break;}}if(a==0){printf(Key:%d\n,key);printf(姓名:%s\t地址:%s\t电话:%s\n,q-name,q-address,q-num);break;华北电力大学实验报告第页共页}elseq=q-next;}if(a==1)printf(无此记录\n);}voiddeletenode(charnu[]){intkey=0,a=1;for(inti=0;i11;i++){key=key+(int)(nu[i]-'0');}key=key%7;structnode*q=lis[key].lnext;structnode*p=newnode;if(q==NULL)printf(无此记录\n);else{for(inti=1;;i++){for(intj=0;j11;j++){if(nu[j]==q-num[j]){a=0;continue;}else{a=1;break;}}if(a==0){if(i==1)lis[key].lnext=q-next;p-next=q-next;q=NULL;deleteq;printf(节点已删除\n);break;华北电力大学实验报告第页共页}else{p=q;q=q-next;}if(q==NULL)break;}if(a==1)printf(信息不存在\n);}}voidmenu()//chooseoperation{printf(1.添加记录\n);printf(2.查找记录\n);printf(3.号码显示\n);printf(4.号码删除\n);printf(5.退出系统\n);}voidmain(){structlistlis[length];for(inti=0;ilength;i++){lis[i].lnext=NULL;}intsel;//selectforoperationwhile(1){menu();scanf(%d,&sel);if(sel==1)//addnode{createnode();}if(sel==2)//findinfo{charnumb[11];printf(请输入电话号码:\n);scanf(%s,numb);printf(输出查找的信息:\n);find(numb);}if(sel==3)//showlist华北电力大学实验报告第页共页{printf(号码显示结果:\n);showlist();}if(sel==4){charnumb[11];printf(请输入电话号码:\n);scanf(%s,numb);deletenode(numb);}if(sel==5)break;}}