通讯录管理系统-数据结构课程设计.doc

数据结构课程设计论文

题目： 1.通讯录管理系统**
7 .建立二叉树，层序、先序遍历
14. 拓扑排序
姓名： 李东东

学号： 201110510212

班级： 11 计科（2）班

指导教师： 李娟 徐星

2013年 6 月 24日

1

1. 通讯录管理系统
开发目的
数据结构旨在使读者学会分析研究数据对象的特性，学会数据的组织方法，以便选择合适的数据逻辑结构和存储结构，以及相应的运算，把现实世界中的问题转化为计算机内部的表示和处理。
设计目的
进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法；掌握软件设计的基本内容和设计方法，并培养规范化软件设计的能力；将理论知识和实际结合起来，锻炼分析解决实际问题的能力。
设计要求
实现通讯录的建立和输出、通讯者的插入、删除和查询等几种操作功能。
用单链表作存储结构；用菜单作为应用程序的主要界面，主界面的主控菜单如下：
通讯录链表
************************************
1. 通讯录链表的建立
2. 通讯录结点的插入
3. 通讯录结点的查询
4. 通讯录结点的删除
5. 通讯录链表的输出
0. 退出通讯录管理系统
************************************
请选择菜单号<0~5>：
*：使用数字0~5来选择菜单项，其他输入无效，并给出错误提示。
设计功能
程序运行后的功能有：
（1）菜单选择界面
（2）建立通讯录记录
（3）插入联系人记录
（4）查找联系人记录（名称和编号查询）
（6）删除联系人记录
（7）输出所有联系人记录
（8）退出程序
算法设计
系统流程图如图所示：

主函数设计
由于主函数设计的是菜单选择项，所以在程序未退出的的情况下要实现循环运行，并且要考虑到未建立通讯录链表的情况下其他功能无法实现的情况。故在实现循环运行的功能时定义一个变量j=1，在选择退出后再将j赋值为0，要考虑判定是否建表的情况定义了一个全局变量flag1=0，建链表后flag1赋值为1。
为了达到选择各功能,采用switch判定选择项并跳转入相应功能函数。
判定是否建表语句:
if(flag1!=1)
{printf("请先建立表!");
getchar();
system("cls");}

3

1
6

功能程序设计
为了达到程序各项功能的实现，以及满足菜单选择项的功能，对每个功能的实现分别用了不同函数，并且有用到函数的嵌套以减少代码的重复。
建立通讯链表设计

要建立链表，首先要生成结点，因此，尾插法建立链表算法描述如下：
（1）使链表的头尾指针head、rear指向新生成的头结点（也就是尾结点）；
（2）置结束标志为0（假）；
（3）while(结束标志不为真)
｛
P指向新生成的结点；
读入一个通讯者数据至新结点的数据域；
将新结点链到尾结点之后；
主函数设计

主函数设计

主函数设计
实现循环运行的功能时定义一个变量j=1，在选择退出后再将j赋值为0，要考虑判定是否建表的情况定义了一个全局变量flag1=0，建链表后flag1赋值为1。
为了达到选择各功能,采用switch判定选择项并跳转入相应功能函数。
判定是否建表语句:
if(flag1!=1)
{printf("请先建立表!");
getchar();
system("cls");}

4

建立通讯链表设计
要建立链表，首先要生成结点，因此，尾插法建立链表算法描述如下：
（1）使链表的头尾指针head、rear指向新生成的头结点（也就是尾结点）；
（2）置结束标志为0（假）；
（3）while(结束标志不为真)
｛
P指向新生成的结点；
读入一个通讯者数据至新结点的数据域；
将新结点链到尾结点之后；
使尾指针指向新结点；
提示是否继续建表，读入一个结束的标志；
｝
（4）尾结点的指针域置空置NULL。
具体算法实现如下：
/*******尾插法建立带头结点的通讯录链表算法*******/
LinkList CreateList(void)
{
LinkList head=(ListNode *)malloc(sizeof(ListNode)); /*申请头结点*/
ListNode *p,*rear;
char flag='y'; //int flag=0; /*结束标志置0*/
rear=head; /*尾指针初始指向头结点*/
while (flag=='y')
{

1
6
p=(ListNode *)malloc(sizeof(ListNode)); /*申新结点*/
printf("编号(4) 姓名(8) 性别 电话(11) 地址(31)\n");
printf("-----------------------------------------------\n");
printf("\n添加的编号:\n");
scanf("%s",p->data.num);
printf("\n添加的姓名:\n");
scanf("%s",p->data.name);
printf("\n性别:\n");
scanf("%s",p->data.sex);
printf("\n电话:\n");
scanf("%s",p->data.phone);
printf("\n地址:\n");
scanf("%s",p->data.addr);
rear->next=p; /*新结点连接到尾结点之后*/
rear=p; /*尾指针指向新结点*/
printf("继续建表?(y/n):");
scanf("%s",&flag);
}
rear->next=NULL; /*终端结点指针置空*/
return head; /*返回链表头指针*/
}
通讯者结点信息的插入
链表结点的插入，要求将一个通讯者记录的数据结点按其编号的次序插入有序通讯表相应位置，以保持通讯录的有序性。插入的基本思想是：使用两个指针变量p1和p2分别指向当前访问过的结点和下一个结点，循环顺序查找链表。寻找插入结点的位置，其中p1指向待插入位置的前一个结点。具体实现算法如下：
（1）用p1指向原链表头结点，p2指向链表的第一个结点；
（2）while(p2!=NULL && strcmp(p2->data.num,p->data.num)<0)
{
p1=p2; /*p1指向刚访问过的结点*/
p2=p2->next; /*p2指向下一个结点*/
}
(3)插入新结点。具体算法如下：
/*********在通讯录链表head中插入结点************/

5
5
void InsertNode(LinkList head,ListNode *p)
{
ListNode *p1,*p2;
p1=head;
p2=p1->next;
while(p2!=NULL && strcmp(p2->data.num,p->data.num)<0)
{
p1=p2; /*p1指向刚访问过的结点*/
p2=p2->next; /*p2指向表的下一个结点*/
}
p1->next=p; /*插入p所指向的结点*/
p->next=p2; /*连接表中剩余的结点*/
}
通讯者结点信息的查找
通讯录结点查找的基本思想是：首先输入要查找的通讯者编号或姓名，从表头顺序访问表中结点。如果查找成功，则返回一个指向查找道德通讯者信息；若查找失败，则返回一个空的指针NULL。具体实现如下：
/**********有序通讯录链表的查找 ****************/
ListNode *ListFind(LinkList head)
{
ListNode *p;
char num[5];
char name[9];
char pp;
printf("==================\n");
printf(" a. 按编号查询 \n");
printf(" b. 按姓名查询 \n");
printf("==================\n");
printf(" 请 选 择： ");
p=head->next;
scanf("%s",&pp);
if (pp=='a'||pp=='A')
{
printf("请输入要查找者的编号：");

6
6
scanf("%s",num);
while (p&&strcmp(p->data.num,num)!=0) p=p->next;
if ((p==NULL)) p=NULL; /*没有查到要查找的通讯信息*/
}
else
if (pp=='b'||pp=='B')
{
printf(" 请输入要查找者的姓名：");
scanf("%s",name);
while(p&&strcmp(p->data.name,name)!=0) p=p->next;
}
return p;
}
通讯者结点信息的删除
通讯录结点的删除，先调用查找函数，查询到要删除的结点，删除即可。其实现算法如下：

/********通讯录链表上的结点删除*****************/
void DelNode(LinkList head)
{
char cho;
ListNode *p,*q;
p=ListFind(head); /*调用查找函数*/
if (p==NULL)
{
printf("没有查到要删除的通讯者!\n");
return;
}
else if(p!=NULL)
{
printf("真的要删除该结点吗？（y/n）");
scanf("%s",&cho);
if (cho=='y'||cho=='Y')
{

7
7
q=head;
while ((q!=NULL)&&(q->next!=p)) q=q->next;
q->next=p->next; /*删除结点*/
free(p); /*释放被删结点空间*/
printf("删除成功！\n");
}
}
}
通讯者结点信息的输出
通讯录链表的输出只要讲表头指针赋给一个指针变量p，然后用p向后扫描，直到表尾，p为空为止。因此，其输出链表的算法实现如下：
/********通讯录链表的输出函数 **********/
void PrintList(LinkList head)
{
ListNode *p;
p=head->next;
printf("编号 姓 名 性别 联系电话 地址 \n");
printf("------------------------------------------\n");
while (p!=NULL)
{
printf("%s,%s,%s,%s,%s\n",p->data.num,p->data.name,p->data.sex,p->data.phone,p->data.addr);
printf("----------------------------------------------\n");
p=p->next; /*后移一个结点*/
}
}

程序源代码
#include<stdio.h>
#include "string.h"
#include "stdlib.h"
int flag1=0;
typedef struct { /*通讯录结点类型*/
char num[5]; /*编号*/
char name[9]; /*姓名*/
char sex[3]; /*性别*/
char phone[13]; /*电话*/
char addr[31]; /*地址*/
} DataType;
typedef struct node { /*结点类型定义*/
DataType data; /*结点数据域*/
struct node *next; /*结点指针域*/
} ListNode;
typedef ListNode *LinkList;
LinkList head;
ListNode *p;

LinkList CreateList(void);
void InsertNode(LinkList head,ListNode *p);
ListNode *ListFind(LinkList head);
void DelNode(LinkList head);
void PrintList(LinkList head);

/*******尾插法建立带头结点的通讯录链表算法*******/
LinkList CreateList(void)
{
LinkList head=(ListNode *)malloc(sizeof(ListNode)); /*申请头结点*/
ListNode *p,*rear;
char flag='y'; //int flag=0; /*结束标志置0*/
rear=head; /*尾指针初始指向头结点*/
while (flag=='y')
{
p=(ListNode *)malloc(sizeof(ListNode)); /*申新结点*/
printf("编号 姓名 性别 电话 地址 \n");
printf("-----------------------------------------------\n");
printf("\n添加的编号:\n");
scanf("%s",p->data.num);
printf("\n添加的姓名:\n");
scanf("%s",p->data.name);
printf("\n性别:\n");
scanf("%s",p->data.sex);
printf("\n电话:\n");
scanf("%s",p->data.phone);
printf("\n地址:\n");
scanf("%s",p->data.addr);
rear->next=p; /*新结点连接到尾结点之后*/
rear=p; /*尾指针指向新结点*/
printf("继续建表?(y/n):");
scanf("%s",&flag);
}
rear->next=NULL; /*终端结点指针置空*/
return head; /*返回链表头指针*/
}

/*********在通讯录链表head中插入结点************/
void InsertNode(LinkList head,ListNode *p)
{
ListNode *p1,*p2;
p1=head;
p2=p1->next;
while(p2!=NULL && strcmp(p2->data.num,p->data.num)<0)
{
p1=p2; /*p1指向刚访问过的结点*/
p2=p2->next; /*p2指向表的下一个结点*/
}
p1->next=p; /*插入p所指向的结点*/
p->next=p2; /*连接表中剩余的结点*/
}

/**********有序通讯录链表的查找 ****************/
ListNode *ListFind(LinkList head)
{
ListNode *p;
char num[5];
char name[9];
char pp;
printf("==================\n");
printf(" a. 按编号查询 \n");
printf(" b. 按姓名查询 \n");
printf("==================\n");
printf(" 请 选 择： ");
p=head->next;
scanf("%s",&pp);
if (pp=='a'||pp=='A')
{
printf("请输入要查找者的编号：");
scanf("%s",num);
while (p&&strcmp(p->data.num,num)!=0) p=p->next;
if ((p==NULL)) p=NULL; /*没有查到要查找的通讯信息*/
}
else
if (pp=='b'||pp=='B')
{
printf(" 请输入要查找者的姓名：");
scanf("%s",name);
while(p&&strcmp(p->data.name,name)!=0) p=p->next;
}
return p;
}

/********通讯录链表上的结点删除*****************/
void DelNode(LinkList head)
{
char cho;
ListNode *p,*q;
p=ListFind(head); /*调用查找函数*/
if (p==NULL)
{
printf("没有查到要删除的通讯者!\n");
return;
}
else if(p!=NULL)
{
printf("真的要删除该结点吗？（y/n）");
scanf("%s",&cho);
if (cho=='y'||cho=='Y')
{
q=head;
while ((q!=NULL)&&(q->next!=p)) q=q->next;
q->next=p->next; /*删除结点*/
free(p); /*释放被删结点空间*/
printf("删除成功！\n");
}
}
}

/********通讯录链表的输出函数 **********/
void PrintList(LinkList head)
{
ListNode *p;
p=head->next;
printf("编号 姓 名 性别 联系电话 地址 \n");
printf("----------------------------------------------------\n");
while (p!=NULL)
{
printf("%s,%s,%s,%s,%s\n",p->data.num,p->data.name,p->data.sex,p->data.phone,p->data.addr);
printf("----------------------------------------------------\n");
p=p->next; /*后移一个结点*/
}
}

void main()
{
int choice,j=1;
while(j)
{
printf("\n\n\n\n\n");
printf("\t\t\t\t通 信 录 链 表 \n");
printf("\n\t\t\t******************************");
printf("\n\t\t\t* 1．通讯录链表的建立 *");
printf("\n\t\t\t* 2．通讯者结点的插入 *");
printf("\n\t\t\t* 3．通讯者结点的查询 *");
printf("\n\t\t\t* 4．通讯者结点的删除 *");
printf("\n\t\t\t* 5．通讯录链表的输出 *");
printf("\n\t\t\t* 0．退出通讯录管理系统 *");
printf("\n\t\t\t******************************");
printf("\n\t\t\t请选择菜单号(0--5):");
scanf("%d",&choice);
getchar();
switch(choice)
{
case 1:
{
printf("**********************************\n");
printf("* 通 讯 录 链 表 的 建 立 *\n");
printf("**********************************\n");
head=CreateList( );
flag1=1;
system("cls");
break;
}
case 2:
{
if(flag1!=1)
{printf("请先建立表!");
getchar();
system("cls");}
else {
printf("**********************************\n");
printf("* 通 讯 者 信 息 的 添 加 *\n");
printf("**********************************\n");
printf("编号 姓名 性别 电话 地址 \n");
printf("************************************* \n");
p=(ListNode *)malloc(sizeof(ListNode)); /*申请新结点*/
printf("\n添加的编号:\n");
scanf("%s",p->data.num);
printf("\n添加的姓名:\n");
scanf("%s",p->data.name);
printf("\n性别:\n");
scanf("%s",p->data.sex);
printf("\n电话:\n");
scanf("%s",p->data.phone);
printf("\n地址:\n");
scanf("%s",p->data.addr);
InsertNode(head,p);
system("cls");}
break;
}
case 3:
{
if(flag1!=1)
{
printf("请先建立表!");
getchar();
system("cls");
}
else
{
printf("***********************************\n");
printf("* 通 讯 录 信 息 的 查 询 *\n");
printf("***********************************\n");
p=ListFind(head);
if (p!=NULL)
{
printf("编号 姓 名 性别 联系电话 地址 \n");
printf("--------------------------------------------------\n");
printf("%s,%s,%s,%s,%s\n",p->data.num,p->data.name,p->data.sex,p->data.phone,p->data.addr);
printf("---------------------------------------------------\n");
}
else printf("没有查到要查询的通讯者！\n");
}
break;
}
case 4:
{
if(flag1!=1) {
printf("请先建立表!");
getchar();
system("cls");
}
else
{
printf("***********************************\n");
printf("* 通 讯 录 信 息 的 删 除 *\n");
printf("***********************************\n");
DelNode(head); /*删除结点*/
}
break;
}
case 5:
{
if(flag1!=1)
{
printf("请先建立表!");
getchar();
system("cls");
}
else
{
printf("************************************\n");
printf("* 通 讯 录 链 表 的 输 出 *\n");
printf("************************************\n");
PrintList(head);
}
break;
}
case 0:
printf("是否退出（y/n）?");
choice=getchar();
if(choice=='y'||choice=='Y')
{
j=0;
system("cls");
printf("\n\n\n\n\t\t\t========谢谢使用！=========");
printf("\n按任意键退出...");
getchar();
}

break;
default:
printf("\t\t\n 输入有错，请重新输入!\n");
printf("\n按任意键继续...");
getchar();
system("cls");
break;
}
}
}

程序调试
可执行文件的生成
（1）打开VC++6.0，编译连接程序是否有错：

15

Ⅰ

连接生成可执行exe文件，成功

程序的运行过程
双击“通讯录管理系统.exe”
（1）出现菜单界面

1
28

（2） 输入菜单项选择外的编号“6”：

（3） 未输入选项“1”的情况下还未建立通讯录链表，如果直接输入其他除退出外的可选选项此时会提示用户

16
（4） 选择1建立通讯录链表，并录入相关信息，如图所示。

录入完信息后，会提示是否继续，如果不在继续则输入“n”程序会返回主菜单界面，如果继续则输入“y”程序会继续执行建表。

（5）在建好表的基础上，选择选项2，则可根据提示录入相关信息，如图所示。

17

（6）在建表的基础上，选择3，进行通讯者信息查询出现提示“按编号查找”和“按姓名查找”，用户根据需求进行选择操作，如图所示。

（7）在建表的基础上，选择4，进行通讯者结点的删除，会首先提示安何种方式进行删除。选择并录入正确的信息后会提示用户确认删除。

18

（7）在建表的基础上，选择5，进行所有通讯者的信息输出，如图所示。

（8）进入主菜单选择0，程序提示用户是否退出程序，如图所示。

设计总结
课程设计心得
课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对实际工作能力的具体训练和考察过程.通过这次实训，增加了我学习软件技术的兴趣，基本理解和掌握课堂上所学各种基本抽
19
象数据类型的逻辑结构、存储结构和操作实现算法，以及它们在程序中的使用方法，在不清楚如何下手时，从网上搜索资料进行参考，获益匪浅。

2. 建立二叉树，层序、先序遍历
设计目标
二叉树是一个重要的数据类型，通过建立一个链式存储结构，能够实现前序遍历，中序遍历，后序遍历。以及能够从输入的数据中得知二叉树的叶子节点的个数，二叉树的深度。
二叉树遍历实现流程图

3设计实现

主函数设计
void main ()

20
{
BTNode * b,*p;
CreateBTNode (b,"a(b(d,e),c(f,g)) ");
printf("(1)输出二叉树:");DispBTNode (b);printf("\n");
printf("(2)层次遍历序列：");TravLevel(b);printf("\n");
printf("(3)先序遍历序列：");PreOrder(b);printf("\n");}
用递归算法的先序遍历函数
void PreOrder(BTNode *b)
{
if(b!=NULL)
{
printf ("%c",b->data);
PreOrder(b->lchild);
PreOrder(b->rchild);
}
4源代码
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
ElemType data;
struct node *lchild;
struct node *rchild;
}BTNode;
void CreateBTNode(BTNode *&b,char *str)//创建二叉树
{
BTNode *St[MaxSize],*p=NULL;
int top=-1,k,j=0;
char ch;
b=NULL;
ch=str[j];
while (ch!='\0')
{
switch (ch)
{
case'(':top++;St[top]=p;k=1;break;
case')':top--;break;

21
case',':k=2;break;
default:p=(BTNode *)malloc(sizeof(BTNode));
p->data=ch;
p->lchild=p->rchild=NULL;
if(b==NULL)
b=p;
else
{
switch(k)
{
case 1:St[top]->lchild=p;break;
case 2:St[top]->rchild=p;break;
}
}
}
j++;
ch=str[j];
}
}
void DispBTNode(BTNode *b)//括号表示法输出二叉树
{
if (b!=NULL)
{
printf ("%C",b->data);
if(b->lchild!=NULL||b->rchild!=NULL)
{
printf("(");
DispBTNode(b->lchild);
if(b->rchild!=NULL)printf(",");
DispBTNode(b->rchild);
printf(")");
}
}
}
void TravLevel(BTNode *b)//层次遍历
{
BTNode *Qu[MaxSize];
int front,rear;
front=rear=0;
if(b!=NULL)
printf("%c"