拓扑排序专业课程设计方案报告.doc

数据构造课程设计

设计题目： 有向图拓扑排序
专 业： 信息与计算科学
学 号：
姓 名： 黄秋实
指引教师： 文 军

11月28日

数据构造课程设计
----拓扑排序
一 需求分析
1.问题描述
本次课程设计题目是：用邻接表构造图 然后进行拓扑排序，输出拓扑排序序列
拓扑排序基本思想为：
1).从有向图中选一种无前驱顶点输出；2).将此顶点和以它为起点弧删除；3). 重复1),2)直到不存在无前驱顶点；4). 若此时输出顶点数不大于有向图中顶点数，则阐明有向图中存在回路，否则输出顶点顺序即为一种拓扑序列。
2. 拓扑排序 有向图拓朴排序算法基本环节如下： ①从图中选取一种入度为0顶点，输出该顶点； ②从图中删除该顶点及其有关联弧，调节被删弧弧头结点入度（入度-1）； ③重复执行①、②直到所有顶点均被输出，拓朴排序完毕或者图中再也没有入度为0顶点（此种状况阐明原有向图具有环）。
3基本规定
(1) 输入形式和输入值范畴；
一方面是输入要排序顶点数和弧数，都为整型，中间用分隔符隔开；再输入各顶点值，为正型，中间用分隔符隔开；然后输入各条弧两个顶点值，先输入弧头，再输入弧尾，中间用分隔符隔开，输入值只能是开始输入顶点值否则系统会提示输入值顶点值不对的，请重新输入，只要继续输入对的值就行。
(2) 输出形式；
一方面输出建立邻接表，然后是最后各顶点出度数，再是拓扑排序序列，并且每输出一种顶点，就会输出一次各顶点入度数。
(3) 程序所能达到功能；
由于该程序是求拓扑排序，因此算法功能就是要输出拓扑排序序列，
在一种有向图中，若用顶点表达活动，有向边就表达活动间先后顺序，那么输出拓扑序列就表达各顶点间关系为反映出各点存储构造，以邻接表存储并输出各顶点入度。
二 概要设计
1. 算法中用到所有各种数据类型定义
在该程序中用邻接表作为图存储构造。一方面，定义表结点和头结点构造类型，然后定义图构造类型。创立图用邻接表存储函数，其中依照规定输入图顶点和边数，并依照规定设定每条边起始位置，构建邻接表依次将顶点插入到邻接表中。
拓扑排序函数在该函数中一方面要对各顶点求入度，其中要用到求入度函数，为了避免重复检测入度为零顶点，设立一种辅助栈，因而要定义顺序栈类型，以及栈函数：入栈，出栈，判断栈与否为空。
2.各程序模块之间层次调用关系
第一某些，void ALGraph *G函数构建图，用邻接表存储。这个函数没有调用函数。
第二某些，void TopologicalSort(ALGraph *G)输出拓扑排序函数，这个函数一方面调用FindInDegree(G,indegree)对各顶点求入度indegree[0……vernum-1];然后设立了一种辅助栈，调用InitStack(&S)初始化栈，在调用Push(&S,i)入度为0者进栈，while(!StackEmpty(&S))栈不为空时，调用Pop(&sS,&n)输出栈中顶点并将以该顶点为起点边删除，入度indegree[k]--,当输出某一入度为0顶点时，便将它从栈中删除。
第三某些，主函数，先后调用void CreatGraph(ALGraph *G)函数构建图、
void TopologicalSort(ALGraph *G)函数输出拓扑排序实现整个程序。
3.设计主程序流程(见附页)
三 详细设计
（实现概要设计中定义所有数据类型,对每个操作写出伪码算法；对主程序和其她模块也都需要写出伪码算法(伪码算法达到详细限度建议为；按照伪码算法可以在计算机键盘直接输入高档程序设计语言程序);写出出函数和过程调用关系。）
1.实现概要设计中定义所有数据类型
#include<stdio.h>
#include<stdlib.h>
#define MAX_VEXTEX_NUM 100
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define M 100
#define ERROR 0
typedef int ElemType；
typedef struct ArcNode
{
int adjvex；
struct ArcNode *nextarc；
}ArcNode；
typedef struct VNode
{
int data；
ArcNode *firstarc；
}VNode,AdjList[MAX_VEXTEX_NUM]；
typedef struct
{
AdjList vertices；
int vexnum，arcnum；
}ALGraph；
typedef struct
{
ElemType *base；
ElemType *top；
int stacksize；
}SqStack;
2.算法和各模块代码
程序中各函数算法思想如下：
2.1 void InitStack(SqStack *S)
初始化栈将栈空间设为 STACK-INIT-SIZE。
2.2 int Pop(SqStack *S,ElemType *e)
出栈操作，若站不空，删除S栈顶元素，用e返回其值，并返回OK；否则返回ERROR。
2.3 void Push(SqStack *S,ElemType e)
进栈操作，插入元素e为新栈顶元素。
2.4 int StackEmpty(SqStack *S)
判断栈与否为空,语句if (S->top=S->base )判断，若栈不为空，则删除S栈顶元素，并返回OK；否则返回ERROR。
2.5 void CreatGraph (ALGraph *G)
构建图，用邻接表存储，一方面定义邻接表指针变量，输入顶点数和弧数，初始化邻接表，将表头向量域置空，输入存在弧点集合，当输入顶点值超过输入值范畴就会出错，否则依次插入进邻接表，最后输出建立好邻接表。
2.6 void FindInDegree(ALGrap G，int indegreee[])
求入度操作，设一种存储各顶点入度数组indegreee[]，然后
indegreee[i]=0赋初值，for循环indegreee[]++，存储入度数。
2.7 void TopologicalISort(ALGraph G)
输出拓扑排序函数。其思路是若G无回路，则输出G顶点一种拓扑序列并返回OK，否则返回ERROR。一方面由于邻接表存储构造入度为零顶点即为没有前驱顶点，咱们可以附设一种存储个顶点入度数组，调用FindInDegree( G，indegreee[])对各顶点求入度；为了避免重复检测入度为零0顶点，设立一种栈，调用InitStack(&S)初始化栈，在调用Push(&S,i)入度为0者进栈，while(!StackEmpty(&S))栈不为空时，调用Pop(&sS,&n)输出栈中顶点并将以该顶点为起点边删除，入度indegree[k]--,当输出某一入度为0顶点时，便将它从栈中删除。
3.算法时间复杂度和空间复杂度
拓扑排序实际是对邻接表表达图G进行遍历过程，每次访问一种入度为零顶点，若图G中没有回路，则需扫描邻接表中所有边结点，在算法开始时，为建立入度数组D需访问表头向量中所有边结点，算法时间复杂度为O(n+e)。
四 测试与分析
对有向无环图【下图】进行拓扑排序。

输入：

成果如下：

五 总结
拓扑排序就是对一种有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一种线性序列，使得图中任意一对顶点u和v，若<u，v> ∈E(G)，则u在线性序列中出当前v之前。
在进行课程设计中，更好结识了拓扑排序。理清了各个模块之间算法之间条理。结识了　伪代码（Pseudocode）是一种算法描述语言。使用伪代码目是为了使被描述算法可以容易地以任何一种编程语言（Pascal，C，Java，etc）实现。因而，伪代码必要构造清晰、代码简朴、可读性好，并且类似自然语言。 介于自然语言与编程语言之间。它是一种让人便于理解代码。不依赖于语言，用来表达程序执行过程，而不一定能编译运营代码。在数据构造讲算法时候用诸多。
在设计中，咱们遇到了程序对的，却对某些无向图无法进行拓扑排序问题。多次对程序进行修改后，才可以进行拓扑排序。问题出在调用函数错误理解，模块之间联系模糊不清。
六附录：源程序：
#include<stdio.h>
#include<stdlib.h>
#define MAX_VEXTEX_NUM 100
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define M 100
#define ERROR 0
typedef int ElemType；
typedef struct ArcNode
{
int adjvex；
struct ArcNode *nextarc；
}ArcNode；
typedef struct VNode
{
int data；
ArcNode *firstarc；
}VNode,AdjList[MAX_VEXTEX_NUM]；
typedef struct
{
AdjList vertices；
int vexnum，arcnum；
}ALGraph；
typedef struct
{
ElemType *base；
ElemType *top；
int stacksize；
}SqStack；
void InitStack(SqStack *)；
int Pop(SqStack *，ElemType *)；
void Push(SqStack *,ElemType )；
int StackEmpty(SqStack *)；
void CreatGraph(ALGraph *)；
void FindInDegree(ALGraph ，int * )；
void TopologicalSort(ALGraph )；
void InitStack(SqStack *S)
{
S->base=(ElemType *)malloc(STACK_INIT_SIZE*sizeof(ElemType))；
if(!S->base)
{
printf("内存分派失败，请检查储存位置，再会")；
exit(1)；
}
S->top=S->base；
S->stacksize=STACK_INIT_SIZE；
}
int Pop(SqStack *S,ElemType *e)
{
if(S->top==S->base)
{
return ERROR；
}
*e=*--S->top；
return 0；
}
void Push(SqStack *S,ElemType e)
{
if(S->top-S->base>=S->stacksize)
{
S->base = (ElemType *)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(ElemType))；
if(!S->base)
{
printf("内存分派失败，请检查储存位置，再会")；
exit(1)；
}
S->top = S->base+S->stacksize；
S->stacksize+=STACKINCREMENT；
}
*S->top++=e；
}
int StackEmpty(SqStack *S)
{
if(S->top==S->base)
return OK；
else
return ERROR；
}
void CreatGraph(ALGraph *G)
{
int m，n，i；
ArcNode *p；
printf("请输入顶点数和边数:")；
scanf("%d%d",&G->vexnum,&G->arcnum)；
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请输入存在边两个顶点序号，先输入弧尾，再输入弧头:")；
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("内存分派失败，请检查储存位置，再会")；
exit(1)；
}
p->adjvex = m；
p->nextarc = G->vertices[n].firstarc；
G->vertices[n].firstarc = p；
}
}
void FindInDegree(ALGraph G，int indegree[])
{
int i；
for (i = 1；i <= G.vexnum；i++)
{
indegree[i] = 0；
}
for (i = 1；i <= G.vexnum；i++)
{
while (G.vertices[i].firstarc)
{
indegree[G.vertices[i].firstarc->adjvex]++；
G.vertices[i].firstarc = G.vertices[i].firstarc->nextarc；
}
}
}
void TopologicalSort(ALGraph G)
{
int indegree[M]；
int i，k，n,b,j=0；
int a[20];
int count = 0；
ArcNode *p；
SqStack S；
FindInDegree(G，indegree)；
InitStack(&S)；
for ( i = 1；i <= G.vexnum；i++)
{
if (!indegree[i])
Push(&S,i)；
}
while(!StackEmpty(&S))
{
Pop(&S,&n)；
a[j]=G.vertices[n].data;
j++；
count++；
for (p = G.vertices[n].firstarc； p != NULL； p = p->nextarc)
{
k = p->adjvex；
if (!(--indegree[k]))
{
Push(&S,k)；
}
}
}
printf("\n")；
if (count < G.vexnum)
{
printf("该有向图有环\n")；
}
else
{
printf("排序成功\n")；
printf("进行拓扑排序输出顺序为:")；
for (b=0;b<j;b++)
{
printf("%4d",a[b]);
}
printf("\n");
}
}
int main(void)
{
ALGraph G；
CreatGraph(&G)；
TopologicalSort(G)；
system("pause")；
return 0;
}