专业课程设计试验报告哈希表的设计和实现.doc

数据构造课程设计

题 目 哈希表设计与实现
作 者
院 系 信息工程学院
专 业 信息管理与信息系统
学 号
指引教师 张 慧
答辩时间 12月18日

目录
数据构造课程设计 0
1系统需求分析 2
1.1顾客需求分析 3
1.2功能需求分析 3
1.3数据需求分析 3
1.4 小结 4
2系统设计 4
2.1设计内容及规定 4
2.2总体设计思路 4
2.3程序详细设计流程图 5
2.31以姓名为核心字Hash()函数流程图 5
2.32添加结点信息流程图: 7
2.33按姓名查找流程图: 7
2.34按号码查找流程图 8
2.35主程序流程图 9
2.4详细设计编码 11
2.41建立节点 11
2.42对哈希函数定义 11
2.43哈希查找 12
2.44主函数 12
3系统测试 13
3.1上机调试 13
3.2调试成果与分析 14
4总结 18
5附录 18

1系统需求分析
在信息化时代今天，计算机技术已经是发展到一种很可观地步了，特别是面向窗口操作系统浮现，使得程序设计更加容易了。在过去计算机内存容量小，CPU计算速度慢，关于程序设计中数据构造也因而提出来诸多关于解决这方面问题。哈希表就是其中之一，哈希表是一种由核心字与值构成特殊一种数据构造。它浮现重要是为理解决在构造中查找记录时需要进行一系列和核心字比较,这一类查找办法是建立在“比较”基本上，在顺序等查找中，查找效率是依赖于查找过程中所比较次数。
抱负状况是但愿不通过任何比较一次存取便能得到所查记录，那就必要在记录存储位置和它核心字之间建立一种拟定相应关系，使得每个核心字和构造中一种唯一存储位置相相应。因而在查找时只要依照这个相应关系找到给定值像。若构造中存在核心字和该值相等记录，则所要查找数就必然就是这个所查找到记录。
哈希函数是建立哈希表一种重要成员，它构造办法分为如下几种：
直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法。
本程序中重要用是除余取留法,除留取余法重要是取核心字被某个不不不大于哈希表表长m数p出后所得余数为哈希地址即:H(key)=key MOD p，p<=m，这是一种最简朴，也是一种最惯用构造函数办法，它不但可以对核心字直接取模，也可在折叠、平方中档运算之后取模。
在哈希表建立中，很容易浮现同义词，这些同义词浮现也导致了建立哈希表时冲突浮现，如果不解决这些冲突那么建立好哈希表与预料哈希表不同。关于解决冲突办法重要有：开放定址法、再哈希法、链地址法。本程序中重要用就是链地址法莱解决冲突。

1.1顾客需求分析
设计一种程序可以使用哈希表实现电话号码查询系统。该系统可以从键盘输入各记录，分别以电话号码和顾客名为核心字建立哈希表，可以从输入记录中查找并显示给定顾客记录，最后并且可以进行清除记录和退出功能。
1.2功能需求分析
（1）设计一种结点使该结点涉及电话号码、顾客名、地址。
（2）运用顾客名和电话号码为核心字建立哈希表，哈希函数用除留余数法构照。
（3）运用链表法解决冲突问题。
（4）查找并显示给定顾客名，地址，电话号码记录。
（5）显示哈希表中给定顾客记录。
（6）当完毕操作后，可以退出系统。

1.3数据需求分析
由问题分析知，本设计重要规定分别以电话号码和顾客名为核心字建立哈希表，并实现查找功能。因此本设计核心问题是如何解决散列问题，亦即设计一种良好哈希表。由于结点个数无法确认，并且如果采用线性探测法散列算法，删除结点会引起“信息丢失”问题。因此采用链地址法散列算法。采用链地址法，当浮现同义词冲突时，使用链表构造把同义词链接在一起，即同义词存储地址不是散列表中其她空地址。
一方面，解决是定义链表结点，在链地址法中，每个结点相应一种链表结点，它由三个域构成，而由于该程序需要分别用电话号码和顾客名为核心字建立哈希表，因此该链表结点它是由四个域构成.name[8] 、num[11]和address[20]都是char浮点型，输入输出都只能是浮点型。
采用链地址法，其中所有同义词构成一种单链表，再由一种表头结点指向这个单链表第一种结点。这些表头结点构成一种一维数组，即哈希表。数组元素下标相应由散列函数求出散列地址。
1.4 小结
通过以上需求分析，懂得了设计一种哈希表目和可以“实现什么功能”，为接下来操作明确方向，罗列了需要运用到知识，自己应当在接下来程序设计和实现应当怎么做。

2系统设计
2.1设计内容及规定
本设计重要规定分别以电话号码和顾客名为核心字建立哈希表，并实现查找功能。本程序规定是设计散列函数，亦即设计一种良好哈希表。本程序需要设计两个散列函数才干解决问题，程序需要分别为以电话号码和顾客名为核心字建立哈希表。因此要分别以顾客名、号码为核心字建立两个散列函数，要添加顾客信息，即要有实现添加结点功能函数，因此要设计一种必要涉及一种输入结点信息、添加结点函数；
要实现查找函数，则必要涉及一种查找结点函数；
此外尚有一种必不可少就是运营之后要有一种主菜单，即要设计一种主函数（main()）。
2.2总体设计思路
本设计涉及到数据构造为：哈希表。规定输入电话号码、顾客名、地址三个信息，并规定分别以电话号码和顾客名为核心字进行查找，因此本问题要用到两个哈希函数，进行哈希查找。
在链地址法中，每个结点相应一种链表结点，它由三个域构成，而由于该程序需要分别用电话号码和顾客名为核心字建立哈希表，因此该链表结点它是由四个域构成，链地址法结点构造如图：
name[8]
num[11]
address[20]
next

其中name[8]和num[11]是分别为以电话号码和顾客名为核心字域，存储核心字（key）；address[20](data)为结点数据域，用来存储顾客地址。Next指针是用来指向下一种结点地址。

2.3程序详细设计流程图
2.31以姓名为核心字Hash()函数流程图

结束
Key2=key%20
name[i]不为空
开始
i从0开始取
取整型name[0]赋给key2
Key2+=name[i]
i++

1-1 姓名为核心字Hash()函数流程图

2.32添加结点信息流程图:

运用顾客名为核心字插入
拉链法解决冲突
调用hash()函数

调用hash()函数
Newname指向newphone
Newphone=input()
结束
申请新结点newphone,newname即新号码和名字
开始

1-2添加结点信息流程图:

2.33按姓名查找流程图:

q不为空
结束
输出无记录
输出相应记录
q=q->next
q 不为空
调用hash()函数中新结点q指向phone[key]->next
开始

2.34按号码查找流程图

开始
调用hash2()函数中新结点q指向phone[key]->next
q 不为空
q=q->next
q不为空
输出无记录
输出相应记录
结束

2.35主程序流程图

开 始
Main ()
初始化散列链表（1）并为其动态分派内存空间
初始化散列链表（2）并为其动态分派内存空间
Menu（）主菜单
输入选取
选取1
选６
选7
查找号码find()
查找顾客
find2()
输出成果
输出成果
选取2
选取0
选取3

选取4

选取5
进行姓名散列list2()
姓名散列成果
添加记录 apend()
退出系统return 0
进行号码散列 list()

清空creat();creat2()
列表已清空
号码散列成果
结 束

2.4详细设计编码
2.41建立节点
struct node //建节点
{
char name[8],address[20];//节点中要包括顾客名，顾客地址，电话号码以及指向下一种结点指针
char num[11]；
node * next；
}；
typedef node* pnode；//typedef可觉得一种已有数据类型声明各种别名，这里为该类型声明了两个指针
typedef node* mingzi；
node **phone；
node **nam；
node *a;
2.42对哈希函数定义
void hash(char num[11]) //以电话号码为核心字建立哈希函数
{
key=(int)num[2]；

while(num[i]!=NULL)
{
key+=(int)num[i]；
i++；
}
key=key%20；
}
b)
void hash2(char name[8]) //以顾客名为核心字建立哈希函数
{
int i = 1；
key2=(int)name[0]；

while(name[i]!=NULL)
{
key2+=(int)name[i]；
i++；
}
key2=key2%20；
}
2.43哈希查找
void find(char num[11]) //在以电话号码为核心字哈希表中查找顾客信息
{
hash(num)；
node *q=phone[key]->next；
while(q!= NULL)
{
if(strcmp(num,q->num)==0)
break；
q=q->next；
}
if(q)
printf("%s_%s_%s\n",q->name,q->address,q->num);
else printf("无此记录\n")；
}
b)、void find2(char name[8]) // 在以顾客名为核心字哈希表中查找顾客信息
{
hash2(name)；
node *q=nam[key2]->next；
while(q!= NULL)
{
if(strcmp(name,q->name)==0)
break；
q=q->next；
}
if(q)
printf("%s_%s_%s\n",q->name,q->address,q->num);
else printf("无此记录\n")；
}
2.44主函数
主函数
本程序需要创立一种主菜单和一种主函数，主菜单便于顾客使用，主函数中，涉及所有功能相应数值，使之和主菜单相相应。
***************************主函数界面设计如下************************

0添加记录
1查找记录
2姓名散列
3号码散列
4清空记录
5退出系统

void menu() //菜单
{
system("color 2d");
printf("********************************************************************************\n");
printf("\t\t\t***********欢迎使用***********\t\t\t\n");
printf("\n");
printf("\t\t\t\t 0.添加记录\t\t\t\t\n")；
printf("\t\t\t\t 1.查找记录\t\t\t\t\n")；
printf("\t\t\t\t 2.姓名散列\t\t\t\t\n")；
printf("\t\t\t\t 3.号码散列\t\t\t\t\n")；
printf("\t\t\t\t 4.清空记录\t\t\t\t\n")；
printf("\t\t\t\t 5.退出系统\t\t\t\t\n")；
}

3系统测试
3.1上机调试
1一方面键入0,添加结点信息,然后按1进行查找,分别进行号码和姓名查找,最后可在主菜单中，选取号码散列和姓名散列,由此查看程序运营成果。
2语法错误及修改：程序是分块写,调试时可以使用分步调试方式进行,以便能查找看程序是在哪出错了。本算法使用了链表构造和链地址法解决冲突问题，在以姓名为核心字哈希表中要注意涉及ASCLL码类型转换，要注意输出不能是“%d”，否则不能输出成果。编写程序时要多注意程序中各种指针使用，尚有各类变量定义，函数使用。这些问题均可以依照编译器警告提示，相应将其解决。
3逻辑问题修改和调节：链表构造办法虽然以便了运营，但是增长了对算法过程结识难度。在本程序中每一种函数中都需要涉及到指针操作。因此需要仔细分析函数中指针指向。在插入结点，查找结点时尤为突出。对于主菜单和主函数相应，一定要一致，这样才干保证运营时不会出错。
4时间，空间性能分析：散列法本质上是一种通过核心字直接计算存储地址办法。在抱负状况下，散列函数可以把结点均匀地分布到散列表中，不发生冲突，则查找过程无需比较，其时间复杂度O（n）=1。但在实际使用过程中，为了将范畴广泛核心字映射到一组持续存储空间，往往会发生同义词冲突，这时在查找过程中就需要进行核心字比较。因而散列法查找性能取决于3个因素：散列函数、冲突解决办法和填充因子。采用链地址法，可以从主线上杜绝“二次汇集”发生，从而提高散列表均匀度，提高查找性能，但是也会“挥霍”一某些散列表空间。当散列函数和冲突解决办法固定期，散列法查找性能就取决于散列表填充因子。填充因子a=表中已有结点数/表长度。填充因子a标志表添满限度。很显然，a越小则发生冲突机会就越小；反之，a越大冲突机会就越大，查找性能也就越低。哈希表链地址法查找成功平均查找长度SNc=1+a/2。链地址法查找不成功平均查找长度Un满足：Unc=a+e-a.由以上可以看出，散列表平均查找长度是填充因子函数，和散列表长度没关于系，因而在实际应用中，咱们应当选取一种恰当填充因子，以便把平均查找长度控制在一种尽量小范畴内。
3.2调试成果与分析
程序主菜单

添加记录:

分别按电话号码和姓名查找:

分别输出按姓名和号码散列成果:

清空记录:

4总结
通过为期两周课程设计，本次课程设计时间虽然比较短暂，但是我通过这次实践学到了诸多知识，也理解了自己诸多局限性之处。我是一名信息工程学院学生，数据构造对于我来说就显得尤为重要，这也是我必要认真学懂一门课程。在课程设计之前，咱们已经学习C语言这门课程已经一种学期，对其有了一定理解，但是更多还是停留在学习理解范畴，对里面好多东西还是很陌生，并不是很纯熟，有着许多欠缺，更多在运用起来时候还是感到很不好动手。C语言课堂上许多关于C语言语法规则，听起来十分枯燥无味，也不容易记住，死记硬背是不可取。然而要使用C语言这个工具解决实际问题，又必要掌握它。通过多次上机练习，对于语法知识有了感性结识，加深对它理解，在理解基本上就会自然而然地掌握C语言语法规定。对于某些内容自己以为在课堂上听懂了，但上机实践中会发现本来理解偏差，更加巩固了学过知识，并且在设计时候学要系统知识，也是一种较大挑战，某一方面知识欠缺都将影响到整个程序设计。我从本来对这门课程不懂，到当前可以独立完毕一种小型程序。
这次课程设计，重温了和学习了许多关于c语言知识，还掌握了某些现实中编程某些小技巧，实际编程能力也得到了历练，本次课程设计对我协助诸多。

5附录
************************程序源代码**************************

#include<stdio.h>
#include<string.h>

#define NULL 0
unsigned int key；//定义两个核心字
unsigned int key2；

int *p；
struct node //建节点 每个结点涉及顾客姓名、地址、电话号码、以及指向下一种结点指针
{
char name[8],address[20]；
char num[11]；
node * next；
}；
typedef node* pnode；//typedef可觉得一种已有数据类型声明各种别名，这里为该类型声明了两个指针
typedef node* mingzi；
node **phone；
node **nam；
node *a；

void hash(char num[11]) //哈希函数 ，以电话号码为核心字建立哈希函数
//哈希函数主旨是将电话号码十一位数字所有加起来
{
int i = 3；
key=(int)num[2]；

while(num[i]!=NULL)
{
key+=(int)num[i]；
i++；
}
key=key%20；
}
void hash2(char name[8]) //哈希函数 以顾客名为核心字建立哈希函数
//运用强制类型转换，将顾客名每一种字母ASCLL码值相加并且除以20后余数
{
int i = 1；
key2=(int)name[0]；

while(name[i]!=NULL)
{
key2+=(int)name[i]；
i++；
}
key2=key2%20；
}

node* input() //输入节点信息 ，建立结点，并将结点next指针指空
{
node *temp；
temp = new node； //new功能是动态分派内存，语法形式：new 类型名T（初值列表
temp->next=NULL；
printf("请输入姓名:\n");
scanf("%s",temp->name);
printf("输入地址： \n");
scanf("%s",temp->address);
printf("输入电话：\n");
scanf("%s",temp->num);

return temp；//对于指针类型返回是地址

}
int apend() //添加节点
{
node *newphone；
node *newname；
newphone=input()；
newname=newphone；
newphone->next=NULL；
newname->next=NULL；
hash(newphone->num)； //运用哈希函数计算出相应核心字存储地址
hash2(newname->name)；
newphone->next = phone[key]->next；//运用电话号码为核心字插入
phone[key]->next=newphone；//是采用链地址法，拉链法解决冲突散列表构造
newname->next = nam[key2]->next； //运用顾客名为核心字插入
nam[key2]->next=newname；
return 0；
}
void create() //新建节点
{
int i；
phone=new pnode[20];//动态创立对象数组
for(i=0;i<20;i++)
{
phone[i]=new node；
phone[i]->next=NULL；

}

}
void create2() //新建节点
{
int i；
nam=new mingzi[20]；
for(i=0;i<20;i++)
{
nam[i]=new node；
nam[i]->next=NULL；

}

}
void list() //显示列表
{
int i；
node *p；
for(i=0;i<20;i++)
{
p=phone[i]->next；
while(p)
{
printf("%s_%s_%s\n",p->name,p->address,p->num);

p=p->next；
}
}
}
void list2() //显示列表
{
int i；
node *p；
for(i=0;i<20;i++)
{
p=nam[i]->next；
while(p)
{
printf("%s_%s_%s\n",p->name,p->address,p->num);
p=p->next；
}
}
}

void find(char num[11]) //在以电话号码为核心字哈希表中查找顾客信息
{
hash(num)；
node *q=phone[key]->next；
while(q!= NULL)
{
if(strcmp(num,q->num)==0)
break；
q=q->next；
}
if(q)
printf("%s_%s_%s\n",q->name,q->address,q->num);
else printf("无此记录\n")；
}
void find2(char name[8]) // 在以顾客名为核心字哈希表中查找顾客信息
{
hash2(name)；
node *q=nam[key2]->next；
while(q!= NULL)
{
if(strcmp(name,q->name)==0)
break；
q=q->next；
}
if(q)
printf("%s_%s_%s\n",q->name,q->address,q->num);
else printf("无此记录\n")；
}

void menu() //菜单
{

printf("0.添加记录\n")；
printf("1.查找记录\n")；
printf("2.姓名散列\n")；
printf("3.号码散列\n")；
printf("4.清空记录\n")；
printf("5.退出系统\n")；
}

int main()
{

char num[11]；
char name[8]；

create()；
create2() ；

int sel；
while(1)
{
menu()；
scanf("%d",&sel)；
if(sel==1)
{
printf("6号码查询，7姓名查询\n")；
int b；
scanf("%d",&b)；
if(b==6)
{
printf("请输入电话号码:\n")；
scanf("%s",num);
printf("输出查找信息:\n")；
find(num)；
}
else
{
printf("请输入姓名:\n")；
scanf("%s",name)；
printf("输出查找信息:\n")；
find2(name);}}
if(sel==2)
{printf("姓名散列成果:\n")；
list2();}

if(sel==0)
{printf("请输入要添加内容:\n")；
apend();}
if(sel==3)
{printf("号码散列成果:\n")；
list()；
}
if(sel==4)
{printf("列表已清空:\n")；
create();create2();}

if(sel==6) return 0；

}

return 0；
}