哈希表制作通讯录数据结构程序设计.docx
《哈希表制作通讯录数据结构程序设计.docx》由会员分享，可在线阅读，更多相关《哈希表制作通讯录数据结构程序设计.docx（20页珍藏版）》请在冰点文库上搜索。
哈希表制作通讯录数据结构程序设计
软件学院
课程设计报告书
课程名称数据结构
设计题目哈希表制作通讯录
专业班级
学号
姓名
指导教师
2014年1月
1设计时间.....................................................1
2设计目的.....................................................1
3设计任务.....................................................1
4设计内容.....................................................1
4.1需求分析................................................1
4.11程序所能达到的功能.............................................................1
4.12输入的形式和输入的范围......................................................1
4.2总体设计................................................1
4.21说明本程序中用到的所有抽象数据类型的定义.......................1
4.22说明主程序的流程.................................................................2
4.23说明各程序模块之间的层次（调用）关系..............................2
4.3详细设计................................................3
4.31实现概要设计中定义的所有数据类型，对每个操作只需要写出
伪码算法.......................................................................................3
4.32对主程序和其它主要函数写出伪码算法.................................4
4.4测试....................................................5
4.5附录....................................................6
5总结与展望..................................................16
参考文献......................................................17
成绩评定......................................................18
1设计时间
2014年1月13日到2014年1月15号
2设计目的
要求学生掌握数据结构的应用、算法的编写、类C语言的算法转换成C程序并上机调试的
基本方法。
这对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的
促进作用。
3设计任务
针对你所在班集体中的“人名”，设计一个哈希表，使得平均查找长度不超过R，完成相
应的建表和查找过程。
4设计内容
（1）每个人的信息至少包括姓名，电话，地址。
至少包括对通讯录的创建，添加和按姓名
查找等功能。
（2）假设人名为汉语拼音全拼形式，待插入哈希表的长度为你所在班级的人数。
哈希函数
用除留余数法构造，采用链地址法或二次探测再散列法解决冲突。
（3）完成菜单设计。
操作有必要的提示。
4.1需求分析
4.11程序所能达到的功能
以人命的汉语拼音全拼形式查找你所在班级的人的信息（姓名，电话，地址）
4.12输入的形式和输入的范围
把人名都到转换成汉语拼音全拼的形式，人命最大长度不超过20个字符
4.2总体设计
4.21说明本程序中用到的所有抽象数据类型的定义
该程序采用的是结构体类型来处理学生的所有基本信息，如下所述。
1
typedefstruct{/*用结构体类型来处理学生的所有基本信息*/
NAname;/*NA为typedef定义的字符数组类型*/
}Record;
typedefstruct{/*哈希表*/
Record*elem[HASHSIZE];//数据元素存储基址
intcount;//当前存储的数据元素个数
intsize;//当前容量，即表长
}HashTable;
4.22说明主程序的流程
inputsenter
insert
ddelete
menu_select
find
listdisplay
search
main
save
文
load
件
exit
函数之间的相互调用
4.23说明各程序模块之间的层次（调用）关系
2
各函数模块之间的调用关系主要是主函数调用主要功能函数，即：
输入与保存函数、哈希
表建立函数、查找信息函数，主要功能函数也会调用一些基本功能函数完成相应功能，如：
CreateHash（）会调用Hash（）来求哈希地址，而Hash（）会调用fold（）对关键字先进行折叠处理，
当地址冲突时，Hash（）又会调用collision（）解决冲突；SearchHash）（也会调用Hash（）、fold（）、
collision（）以及eq（）。
并且主函数利用while循环使各个功能函数运行完毕后都会回到菜单，询
问是否继续进行操作。
4.3详细设计
4.31实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法
voidmain（）
{
start=last=NULL;
for（;;）/*无限循环*/
{
switch（menu_select（））/*调用主界面的选择函数，带回返回值*/
{
case1:
enter（）;
continue;
case2:
ddelete（&start,&last）;
continue;
case3:
list（）;
continue;
case4:
search（）;
continue;
case5:
save（）;
continue;case6:
load（）;
continue;
case7:
exit（0）;
}
}
}
intmenu_select（void）/*主目录*/
{
chars[80];
intc;
printf（",,,,,,^欢迎使用DOS通讯录系统^,,,,,,\n"）;
printf（"************请在做其它操作前先导入*************\n"）;
3
printf（"***********************************************\n"）;
printf（"*****************1.输入信息******************\n"）;
printf（"*****************2.删除信息******************\n"）;printf（"*****************3.显示信息******************\n"）;
printf（"*****************4.查找******************\n"）;printf（"*****************5.存盘******************\n"）;printf（"*****************6.导入******************\n"）;printf（"*****************7.退出******************\n"）;printf（"***********************************************\n"）;
do{
printf（"\nPleaseenteryourchoice:
\n"）;
gets（s）;
c=atoi（s）;/*将获取的字符串转换成整型*/
}while（c<0||c>7）;
returnc;/*返回输入值*/
}
4.32对主程序和其它主要函数写出伪码算法
structaddress*info;/*定义当前结点*/
for（;;）
{
info=（structaddress*）malloc（sizeof（structaddress））;/*为当前结点分配
空间*/
if（!
info）
{
printf（"\nOutofmemory"）;
exit（0）;/*如果分配空间
失败，退出程序*/
}
printf（"输入空姓名结束:
\n"）;
inputs（"请输入姓名:
",info->name,10）;
if（!
info->name[0]）break;/*如果输入姓名为
空，结束循环*/
inputs（"请输入街道:
",info->street,50）;
inputs（"请输入城市:
",info->city,15）;
inputs（"请输入国家:
",info->state,15）;
inputs（"请输入电话:
",info->tel,7）;
insert（info,&start,&last）;/*调用结点插入函数*/
}
4
4.4测试
图4-1程序运行图
图4-2输入信息图
5
图4-3显示信息
4.5附录
#include
#include
#include
structaddress{/*定义结构*/
charname[10];
charstreet[50];
charcity[10];
charstate[15];
chartel[7];
structaddress*next;/*后继指针*/
structaddress*prior;/*前驱指针*/
};
6
structaddress*start;/*首结点*/
structaddress*last;/*尾结点*/
structaddress*find（char*）;/*声明查找函数*/
voidenter（）;/*函数声明*/
voidsearch（）;
voidsave（）;
voidload（）;
voidlist（）;
voidddelete（structaddress**start,structaddress**last）;
voidinsert（structaddress*i,structaddress**start,
structaddress**last）;
voidinputs（char*,char*,int）;
voiddisplay（structaddress*）;
intmenu_select（void）;
voidmain（）
{
start=last=NULL;
for（;;）
{
switch（menu_select（））
{
case1:
enter（）;
continue;
case2:
ddelete（&start,&last）;
continue;
case3:
list（）;
7
continue;
case4:
search（）;
continue;
case5:
save（）;
continue;
case6:
load（）;
continue;
case7:
exit（0）;
}
}
}
intmenu_select（void）/*主目录*/
{
chars[80];
intc;
printf（"⋯⋯⋯⋯⋯⋯欢^迎使用DOS通讯录系统^⋯⋯⋯⋯⋯⋯\n"）;
printf（"************请在做其它操作前先导入*************\n"）;
printf（"***********************************************\n"）;
printf（"*****************1.输入信息******************\n"）;
printf（"*****************2.删除信息******************\n"）;
printf（"*****************3.显示信息******************\n"）;
printf（"*****************4.查找******************\n"）;
printf（"*****************5.存盘******************\n"）;
printf（"*****************6.导入******************\n"）;
printf（"*****************7.退出******************\n"）;
printf（"***********************************************\n"）;
do{
printf（"\nPleaseenteryourchoice:
\n"）;
8
gets（s）;
c=atoi（s）;
}while（c<0||c>7）;
returnc;/*返回输入值*/
}
voidenter（）/*输入函数,本函数循环输入资料，当输入姓名为空
时退出*/
{
structaddress*info;/*定义当前结点*/
for（;;）
{
info=（structaddress*）malloc（sizeof（structaddress））;/*为当前结点分配空间*/
if（!
info）
{
printf（"\nOutofmemory"）;
exit（0）;/*如果分配空间失
败，退出程序*/
}
printf（"输入空姓名结束:
\n"）;
inputs（"请输入姓名:
",info->name,10）;
if（!
info->name[0]）
break;/*如果输入姓名为空，结束循环*/
inputs（"请输入街道:
",info->street,50）;
inputs（"请输入城市:
",info->city,15）;
inputs（"请输入国家:
",info->state,15）;
inputs（"请输入电话:
",info->tel,7）;
9
insert（info,&start,&last）;/*调用结点插入函数*/
}
}
voidinputs（char*prompt,char*s,intcount）/*输入函数，有越界检测功能*/
{
charp[255];
do
{
printf（prompt）;
fgets（p,254,stdin）;
if（strlen（p）>count）
printf（"\nTooLong\n"）;
}while（strlen（p）>count）;
p[strlen（p）-1]=0;
strcpy（s,p）;
}
voidinsert（/*数据插入函数*/
structaddress*i,
structaddress**start,
structaddress**last
）
{
if（*last==NULL）/*如果尾结点为空,意味着当前链表为空*/
10
{
i->next=NULL;
i->prior=NULL;
*last=i;
*start=i;
return;
}
else
{
（*last）->next=i;
i->prior=*last;
i->next=NULL;
*last=（*last）->next;
}
}
voidddelete（structaddress**start,structaddress**last）/*删除函数*/
{
structaddress*info;
chars[80];
inputs（"请输入姓名:
",s,10）;/*输入欲删除结点的name域内容*/
info=find（s）;/*查找该内容*/
if（info）/*如果找到*/
{
printf（"Deleting......\n"）;
if（*start==info）/*如果该结点为首结点,把该结点的下驱作为
11
新的首结点（入口）*/
{
*start=info->next;
if（*start）
（*start）->prior=NULL;
else*last=NULL;
}
else/*如果欲删除的结点不是首结点*/
{
info->prior->next=info->next;/*令该结点的前驱的next指针指向该结点的
后驱，
*又令该结点的后驱的prior指点指向该结点
的前驱*/
if（info!
=*last）/*如果该结点是尾结点，则令该结点的前驱
为尾结点*/
info->next->prior=info->prior;
else
*last=info->prior;
}
free（info）;/*释放该结点所占用的内存*/
printf（"-Ok,删除成功!
\n"）;
}
}
structaddress*find（char*name）/*查找函数,形参为欲查找结点的name域*/
{
structaddress*info;
info=start;
while（info）
12
{
if（!
strcmp（name,info->name））returninfo;
info=info->next;
}
printf（"未找到相关信息.\n"）;
returnNULL;
}
/*输出整个链表*/
voidlist（void）
{
structaddress*info;
info=start;
if（info==NULL）
printf（"当前记录为空!
"）;
elseprintf（"姓名\t街道\t\t城市\t国家\t电话\t\n"）;
while（info）
{
display（info）;
if（info->next==NULL）{break;}info=info->next;
};
printf（"\n\n"）;
}
voiddisplay（structaddress*info）/*输出传入结点函数*/
{
printf（"%s\t",info->name）;
printf（"%s\t",info->street）;
printf（"%s\t",info->city）;
13
printf（"%s\t",info->state）;
printf（"%s\t",info->tel）;
printf（"\n"）;
}
voidsearch（void）/*查找函数*/
{
charname[40];
structaddress*info;
printf（"请输入要查找的姓名:
"）;/*输入欲查找的姓名*/
gets（name）;
info=find（name）;
if（!
info）
printf（"姓名不存在\n"）;/*如果没找到，显示Notfound*/
else
display（info）;/*如果找到，显示该结点资料*/
}
voidsave（void）/*保存函数*/
{
structaddress*info;
FILE*fp;
fp=fopen（"record.txt","wb"）;/*生成文件*/
if（!
fp）
{
printf（"Cannotopenfile.\n"）;
return;
}
nSaveing⋯⋯\n"）;
14
info=start;
while（info）/*把链表写入文件*/
{
fwrite（info,sizeof（structaddress）,1,fp）;
info=info->next;
}
printf（"-ok!
\n"）;
fclose（fp）;/*链表全部写入文件后，关闭文件*/
}
voidload（）/*调用预存文件函数*/
{
registerintt,size;
structaddress*info,*temp=0;
char*p;
FILE*fp;/*打开文件*/
if（（fp=fopen（"record.txt","r"））==NULL）
{
printf（"Cannotopenfile!
\n"）;
return;
}
printf（"\n\nLoading...\n"）;/*调用文件*/
size=sizeof（structaddress）;/*为结点分配内存*/
start=（structaddress*）malloc（size）;
if（!
start）/*如果读取失败，返回*/
{
printf（"Outofmemory!
\n"）;
15
exit（0）;
}
info=start;
p=（char*）info;
while（（*p++=getc（fp））!
=EOF）
{
for（t=0;t*p++=getc（fp）;
info->next=（structaddress*）malloc（size）;
if（!
info->next）
{
printf（"Outofmemory!
\n"）;
return;
}
info->prior=temp;
temp=info;
info=info->next;
p=（char*）info;
}
temp->next=0;
last=temp;
start->prior=0;
fclose（fp）;
printf（"-OK!
\n"）;
}
5总结与展望
通过一星期的数据结构与算法分析课程设计实习，我从中受益匪浅。
对数据结构程序设
计这一门课程有了更深一步的认识，对一些细节语法有了更新、更深刻的理解，知其然，亦知
其所以然。
尤其在程序调试过程中，程序的执行过程与语法相联系，尽量独立差错纠错，最后
16
请教老师，对程序的优化设计和调试方法都有了很大的进步。
这次课程设计的进步是很大的，
我了解到，我们需要将所学的理论知识和实践联系起来，在实践设计中不断进步，不断熟练，
光是读透书本知识是不够的。
虽然我对一些C语言知识运用得还不是很熟练，但是我相信在接
下来的学习过程中，我会有更大的进步，还有很大的空间可以发挥。
在这次课程设计中，我做的是课题10，建立27人的通讯录，设计散列表实现通讯录查找系统，
并完成相应的建表和查表程序。
其中运用了很多方面的知识。
如，运用结构体建通讯录，保存
信息。
构建哈希表，用除留余数法构造哈希函数，采用二次探测再散列法解决冲突，对关键字
的折叠处理等等。
可以看出，一个简单设计的完成，需要很多方面的知识来共同完成，每方面
的知识都要理解透彻，运用熟练，其实我们需要在平日里打好基础。
而且，要会用其他算法或
其他数据结构来优化算法，这对知识运用的灵活性掌握有很高的要求。
所以，通过一次短短的
课程设计就可以看出，我们需要学习的还很多，掌握的知识也不够透彻明白。
总之，这次课程
设计，让我看到很多不足，为我今后的学习指出了新的学习方向，这是我最大的收获
参考文献
17
[1]严蔚敏，
升级会员 