1、软件技术基础软件技术基础课程设计课程设计 中南民族大学计算机科学学院 专业 :自动化 学号：* 姓名 ：* 1 拓扑排序拓扑排序 一一 目的目的 通过课程设计，加深对程序设计语言和软件技术基础课程所学知识的理解， 熟练掌握和巩固 C语言的基本知识和语法规范，包括：数据类型（整形、实型、字符型、指 针、数组、结构等）；运算类型（算术运算、逻辑运算、自增自减运算、赋值运算等）；程 序结构（顺序结构、判断选择结构、循环结构）；库函数应用等；复杂任务功能分解方法 （自顶向下逐步求精、模块化设计、信息隐藏等），熟练掌握和巩固三种基本图形结构的逻 辑结构、存储结构以及相关运算和应用。 学会编制结构清晰、风
2、格良好、数据结构适当的 C语言程序，从而具备利用计算机编 程分析解决综合性实际问题的初步能力。 二二 需求分析需求分析 题目描述：题目描述：判断一个有向图是否存在回路，并求出有向无环图的拓扑序列。 1、输入数据 在工程文件中保存输入 2 个字符串数 TXT 文件。第一个为图按次序排列的所有边的前 顶点，第二个为相对应的第二个顶点。 2、输出数据 图的定点数，边数，每个顶点的信息及入度，构造的邻接表，图的拓扑排序。 3、程序功能 已将 AOV网存入文件中，运行时从文件读取数据；对一个 AOV 网，应判断其是否是有 向无环图，若是则输出其任意一个拓扑排序序列，不是则进行相关的说明；构造图的邻接 表
3、；输出所有顶点的入度。 三三 概要设计概要设计 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_NU
4、M; 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, El
5、em_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 TuoPu(ALGraph G); 功能：实现拓扑排序，并在图形界面上演示排序过程 参数：G 待进行拓扑排序的图 错误判断：包含有向图是否有环的判断 软件技术基础软件技术基础课程设计课程设计 中南民族大学计算机科学学院 专业 :自动化 学号：* 姓名 ：* 3 四四 详细设计详细设计 源代码详情如下： /*拓扑排序*/ /*张雪涛*/ /*2013.12.27*/ /*函数头文件、宏定义、变量声明*/ #include #include #define MAX_NUM 15 #define STACK_SIZE 100
