软件技术基础课程设计中南民族大学计算机科学学院 专业 :自动化 学号：* 姓名 ：* 1拓扑排序一 目的通过课程设计，加深对程序设计语言和软件技术基础课程所学知识的理解，熟练掌握和巩固 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; /指向第一条弧（边）的指针软件技术基础课程设计中南民族大学计算机科学学院 专业 :自动化 学号：* 姓名 ：* 2 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 待进行拓扑排序的图错误判断：包含有向图是否有环的判断软件技术基础课程设计中南民族大学计算机科学学院 专业 :自动化 学号：* 姓名 ：* 3四 详细设计源代码详情如下：/*拓扑排序*/*张雪涛*/*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;软件技术基础课程设计中南民族大学计算机科学学院 专业 :自动化 学号：* 姓名 ：* 4/*函数声明*/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;ibase = (Elem_T *) malloc(STACK_SIZE * sizeof (Elem_T);/构建空指针if (!S-base) printf(memory allocation failed, goodbye);/判断是否建立成功软件技术基础课程设计中南民族大学计算机科学学院 专业 :自动化 学号：* 姓名 ：* 5exit(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;elsereturn 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;软件技术基础课程设计中南民族大学计算机科学学院 专业 :自动化 学号：* 姓名 ：* 6j=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, while (n G-vex_num | m G-vex_num) printf(n 输入的顶点序号不正确 请重新输入!);printf(n 第);printf(%d ,i);if(i=10)printf(条边的两顶点序号分别为为:);elseprintf( 条边的两顶点序号分别为为:);scanf(%d%d, 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 adjvex+;G.verticesi.firstarc = G.verticesi.firstarc-