拓扑排序课程设计报告

拓扑排序一 目的通过课程设计，加深对程序设计语言和软件技术基础课程所学知识的理解，熟练掌握和巩固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, AdjListMAX_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；栈非空返回 03) Void Int(Sq *S, Elem_T e)功能：元素入栈参数：*S 待操作的栈；插入元素e为新的栈顶元素4) void Out(Sq *S, Elem_T e);功能：元素出栈参数：*S 待操作的栈；若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回05) void Creat_Graph(ALGraph *G)功能：建立图。函数内包含了由用户输入顶点数、弧数、顶点以及弧的操作参数：*G 待操作的图返回值：图建立成功返回1；图建立失败返回06) void Find_InDegree(ALGraph G, int indegree)功能：求顶点的入度参数：G 待操作的图，indegree储存每个顶点的入度的数组7) void TuoPu(ALGraph G);功能：实现拓扑排序，并在图形界面上演示排序过程参数：G 待进行拓扑排序的图错误判断：包含有向图是否有环的判断四 详细设计源代码详情如下：/*拓扑排序*/*张雪涛*/*2013.12.27*/*函数头文件、宏定义、变量声明*/#include#include#define MAX_NUM 15 #define STACK_SIZE 100#define STACK_MENT 10#define OK 1#define M 20#define ERROR 0#define NUM 15typedef int Elem_T;char number1NUM;char number2NUM;/*结构体定义*/typedef struct A_Node /定义表结点结构 int adjvex; /与vi相邻接的顶点编号 struct A_Node *nextarc; /指向下一条弧(边)的指针 A_Node;typedef struct V_Node /定义表头结点结构 int data; A_Node *firstarc; /指向第一条弧（边）的指针 V_Node, AdjListMAX_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 Stack(Sq *); void TuoPu(ALGraph);int Out(Sq *, Elem_T);int Int(Sq *, Elem_T *);void Creat_Graph(ALGraph *);void Find_InDegree(ALGraph, int *);/*主函数*/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,&number1i);/将文件的内容读入number1数组中fclose(fp); /关闭文件fp=fopen(num2.txt,r); /打开文件num2if(fp!=NULL)for(int i=1;ibase = (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 Out(Sq *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(* 学号：10056041 *n); printf(*n); printf(请输入顶点数和边数:10 15); G-vex_num=10 ;/要构建的顶点个数 G-arc_num=15;/要构建的边数 for (i = 1; i vex_num; i+) G-verticesi.data = i;/构建顶点 G-verticesi.firstarc = NULL; j=1; for (i = 1; i arc_num; i+) /输入存在边的点集合 if(j15) j=1;n=number1j;/起点数组m=number2j;/终点数组printf(n 第);printf(%d ,i);if(i=10)printf(条边的两顶点序号分别为为:);elseprintf( 条边的两顶点序号分别为为:);printf(%d ,n);/打印构建的边printf(%d,m);j+; /scanf(%d%d, &n, &m); while (n G-vex_num | m G-vex_num) printf(n 输入的顶点序号不正确 请重新输入!);printf(n 第);printf(%d ,i);if(i=10)printf(条边的两顶点序号分别为为:);elseprintf( 条边的两顶点序号分别为为:); 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-verticesn.firstarc; G-verticesn.firstarc = p; void Find_InDegree(ALGraph G, int indegree)/找入度为零的节点 int i; for (i = 1; i = G.vex_num; i+) indegreei = 0; for (i = 1; i adjvex+; G.verticesi.firstarc = G.verticesi.firstarc-nextarc; void TuoPu(ALGraph G) /进行拓扑排序 int indegreeM; 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 (!indegreei)/如果深度为0则入栈Int(&S, i); if (count nextarc) k = p-adjvex; if (!(-indegreek) /自减若深度为0则入栈 Int(&S, k);/入栈 printf(n);printf(排序成功n);五 调试分析1、测试数据图的拓扑排序：1424444567893102、存在过的问题以及分析解决（1）本课程设计采用先把主体结构写好后在网结构中添加具体的分布功能。采用的是主分式的形式以保证一个功能不能实现并不影响其他的功能。（2）课程设计有较好的容错能力，能够让一般用户也不出错，能正确的输入信息和统计，保证了正确性。（3）修改的时候采用一边调试一边修改，并不断尝试错误输入和验证。六 测试结果测试结果如下图所示：正常使用： 继续选择是否使用：错误的输入如下：有回路的操作如下：七 用户使用说明运行程序前在工程文件中输入所构造图的边顶点并保存,运行后会输出图的顶点数，边数，顶点信息，图的所有边数，构造的连接表，每个顶点的入度和有向无环图的拓扑排序及对有环图进行说明。再按任意键，结束程序运行，进行对其他图的拓扑排序。八 课程设计总结根据本课程设计的实验，从中学到了编程其实也是一项很有考验性的活动，从很大程度上提高了我们对这门课程的了解和学习，并学会从实践中总结经验，从实验中找到方法，通过本次课程设计加深了对所学知识的理解。大家都知道，编程是一件很需要耐心的事。因为几乎每一个程序的编写，都需要学习新的知识才能进行，同时程序调试过程很枯燥，有时候一点小错意味着长时间的查错。如语法错误中，“;”丢失、“”与“”不匹配等问题最难定位到出错语句；逻辑错误中，作为循环变量的“i”与“j”相互混淆、对未分配空间的节点进行操作等，都会使程序运行出错而难以找到原因。算法设计、程序调试的过程中，经常遇到看似简单但又无法解决的问题，这时候很容易灰心丧气，此时切不可烦躁，一定要冷静的思考，认真的分析；而解决问题，完成程序后，那种兴奋感与成就感也令人振奋。可以说编写程序既是一件艰苦的工作，又是一件愉快的事情。在完成课程设计的过程中，我加深了对程序结构的了解程度，对各种语句理解也更透彻，学会了灵活运用。同时体会到了团队合作的乐趣，一向惯于“独立思考”的我们学会了积极地同团队成员交流，取长补短，共同进步，只有和同学多交流多学习才能不断地提高自身水平。 总之，这学期的数据结构课程设计，让我们学到了很多，受益匪浅。