通讯录的制作
课程设计名称: 通讯录的制作
专 业 班 级 :
学 生 姓 名 :
学 号 :
指 导 教 师 :
课程设计时间: 2008年6月23日
1
数据结构课程设计
————通讯录的制作
摘要:............................................................................................................................................... 2
第一章 绪论..................................................................................................................................... 3
1.1课程设计的目的 ................................................................................................................. 3
1.2 问题描述............................................................................................................................ 3
1.3 开发环境............................................................................................................................ 3
1.3.1硬件环境 .................................................................................................................. 3
1.3.2软件环境 .................................................................................................................. 3
1.4开发工具和编程语言 ......................................................................................................... 3
1.4.1 开发工具 ................................................................................................................. 3
1.4.2编程语言 .................................................................................................................. 3 第二章 通讯录的具体实现 .............................................................................................................. 3
2(1 通讯录双向链
的建立 ................................................................................................. 3
2(2 通讯录项目的插入 ......................................................................................................... 4
2(3 通讯录节点的查询 ......................................................................................................... 6
2(4 通讯录节点的删除 ......................................................................................................... 7
2(5 通讯录的输出 ................................................................................................................. 8
2(6 通讯录保存 ..................................................................................................................... 8
2(7 通讯录载入 ..................................................................................................................... 9
2(8 调试分析 ........................................................................................................................ 10
2.8.1程序展示 ................................................................................................................ 10
2.8.2 程序分析 ............................................................................................................... 13 第三章 课程设计总结 ............................................................................................................. 14 第四章 源程序代码................................................................................................................. 14
摘要:
纸质的通讯录已经不能满足我们的要求,更新麻烦,查询困难等缺点是纸质
通讯录所不能克服的。在此情况下,迫切需要一个电子版的通讯录来满足我们的
需求。这次课程设计的通讯录采用了双向链表这一数据结构,并完成了添加、查
找、删除、保存、载入等功能。在VC 6.0平台下实现了简单的人机交互。
关键字:VC 6.0 通讯录 双向链表
2
第一章 绪论
1.1课程设计的目的
数据结构课程主要是研究非数值计算的程序设计中所出现的计算机操作对象以及它们之间的关系和操作的学科。学习数据结构是为了将实际问题中所涉及的对象在计算机表示出来并对它们进行处理。通过课程设计可以提高思维能力、促进综合应用能力和专业素质的提高。
1.2 问题描述
随着生活水平的日益提高,人们的电话号码频繁更换;随着城市开发的日益加快,人们的住处也时有改变。由此导致的问题就是用传统的纸质媒介来记录亲友同事的联系方式变得十分不便。一旦纸质通讯录上的某人的联系方式发生改变,就只能将其划掉,另写一行。当这样的修改过多之后,整个通讯录就会变得十分凌乱;再随着记录的人数,就会引起查找上的困难,有时需要从头到尾找好几遍才能找到所需的联系方式;另外由于纸质媒介不容易保存,经常出现破损和丢失的现象,因此对纸质通讯录进行改进是迫切需要解决的问题,这次课程设计的通讯录采用了双向链表这一数据结构,要求的模块包括:添加、查找、删除、保存、载入。在VC 6.0平台下实现了简单的人机交互。
1.3 开发环境
1.3.1硬件环境
基于X86的PC
1.3.2软件环境
(1)Windows XP
(2)Virtual Serial Port Driver 6.0 (by Eltima Software)
1.4开发工具和编程语言
1.4.1 开发工具
Microsoft Visual C++ 6.0 1.4.2编程语言
Visual C
第二章 通讯录的具体实现
2(1 通讯录双向链表的建立
a).需求分析
建立一个双向链表。
b).概要设计
typedef struct DuLNode{
ElemType data;
struct DuLNode *prior;
struct DuLNode *next;
3
}DuLNode,*DuLinkList;
c)详细设计
struct address{
char name[30];
char street[100];
char city[30];
char state[30];
char zip[11];
struct address *next;
struct address *prior;
};
2(2 通讯录项目的插入
a)需求分析
向一个已经初始化的双向链表中添加一个项目。
b)概要设计
向链表中添加一个项目时, 应该首先检查链表中是否还有空位给新节 在
点。然后,由于双向链表被定义成不含有相同的项目,所以要检查链表中是否已
经有该项目。如果这个新项目通过前两步检查,就可以创建一个新的节点,将项
目复制到节点中,并设置此节点的前导和后继指针为NULL。然后要更新链表结
构的size成员,以记录添加了一个新项目。接下来,要找出该把此节点放在链表
中的什么位置,如果链表为空,就要将后继指针指向该新节点,否则,在链表中
查找到放置该节点的位置。
c)详细设计
void enter()
{
struct address *info;
for(;;)
{
info=(struct address *)malloc(sizeof(struct address));
if(!info)
{
printf("\n Out of memory");
exit(0);
}
inputs("Enter name:",info->name,30);
if(!info->name[0])
break;
inputs("Enter street:",info->street,100);
inputs("Enter city:",info->city,30);
inputs("Enter state:",info->state,30);
inputs("Enter zip:",info->zip,11);
4
dls_store(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 dls_store(struct address *i, struct address **start, struct address **last )
{
struct address *old,*p;
if(*last==NULL)
{
i->next=NULL;
i->prior=NULL;
*last=i;
*start=i;
return;
}
p=*start;
old=NULL;
while(p)
{
if(strcmp(p->name,i->name)<0)
{
old=p;
p=p->next;
}
else
{
if(p->prior)
5
{
p->prior->next=i;
i->next=p;
i->prior=p->prior;
->prior=i; p
return;
}
i->next=p;
i->prior=NULL;
p->prior=i;
*start=i;
return;
}
}
old->next=i;
i->next=NULL;
i->prior=old;
*last=i;
}
2(3 通讯录节点的查询
a)需求分析
在用户输入查找条件时,用顺序法遍历链表。
b)概要设计
在实现中由search()来调用,由find()进行查找,用while循环来控制链
表中的从前到后的搜索。开始时find()设置节点的前导指针指向链表的开始,然
后按顺序一直到链表的结束。如果未找到,则返回NULL。
c)详细设计
void search(void)
{
char name[40];
struct address *info;
printf("Enter name to find:");
gets(name);
info=find(name);
if(!info)
printf("Not found\n");
else
display(info);
}
struct address *find(char *name)
{
struct address *info;
info=start;
6
while(info)
{
if(!strcmp(name,info->name))return info;
info=info->next;
}
printf("Name not found.\n");
return NULL;
}
2(4 通讯录节点的删除
a)需求分析
删除一个项目,并将前一个节点和后一个节点重新连接起来形成一个合法
的链表。
b)概要设计
如果要删除的节点没有后继节点,则将该节点的前导节点的后继指针置为
NULL并用free()函数释放被删除节点占用的内存。
如果要删除的节点没有前导节点,则将该节点的后继节点的前导指针置为
NULL,并用free()函数释放被删除节点占用的内存。
如果要删除的节点既有前导节点又有后继结点,则将该节点的前导节点的后
继指针指向该节点的后继节点,将该节点的后继节点的前导指针指向该节点的前
导节点。
c)详细设计
void mldelete(struct address **start,struct address **last) /*删除函数*/
{
struct address *info;
char s[80];
inputs("Enter name:",s,30);
info=find(s);
if(info)
{
if(*start==info)
{
*start=info->next;
if(*start)
(*start)->prior=NULL;
else *last=NULL;
}
else
{
info->prior->next=info->next;
if(info!=*last)
info->next->prior=info->prior;
else
*last=info->prior;
7
}
free(info);
}
}
2(5 通讯录的输出
a)需求分析
用顺序发遍历链表。
b)概要设计
从链表的头节点开始,俺顺序一直到链表的结束。由display()函数显示信息。
c)详细设计
void list(void)
{
struct address *info;
info=start;
while(info)
{
display(info);
info=info->next;
}
printf("\n\n");
}
void display(struct address *info)
{
printf("%s\n",info->name);
printf("%s\n",info->street);
printf("%s\n",info->city);
printf("%s\n",info->state);
printf("%s\n",info->zip);
printf("\n\n");
}
2(6 通讯录保存
a)需求分析
将用户输入或插入的项目保存到文件中。
b)概要设计
建立一个文件,属性设为可读写的,把链表写入文件,写入完毕,关闭文件。
c)详细设计
void save(void)
{
struct address *info;
FILE *fp;
fp=fopen("mlist","wb");
8
if(!fp)
{
printf("Cannot open file.\n");
exit(1);
}
printf("\nSaveing ……\n");
info=start;
while(info)
{
fwrite(info,sizeof(struct address),1,fp);
info=info->next;
}
printf("-ok!\n");
fclose(fp);/
}
2(7 通讯录载入
a)需求分析
将用户保存在文件中的信息载入
b)概要设计
读取保存信息的文件,把文件中的信息载入到程序中,以备用户查询。载入成功后,关闭文件。
c)详细设计
void load()
{
register int t, size;
struct address *info,*temp=0;
char *p;
FILE *fp;
if((fp=fopen("mlist","r"))==0)
{
printf("Cannot open file!\n");
exit(0);
}
printf("\n\nLoading...\n");
size=sizeof(struct address);
start=malloc(size);
if(!start)
{
printf("Out of memory!\n");
return;
}
info=start;
p=(char*)info;
while((*p++=getc(fp))!=EOF)
9
{
for(t=0;t
next=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");
}
2(8 调试分析
在调试过程中遇到了很多问题,但通过查资料,询问同学和老师,都得到了解决。
2.8.1程序展示
程序界面如图示:
程序主界面,供用户输入选择,进行相应的操作。
10
1(输入信息:
输入信息功能,当用户在主界面中选择1.时执行输入功能,程序依次提示用户输入 Name ,street,city,state, zip 信息,输入空姓名结束。
2(删除信息:
删除信息功能,当用户在主界面选择:2时,进入删除信息功能,程序提示用户输入姓名,然后进行删除操作。
11
3(显示信息:
显示信息功能,当用户在主界面选择3时,程序进入显示信息功能,把储存的信息显示在屏幕上共用户查看。
4(查找:
查找功能,当用户字啊主界面选择4时程序进入查找功能,程序提示用户输入姓名进行查找,如果找不到则显示无信息,如果找到则显示出来。
12
5(存盘:
存盘功能,当用户在主界面菜单中选择5时,进入存盘功能,程序会把信息保存在文件中。
6(装入:
载入功能,当用户在主界面菜单中选择6时,进入载入功能,程序把存储在文件中的信息载入到程序中,以备用户进行操作。
2.8.2 程序分析
这个程序总体上来说比较简单,其中的难点是dls_store()插入函数,在双向链表中,结点除含有数据域外,还有两个链域,一个存储直接后继结点地址,一般称之为右链域;一个存储直接前驱结点地址,一般称之为左链域。
对于双向循环链表,我们现在可以随意地在某已知结点p前或者p后插入一个新的结点。
假若s,p,q是连续三个结点的指针,若我们要在p前插入一个新结点r,则只需把s的右链域指针指向r,r的左链域指针指向s,r的右链域指针指向p,p的左链域指针指向r即可。
在p,q之间插入原理也一样。
13
还有就是文件的保存save()函数与载入load()函数,在开始写时,load
()函数总是出错误,一运行load()函数,Vasual C++6.0就会死掉。
第三章 课程设计总结
功能扩充:
(在此程序的基础上,可以加入记录和本人的关系,例如同学、朋友等,1
按此字段分类,进行分块查找。
2(加入首字母快速查找,即按下字母z键,则快速跳转显示首字母为z的
通讯录项目。
3. 加入界面更加友好的图形界面。
收获:
1( 在这次课程设计中,熟悉了数据结构的算法思想。加深了对非数值数据
的处理能力。
( 进一步加深了对双向链表(double linked list)的了解,巩固了数据结构2
课学到的知识。
3( 在编程的具体过程中,了解到了一些系统函数的工作原理。
第四章 源程序代码
#include
#include
#include
struct address{ /*定义结构*/
char name[30];
char street[100];
char city[30];
char state[30];
char zip[11];
struct address *next; /*后继指针*/
struct address *prior; /*前导指针*/
};
struct address *start; /*首结点*/
struct address *last; /*尾结点*/
struct address *find(char *); /*声明查找函数*/
void enter(); /*函数声明*/
void search();
void save();
14
void load();
void list();
void mldelete(struct address **,struct address **);
void dls_store(struct address *i,struct address **start,
struct address **last); void inputs(char *,char *,int); void display(struct address *); int menu_select(void);
int main(void)
{
start = last = NULL;
for(;;)
{
switch(menu_select())
{
case 1:enter();
continue;
case 2:mldelete(&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("…………^欢迎使用迷你通讯录系统^…………\n");
printf("*****************************************\n");
printf("************** 1.输入信息 ***************\n");
printf("************** 2.删除信息 ***************\n");
printf("************** 3.显示信息 ***************\n");
15
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("Enter name:",info->name,30);
if(!info->name[0])
break; /*如果输入姓名为空,结束循环*/
inputs("Enter street:",info->street,100);
inputs("Enter city:",info->city,30);
inputs("Enter state:",info->state,30);
inputs("Enter zip:",info->zip,11);
dls_store(info,&start,&last); /*调用结点插入函数*/
}
}
void inputs(char *prompt,char *s,int count) /*输入函数,有越界检测功能*/ {
char p[255];
16
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 dls_store( /*数据插入函数,也是本例的关键函数*/
struct address *i, /*接受传入的当前输入结点地址*/
struct address **start, /*接受传入的首结点地址*/
struct address **last /*接受传入的尾结点地址*/
)
{
struct address *old,*p; /*定义临时指针*/
if(*last==NULL) /*如果尾结点为空,意味着当前链表为空*/
{
i->next=NULL; /*当前结点的后驱赋空*/
i->prior=NULL; /*当前结点的前驱赋空*/
*last=i; /*尾结点定义为当前结点*/
*start=i; /*首结点定义为当前结点*/
return; /*返回调用函数*/
}
/*如果链表不为空*/
p=*start; /*p取入口地址(也就是首结点地址)*/
old=NULL; /*old赋空*/
while(p)
{ /*如果p不为空时,执行特循环体,查找比当前结点应该插入的位置*/
if(strcmp(p->name,i->name)<0) /*如果当前结点的name域比p(首结点)大时(实现以name域升序排序)*/
{
old=p; /*old暂存p地址*/
p=p->next; /*p取下一结点*/
}
else /*如果当前输入数据中的name域比p小时,把数据插入结点p之前*/
{
17
if(p->prior) /*如果p的前驱不为空时*/
{
p->prior->next=i; /*令p的前驱的next域指向当前结点*/
i->next=p; /*令当前结点的后继指向p*/
i->prior=p->prior; /*令当前结点的前驱指向p的前驱*/
p->prior=i; /*令p的前驱为当前结点*/
return; /*插入完成,返回调用函数*/
}
i->next=p; /*如果p的前驱为空时,把当前结点作为首结点,并令当前结点的后驱为p*/
i->prior=NULL; /*定义当前结点的前驱为空*/
p->prior=i; /*p的前驱为当前结点*/
*start=i; /*首结点(入口)为当前结点*/
return; /*插入完成,返回调用函数*/
}
} /*循环体结束*/
old->next=i; /*如果在整个链表都找不到name域比当前数据的name域大的结点,
*把当前数据放在作为尾结点放在最后*/
i->next=NULL; /*令链表尾结点后驱批向当前结点,当前结点的后驱为空*/
i->prior=old; /*令当前结点的前驱为之前的最后结点*/
*last=i; /*尾结点取i地址*/
}
void mldelete(struct address **start,struct address **last) /*删除函数*/ {
struct address *info;
char s[80];
inputs("Enter name:",s,30); /*输入欲删除结点的name域内容*/
info=find(s); /*查找该内容*/
if(info) /*如果找到*/
{
printf("Deleting......\n");
if(*start==info) /*如果该结点为首结点,把该结点的下驱作为新的首结点(入口)*/
{
*start=info->next;
if(*start)
(*start)->prior=NULL; /*如果新入口不为空,把入口的前驱置空*/
else *last=NULL; /*如果新入口为空,把尾结点置空,链表为空*/
18
}
else /*如果欲删除的结点不是首结点*/
{
info->prior->next=info->next; /*令该结点的前驱的next指针指向该结点的后驱,
*又令该结点的后驱的prior指点指向该结点的前驱*/
if(info!=*last) /*如果该结点是尾结点,则令该结点的前驱为尾结点*/
info->next->prior=info->prior;
else
*last=info->prior;
}
free(info); /*释放该结点所占用的内存*/
printf("-Ok,deleted successfully!\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("Name not found.\n");
return NULL;
}
/*输出整个链表*/
void list(void)
{
struct address *info;
info=start;
if(info==NULL)
printf("NO information!");
while(info)
{
display(info);
info=info->next;
}
printf("\n\n");
}
19
void display(struct address *info) /*输出传入结点函数*/ {
printf("%s\n",info->name);
printf("%s\n",info->street);
printf("%s\n",info->city);
printf("%s\n",info->state);
printf("%s\n",info->zip);
printf("\n\n");
}
void search(void) /*查找函数*/ {
char name[40];
struct address *info;
printf("Enter name to find:"); /*输入欲查找的姓名*/
gets(name);
info=find(name);
if(!info)
printf("Not found\n"); /*如果没找到,显示Not found*/
else
display(info); /*如果找到,显示该结点资料*/ }
void save(void) /*保存函数*/ {
struct address *info;
FILE *fp;
fp=fopen("mlist","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);/*链表全部写入文件后,关闭文件*/
20
}
void load() /*调用预存文件函数*/ {
register int t, size;
struct address *info,*temp=0;
char *p;
FILE *fp; /*打开文件*/
if((fp=fopen("mlist","r"))==NULL)
{
printf("Cannot open file!\n");
exit(0);
}
printf("\n\nLoading...\n"); /*调用文件*/
size=sizeof(struct address); /*为结点分配内存*/
start=malloc(size);
if(!start) /*如果读取失败,返回*/
{
printf("Out of memory!\n");
exit(0);
}
info=start;
p=(char*)info;
while((*p++=getc(fp))!=EOF)
{
for(t=0;tnext=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");
}
21