散列表的设计与实现

1散列表的设计与实现一、作业要求：【问题描述】设计散列表实现电话号码查找系统。【基本要求】1)设每个记录有下列数据项：电话号码、用户名、地址；2)从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3)采用一定的方法解决冲突；4)查找并显示给定电话号码的记录；5)查找并显示给定用户名的记录。【进一步完成内容】1)系统功能的完善；2)设计不同的散列函数，比较冲突率；3)在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。二、设计分析：用散列表实现电话号码查找系统，采用姓名和电话号码为关键字，动态分配存储空间，根据姓名和电话号码分别进行哈希排序建立不同的数组分别存放姓名和电话号码，能实现电话号码信息的插入、删除、查找、保存等操作，采取线性探测法解决冲突。三、逻辑结构：电话号码查找系统，逻辑上应当是每个结点含有一个人所有的信息，在查找的时候可以通过不同的查找方式对不同的信息进行查找，人和人之间的关系应当是独立的，添加结点的时候对每个人由系统分配新的结点，但是不同人结点中所包含的信息则具有相同的格式，比如每个结点中的姓名、地址、电话号码都具有相同的格式，在进行物理存储的时候可以建立相同的数组来放置同类信息。四、存储结构：所设计的程序采用数组存放各类相同的信息，先建立数组进行初始化，再把不同的结点通过哈希排序以及线性探测的结果存放入对应的数组，建立的数组有两个，分别以姓名和电话号码建立哈希表，对信息进行存储，以后的各种操作，比如查找，散列等都建立在相应的哈希表的基础上，各个信息之间通过链表相连，在查找的时候可以充分利用哈希表查找的快速性，形象化的存储结构如下图：2五、算法设计：六、实现代码：#includestdio.h#includestdlib.h#includeiostream#includestring.h#includefstream#defineNULL0unsignedintkey;unsignedintkey1;unsignedintkey2;int*p;structnode//建节点{charname[8],address[20];charnum[11];node*next;};typedefnode*pnode;typedefnode*mingzi;node**phone;node**nam;node*a;usingnamespacestd;//使用名称空间hash(charnum[11])//建表，以人的电话号码为关键字，建立相应的散列表若哈希地址发生冲突，进行冲突处理。{inti=3,j;key1=(int)num[2];while(num[i]!=NULL)3{key1+=(int)num[i];i++;}key1=key1%20;for(j=0;j20;j++)//线性探测法解决冲突{key=(key1+j)%20;if(phone[key]-num==)break;}return(key);}hash2(charname[8])//建表，以人的姓名为关键字，建立相应的散列表//若哈希地址发生冲突，进行冲突处理{inti=1,j;key2=(int)name[0];while(name[i]!=NULL){key2+=(int)name[i];i++;}key2=key2%20;for(j=0;j20;j++)//线性探测法解决冲突{key=(key2+j)%20;if(phone[key]-name==)break;}return(key);}node*input()//输入节点{node*temp;temp=newnode;temp-next=NULL;cout输入姓名：endl;cintemp-name;cout输入地址：endl;cintemp-address;cout输入电话：endl;4cintemp-num;returntemp;}intapend()//添加节点{node*newphone;node*newname;newphone=input();newname=newphone;//newphone-next=NULL;//newname-next=NULL;newphone-next=phone[hash(newphone-num)]-next;phone[hash(newphone-num)]-next=newphone;newname-next=nam[hash2(newname-name)]-next;nam[hash2(newname-name)]-next=newname;return0;}voidcreate()//新建电话号码数组{inti;phone=newpnode[20];for(i=0;i20;i++){phone[i]=newnode;phone[i]-next=NULL;}}voidcreate2()//新建姓名数组{inti;nam=newmingzi[20];for(i=0;i20;i++){nam[i]=newnode;nam[i]-next=NULL;}}voidlist()//显示列表(号码散列){inti;node*p;for(i=0;i20;i++)5{p=phone[i]-next;while(p){coutp-name'_'p-address'_'p-numendl;p=p-next;}}}voidlist2()//显示列表（姓名散列）{inti;node*p;for(i=0;i20;i++){p=nam[i]-next;while(p){coutp-name'_'p-address'_'p-numendl;p=p-next;}}}voidfind(charnum[11])//查找用户信息（号码查找）{inti,j=0;node*p;for(i=0;i20;i++){p=phone[i]-next;while(p){if(strcmp(num,p-num)==0){coutp-name'_'p-address'_'p-numendl;j++;}p=p-next;}}if(j==0)cout无此记录endl;}6voidfind2(charname[8])//查找用户信息（姓名查找）{inti,j=0;node*p;for(i=0;i20;i++){p=nam[i]-next;while(p){if(strcmp(name,p-name)==0){coutp-name'_'p-address'_'p-numendl;j++;}p=p-next;}}if(j==0)cout无此记录endl;}voidDelete(charnum[11]){node*p;hash(num);p=phone[key]-next;phone[key]-next=p-next;}voidDelete1(charname[8]){node*p;hash2(name);p=nam[key]-next;nam[key]-next=p-next;}voidsave()//保存用户信息{inti;node*p;fstreamiiout(out.txt,ios::out);for(i=0;i20;i++){p=phone[i]-next;7while(p){iioutp-name_p-address_p-numendl;p=p-next;}}}voidmenu()//菜单{cout0.添加记录endl;cout1.查找记录endl;cout2.姓名散列endl;cout3.号码散列endl;cout4.清空记录endl;cout5.保存记录endl;cout6.删除信息endl;cout7.退出系统endl;}intmain(){cout欢迎使用电话号码查找系统endl;cout***************散列表的设计与实现****************endl;charnum[11];charname[8];create();create2();intsel;while(1){menu();cinsel;//输入选择项目操作if(sel==0){cout请输入要添加的内容:endl;apend();}elseif(sel==1){cout9号码查询，8姓名查询endl;8intb;cinb;if(b==9){cout请输入电话号码:endl;cinnum;cout输出查找的信息:endl;find(num);}elseif(b==8){cout请输入姓名:endl;cinname;cout输出查找的信息:endl;find2(name);}elseprintf(不合法操作！\n);}elseif(sel==2){cout姓名散列结果:endl;list2();}elseif(sel==3){cout号码散列结果:endl;list();}elseif(sel==4){cout列表已清空:endl;create();create2();}elseif(sel==5){cout通信录已保存:endl;save();}elseif(sel==6){intc;cout删除信息:endl;cout9.按号码删除8.按姓名删除endl;cinc;if(c==9){9cout请输入号码：endl;cinnum;Delete(num);}elseif(c==8){cout请输入姓名：endl;cinname;Delete1(name);}elsecout不合法操作！endl;cout信息已删除\nendl;}elseif(sel==7)return0;elsecout不合法操作！endl;}return0;}