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

1、华 北 科 技 学 院课程设计说明书学号： 班级: 网络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

2、、功能需求分析1)每个记录有下列数据项：电话号码、用户名、地址；2)从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；3)采用一定的方法解决冲突；4)查找并显示给定电话号码的记录；5)查找并显示给定用户名的记录。6)在散列函数确定的前提下，尝试各种不同类型处理冲突的方法，考察平均查找长度的变化。二、概要设计1、总体设计思路程序的总体实现思路、方法：本程序使用了链地址法和开放定址法处理冲突，可以实现从键盘输入各记录，分别以电话号码和用户名为关键字建立散列表；查找并显示给定电话号码的记录；查找并显示给定用户名的记录；计算使用不同方法处理冲突时的平均查找长度。当使用链地址法处理冲突，电话号

3、码为关键字建立散列表时，使用除留余数法(t=e->number%n)，确定哈希地址。当使用链地址法处理冲突，用户名为关键字建立散列表时，把储存用户名的字符数组（name）的0号位置的字符(name0)强制转换为int类型(i)，即i=（int）name0,再使用除留余数法确定哈希地址(i=i%n，n=13)。当使用开放定址法处理冲突，电话号码为关键字建立散列表时，增量序列取用线性探测再散列法。当使用开放定址法处理冲突，用户名为关键字建立散列表时，把储存用户名的字符数组（name2）的0号位置的字符(name20)强制转换为int类型(e)，即e=(int)name0,使用开放定址法取得哈

4、希地址，如果产生冲突增量取用线性探测再散列法。用户名为关键字号码为关键字添加查询用户名为关键字号码为关键字用户名为关键字号码为关键字添加查询用户名为关键字号码为关键字链地址法开放定址法电话号码查找系统初始化散列表记算ASL程序总的功能结构图。2、 模块简介链地址法：void hashlistinit(newnode *p)/初始化散列表void hashinputname(newnode *p)/添加记录（以用户名为关键字）void hashshow2name(newnode *p)/查询记录（以用户名为关键字）void hashinput(newnode *p)/添加记录（以号码为关键字）v

5、oid hashshow(newnode *p)/查询记录（以号码为关键字）void ASL(newnode *p)/计算ASL开放定址法void hashlistinit2(anode3 w)/初始化散列表void hashinput2(anode3 w)/添加记录（以号码为关键字）void hashshow2(anode3 w)/查询记录（以号码为关键字）void hashinputname2(anode3 w/添加记录（以用户名为关键字）void hashshow2name2(anode3 w)/查询记录（以用户名为关键字）void ASL2(anode3 w)/计算ASLint sca

6、n()/菜单显示函数int scan2()/菜单显示函数三、详细设计1、数据结构设计链地址法：电话号码地址名字指向下一个结点typedef struct node 0int number; char addresssize;char namesize;struct node *next;newnode,*anode; 13开放定址法： 电话号码地址名字记录使用开放定址法时的冲突次数typedef struct node2 int number2;char address2size;char name2size;int v;/冲突次数newnode2,*anode2;指向（newnod型数组）储

7、存录入信息的数组判断存储空间是否已满记录表长typedef struct node3anode2 q;/信息录入数组int i;/判断存储空间int j;/表长newnode3,*anode3;2、 算法分析与实现开放定址法添加记录（以用户名为关键字）使用开放定址法，以用户名为关键字，添加记录当输入的电话号码不为-1时，输入姓名（英文），把姓名的第一个英文字母（char型）强制转换为整型e,再使用开放定址法获取哈希地址，增量取用线性探测再散列法。e=（ (int)a0 +k）%表长该位置是否为空?在该位置插入数据输入地址K=k+1输入地址 在该位置插入数据输出内存已满结束e=(int)a0%表

8、长该位置是否为空?哈希表是否已满？K=1输入姓名（char a100）d= -1?开始输入电话号码d Y N N Y Y Y N N Y N Y Y 四、运行结果和调试分析测试数据：姓名住址电话号码Fu云南19Yuan河北14Dong山西23链地址法：用户名为关键字建立散列表：ASL=1以号码为关键字建立散列表：ASL=1开放定址法：用户名为关键字建立散列表：ASL=1以号码为关键字建立散列表：ASL=1运行结果图。1.选用建表方法，初始化散列表。链地址法2. 添加记录（以用户名为关键字）链地址法3. 查询记录（以用户名为关键字）链地址法4. 计算ASL链地址法5. 添加记录（以号码为关键字）

9、链地址法6. 查询记录（以号码为关键字）链地址法7.切换开放定址法8. 初始化散列表，添加记录（以用户名为关键字）开放定址法9. 查询记录（以用户名为关键字）开放定址法10. 计算ASL开放定址法11. 添加记录（以号码为关键字）开放定址法12. 查询记录（以号码为关键字）开放定址法13.退出系统五、总结体会课程设计使我对数据结构课程的理解更深入，也能够发现自己平时不太注意的语法错误。当遇到问题时就翻书，或者上网查资料。在程序调试的过程中也能够完善系统。在课程设计过程中，使我的思路更为开拓。参考文献1严蔚敏，吴伟民编著数据结构（C语言版）清华大学出版社。2孙改平，王德志编著，C语言程序设计，清

10、华大学出版社。程序源码：#include <iostream>#include <stdio.h>#include<stdlib.h>#include<string.h>#define size 100#define n 13typedef struct nodeint number;char addresssize;char namesize;struct node *next;newnode,*anode;typedef struct node2int number2;char address2size;char name2size;int

11、v;/冲突次数newnode2,*anode2;typedef struct node3anode2 q;/信息录入数组int i;/判断存储空间int j;/表长newnode3,*anode3;void hashlistinit(newnode *p)/初始化散列表链地址法int i;for(i=0;i<n;i+) pi=NULL;printf("亲，散列表已初始化完毕n");void hashinputname(newnode *p)/添加记录（以用户名为关键字）链地址法int i,v;printf("请输入数据n");printf(&quo

12、t;请输入电话号码，输入-1结束n");scanf("%d",&v);while(v!=-1) anode e=(anode)malloc(sizeof(newnode); e->number=v; printf("请输入地址n"); scanf("%s",e->address); printf("请输入名字(英文)n"); scanf("%s",e->name); i=(int)e->name0; i=i%n; e->next=pi; pi=e;

13、 printf("请输入电话号码，输入-1结束n"); scanf("%d",&v);void hashshow2name(newnode *p)/查询记录（以用户名为关键字）链地址法char asize;anode t;int i;printf("请输入要查询用户名n");scanf("%s",a);i=(int)a0;i=i%n;t=pi;while(t&&strcmp(t->name,a)!=0) t=t->next;if(t=NULL) printf("您所查询

14、的用户不存在n");else printf("-n"); printf("姓名:%sn",t->name); printf("电话:%dn",t->number); printf("地址:%sn",t->address); printf("-n");void hashinput(newnode *p)/添加记录（以号码为关键字）链地址法int t,v;printf("请输入数据n");printf("请输入电话号码，输入-1结束n&quo

15、t;);scanf("%d",&v);while(v!=-1) anode e=(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=pt; pt=e; printf("请输入电话号码，输入-1结束n&

16、quot;); scanf("%d",&v);void hashshow(newnode *p)/查询记录（以号码为关键字）链地址法int d,h;anode t;printf("请输入所要查询的电话号码n");scanf("%d",&d);h=d%n;t=ph;while(t&&t->number!=d) t=t->next;if(t=NULL) printf("您所要查询的号码不存在n");else printf("-n"); printf(&qu

17、ot;姓名:%sn",t->name); printf("电话:%dn",t->number); printf("地址:%sn",t->address); printf("-n");void ASL(newnode *p)/计算ASL链地址法int asize,l,asl,z,b;asl=0;z=0;anode u;for(l=0;l<size+1;l+) al=0;for(l=0;l<n;l+) b=1; u=pl; while(u) ab+; b+; u=u->next; for(l=

18、1;l<n+1;l+) asl=asl+al*l; z=z+al;asl=asl/z;printf("用链地址法处理冲突：ASL=%dn",asl);void hashlistinit2(anode3 w)/初始化散列表开放定址法链地址法anode2 e;e=(anode2)malloc(n*sizeof(newnode2);if(!e) exit(0);w->q=e;w->i=n;w->j=n;for(int h=0;h<w->j;h+) w->qh.number2=0; w->qh.v=0; strcpy(w->qh

19、.address2,"无"); strcpy(w->2,"无");void hashinput2(anode3 w)/添加记录（以号码为关键字）开放定址法int d,t,k;k=1;printf("亲请输入所要录入的信息n");printf("电话号码(输入-1结束)：");scanf("%d",&d);t=d%w->j;while(d!=-1)if(w->qt.number2=0&&w->i!=0)w->qt.number2=

20、d;printf("姓名：");scanf("%s",w->2);printf("地址：");scanf("%s",w->qt.address2);w->i=w->i-1;w->qt.v=1;else if(w->i=0) printf("内存已满n");else if(w->qt.number2!=0) t=(d+k)%w->j; k=k+1; w->qt.v=2; while(w->qt.number2!=0&

21、&k<w->j) t=(d+k)%w->j; k=k+1; w->qt.v+; w->qt.number2=d;printf("姓名：");scanf("%s",w->2);printf("地址：");scanf("%s",w->qt.address2);w->i=w->i-1;printf("电话号码(输入-1结束)：");scanf("%d",&d);t=d%w->j;void ha

22、shshow2(anode3 w)/查询记录（以号码为关键字）开放定址法int d,k,t;k=1;printf("请输入要查询的电话号码：");scanf("%d",&d);t=d%w->j;if(w->qt.number2=d) printf("-n"); printf("姓名:%sn",w->2); printf("电话:%dn",w->qt.number2); printf("地址:%sn",w->qt.addres

23、s2); printf("-n");else t=(d+k)%w->j; k=k+1; while(w->qt.number2!=d&&k<w->j) t=(d+k)%w->j; k=k+1; if(w->qt.number2=d) printf("-n"); printf("姓名:%sn",w->2); printf("电话:%dn",w->qt.number2); printf("地址:%sn",w->qt.

24、address2); printf("-n"); else printf("您所要查询的号码不存在n"); void hashinputname2(anode3 w)/添加记录（以用户名为关键字）开放定址法char asize;int e,k,d;k=1;printf("请输入要录入的信息n");printf("电话号码(输入-1结束)：");scanf("%d",&d);while(d!=-1) printf("姓名（英文）："); scanf("%s&q

25、uot;,a); e=(int)a0; e=e%w->j; if(strcmp(w->2,"无")=0&&w->i!=0) strcpy(w->2,a); w->qe.number2=d; printf("地址："); scanf("%s",w->qe.address2); w->i=w->i-1; w->qe.v=1;else if(w->i=0) printf("内存已满n");else if(strcmp(

26、w->2,"无")!=0) e=(e+k)%w->j; k=k+1; w->qe.v=2; while(strcmp(w->2,"无")!=0&&k<w->j) e=(e+k)%w->j; k=k+1; w->qe.v+; strcpy(w->2,a); w->qe.number2=d; printf("地址："); scanf("%s",w->qe.address2); w->i=w-

27、>i-1;printf("电话号码(输入-1结束)：");scanf("%d",&d);void hashshow2name2(anode3 w)/查询记录（以用户名为关键字）开放定址法char asize;int e,k;k=1;printf("请输入要查询的用户名（英文）:");scanf("%s",a);e=(int)a0;e=e%w->j;if(strcmp(w->2,a)=0) printf("-n"); printf("姓名:%sn&

28、quot;,w->2); printf("电话:%dn",w->qe.number2); printf("地址:%sn",w->qe.address2); printf("-n");else e=(e+k)%w->j; k=k+1; while(strcmp(w->2,a)!=0&&k<w->j) e=(e+k)%w->j; k=k+1; if(k>=w->j) printf("您所查询的用户不存在n"); el

29、se printf("-n"); printf("姓名:%sn",w->2); printf("电话:%dn",w->qe.number2); printf("地址:%sn",w->qe.address2); printf("-n"); void ASL2(anode3 w)/计算ASL开放定址法int asl,c,z;asl=0;z=0;for(c=0;c<w->j;c+) asl=asl+w->qc.v;for(c=0;c<w->

30、j;c+) if(w->qc.number2!=0) z+; asl=asl/z;printf("用开放定址法处理冲突：ASL=%dn",asl);int scan()int m;printf("*n");printf(" 菜单 1 n");printf("*n");printf("亲，您要用选用哪个方法？n");printf("1.链地址法n");printf("2.开放定址法n");printf("-n");printf(&q

31、uot;亲，请您输入要选用的方法：");scanf("%d",&m);return m;int scan2()int j1;printf("*n");printf(" 菜单 2 n");printf("*n");printf("亲啊，我有如下功能哦n");printf("1.初始化散列表n");printf("2.添加记录（以用户名为关键字）n");printf("3.查询记录（以用户名为关键字）n");printf("4.添加记录（以号码为关键字）n")