拓扑排序课程设计报告

《拓扑排序课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、《软件技术基础》课程设计拓扑排序一目的通过课程设计，加深对《程序设计语言》和《软件技术基础》课程所学知识的理解，熟练掌握和巩固C语言的基本知识和语法规范，包括：数据类型（整形、实型、字符型、指针、数组、结构等）；运算类型（算术运算、逻辑运算、自增自减运算、赋值运算等）；程序结构（顺序结构、判断选择结构、循环结构）；库函数应用等；复杂任务功能分解方法（自顶向下逐步求精、模块化设计、信息隐藏等），熟练掌握和巩固三种基本图形结构的逻辑结构、存储结构以及相关运算和应用。学会编制结构清晰、风格良好、数据结构适当的C语言程序，从而具备利用计算机编程分析解决综合性实际问题的初步能力。二需求分析题目

2、描述：判断一个有向图是否存在回路，并求出有向无环图的拓扑序列。1、输入数据在工程文件中保存输入2个字符串数TXT文件。第一个为图按次序排列的所有边的前顶点，第二个为相对应的第二个顶点。2、输出数据图的定点数，边数，每个顶点的信息及入度，构造的邻接表，图的拓扑排序。3、程序功能已将AOV网存入文件中，运行时从文件读取数据；对一个AOV网，应判断其是否是有向无环图，若是则输出其任意一个拓扑排序序列，不是则进行相关的说明；构造图的邻接表；输出所有顶点的入度。三概要设计1、全局变量或类型说明//********结构体定义***********//typedefstructA_Node//定义

3、表结点结构{intadjvex;//与vi相邻接的顶点编号structA_Node*nextarc;//指向下一条弧(边)的指针}A_Node;typedefstructV_Node//定义表头结点结构{intdata;A_Node*firstarc;//指向第一条弧（边）的指针11中南民族大学计算机科学学院专业:自动化学号：*******姓名：*******《软件技术基础》课程设计}V_Node,AdjList[MAX_NUM];typedefstruct//定义邻接表结构{AdjListvertices;//表头结点数组intvex_num,arc_num;//顶点和弧（边）的个

4、数}ALGraph;typedefstruct//构件栈{Elem_T*base;Elem_T*top;intstacksize;}Sq;2、模块功能1)voidInit(Sq*S);功能：初始化栈。构造一个空栈S参数：*S待初始化的栈2)intStack(Sq*S)功能：判断空栈参数：S待判断的栈返回值：栈为空返回1；栈非空返回03)VoidInt(Sq*S,Elem_Te)功能：元素入栈参数：*S待操作的栈；插入元素e为新的栈顶元素4)voidOut(Sq*S,Elem_Te);功能：元素出栈参数：*S待操作的栈；若栈不空，则删除S的栈顶元素，用e返回其值，并返回1；否则返回05

5、)voidCreat_Graph(ALGraph*G)功能：建立图。函数内包含了由用户输入顶点数、弧数、顶点以及弧的操作参数：*G待操作的图返回值：图建立成功返回1；图建立失败返回06)voidFind_InDegree(ALGraphG,intindegree[])功能：求顶点的入度参数：G待操作的图，indegree[]储存每个顶点的入度的数组7)voidTuoPu(ALGraphG);功能：实现拓扑排序，并在图形界面上演示排序过程参数：G待进行拓扑排序的图错误判断：包含有向图是否有环的判断11中南民族大学计算机科学学院专业:自动化学号：*******姓名：*******《软件技

6、术基础》课程设计四详细设计源代码详情如下：//*****拓扑排序*********////******张雪涛*********////*****2013.12.27******////*****函数头文件、宏定义、变量声明*******//#include#include#defineMAX_NUM15#defineSTACK_SIZE100#defineSTACK_MENT10#defineOK1#defineM20#defineERROR0#defineNUM15typedefintElem_T;charnumber1[NUM];charnu

7、mber2[NUM];//********结构体定义***********//typedefstructA_Node//定义表结点结构{intadjvex;//与vi相邻接的顶点编号structA_Node*nextarc;//指向下一条弧(边)的指针}A_Node;typedefstructV_Node//定义表头结点结构{intdata;A_Node*firstarc;//指向第一条弧（边）的指针}V_Node,AdjList[MAX_NUM];typ