设计散列表实现电话号码查找系统。

华北科技学院课程设计说明书学号：班级:网络B15-1姓名:设计题目:散列表的设计与实现设计地点:___________________________设计时间:2017-2-27至2017-3-10成绩评定：1、工作量：A（），B（），C（），D（）,F()2、难易度：A（），B（），C（），D（）,F()3、答辩情况：A（），B（），C（），D（）,F()4、报告规范度：A（），B（），C（），D（）,F()5、学习态度：A（），B（），C（），D（）,F()总评成绩:___________________________指导教师:朱冬梅一、问题描述与需求分析1、问题描述设计散列表实现电话号码查找系统。2、功能需求分析1)每个记录有下列数据项：电话号码、用户名、地址；2)从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3)采用一定的方法解决冲突；4)查找并显示给定电话号码的记录；5)查找并显示给定用户名的记录。6)在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。二、概要设计1、总体设计思路程序的总体实现思路、方法：本程序使用了链地址法和开放定址法处理冲突，可以实现从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；查找并显示给定电话号码的记录；查找并显示给定用户名的记录；计算使用不同方法处理冲突时的平均查找长度。当使用链地址法处理冲突，电话号码为关键字建立散列表时，使用除留余数法(t=e-number%n)，确定哈希地址。当使用链地址法处理冲突，用户名为关键字建立散列表时，把储存用户名的字符数组（name）的0号位置的字符(name[0])强制转换为int类型(i)，即i=（int）name[0],再使用除留余数法确定哈希地址(i=i%n，n=13)。当使用开放定址法处理冲突，电话号码为关键字建立散列表时，增量序列取用线性探测再散列法。当使用开放定址法处理冲突，用户名为关键字建立散列表时，把储存用户名的字符数组（name2）的0号位置的字符(name2[0])强制转换为int类型(e)，即e=(int)name[0],使用开放定址法取得哈希地址，如果产生冲突增量取用线性探测再散列法。程序总的功能结构图。2、模块简介链地址法：voidhashlistinit(newnode**p)//初始化散列表voidhashinputname(newnode**p)//添加记录（以用户名为关键字）voidhashshow2name(newnode**p)//查询记录（以用户名为关键字）voidhashinput(newnode**p)//添加记录（以号码为关键字）voidhashshow(newnode**p)//查询记录（以号码为关键字）voidASL(newnode**p)//计算ASL用户名为关键字号码为关键字添加查询用户名为关键字号码为关键字用户名为关键字号码为关键字添加查询用户名为关键字号码为关键字链地址法开放定址法电话号码查找系统初始化散列表记算ASL开放定址法voidhashlistinit2(anode3w)//初始化散列表voidhashinput2(anode3w)//添加记录（以号码为关键字）voidhashshow2(anode3w)//查询记录（以号码为关键字）voidhashinputname2(anode3w{//添加记录（以用户名为关键字）voidhashshow2name2(anode3w)//查询记录（以用户名为关键字）voidASL2(anode3w)//计算ASLintscan()//菜单显示函数intscan2(){//菜单显示函数三、详细设计1、数据结构设计链地址法：typedefstructnode{0intnumber;charaddress[size];charname[size];structnode*next;}newnode,*anode;13开放定址法：typedefstructnode2{intnumber2;charaddress2[size];charname2[size];intv;//冲突次数}newnode2,*anode2;电话号码地址名字指向下一个结点电话号码地址名字记录使用开放定址法时的冲突次数typedefstructnode3{anode2q;//信息录入数组inti;//判断存储空间intj;//表长}newnode3,*anode3;2、算法分析与实现开放定址法添加记录（以用户名为关键字）使用开放定址法，以用户名为关键字，添加记录当输入的电话号码不为-1时，输入姓名（英文），把姓名的第一个英文字母（char型）强制转换为整型e,再使用开放定址法获取哈希地址，增量取用线性探测再散列法。YNNYYYNNYNYY指向（newnod型数组）储存录入信息的数组判断存储空间是否已满记录表长e=（(int)a[0]+k）%表长该位置是否为空?在该位置插入数据输入地址K=k+1输入地址在该位置插入数据输出内存已满结束e=(int)a[0]%表长该位置是否为空?哈希表是否已满？K=1输入姓名（chara[100]）d=-1?开始输入电话号码d四、运行结果和调试分析测试数据：姓名住址电话号码Fu云南19Yuan河北14Dong山西23链地址法：用户名为关键字建立散列表：ASL=1以号码为关键字建立散列表：ASL=1开放定址法：用户名为关键字建立散列表：ASL=1以号码为关键字建立散列表：ASL=1运行结果图。1.选用建表方法，初始化散列表。——————————链地址法2.添加记录（以用户名为关键字）——————————链地址法3.查询记录（以用户名为关键字）——————————链地址法4.计算ASL——————————链地址法5.添加记录（以号码为关键字）——————————链地址法6.查询记录（以号码为关键字）——————————链地址法7.切换开放定址法8.初始化散列表，添加记录（以用户名为关键字）—————开放定址法9.查询记录（以用户名为关键字）——————————开放定址法10.计算ASL——————————开放定址法11.添加记录（以号码为关键字）——————————开放定址法12.查询记录（以号码为关键字）——————————开放定址法13.退出系统五、总结体会课程设计使我对数据结构课程的理解更深入，也能够发现自己平时不太注意的语法错误。当遇到问题时就翻书，或者上网查资料。在程序调试的过程中也能够完善系统。在课程设计过程中，使我的思路更为开拓。参考文献[1]严蔚敏，吴伟民编著．《数据结构》（C语言版）．清华大学出版社。[2]孙改平，王德志编著，《C语言程序设计》，清华大学出版社。程序源码：#includeiostream#includestdio.h#includestdlib.h#includestring.h#definesize100#definen13typedefstructnode{intnumber;charaddress[size];charname[size];structnode*next;}newnode,*anode;typedefstructnode2{intnumber2;charaddress2[size];charname2[size];intv;//冲突次数}newnode2,*anode2;typedefstructnode3{anode2q;//信息录入数组inti;//判断存储空间intj;//表长}newnode3,*anode3;voidhashlistinit(newnode**p){//初始化散列表链地址法inti;for(i=0;in;i++){p[i]=NULL;}printf(亲，散列表已初始化完毕\n);}voidhashinputname(newnode**p){//添加记录（以用户名为关键字）链地址法inti,v;printf(请输入数据\n);printf(请输入电话号码，输入-1结束\n);scanf(%d,&v);while(v!=-1){anodee=(anode)malloc(sizeof(newnode));e-number=v;printf(请输入地址\n);scanf(%s,e-address);printf(请输入名字(英文)\n);scanf(%s,e-name);i=(int)e-name[0];i=i%n;e-next=p[i];p[i]=e;printf(请输入电话号码，输入-1结束\n);scanf(%d,&v);}}voidhashshow2name(newnode**p){//查询记录（以用户名为关键字）链地址法chara[size];anodet;inti;printf(请输入要查询用户名\n);scanf(%s,a);i=(int)a[0];i=i%n;t=p[i];while(t&&strcmp(t-name,a)!=0){t=t-next;}if(t==NULL){printf(您所查询的用户不存在\n);}else{printf(------------------------------------------\n);printf(姓名:%s\n,t-name);printf(电话:%d\n,t-number);printf(地址:%s\n,t-address);printf(------------------------------------------\n);}}voidhashinput(newnode**p){//添加记录（以号码为关键字）链地址法intt,v;printf(请输入数据\n);printf(请输入电话号码，输入-1结束\n);scanf(%d,&v);while(v!=-1){anodee=(anode)malloc(sizeof(newnode));e-number=v;printf(请输入地址\n);scanf(%s,e-address);printf(请输入名字(英文)\n);scanf(%s,e-name);t=e-number%n;e-next=p[t];p[t]=e;printf(请输入电话号码，输入-1结束\n);scanf(%d,&v);}}voidhashshow(newnode**p){//查询记录（以号码为关键字）链地址法intd,h;anodet;printf(请输入所要查询的电话号码\n);scanf(%d,&d);h=d%n;t=p[h];while(t&&t-number!=d){t=t-next;}if(t==NULL){printf(您所要查询的号码不存在\n);}else{printf(------------------------------------------\n);printf(姓名:%s\n,t-name);printf(电话:%d\n,t-number);printf(地址:%s\n,t-address);printf(------------------------------------------\n);}}voidASL(newnode**p){//计算ASL链地址法inta[size],l,asl,z,b;asl=0;z=0;anodeu;for(l=0;lsize+1;l++){a[l]=0;}for(l=0;ln;l++){b=1;u=p[l];while(u){a[b]++;b++;u=u-next;}}for(l=1;ln+1;l++){asl=asl+a[l]*l;z=z+a[l];}asl=asl/z;printf(用链地址法处理冲突：ASL=%d\n,asl);}voidhashlistinit2(anode3w){//初始化散列表开放定址法链地址法anode2e;e=(anode2)malloc(n*sizeof(new