设计散列表实现电话号码查找系统.docx
- 文档编号:948236
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:34
- 大小:672.44KB
设计散列表实现电话号码查找系统.docx
《设计散列表实现电话号码查找系统.docx》由会员分享,可在线阅读,更多相关《设计散列表实现电话号码查找系统.docx(34页珍藏版)》请在冰点文库上搜索。
设计散列表实现电话号码查找系统
华北科技学院
课程设计说明书
学号:
班级:
网络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
开放定址法
voidhashlistinit2(anode3w)//初始化散列表
voidhashinput2(anode3w)//添加记录(以号码为关键字)
voidhashshow2(anode3w)//查询记录(以号码为关键字)
voidhashinputname2(anode3w{//添加记录(以用户名为关键字)
voidhashshow2name2(anode3w)//查询记录(以用户名为关键字)
voidASL2(anode3w)//计算ASL
intscan()//菜单显示函数
intscan2(){//菜单显示函数
三、详细设计
1、数据结构设计
链地址法:
typedefstructnode{0
intnumber;
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,
再使用开放定址法获取哈希地址,增量取用线性探测再散列法。
Y
N
N
Y
YY
N
NY
N
Y
Y
四、运行结果和调试分析
测试数据:
姓名
住址
电话号码
Fu
云南
19
Yuan
河北
14
Dong
山西
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语言程序设计》,清华大学出版社。
程序源码:
#include
#include
#include
#include
#definesize100
#definen13
typedefstructnode{
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;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;l a[l]=0; } for(l=0;l b=1; u=p[l]; while(u){ a[b]++; b++; u=u->next; } } for(l=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(newnode2)); if(! e)exit(0); w->q=e; w->i=n; w->j=n; for(inth=0;h w->q[h].number2=0; w->q[h].v=0; strcpy(w->q[h].address2,"无"); strcpy(w->q[h].name2,"无"); } } voidhashinput2(anode3w){//添加记录(以号码为关键字)开放定址法 intd,t,k; k=1; printf("亲请输入所要录入的信息\n"); printf("电话号码(输入-1结束): "); scanf("%d",&d); t=d%w->j; while(d! =-1){ if(w->q[t].number2==0&&w->i! =0){ w->q[t].number2=d; printf("姓名: "); scanf("%s",w->q[t].name2); printf("地址: "); scanf("%s",w->q[t].address2); w->i=w->i-1; w->q[t].v=1; } elseif(w->i==0){ printf("内存已满\n"); } elseif(w->q[t].number2! =0){ t=(d+k)%w->j; k=k+1; w->q[t].v=2; while(w->q[t].number2! =0&&k t=(d+k)%w->j; k=k+1; w->q[t].v++; } w->q[t].number2=d; printf("姓名: "); scanf("%s",w->q[t].name2); printf("地址: "); scanf("%s",w->q[t].address2); w->i=w->i-1; } printf("电话号码(输入-1结束): "); scanf("%d",&d); t=d%w->j; } } voidhashshow2(anode3w){//查询记录(以号码为关键字)开放定址法 intd,k,t; k=1; printf("请输入要查询的电话号码: "); scanf("%d",&d); t=d%w->j; if(w->q[t].number2==d){ printf("------------------------------------------\n"); printf("姓名: %s\n",w->q[t].name2); printf("电话: %d\n",w->q[t].number2); printf("地址: %s\n",w->q[t].address2); printf("------------------------------------------\n"); } else{ t=(d+k)%w->j; k=k+1; while(w->q[t].number2! =d&&k t=(d+k)%w->j; k=k+1; } if(w->q[t].number2==d){ printf("------------------------------------------\n"); printf("姓名: %s\n",w->q[t].name2); printf("电话: %d\n",w->q[t].number2); printf("地址: %s\n",w->q[t].address2); printf("------------------------------------------\n"); } else{ printf("您所要查询的号码不存在\n"); } } } voidhashinputname2(anode3w){//添加记录(以用户名为关键字)开放定址法 chara[size]; inte,k,d; k=1; printf("请输入要录入的信息\n"); printf("电话号码(输入-1结束): "); scanf("%d",&d); while(d! =-1){ printf("姓名(英文): "); scanf("%s",a); e=(int)a[0]; e=e%w->j; if(strcmp(w->q[e].name2,"无")==0&&w->i! =0){ strcpy(w->q[e].name2,a); w->q[e].number2=d; printf("地址: "); scanf("%s",w->q[e].address2); w->i=w->i-1; w->q[e].v=1; } elseif(w->i==0){ printf("内存已满\n"); } elseif(strcmp(w->q[e].name2,"无")! =0){ e=(e+k)%w->j; k=k+1; w->q[e].v=2; while(strcmp(w->q[e].name2,"无")! =0&&k e=(e+k)%w->j; k=k+1; w->q[e].v++; } strcpy(w->q[e].name2,a); w->q[e].number2=d; printf("地址: "); scanf("%s",w->q[e].address2); w->i=w->i-1; } printf("电话号码(输入-1结束): "); scanf("%d",&d); } } voidhashshow2name2(anode3w){//查询记录(以用户名为关键字)开放定址法 chara[size]; inte,k; k=1; printf("请输入要查询的用户名(英文): "); scanf("%s",a); e=(int)a[0]; e=e%w->j; if(strcmp(w->q[e].name2,a)==0){ printf("------------------------------------------\n"); printf("姓名: %s\n",w->q[e].name2); printf("电话: %d\n",w->q[e].number2); printf("地址: %s\n",w->q[e].address2); printf("------------------------------------------\n"); } else{ e=(e+k)%w->j; k=k+1; while(strcmp(w->q[e].name2,a)! =0&&k e=(e+k)%w->j; k=k+1; } if(k>=w->j){ printf("您所查询的用户不存在\n"); } else{ printf("------------------------------------------\n"); printf("姓名: %s\n",w->q[e].name2); printf("电话: %d\n",w->q[e].number2); printf("地址: %s\n",w->q[e].address2); printf("------------------------------------------\n"); } } } voidASL2(anode3w){//计算ASL开放定址法 intasl,c,z; asl=0; z=0; for(c=0;c asl=asl+w->q[c].v; } for(c=0;c if(w->q[c].number2! =0){ z++; } } asl=asl/z; printf("用开放定址法处理冲突: ASL=%d\n",asl); } intscan(){ intm; printf("**************************************\n"); printf("菜单1\n"); printf("**************************************\n"); printf("亲,您要用选用哪个方法? \n"); printf("1.链地址法\n"); printf("2.开放定址法\n"); printf("--------------------------------------\n"); printf("亲,请您输入要选用的方法: "); scanf("%d",&m); returnm; } intscan2(){ intj1; printf("**************************************\n"); printf("菜单2\n"); printf("**************************************\n"); printf("亲啊,我有如下功能哦~\n"); printf("1.初始化散列表\n"); printf("2.添加记录(以用户名为关键字)\n"); printf("3.查询记录(以用户名为关键字)\n"); printf("4.添加记录(以号码为关键字)\n"); printf("5.查询记录(以号码为关键字)\n"); printf("6.计算ASL\n"); printf("7.选用另一个方法\n"); printf("8.退出系统\n"); printf("--------------------------------------\n"); printf("亲啊,您要使用那个功能呢: "); scanf("%d",&j1); printf("-----------
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 设计 列表 实现 电话号码 查找 系统