哈希表制作通讯录-数据结构程序设计.doc

软 件 学 院
课程设计报告书

课程名称 数据结构
设计题目 哈希表制作通讯录
专业班级
学 号
姓 名
指导教师

2014年 1月
17

目录
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说明各程序模块之间的层次（调用）关系 3
4.3详细设计 3
4.31实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法 3
4.32对主程序和其它主要函数写出伪码算法 4
4.4测试 5
4.5 附录 6
5 总结与展望 16
参考文献 18
成绩评定 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说明本程序中用到的所有抽象数据类型的定义
该程序采用的是结构体类型来处理学生的所有基本信息，如下所述。
typedef struct{ /*用结构体类型来处理学生的所有基本信息*/
NA name; /*NA为typedef定义的字符数组类型*/
}Record;
typedef struct{ /*哈希表*/
Record *elem[HASHSIZE]; //数据元素存储基址
int count; //当前存储的数据元素个数
int size; //当前容量，即表长
}HashTable;
4.22说明主程序的流程
main
menu_select
enter
ddelete
list
search
save
save
load
exit
inputs
insert
find
display
文件
函数之间的相互调用

4.23说明各程序模块之间的层次（调用）关系
各函数模块之间的调用关系主要是主函数调用主要功能函数，即：输入与保存函数、哈希表建立函数、查找信息函数，主要功能函数也会调用一些基本功能函数完成相应功能，如：CreateHash()会调用Hash()来求哈希地址，而Hash()会调用fold()对关键字先进行折叠处理，当地址冲突时，Hash()又会调用collision()解决冲突；SearchHash()也会调用Hash()、fold()、collision()以及eq()。并且主函数利用while循环使各个功能函数运行完毕后都会回到菜单，询问是否继续进行操作。
4.3详细设计
4.31实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法
void main()
{
start = last = NULL;

for(;;) /*无限循环*/
{
switch(menu_select()) /*调用主界面的选择函数，带回返回值*/
{
case 1:enter();
continue;
case 2:ddelete(&start,&last);
continue;
case 3:list();
continue;
case 4:search();
continue;
case 5:save();
continue;
case 6:load();
continue;
case 7:exit(0);
}
}
}
int menu_select(void) /*主目录*/
{
char s[80];
int c;
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("\nPlease enter your choice:\n");
gets(s);
c = atoi(s); /*将获取的字符串转换成整型*/
}while(c<0||c>7);

return c; /*返回输入值*/
}
4.32对主程序和其它主要函数写出伪码算法
struct address *info; /*定义当前结点*/
for(;;)
{
info=(struct address *)malloc(sizeof(struct address)); /*为当前结点分配空间*/
if(!info)
{
printf("\n Out of memory");
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-1 程序运行图

图4-2输入信息图

图4-3显示信息
4.5 附录
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct address{ /*定义结构*/
char name[10];
char street[50];
char city[10];
char state[15];
char tel[7];
struct address *next; /*后继指针*/
struct address *prior; /*前驱指针*/
};

struct address *start; /*首结点*/
struct address *last; /*尾结点*/
struct address *find(char *); /*声明查找函数*/

void enter(); /*函数声明*/
void search();
void save();
void load();
void list();
void ddelete(struct address **start,struct address **last);
void insert(struct address *i,struct address **start,
struct address **last);
void inputs(char *,char *,int);
void display(struct address *);
int menu_select(void);
void main()
{
start = last = NULL;

for(;;)
{
switch(menu_select())
{
case 1:enter();
continue;
case 2:ddelete(&start,&last);
continue;
case 3:list();
continue;
case 4:search();
continue;
case 5:save();
continue;
case 6:load();
continue;
case 7:exit(0);
}
}
}

int menu_select(void) /*主目录*/
{
char s[80];
int c;
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("\nPlease enter your choice:\n");
gets(s);
c = atoi(s);
}while(c<0||c>7);

return c; /*返回输入值*/
}

void enter() /*输入函数,本函数循环输入资料，当输入姓名为空时退出*/
{
struct address *info; /*定义当前结点*/

for(;;)
{
info=(struct address *)malloc(sizeof(struct address)); /*为当前结点分配空间*/
if(!info)
{
printf("\n Out of memory");
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); /*调用结点插入函数*/
}
}

void inputs(char *prompt,char *s,int count) /*输入函数，有越界检测功能*/
{
char p[255];
do
{
printf(prompt);
fgets(p,254,stdin);
if(strlen(p)>count)
printf("\nToo Long\n");
}while(strlen(p)>count);

p[strlen(p)-1]=0;
strcpy(s,p);
}

void insert( /*数据插入函数*/
struct address *i,
struct address **start,
struct address **last
)
{

if(*last==NULL) /*如果尾结点为空,意味着当前链表为空*/
{
i->next=NULL;
i->prior=NULL;
*last=i;
*start=i;
return;
}

else
{

(*last)->next=i;
i->prior=*last;
i->next=NULL;
*last=(*last)->next;
}
}
void ddelete(struct address **start,struct address **last) /*删除函数*/
{
struct address *info;
char s[80];

inputs("请输入 姓名:",s,10); /*输入欲删除结点的name域内容*/
info=find(s); /*查找该内容*/
if(info) /*如果找到*/
{
printf("Deleting......\n");
if(*start==info) /*如果该结点为首结点,把该结点的下驱作为新的首结点（入口）*/
{
*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");
}
}

struct address *find(char *name) /*查找函数,形参为欲查找结点的name域*/
{
struct address *info;
info=start;
while(info)
{
if(!strcmp(name,info->name))return info;
info=info->next;
}
printf("未找到相关信息.\n");
return NULL;
}
/*输出整个链表*/
void list(void)
{
struct address *info;
info=start;
if(info==NULL)
printf("当前记录为空!");
else printf("姓名\t街道\t\t城市\t国家\t电话\t\n");
while(info)
{
display(info);
if(info->next==NULL){break; } info=info->next;
};
printf("\n\n");

}

void display(struct address *info) /*输出传入结点函数*/
{
printf("%s\t",info->name);
printf("%s\t",info->street);
printf("%s\t",info->city);
printf("%s\t",info->state);
printf("%s\t",info->tel);
printf("\n");
}

void search(void) /*查找函数*/
{
char name[40];
struct address *info;
printf("请输入要查找的姓名:"); /*输入欲查找的姓名*/
gets(name);
info=find(name);
if(!info)
printf("姓名不存在\n"); /*如果没找到，显示Not found*/
else
display(info); /*如果找到，显示该结点资料*/
}

void save(void) /*保存函数*/
{
struct address *info;
FILE *fp;
fp=fopen("record.txt","wb"); /*生成文件*/
if(!fp)
{
printf("Cannot open file.\n");
return;
}
printf("\nSaveing ……\n");
info=start;
while(info) /*把链表写入文件*/
{
fwrite(info,sizeof(struct address),1,fp);
info=info->next;
}
printf("-ok!\n");
fclose(fp);/*链表全部写入文件后，关闭文件*/

}

void load() /*调用预存文件函数*/
{
register int t, size;
struct address *info,*temp=0;
char *p;
FILE *fp; /*打开文件*/
if((fp=fopen("record.txt","r"))==NULL)
{
printf("Cannot open file!\n");
return;

}
printf("\n\nLoading...\n"); /*调用文件*/
size=sizeof(struct address); /*为结点分配内存*/
start= (struct address *)malloc(size);
if(!start) /*如果读取失败，返回*/
{
printf("Out of memory!\n");
exit(0);
}
info=start;
p=(char*)info;
while((*p++=getc(fp))!=EOF)
{
for(t=0;t<size-1;++t)
*p++=getc(fp);
info->next=(struct address *)malloc(size);
if(!info->next)
{
printf("Out of memory!\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 总结与展望
通过一星期的数据结构与算法分析课程设计实习，我从中受益匪浅。对数据结构程序设计这一门课程有了更深一步的认识，对一些细节语法有了更新、更深刻的理解，知其然，亦知其所以然。尤其在程序调试过程中，程序的执行过程与语法相联系，尽量独立差错纠错，最后请教老师，对程序的优化设计和调试方法都有了很大的进步。这次课程设计的进步是很大的，我了解到，我们需要将所学的理论知识和实践联系起来，在实践设计中不断进步，不断熟练，光是读透书本知识是不够的。虽然我对一些C语言知识运用得还不是很熟练，但是我相信在接下来的学习过程中，我会有更大的进步，还有很大的空间可以发挥。
在这次课程设计中，我做的是课题10，建立27人的通讯录，设计散列表实现通讯录查找系统，并完成相应的建表和查表程序。其中运用了很多方面的知识。如，运用结构体建通讯录，保存信息。构建哈希表，用除留余数法构造哈希函数，采用二次探测再散列法解决冲突，对关键字的折叠处理等等。可以看出，一个简单设计的完成，需要很多方面的知识来共同完成，每方面的知识都要理解透彻，运用熟练，其实我们需要在平日里打好基础。而且，要会用其他算法或其他数据结构来优化算法，这对知识运用的灵活性掌握有很高的要求。所以，通过一次短短的课程设计就可以看出，我们需要学习的还很多，掌握的知识也不够透彻明白。总之，这次课程设计，让我看到很多不足，为我今后的学习指出了新的学习方向，这是我最大的收获

参考文献

[1]严蔚敏，吴伟民。《数据结构》清华大学计算机系列教材。北京：清华大学出版社，2007
[2] 陈锐。《零基础学数据结构》北京：机械工业出版社，2010。]谭浩强《C程序设计（第三版）》北京：清华大学出版社，2005
成绩评定

成绩 教师签字