数据结构优秀课程设计有向图拓扑排序算法的实现.docx

数据结构课程设计
设计说明书

有向图拓扑排序算法实现

学生姓名
樊佳佳
学号

班级
网络工程1301
成绩

指导老师
申静

数学和计算机科学学院
1月4日
课程设计任务书
—第一学期
课程设计名称：
数据结构课程设计
课程设计题目：
图拓扑排序算法实现
完 成 期 限：
自 12月20日至 1 月 3 日共 2 周
设计内容：
1、设计任务
（1）给出一个有向无环图，遍历全部节点；（2）能够实现对全部顶点拓扑；(3)界面友好，可操作性强。
2、需求分析
对系统功效及性能要求进行分析，写出需求规格说明书（可行性分析汇报、系统分层DFD图）。
3、软件设计
软件设计分两个阶段进行：总体设计和具体设计；
总体设计：确定系统总体设计方案，完成系统模块结构图及模块功效说明；
具体设计：对模块内部过程及数据结构进行设计，和进行数据库设计、用户界面设计等编写出该项目标具体设计汇报；
4、具体编码
编写程序，要求给出具体注释，包含：模块名、模块功效、中间过程功效、 变量说明等。同时编写用户使用手册、程序模块说明等文档；
5、软件测试
全部测试过程要求采取综合测试策略：先作静态分析，再作动态测试。应事先制订测试计划，并要求保留全部测试用例，完成测试汇报。
指导老师：申静 教研室责任人：申静
课程设计评阅
评语：

指导老师署名：
年 月 日

摘 要
设计了一个对有向图进行拓扑排序算法，该算法首先用邻接表结构有向图存放结构，然后对此有向图进行拓扑排序，输出拓扑排序结果。用VC++作为软件开发环境，以邻接表作为图存放结构，将图中全部顶点排成一个线性序列，输出拓扑排序结果。拓扑排序常见来确定一个依靠关系集中，事物发生次序。拓扑排序是对有向无环图顶点一个排序，它使得假如存在一条从顶点A到顶点B路径，那么在排序中B出现在A后面。

关键词：邻接表；有向无环图；拓扑排序
目 录
1 课题描述 1
2 问题分析和任务定义 2
3 逻辑设计 3
3.1程序模块功效图 3
3.2 抽象数据类型 3
4 具体设计 4
4.1 C语言定义相关数据类型 4
4.2 关键模块伪码算法 4
4.2.1主函数伪码算法 4
4.2.2邻接表伪码算法 4
4.2.3拓扑排序伪码算法： 5
4.3 主函数步骤图 6
5 程序编码 7
6 程序调试和测试 13
7 结果分析 16
8 总结 17
参考文件 18

1 课题描述
根依据设计要求利用C语言程序设计了一个对有向图进行拓扑排序算法，该算法首先用邻接表结构有向图存放结构，然后对此有向图进行拓扑排序，输出拓扑排序结果。
如给定一个有向无环图图1.1所表示。在此图中，从入度为0顶点出发，删除此顶点和全部以它为尾弧；反复直至全部顶点均已输出；或当图中不存在无前驱顶点为止。
2

3

1

4

5

图1.1 有向无环图

开发工具：Visual C++ 6.0
2 问题分析和任务定义
对一个有向无环图G进行拓扑排序，是将G中全部顶点排成一个线性序列，使得图中任意一对由某个集合上一个偏序得到该集合上一个全序，这个操作就称之为拓扑排序。偏序集合中仅有部分组员之间颗比较，而全序指集合中全体组员之间均可比较，而由偏序定义得到拓扑有序操作便是拓扑排序。
一个表示偏序有向图可用来表示一个步骤图，经过抽象出来就是AOV-网，若从顶点i到顶点j有一条有向路径，则i是j前驱，j是i后继。若（i，j）是一条弧，则i是j直接前驱；j是i直接后继。
在AOV-网中，不应该出现有向环，用拓扑排序就能够判定网中是否有环，若网中全部顶点全部在它拓扑有序序列中，则该AOV-网肯定不存在环。

3 逻辑设计
主函数
3.1程序模块功效图

拓扑排序
节点入度
栈初始化
创建邻接表
有向图初始化

图3.1程序模块功效图
3.2 抽象数据类型
ADT ALGraph
｛
数据对象：D={V|V是含有相同特征数据元素集合，即顶点集}
数据关系：R={<v,w>|v,w∈V,<v,w>表示顶点v到顶点w弧}
基础操作P:
CreatGraphlist(ALGraph *G)
初始条件：成对输入顶点集V中点。
操作结果：结构图G邻接表。
FindInDegree(ALGraph G, int indegree[])
初始条件：图G邻接表中存在结点V。
操作结果：找到图中入度为0结点。
Initgraph()
操作结果：完成图形初始化。
TopologicalSort(ALGraph G)
初始条件：结构有向图G已初始化。
操作结果：对于有向图G依据邻接存放表进行拓扑排序。
}

4 具体设计
4.1 C语言定义相关数据类型
#define max_vextex_num 20 /*宏定义最大顶点个数*/
#define stack_init_size 100 /*宏定义栈存放空间大小*/
typedef int ElemType;
typedef struct VNode /*邻接表头结点类型*/
{
int data; /*顶点信息,数据域*/
}VNode, AdjList[MAX_VEXTEX_NUM]; /*AdjList是邻接表类型*/

typedef struct
{
AdjList vertices; /*邻接表*/
int vexnum, arcnum; /*图中顶点数vexn和边数arcn*/
}ALGraph; /*图类型*/

typedef struct //构建栈
{
ElemType *base; /*数据域*/
ElemType *top; /*栈指针域*/
int stacksize;
}SqStack;
4.2 关键模块伪码算法
4.2.1主函数伪码算法：
开始
{
创建及输出邻接表CreatGraphlist(&G);
输出排序后输出序列TopologicalSort(G);
}
结束
4.2.2邻接表伪码算法：
#define MAX_VEXTEX_NUM 20
typedef struct VNode /*邻接表头结点类型*/
{
int data; /*顶点信息,数据域*/
ArcNode *firstarc; /*指向第一条弧*/
}VNode, AdjList[MAX_VEXTEX_NUM]; /*AdjList是邻接表类型*/
typedef struct
{
AdjList vertices; /*邻接表*/
int vexnum, arcnum; /*图中顶点数vexn和边数arcn*/
}ALGraph; /*图类型*/
开始
{
定义一个指针P
置i初值为1
邻接表中全部头结点指针置初值
当i<=G-vexnum时自加，实施下面操作：
输出数据域里顶点信息
使指针p指向顶点i第一条弧头结点
输出访问顶点
使指针p指向顶点i下一条弧头结点
类此循环到输出最终一个顶点
}
结束
4.2.3拓扑排序伪码算法
开始
{
引入栈操作函数和入度操作函数
访问邻接存放表中顶点n
If该顶点入度为0
顶点进栈
循环操作到全部顶点入栈
当栈不为空
顶点出栈
}
结束

4.3 主函数步骤图
主函数步骤图图4.3所表示

开始

输入顶点数和弧数

N
输入

判定是否满足条件

Y
依据输入信息建立邻接表

建栈

在邻接表中寻求入度为零顶点，使其入栈

N

输出栈顶元素，打印，将和栈顶元素邻接顶点入度减1

判定是否空栈

Y
结束

图4.3 主函数程序步骤图
5 程序编码
#include<stdio.h>
#include<stdlib.h>
#define true 1
#define false 0
#define MAX_VEXTEX_NUM 20
#define M 20
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

/*-----------------------图邻接表存放结构------------------------*/

typedef struct ArcNode /*弧结点结构类型*/
{
int adjvex; /*该弧指向顶点位置*/
struct ArcNode *nextarc; /*指向下一条弧指针*/
}ArcNode;

typedef struct VNode /*邻接表头结点类型*/
{
int data; /*顶点信息*/
ArcNode *firstarc; /*指向第一条依附于该点弧指针*/
}VNode,AdjList[MAX_VEXTEX_NUM]; /*AdjList为邻接表类型*/

typedef struct
{
AdjList vertices;
int vexnum, arcnum;
}ALGraph;
/*----------------------------------------------------------------*/
void CreatGraph(ALGraph *G) /*经过用户交互产生一个图邻接表*/
{
int m, n, i;
ArcNode *p;
printf("=======================================================");
printf("\n输入顶点数:");
scanf("%d",&G->vexnum);
printf("\n输入边数:");
scanf("%d",&G->arcnum);
printf("=======================================================");
for (i=1; i<=G->vexnum;i++) /*初始化各顶点*/
{
G->vertices[i].data=i; /*编写顶点位置序号*/
G->vertices[i].firstarc=NULL;
}
for (i=1;i<=G->arcnum;i++) /*统计图中由两点确定弧*/
{
printf("\n输入确定弧两个顶点u，v:");
scanf("%d %d",&n,&m);
while (n<0||n>G->vexnum||m<0||m>G->vexnum)
{
printf("输入顶点序号不正确 请重新输入:");
scanf("%d%d",&n,&m);
}

p=(ArcNode*)malloc(sizeof(ArcNode)); /*开辟新弧结点来存放用户输入弧信息*/
if(p==NULL)
{
printf("ERROR!");
exit(1);
}
p->adjvex=m; /*该弧指向位置编号为m结点*/
p->nextarc=G->vertices[n].firstarc;
/*下一条弧指向是依附于n第一条弧*/
G->vertices[n].firstarc=p;
}
printf("=======================================================");

printf("\n建立邻接表为:\n");
/*打印生成邻接表（以一定格式）*/
for(i=1;i<=G->vexnum;i++)
{
printf("%d",G->vertices[i].data);
for(p=G->vertices[i].firstarc;p;p=p->nextarc)
printf("-->%d",p->adjvex);
printf("\n");

}
printf("=======================================================");
}
/*----------------------------------------------------------------*/
typedef struct /*栈存放结构*/
{
int *base; /*栈底指针*/
int *top; /*栈顶指针*/
int stacksize;
}SqStack;
/*----------------------------------------------------------------*/
void InitStack(SqStack *S) /*初始化栈*/
{
S->base=(int *)malloc(STACK_INIT_SIZE*sizeof(int));
if(!S->base) /*存放分配失败*/
{
printf("ERROR!");
exit(1);
}
S->top=S->base;
S->stacksize=STACK_INIT_SIZE;
}

/*----------------------------------------------------------------*/

void Push(SqStack *S,int e) /*压入新元素为栈顶*/
{
if(S->top-S->base>=S->stacksize)
{
S->base=(int *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(int)); /*追加新空间*/
if(!S->base) /*存放分配失败*/
{
printf("ERROR!");
exit(1);
}
S->top=S->base+S->stacksize;
S->stacksize+=STACKINCREMENT;
}
*S->top++=e; /*e作为新栈顶元素*/
}

/*----------------------------------------------------------------*/

int Pop(SqStack *S,int *e) /*弹出栈顶，用e返回*/
{
if(S->top==S->base) /*栈为空*/
{
return false;
}
*e=*--S->top;
return 0;
}

/*----------------------------------------------------------------*/

int StackEmpty(SqStack *S) /*判定栈是否为空，为空返回1，不为空返回0*/
{
if(S->top==S->base)
return true;
else
return false;
}

/*----------------------------------------------------------------*/
void FindInDegree(ALGraph G, int indegree[]) /*对各顶点求入度*/
{
int i;
for(i=1; i<=G.vexnum;i++) /*入度赋初值0*/
{
indegree[i]=0;
}

for(i=1;i<=G.vexnum;i++)
{
while(G.vertices[i].firstarc)
{
indegree[G.vertices[i].firstarc->adjvex]++;

/*出度不为零，则该顶点firstarc域指向弧指向顶点入度加一*/

G.vertices[i].firstarc = G.vertices[i].firstarc->nextarc;
}
}
}

/*----------------------------------------------------------------*/

void TopoSort(ALGraph G)
{
int indegree[M];
int i, k, n;
int count=0; /*初始化输出计数器*/
ArcNode *p;
SqStack S;
FindInDegree(G,indegree);
InitStack(&S);
for(i=1;i<=G.vexnum;i++)
{
printf("\n");
printf("indegree[%d] = %d \n",i,indegree[i]); /*输出入度*/
}
printf("\n");
for(i=1;i<=G.vexnum;i++) /*入度为0入栈*/
{
if(!indegree[i])
Push(&S,i);
}
printf("=======================================================");
printf("\n\n拓扑排序序列为:");
while(!StackEmpty(&S)) /*栈不为空*/
{
Pop(&S,&n); /*弹出栈顶*/
printf("%4d",G.vertices[n].data); /*输出栈顶并计数*/
count++;
for(p=G.vertices[n].firstarc; p!=NULL;p=p->nextarc)
/*n号顶点每个邻接点入度减一*/
{
k=p->adjvex;
if(!(--indegree[k])) /*若入度减为零，则再入栈*/
{
Push(&S,k);
}
}

}
if(count<G.vexnum)/*输出顶点数小于原始图顶点数，有向图中有回路*/
{
printf("ERROR 出现错误!");
}
else
{
printf(" 排序成功!");
}
}
/*----------------------------------------------------------------*/
main(void) /*编写主调函数以调用上述被调函数*/
{
ALGraph G;
CreatGraph(&G); /*建立邻接表*/
TopoSort(G); /*对图G进行拓扑排序*/
printf("\n\n");
system("pause");
/*调用系统dos命令：pause;显示:"按任意键继续..."*/
return 0;
}
6 程序调试和测试
（1）当为有向有环图结构图6.3所表示

图6.3 有向有环图结构
输出结果图6.4所表示

图6.4有向有环图输出
（2）输入检验图图6.5所表示：

图6.5 检验图

由邻接表定义能够得到上图邻接表图6.6所表示：

图6.6邻接表

其中一个拓扑序列： 2 7 1 3 4 6 5
将图输入到程序中结果图6.7所表示：

图6.8 检验图输出

所得结果和估计结果一致。

7 结果分析
对于算法时间复杂度和空间复杂度， 拓扑排序实际是对邻接表表示图G进行遍历过程，每次访问一个入度为零顶点，若图G中没有回路，则需扫描邻接表中全部边结点，在算法开始时，为建立入度数组D需访问表头向量中全部边结点，算法时间复杂度为O(n+e)。
其次在编写代码时应依据步骤图进行同时编写，综合考虑需求分析进行编辑。不然会出现偏离专题错误。
当然在输出结果后，为避免输入引发错误，因该先对开始和结束结果进行先得出，和运行结果对照，小问题应该进行尽可能避免，或减小到最小值。

8 总结
平时我就比较爱好编程，有时候自己也会设想部分小程序，然后经过自己努力来实现。所以我把此次课程设计看成了又一次锻炼，拿到题目后，经过和组员讨论便开始了程序编写。
大家全部知道，编程是一件很需要耐心事。因为几乎每一个程序编写，全部需要学习新知识才能进行，同时程序调试过程很枯燥，有时候一点小错意味着长时间查错。如语法错误中，“;”丢失、“{”和“}”不匹配等问题最难定位到犯错语句；逻辑错误中，作为循环变量“i”和“j”相互混淆、对未分配空间节点进行操作等，全部会使程序运行犯错而难以找到原因。算法设计、程序调试过程中，常常碰到看似简单但又无法处理问题，这时候很轻易气馁丧气，此时切不可烦躁，一定要冷静思索，认真分析；而处理问题，完成程序后，那种兴奋感和成就感也令人振奋。能够说编写程序既是一件艰苦工作，又是一件愉快事情。
我小组课程设计题目标关键是“拓扑排序”。即使平时对拓扑排序有部分了解，上课也学过，但真正应用到程序中，写出算法却一点也不简单。拓扑排序，首先需要有被排序主体，也就是有向图，于是先要实现有向图建立及相关操作；有向图建立，该选择怎样数据结构，是邻接矩阵还是邻接表，本着尽可能靠近实际应用态度，我选择了节省存放空间邻接表；拓扑排序要将图中零入度顶点先输出，可利用栈或队列实现，而本程序一个应用是实现教学计划安排，考虑到教学计划安排实际情况，通常先学各门基础课（入度为零），再学专业课（入度不为零），和队列优异先出特点相符，故采取队列实现。总而言之，什么地方该用什么数据结构，该写出怎样算法，全部要经过精心分析和仔细考虑。
课程设计不是一个人任务，而是一个小组三个组员共同任务，不仅要能完成程序，而且在完成过程中也要让团体有效地协作起来。在此次课程设计过程中，我认识到以下几点：第一，要有奉献精神，不要怕自己多做了，不要怕自己负担任务有多重，而其它组员做极少。多去做一点不会吃亏，还能学到更多东西。团体组员之间应团结互助，不计功过得失；第二，分工上不能马虎，要具体到个人，每个人负责哪部分任务，什么时候完成，全部要有明确说明，应各尽其能，做到资源优化配置；第三，具体工作时，各组员应频繁交流，避免各自为政，最终造成函数功效不符要求，参数调用不方便，或是论文作者无从下手；第四，当工作出现问题时，各组员应仔细商讨，立即找到问题症结，决不应推卸责任，更不能相互埋怨。
在完成课程设计过程中，我加深了对程序结构了解程度，对多种语句了解也更透彻，学会了灵活利用。同时体会到了团体合作乐趣，一向惯于“独立思索”我们学会了主动地同团体组员交流，取长补短，共同进步，只有和同学多交流多学习才能不停地提升本身水平。
总而言之，这学期数据结构课程设计，让我们学到了很多，受益匪浅。

参考文件
[1] 严蔚敏，吴伟民.数据结构(C语言版)[M]. 北京：清华大学出版社,
[2] 李春葆.数据结构(C语言版)习题和解析[M]. 北京：清华大学出版社,
[3] 钱能.C++程序设计教程[M]. 北京：清华大学出版社,
[4] 谭浩强.C程序设计.第三版[M]. 北京.清华大学出版社,.
[5] 张晓莉，刘振鹏，许百成．数据结构和算法[M]. 北京：机械工业出版社,
[6] 叶核亚．数据结构（C++版）[M]．北京：机械工业出版社，