课程设计-散列表实现电话号码查找系统.doc

华 北 科 技 学 院

课程设计说明书

学号：
班级: 网络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],使用开放定址法取得哈希地址，如果产生冲突增量取用线性探测再散列法。

用
户
名
为关
键字
号码为关键字
添加
查询

用
户
名
为关
键字
号码为关键字
用
户
名
为关
键字
号码为关键字
添加
查询

用
户
名
为关
键字
号码为关键字
链地址法

开放定址法
电话号码查找系统
初始化散列表
记算ASL
程序总的功能结构图。

2、 模块简介
链地址法：
void hashlistinit(newnode **p)//初始化散列表
void hashinputname(newnode **p)//添加记录（以用户名为关键字）
void hashshow2name(newnode **p)//查询记录（以用户名为关键字）
void hashinput(newnode **p)//添加记录（以号码为关键字）
void 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)//计算ASL
int scan()//菜单显示函数
int scan2(){//菜单显示函数
三、详细设计
1、数据结构设计
链地址法：

电话号码

地址
名字

指向下一个结点
typedef struct node{ 0
int number;
char address[size];
char name[size];
struct node *next;
}newnode,*anode;
13

开放定址法：
电话号码

地址
名字

记录使用开放定址法时的冲突次数
typedef struct node2{
int number2;
char address2[size];
char name2[size];
int v;//冲突次数
}newnode2,*anode2;

指向（newnod型数组）储存录入信息的数组

判断存储空间是否已满

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

输入地址
K=k+1
输入地址
在该位置插入数据
输出内存已满
结束
e=(int)a[0]%表长
该位置是否为空?
哈希表是否已满？
K=1
输入姓名（char a[100]）
d= -1?
开始
输入电话号码d

Y
N

N
Y
Y Y
N
N Y

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 <iostream>
#include <stdio.h>
#include<stdlib.h>
#include<string.h>
#define size 100
#define n 13
typedef struct node{
int number;
char address[size];
char name[size];
struct node *next;
}newnode,*anode;
typedef struct node2{
int number2;
char address2[size];
char name2[size];
int v;//冲突次数
}newnode2,*anode2;
typedef struct node3{
anode2 q;//信息录入数组
int i;//判断存储空间
int j;//表长
}newnode3,*anode3;
void hashlistinit(newnode **p){//初始化散列表链地址法
int i;
for(i=0;i<n;i++){
p[i]=NULL;
}
printf("亲，散列表已初始化完毕\n");
}
void hashinputname(newnode **p){//添加记录（以用户名为关键字）链地址法
int i,v;
printf("请输入数据\n");
printf("请输入电话号码，输入-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->name[0];
i=i%n;
e->next=p[i];
p[i]=e;
printf("请输入电话号码，输入-1结束\n");
scanf("%d",&v);
}
}
void hashshow2name(newnode **p){//查询记录（以用户名为关键字）链地址法
char a[size];
anode t;
int i;
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");
}
}
void hashinput(newnode **p){//添加记录（以号码为关键字）链地址法
int t,v;
printf("请输入数据\n");
printf("请输入电话号码，输入-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);
t=e->number%n;
e->next=p[t];
p[t]=e;
printf("请输入电话号码，输入-1结束\n");
scanf("%d",&v);
}
}
void hashshow(newnode **p){//查询记录（以号码为关键字）链地址法
int d,h;
anode t;
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");
}
}
void ASL(newnode **p){//计算ASL链地址法
int a[size],l,asl,z,b;
asl=0;
z=0;
anode u;
for(l=0;l<size+1;l++){
a[l]=0;

}
for(l=0;l<n;l++){
b=1;
u=p[l];
while(u){
a[b]++;
b++;
u=u->next;
}
}
for(l=1;l<n+1;l++){
asl=asl+a[l]*l;
z=z+a[l];
}
asl=asl/z;
printf("用链地址法处理冲突：ASL=%d\n",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->q[h].number2=0;
w->q[h].v=0;
strcpy(w->q[h].address2,"无");
strcpy(w->q[h].name2,"无");
}
}
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->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;
}
else if(w->i==0){
printf("内存已满\n");

}
else if(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<w->j){
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;
}

}
void hashshow2(anode3 w){//查询记录（以号码为关键字）开放定址法
int d,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<w->j){
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");
}
}
}
void hashinputname2(anode3 w){//添加记录（以用户名为关键字）开放定址法
char a[size];
int e,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;
}
else if(w->i==0){
printf("内存已满\n");
}
else if(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<w->j){
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);
}
}
void hashshow2name2(anode3 w){//查询记录（以用户名为关键字）开放定址法
char a[size];
int e,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<w->j){
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");
}
}
}
void ASL2(anode3 w){//计算ASL开放定址法
int asl,c,z;
asl=0;
z=0;
for(c=0;c<w->j;c++){
asl=asl+w->q[c].v;
}
for(c=0;c<w->j;c++){

if(w->q[c].number2!=0){
z++;
}
}

asl=asl/z;
printf("用开放定址法处理冲突：ASL=%d\n",asl);
}
int scan(){
int m;
printf("**************************************\n");
printf(" 菜单 1 \n");
printf("**************************************\n");
printf("亲，您要用选用哪个方法？\n");
printf("1.链地址法\n");
printf("2.开放定址法\n");
printf("--------------------------------------\n");
printf("亲，请您输入要选用的方法：");
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");
printf("5.查询记录（以号码为关键字）\n");
printf("6.计算ASL\n");
printf("7.选用另一个方法\n");
printf("8.退出系统\n");
printf("--------------------------------------\n");
printf("亲啊，您要使用那个功能呢：");
scanf("%d",&j1);
printf("--------------------------------------\n");
return j1;
}
int main(){
int t,v,x;
newnode *p[n];
anode3 w;
newnode3 y1;
w=&y1;
v=1;
t=scan();
while(v){
if(t==1){
x=scan2();
switch(x){
case 1:hashlistinit(p);
break;
case 2:hashinputname(p);
break;
case 3:hashshow2name(p);
break;
case 4:hashinput(p);
break;
case 5:hashshow(p);
break;
case 6:ASL(p);
break;
case 7:t=2;
printf("已为您切换开放定址法\n");
break;
case 8:v=0;
break;
default:printf("输入错误！\n");
break;
}
}
else if(t==2){
x=scan2();
switch(x){
case 1:hashlistinit2(w);
break;
case 2:hashinputname2(w);
break;
case 3:hashshow2name2(w);
break;
case 4:hashinput2(w);
break;
case 5:hashshow2(w);
break;
case 6:ASL2(w);
break;
case 7:t=1;
printf("已为您切换链地址法\n");
break;
case 8:v=0;
break;
default:printf("输入错误\n");
break;
}
}
else if(t!=1&&t!=2){
printf("输入错误！\n");
t=scan();
}
}
}
1. 基于C8051F单片机直流电动机反馈控制系统的设计与研究
2. 基于单片机的嵌入式Web服务器的研究
3. MOTOROLA单片机MC68HC（8）05PV8/A内嵌EEPROM的工艺和制程方法及对良率的影响研究
4. 基于模糊控制的电阻钎焊单片机温度控制系统的研制
5. 基于MCS-51系列单片机的通用控制模块的研究
6. 基于单片机实现的供暖系统最佳启停自校正（STR）调节器
7. 单片机控制的二级倒立摆系统的研究
8. 基于增强型51系列单片机的TCP/IP协议栈的实现
9. 基于单片机的蓄电池自动监测系统
10. 基于32位嵌入式单片机系统的图像采集与处理技术的研究
11. 基于单片机的作物营养诊断专家系统的研究
12. 基于单片机的交流伺服电机运动控制系统研究与开发
13. 基于单片机的泵管内壁硬度测试仪的研制
14. 基于单片机的自动找平控制系统研究
15. 基于C8051F040单片机的嵌入式系统开发
16. 基于单片机的液压动力系统状态监测仪开发
17. 模糊Smith智能控制方法的研究及其单片机实现
18. 一种基于单片机的轴快流CO〈,2〉激光器的手持控制面板的研制
19. 基于双单片机冲床数控系统的研究
20. 基于CYGNAL单片机的在线间歇式浊度仪的研制
21. 基于单片机的喷油泵试验台控制器的研制
22. 基于单片机的软起动器的研究和设计
23. 基于单片机控制的高速快走丝电火花线切割机床短循环走丝方式研究
24. 基于单片机的机电产品控制系统开发
25. 基于PIC单片机的智能手机充电器
26. 基于单片机的实时内核设计及其应用研究
27. 基于单片机的远程抄表系统的设计与研究
28. 基于单片机的烟气二氧化硫浓度检测仪的研制
29. 基于微型光谱仪的单片机系统
30. 单片机系统软件构件开发的技术研究
31. 基于单片机的液体点滴速度自动检测仪的研制
32. 基于单片机系统的多功能温度测量仪的研制
33. 基于PIC单片机的电能采集终端的设计和应用
34. 基于单片机的光纤光栅解调仪的研制
35. 气压式线性摩擦焊机单片机控制系统的研制
36. 基于单片机的数字磁通门传感器
37. 基于单片机的旋转变压器-数字转换器的研究
38. 基于单片机的光纤Bragg光栅解调系统的研究
39. 单片机控制的便携式多功能乳腺治疗仪的研制
40. 基于C8051F020单片机的多生理信号检测仪
41. 基于单片机的电机运动控制系统设计
42. Pico专用单片机核的可测性设计研究
43. 基于MCS-51单片机的热量计
44. 基于双单片机的智能遥测微型气象站
45. MCS-51单片机构建机器人的实践研究
46. 基于单片机的轮轨力检测
47. 基于单片机的GPS定位仪的研究与实现
48. 基于单片机的电液伺服控制系统
49. 用于单片机系统的MMC卡文件系统研制
50. 基于单片机的时控和计数系统性能优化的研究
51. 基于单片机和CPLD的粗光栅位移测量系统研究
52. 单片机控制的后备式方波UPS
53. 提升高职学生单片机应用能力的探究
54. 基于单片机控制的自动低频减载装置研究
55. 基于单片机控制的水下焊接电源的研究
56. 基于单片机的多通道数据采集系统
57. 基于uPSD3234单片机的氚表面污染测量仪的研制
58. 基于单片机的红外测油仪的研究
59. 96系列单片机仿真器研究与设计
60. 基于单片机的单晶金刚石刀具刃磨设备的数控改造
61. 基于单片机的温度智能控制系统的设计与实现
62. 基于MSP430单片机的电梯门机控制器的研制
63. 基于单片机的气体测漏仪的研究
64. 基于三菱M16C/6N系列单片机的CAN/USB协议转换器
65. 基于单片机和DSP的变压