拓扑排序
一 目的
通过课程设计，加深对《程序设计语言》和《软件技术基础》课程所学知识的理解，熟练掌握和巩固C语言的基本知识和语法规范，包括：数据类型（整形、实型、字符型、指针、数组、结构等）；运算类型（算术运算、逻辑运算、自增自减运算、赋值运算等）；程序结构（顺序结构、判断选择结构、循环结构）；库函数应用等；复杂任务功能分解方法（自顶向下逐步求精、模块化设计、信息隐藏等），熟练掌握和巩固三种基本图形结构的逻辑结构、存储结构以及相关运算和应用。
学会编制结构清晰、风格良好、数据结构适当的C语言程序，从而具备利用计算机编程分析解决综合性实际问题的初步能力。
二 需求分析
题目描述：判断一个有向图是否存在回路，并求出有向无环图的拓扑序列。
1、输入数据
在工程文件中保存输入2个字符串数TXT文件。第一个为图按次序排列的所有边的前顶点，第二个为相对应的第二个顶点。
2、输出数据
图的定点数，边数，每个顶点的信息及入度，构造的邻接表，图的拓扑排序。
3、程序功能
已将AOV网存入文件中，运行时从文件读取数据；对一个AOV网，应判断其是否是有向无环图，若是则输出其任意一个拓扑排序序列，不是则进行相关的说明；构造图的邻接表；输出所有顶点的入度。
三 概要设计
1、全局变量或类型说明
typedef struct A_Node //定义表结点结构
{
int adjvex; //与vi相邻接的顶点编号
struct A_Node *nextarc; //指向下一条弧(边)的指针
} A_Node;
typedef struct V_Node //定义表头结点结构
{
int data;
A_Node *firstarc; //指向第一条弧（边）的指针
} V_Node, AdjList[MAX_NUM];
typedef struct //定义邻接表结构
{
AdjList vertices; //表头结点数组
int vex_num, arc_num; //顶点和弧（边）的个数
} ALGraph;
typedef struct //构件栈
{
Elem_T *base;
Elem_T *top;
int stacksize;
} Sq;
2、模块功能
1) void Init(Sq *S);
功能：初始化栈。构造一个空栈S
参数：*S 待初始化的栈
2) int Stack(Sq *S)
功能：判断空栈
参数：S 待判断的栈
返回值：栈为空返回 1；栈非空返回 0
3) Void Int(Sq *S, Elem_T e)
功能：元素入栈
参数：*S 待操作的栈；插入元素e为新的栈顶元素
4) void Out(Sq *S, Elem_T e);
功能：元素出栈
参数：*S 待操作的栈；若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回0
5) void Creat_Graph(ALGraph *G)
功能：建立图。函数内包含了由用户输入顶点数、弧数、顶点以及弧的操作
参数：*G 待操作的图
返回值：图建立成功返回1；图建立失败返回0
6) void Find_InDegree(ALGraph G, int indegree[])
功能：求顶点的入度
参数：G 待操作的图，indegree[]储存每个顶点的入度的数组
7) void T_Sort(ALGraph G);
功能：实现拓扑排序，并在图形界面上演示排序过程
参数：G 待进行拓扑排序的图
错误判断：包含有向图是否有环的判断
四 详细设计
源代码如下：
#include<STDIO.H>
#include<STDLIB.H>
#define MAX_NUM 20 //最大顶点个数#define M 20
#define STACK_SIZE 100
#define STACK_MENT 10
#define OK 1
#define M 20
#define ERROR 0
#define NUM 15
typedef int Elem_T;
char number1[NUM];
char number2[NUM];
typedef struct A_Node //定义表结点结构
{
int adjvex; //与vi相邻接的顶点编号
struct A_Node *nextarc; //指向下一条弧(边)的指针
} A_Node;
typedef struct V_Node //定义表头结点结构
{
int data;
A_Node *firstarc; //指向第一条弧（边）的指针
} V_Node, AdjList[MAX_NUM];
typedef struct //定义邻接表结构
{
AdjList vertices; //表头结点数组
int vex_num, arc_num; //顶点和弧（边）的个数
} ALGraph;
typedef struct //构件栈
{
Elem_T *base;
Elem_T *top;
int stacksize;
} Sq;
void Init(Sq *); //函数声明
int Int(Sq *, Elem_T *);
void Out(Sq *, Elem_T);
int Stack(Sq *);
void Creat_Graph(ALGraph *);
void Find_InDegree(ALGraph, int *);
void T_Sort(ALGraph);
int main(void) //主函数
{
char num='Y'; FILE *fp;
fp=fopen("num1.txt","r");//打开num1文件
if(fp!=NULL)
{
for(int i=1;i<=NUM;i++)
{
fscanf(fp,"%d",&number1[i]);//将文件的内容读入number1数组中
}
fclose(fp);//关闭文件
}
fp=fopen("num2.txt","r");//打开文件num2
if(fp!=NULL)
{
for(int i=1;i<=NUM;i++)
{
fscanf(fp,"%d",&number2[i]);//读取文件的内容到number2中
}
fclose(fp);//关闭文件
}
while(1)
{
printf("是否继续使用（Y/N):"); //判断是否为Y，若是则继续运行，若是N则退出
scanf("%c",&num);
if(num=='N')
{
exit(0);
}
ALGraph G;
Creat_Graph(&G);//调用函数创建有向图
T_Sort(G);//进行拓扑排序
}
return 0;
}
void Init(Sq *S)//初始化栈
{
S->base = (Elem_T *) malloc(STACK_SIZE * sizeof (Elem_T));//构建空指针
if (!S->base) {
printf("memory allocation failed, goodbye");//判断是否建立成功
exit(1);
}
S->top = S->base;
S->stacksize = STACK_SIZE;
}
int OutSq *S, Elem_T *e)//出栈操作
{
if (S->top == S->base) {
return ERROR;
}
*e = *--S->top;
return 0;
}
Void Int(Sq *S, Elem_T e)//进栈操作
{
if (S->top - S->base >= S->stacksize) {
S->base = (Elem_T *) realloc(S->base, (S->stacksize + STACK_MENT) * sizeof (Elem_T));
if (!S->base) {
printf("memory allocation failed, goodbye");
exit(1);
}
S->top = S->base + S->stacksize;
S->stacksize += STACK_MENT;
}
*S->top++ = e;
}
int Stack(Sq *S)//判断栈是否为空
{
if (S->top == S->base)
return OK;
else
return ERROR;
}
void Creat_Graph(ALGraph *G)//构建图
{
int m, n, i,j;
A_Node *p;
printf("\n***************************************************\n");
printf("********* 欢迎使用拓扑排序 ***********\n");
printf("********* 制作者：杨玉斌 ***********\n");
printf("********* 学号：10064126 ***********\n");
printf("********* 退出：(Y) ***********\n");
printf("***************************************************\n");
printf("请输入顶点数和边数:10 15");
G->vex_num=10 ;//要构建的顶点个数
G->arc_num=15;//要构建的边数
for (i = 1; i <= G->vex_num; i++) {
G->vertices[i].data = i;//构建顶点
G->vertices[i].firstarc = NULL;
}
j=1;
for (i = 1; i <= G->arc_num; i++) //输入存在边的点集合
{
if(j>15)
{ j=1;}
n=number1[j];//起点数组
m=number2[j];//终点数组
printf("\n输入存在边的两个顶点的序号:");
printf("%d ",n);//打印构建的边
printf("%d",m);
j++;
//scanf("%d%d", &n, &m);
while (n < 0 || n > G->vex_num || m < 0 || m > G->vex_num) {
printf("输入的顶点序号不正确 请重新输入:");
scanf("%d%d", &n, &m);
}
p = (A_Node*) malloc(sizeof (A_Node));//构建空链表
if (p == NULL) {
printf("memory allocation failed,goodbey");
exit(1);
}
p->adjvex = m;//表头指向终点
p->nextarc = G->vertices[n].firstarc;
G->vertices[n].firstarc = p;
}
}
void Find_InDegree(ALGraph G, int indegree[])//找入度为零的节点
{
int i;
for (i = 1; i <= G.vex_num; i++) {
indegree[i] = 0;
}
for (i = 1; i <= G.vex_num; i++) {
while (G.vertices[i].firstarc) {
indegree[G.vertices[i].firstarc->adjvex]++;
G.vertices[i].firstarc = G.vertices[i].firstarc->nextarc;
}
}
}
void T_Sort(ALGraph G) //进行拓扑排序
{
int indegree[M];
int i, k, n;
int count = 0; //用来统计顶点的个数
A_Node *p; //定义一个栈，用来保存入度为0的顶点
Sq S;
Find_InDegree(G, indegree);//查找深度
Init(&S);//初始化栈
for (i = 1; i <= G.vex_num; i++) {
if (!indegree[i])//如果深度为0则入栈
Int(&S, i);
}
printf("\n进行拓扑排序输出顺序为:\n"); //输出结果
while (!Stack(&S)) {
Out(&S, &n);//出栈
printf("%4d", G.vertices[n].data);//打印结果
count++;
for (p = G.vertices[n].firstarc; p != NULL; p = p->nextarc) {
k = p->adjvex;
if (!(--indegree[k])) //自减若深度为0则入栈
{ Int(&S, k);//;入栈
}
}
}
printf("\n");
if (count < G.vex_num) {
printf("该有向图有回路");
} else {
printf("排序成功\n");
}
}
五 调试分析
1、测试数据
图的拓扑排序：
2、存在过的问题以及分析解决
（1）本课程设计采用先把主体结构写好后在网结构中添加具体的分布功能。采用的是主分式的形式以保证一个功能不能实现并不影响其他的功能。
（2）课程设计有较好的容错能力，能够让一般用户也不出错，能正确的输入信息和统计，保证了正确性。
（3）修改的时候采用一边调试一边修改，并不断尝试错误输入和验证。
六 测试结果
测试结果如下图所示：
七 用户使用说明
运行程序前在工程文件中输入所构造图的边顶点并保存,运行后会输出图的顶点数，边数，顶点信息，图的所有边数，构造的连接表，每个顶点的入度和有向无环图的拓扑排序及对有环图进行说明。再按任意键，结束程序运行，进行对其他图的拓扑排序。
八 课程设计总结
根据本课程设计的实验，从中学到了编程其实也是一项很有考验性的活动，从很大程度上提高了我们对这门课程的了解和学习，并学会从实践中总结经验，从实验中找到方法，通过本次课程设计加深了对所学知识的理解。大家都知道，编程是一件很需要耐心的事。因为几乎每一个程序的编写，都需要学习新的知识才能进行，同时程序调试过程很枯燥，有时候一点小错意味着长时间的查错。如语法错误中，“;”丢失、“{”与“}”不匹配等问题最难定位到出错语句；逻辑错误中，作为循环变量的“i”与“j”相互混淆、对未分配空间的节点进行操作等，都会使程序运行出错而难以找到原因。算法设计、程序调试的过程中，经常遇到看似简单但又无法解决的问题，这时候很容易灰心丧气，此时切不可烦躁，一定要冷静的思考，认真的分析；而解决问题，完成程序后，那种兴奋感与成就感也令人振奋。可以说编写程序既是一件艰苦的工作，又是一件愉快的事情。
在完成课程设计的过程中，我加深了对程序结构的了解程度，对各种语句理解也更透彻，学会了灵活运用。同时体会到了团队合作的乐趣，一向惯于“独立思考”的我们学会了积极地同团队成员交流，取长补短，共同进步，只有和同学多交流多学习才能不断地提高自身水平。
总之，这学期的数据结构课程设计，让我们学到了很多，受益匪浅。