数据结构课程设计哈希表实验报告.docx

数据结构课程设计哈希表实验报告.docx

《数据结构课程设计哈希表实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计哈希表实验报告.docx（20页珍藏版）》请在冰点文库上搜索。

数据结构课程设计哈希表实验报告

福建工程学院

课程设计

课程：

算法与数据结构

题目：

哈希表

专业：

网络工程

班级：

xxxxxx班

座号：

xxxxxxxxxxxx

姓名：

xxxxxxx

2011年12月31日

实验题目：

哈希表

一、要解决的问题

针对同班同学信息设计一个通讯录，学生信息有姓名，学号，电话号码等。

以学生姓名为关键字设计哈希表，并完成相应的建表和查表程序。

基本要求：

姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。

完成按姓名查询的操作。

运行的环境：

MicrosoftVisualC++6.0

二、算法基本思想描述

设计一个哈希表（哈希表内的元素为自定义的结构体）用来存放待填入的30个人名，人名为中国姓名的汉语拼音形式，用除留余数法构造哈希函数，用线性探查法解决哈希冲突。

建立哈希表并且将其显示出来。

通过要查找的关键字用哈希函数计算出相应的地址来查找人名。

通过循环语句调用数组中保存的数据来显示哈希表。

三、设计

1、数据结构的设计和说明

（1）结构体的定义

typedefstruct//记录

{

NAname;

NAxuehao;

NAtel;

}Record;

录入信息结构体的定义，包含姓名，学号，电话号码。

typedefstruct//哈希表

{

Record*elem[HASHSIZE];//数据元素存储基址

intcount;//当前数据元素个数

intsize;//当前容量

}HashTable;

哈希表元素的定义，包含数据元素存储基址、数据元素个数、当前容量。

2、关键算法的设计

（1）姓名的折叠处理

longfold（NAs）//人名的折叠处理

{

char*p;

longsum=0;

NAss;

strcpy（ss,s）;//复制字符串，不改变原字符串的大小写

strupr（ss）;//将字符串ss转换为大写形式

p=ss;

while（*p!

='\0'）

sum+=*p++;

printf（"\nsum====================%d",sum）;

returnsum;

}

（2）建立哈希表

1、用除留余数法构建哈希函数

2、用线性探测再散列法处理冲突

intHash1（NAstr）//哈希函数

{

longn;

intm;

n=fold（str）;//先将用户名进行折叠处理

m=n%HASHSIZE;//折叠处理后的数，用除留余数法构造哈希函数

returnm;//并返回模值

}Statuscollision（intp,intc）//冲突处理函数，采用二次探测再散列法解决冲突

{

inti,q;

i=c/2+1;

while（i

if（c%2==0）{

c++;

q=（p+i*i）%HASHSIZE;

if（q>=0）returnq;

elsei=c/2+1;

}

else{

q=（p-i*i）%HASHSIZE;

c++;

if（q>=0）returnq;

elsei=c/2+1;

}

}

returnUNSUCCESS;

}

voidbenGetTime（）;

voidCreateHash1（HashTable*H,Record*a）//建表，以人的姓名为关键字，建立相应的散列表

{inti,p=-1,c,pp;

system（"cls"）;//若哈希地址冲突，进行冲突处理

benGetTime（）;

for（i=0;i

c=0;

p=Hash1（a[i].name）;

pp=p;

while（H->elem[pp]!

=NULL）{

pp=collision（p,c）;

if（pp<0）{

printf（"第%d记录无法解决冲突",i+1）;//需要显示冲突次数时输出

continue;

}//无法解决冲突，跳入下一循环

}

H->elem[pp]=&（a[i]）;//求得哈希地址，将信息存入

H->count++;

printf（"第%d个记录冲突次数为%d。

\n",i+1,c）;//需要显示冲突次数时输出

}

printf（"\n建表完成!

\n此哈希表容量为%d,当前表内存储的记录个数为%d.\n",HASHSIZE,H->count）;

benGetTime（）;

}

（3）查找哈希表

voidSearchHash1（HashTable*H,intc）//在通讯录里查找姓名关键字，若查找成功，显示信息

{intp,pp;NAstr;

system（"cls"）;//c用来记录冲突次数,查找成功时显示冲突次数

benGetTime（）;

printf（"\n请输入要查找记录的姓名：

\n"）;

scanf（"%s",str）;

p=Hash1（str）;

pp=p;

while（（H->elem[pp]!

=NULL）&&（eq（str,H->elem[pp]->name）==-1））

pp=collision（p,c）;

if（H->elem[pp]!

=NULL&&eq（str,H->elem[pp]->name）==1）{

printf（"\n查找成功！

\n查找过程冲突次数为%d．以下是您需要要查找的信息：

\n\n",c）;

printf（"姓名：

%s\n学号：

%s\n电话号码：

%s\n",H->elem[pp]->name,H->elem[pp]->xuehao,H->elem[pp]->tel）;

}

elseprintf（"\n此人不存在，查找不成功!

\n"）;

benGetTime（）;

}

（4）显示哈希表

voidShowInformation（Record*a）//显示输入的用户信息

{inti;

system（"cls"）;

for（i=0;i

printf（"\n第%d个用户信息:

\n姓名：

%s\n学号：

%s\n电话号码：

%s\n",i+1,a[i].name,a[i].xuehao,a[i].tel）;

}

（5）主函数的设计

voidmain（intargc,char*argv[]）

{Recorda[MAXSIZE];

intc,flag=1,i=0;

HashTable*H;

H=（HashTable*）malloc（LEN）;

for（i=0;i

H->elem[i]=NULL;

H->size=HASHSIZE;

H->count=0;

}

while

（1）

{intnum;

printf（"\n"）;

printf（"\n欢迎使用同学通讯录录入查找系统"）;

printf（"\n哈希表的设计与实现"）;

printf（"\n【1】.添加用户信息"）;

printf（"\n【2】.读取所有用户信息"）;

printf（"\n【3】.以姓名建立哈希表（再哈希法解决冲突）"）;

printf（"\n【4】.以电话号码建立哈希表（再哈希法解决冲突）"）;

printf（"\n【5】.查找并显示给定用户名的记录"）;

printf（"\n【6】.查找并显示给定电话号码的记录"）;

printf（"\n【7】.清屏"）;

printf（"\n【8】.保存"）;

printf（"\n【9】.退出程序"）;

printf（"\n温馨提示：

"）;

printf（"\nⅠ.进行5操作前请先输出3"）;

printf（"\nⅡ.进行6操作前请先输出4"）;

printf（"\n"）;

printf（"请输入一个任务选项>>>"）;

printf（"\n"）;

scanf（"%d",&num）;

switch（num）{

case1:

getin（a）;

break;

case2:

ShowInformation（a）;

break;

case3:

CreateHash1（H,a）;/*以姓名建立哈希表*/

break;

case4:

CreateHash2（H,a）;/*以电话号码建立哈希表*/

break;

case5:

c=0;

SearchHash1（H,c）;

break;

case6:

c=0;

SearchHash2（H,c）;

break;

case7:

Cls（a）;

break;

case8:

Save（）;

break;

case9:

return0;

break;

default:

printf（"你输错了，请重新输入!

"）;

printf（"\n"）;

}

}

system（"pause"）;

return0;

}

3、模块结构图及各模块的功能：

四、源程序清单：

#include

#include

#include

#include

#defineMAXSIZE20

#defineMAX_SIZE20

#defineHASHSIZE53

#defineSUCCESS1

#defineUNSUCCESS-1

#defineLENsizeof（HashTable）

typedefintStatus;

typedefcharNA[MAX_SIZE];

typedefstruct

{

NAname;

NAxuehao;

NAtel;

}Record;

typedefstruct

{

Record*elem[HASHSIZE];

intcount;

intsize;

}HashTable;

Statuseq（NAx,NAy）

{

if（strcmp（x,y）==0）

returnSUCCESS;

elsereturnUNSUCCESS;

}

StatusNUM_BER;

voidgetin（Record*a）

{inti;

system（"cls"）;

printf（"输入要添加的个数：

\n"）;

scanf（"%d",&NUM_BER）;

for（i=0;i

{

printf（"请输入第%d个记录的姓名:

\n",i+1）;

scanf（"%s",a[i].name）;

printf（"请输入%d个记录的学号:

\n",i+1）;

scanf（"%s",a[i].xuehao）;

printf（"请输入第%d个记录的电话号码:

\n",i+1）;

scanf（"%s",a[i].tel）;

}

}

voidShowInformation（Record*a）

{inti;

system（"cls"）;

for（i=0;i

printf（"\n第%d个用户信息:

\n姓名：

%s\n学号：

%s\n电话号码：

%s\n",i+1,a[i].name,a[i].xuehao,a[i].tel）;

}

voidCls（Record*a）{

printf（"*"）;

system（"cls"）;

}

longfold（NAs）

{

char*p;

longsum=0;

NAss;

strcpy（ss,s）;

strupr（ss）;

p=ss;

while（*p!

='\0'）

sum+=*p++;

printf（"\nsum====================%d",sum）;

returnsum;

}

intHash1（NAstr）

{

longn;

intm;

n=fold（str）;

m=n%HASHSIZE;

returnm;

}

intHash2（NAstr）

{

longn;

intm;

n=atoi（str）;

m=n%HASHSIZE;

returnm;

}

Statuscollision（intp,intc）

{

inti,q;

i=c/2+1;

while（i

if（c%2==0）{

c++;

q=（p+i*i）%HASHSIZE;

if（q>=0）returnq;

elsei=c/2+1;

}

else{

q=（p-i*i）%HASHSIZE;

c++;

if（q>=0）returnq;

elsei=c/2+1;

}

}

returnUNSUCCESS;

}

voidbenGetTime（）;

voidCreateHash1（HashTable*H,Record*a）

{inti,p=-1,c,pp;

system（"cls"）;

benGetTime（）;

for（i=0;i

c=0;

p=Hash1（a[i].name）;

pp=p;

while（H->elem[pp]!

=NULL）{

pp=collision（p,c）;

if（pp<0）{

printf（"第%d记录无法解决冲突",i+1）;

continue;

}

}

H->elem[pp]=&（a[i]）;

H->count++;

printf（"第%d个记录冲突次数为%d。

\n",i+1,c）;

}

printf（"\n建表完成!

\n此哈希表容量为%d,当前表内存储的记录个数为%d.\n",HASHSIZE,H->count）;

benGetTime（）;

}

voidSearchHash1（HashTable*H,intc）

{intp,pp;NAstr;

system（"cls"）;

benGetTime（）;

printf（"\n请输入要查找记录的姓名：

\n"）;

scanf（"%s",str）;

p=Hash1（str）;

pp=p;

while（（H->elem[pp]!

=NULL）&&（eq（str,H->elem[pp]->name）==-1））

pp=collision（p,c）;

if（H->elem[pp]!

=NULL&&eq（str,H->elem[pp]->name）==1）{

printf（"\n查找成功！

\n查找过程冲突次数为%d．以下是您需要要查找的信息：

\n\n",c）;

printf（"姓名：

%s\n学号：

%s\n电话号码：

%s\n",H->elem[pp]->name,H->elem[pp]->xuehao,H->elem[pp]->tel）;

}

elseprintf（"\n此人不存在，查找不成功!

\n"）;

benGetTime（）;

}

voidbenGetTime（）{

SYSTEMTIMEsys;

GetLocalTime（&sys）;

printf（"%4d/%02d/%02d%02d:

%02d:

%02d.%03d\n",sys.wYear,sys.wMonth,sys.wDay,sys.wHour,sys.wMinute,sys.wSecond,sys.wMilliseconds）;

}

voidCreateHash2（HashTable*H,Record*a）

{inti,p=-1,c,pp;

benGetTime（）;

for（i=0;i

c=0;

p=Hash2（a[i].tel）;

pp=p;

while（H->elem[pp]!

=NULL）{

pp=collision（p,c）;

if（pp<0）{

printf（"第%d记录无法解决冲突",i+1）;

continue;

}

}

H->elem[pp]=&（a[i]）;

H->count++;

printf（"第%d个记录冲突次数为%d。

\n",i+1,c）;

}

printf（"\n建表完成!

\n此哈希表容量为%d,当前表内存储的记录个数为%d.\n",HASHSIZE,H->count）;

benGetTime（）;

}

voidSearchHash2（HashTable*H,intc）

{NAtele;intp,pp;

system（"cls"）;

benGetTime（）;

printf（"\n请输入要查找记录的电话号码：

\n"）;

scanf（"%s",tele）;

p=Hash2（tele）;

pp=p;

while（（H->elem[pp]!

=NULL）&&（eq（tele,H->elem[pp]->tel）==-1））

pp=collision（p,c）;

if（H->elem[pp]!

=NULL&&eq（tele,H->elem[pp]->tel）==1）{

printf（"\n查找成功！

\n查找过程冲突次数为%d．以下是您需要要查找的信息：

\n\n",c）;

printf（"姓名：

%s\n学号：

%s\n电话号码：

%s\n",H->elem[pp]->name,H->elem[pp]->xuehao,H->elem[pp]->tel）;

}

elseprintf（"\n此人不存在，查找不成功!

\n"）;

benGetTime（）;

}

voidSave（）{

FILE*fp;

if（（fp=fopen（"c:

\test.txt","w"））==NULL）{

printf（"\nERRORopeningcustometfile"）;

}

fclose（fp）;

}

voidmain（intargc,char*argv[]）

{Recorda[MAXSIZE];

intc,flag=1,i=0;

HashTable*H;

H=（HashTable*）malloc（LEN）;

for（i=0;i

H->elem[i]=NULL;

H->size=HASHSIZE;

H->count=0;

}

while

（1）

{intnum;

printf（"\n"）;

printf（"\n欢迎使用同学通讯录录入查找系统"）;

printf（"\n哈希表的设计与实现"）;

printf（"\n【1】.添加用户信息"）;

printf（"\n【2】.读取所有用户信息"）;

printf（"\n【3】.以姓名建立哈希表（再哈希法解决冲突）"）;

printf（"\n【4】.以电话号码建立哈希表（再哈希法解决冲突）"）;

printf（"\n【5】.查找并显示给定用户名的记录"）;

printf（"\n【6】.查找并显示给定电话号码的记录"）;

printf（"\n【7】.清屏"）;

printf（"\n【8】.保存"）;

printf（"\n【9】.退出程序"）;

printf（"\n温馨提示：

"）;

printf（"\nⅠ.进行5操作前请先输出3"）;

printf（"\nⅡ.进行6操作前请先输出4"）;

printf（"\n"）;

printf（"请输入一个任务选项>>>"）;

printf（"\n"）;

scanf（"%d",&num）;

switch（num）{

case1:

getin（a）;

break;

case2:

ShowInformation（a）;

break;

case3:

CreateHash1（H,a）;

break;

case4:

CreateHash2（H,a）;

break;

case5:

c=0;

SearchHash1（H,c）;

break;

case6:

c=0;

SearchHash2（H,c）;

break;

case7:

Cls（a）;

break;

case8:

Save（）;

break;

case9:

return0;

break;

default:

printf（"你输错了，请重新输入!

"）;

printf（"\n"）;

}

}

system（"pause"）;

return0;

}

五、测试数据及测试结果：

1、主界面

2、添加用户信息

添加后自动跳转到主界面

3、查询所有用户信息（并且自动跳转到主界面）

4、以姓名为关键字建立哈希表，查找并显示给定用户名的记录

查找用户名heziwen

5、清屏功能使用

六、课程设计总结及心得体会：

通过这一周的课程设计，加深我对《算法与数据结构》这门课程所学内容的进一步的理解与掌握；同时，通过对哈希表的设计，使得我将计算机课程所学知识与实际问题很好的相链接在一起。

在这次课程设计中，培养了我开发一个中小型程序的能力。

在课程设计中，出现了蛮多错误的，最多的错误是，提示我的变量i，p等没有进行定义，但是我看了代码确实已经有inti;等代码，然后我将inti;放到清屏函数前就解决了问题。

程序最关键的部分就是哈希表的设计，冲突解决，和关键字查找。

考虑到姓名会重叠，关键字以姓名来查找时出现的问题，所以加上了一段姓名的折叠处理。

用线性探测在散列法进行解决冲突，用除留函数法来构造哈希函数。

在课程设计的过程中我遇到了许多课外的知识，这便促使我去查阅更多的课外资料来充实自己的内容，同时学会在面对困难时药耐心的分析它细心地解决它以及通过合作更完美的深入了解剖析它以便的到提高。

细心、耐心、求知，是我这次课程设计最大的收获。