拓扑排序课程设计报告.pdfVIP

数据结构课程设计 设计题目： 有向图拓扑排序 专 业： 信息与计算科学 学 号： 0 姓 名： 黄秋实 指导教师： 文 军 2013 年 11 月 28 日 数据结构课程设计 拓扑排序 一 需求分析 1.问题描述 本次课程设计题目是：用邻接表构造图 然后进行拓扑排序，输出拓扑排序序列 拓扑排序的基本思想为： 1).从有向图中选一个无前驱的顶点输出； 2).将此顶点和以它为起点的弧删除； 3). 重复 1),2) 直 到不存在无前驱的顶点； 4). 若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在 回路，否则输出的顶点的顺序即为一个拓扑序列。 2. 拓扑排序 有向图拓朴排序算法的基本步骤如下： ①从图中选择一个入度为 0 的顶点，输出 该顶点； ②从图中删除该顶点及其相关联的弧，调整被删弧的弧头结点的入度（入度 -1 ）； ③ 重复执行①、 ②直到所有顶点均被输出， 拓朴排序完成或者图中再也没有入度为 0 的顶点 （此种 情况说明原有向图含有环）。 3 基本要求 输入的形式和输入值的范围； 首先是输入要排序的顶点数和弧数，都为整型，中间用分隔符隔开；再输入各顶点的值，为 正型，中间用分隔符隔开；然后输入各条弧的两个顶点值，先输入弧头，再输入弧尾，中间用分 隔符隔开， 输入的值只能是开始输入的顶点值否则系统会提示输入的值的顶点值不正确， 请重新 输入，只要继续输入正确的值就行。 输出的形式； 首先输出建立的邻接表，然后是最终各顶点的出度数，再是拓扑排序的序列，并且每输出 一个顶点，就会输出一次各顶点的入度数。 (3) 程序所能达到的功能； 因为该程序是求拓扑排序，所以算法的功能就是要输出拓扑排序的序列， 在一个有向图中， 若用顶点表示活动， 有向边就表示活动间先后顺序， 那么输出的拓扑序列就表 示各顶点间的关系为反映出各点的存储结构，以邻接表存储并输出各顶点的入度。 二 概要设计 1. 算法中用到的所有各种数据类型的定义 在该程序中用邻接表作为图的存储结构。 首先，定义表结点和头结点的结构类型， 然后定义图的结构类型。 创建图用邻接表存储的函数， 其中根据要求输入图的顶 点和边数， 并根据要求设定每条边的起始位置， 构建邻接表依次将顶点插入到邻 接表中。 拓扑排序的函数在该函数中首先要对各顶点求入度，其中要用到求入度的函数， 为了避免重复检测入度为零的顶点，设置一个辅助栈，因此要定义顺序栈类型， 以及栈的函数：入栈，出栈，判断栈是否为空。 2.各程序模块之间的层次调用关系 第一部分， void ALGraph *G 函数构建图，用邻接表存储。这个函数没有调 用函数。 第二部分， void TopologicalSort(ALGraph *G)输出拓扑排序函数，这个函数 首先调用 FindInDegree(G,indegree)对各顶点求入度 indegree[0……vernum-1]; 然 后设置了一个辅助栈， 调用 InitStack(S)初始化栈， 在调用 Push(S,i)入度为 0 者 进栈，while(!StackEmpty(S))栈不为空时， 调用 Pop(sS,n)输出栈中顶点并将以 该顶点为起点的边删除，入度 indegree[k]--,当输出某一入度为 0 的顶点时，便将 它从栈中删除。 第三部分，主函数，先后调用 void Cr