下载后可任意编辑数据结构课程设计设计题目: 有向图拓扑排序 专 业: 信息与计算科学 学 号: 姓 名: 黄秋实 指导老师: 文 军 11 月 28 日数据结构课程设计 ----拓扑排序一 需求分析1.问题描述下载后可任意编辑 本次课程设计题目是: 用邻接表构造图 然后进行拓扑排序, 输出拓扑排序序列拓扑排序的基本思想为: 1).从有向图中选一个无前驱的顶点输出; 2).将此顶点和以它为起点的弧删除; 3). 重复 1),2)直到不存在无前驱的顶点; 4). 若此时输出的顶点数小于有向图中的顶点数, 则说明有向图中存在回路, 否则输出的顶点的顺序即为一个拓扑序列。 2. 拓扑排序 有向图拓朴排序算法的基本步骤如下: ① 从图中选择一个入度为 0 的顶点, 输出该顶点; ② 从图中删除该顶点及其相关联的弧, 调整被删弧的弧头结点的入度( 入度-1) ; ③ 重复执行①、 ②直到所有顶点均被输出, 拓朴排序完成或者图中再也没有入度为 0 的顶点( 此种情况说明原有向图含有环) 。3 基本要求(1) 输入的形式和输入值的范围; 首先是输入要排序的顶点数和弧数, 都为整型, 中间用分隔符隔开; 再输入各顶点的值, 为正型, 中间用分隔符隔开; 然后输入各条弧的两个顶点值, 先输入弧头, 再输入弧尾, 中间用分隔符隔开, 输入的值只能是开始输入的顶点值否则系统会提示输入的值的顶点值不正确, 请重新输入, 只要继续输入正确的值就行。(2)输出的形式; 首先输出建立的邻接表, 然后是最终各顶点的出度数, 再是拓扑排序的序列, 而且每输出一个顶点, 就会输出一次各顶点的入度数。(3) 程序所能达到的功能; 因为该程序是求拓扑排序, 因此算法的功能就是要输出拓扑排序的序列, 下载后可任意编辑在一个有向图中, 若用顶点表示活动, 有向边就表示活动间先后顺序, 那么输出的拓扑序列就表示各顶点间的关系为反映出各点的存储结构, 以邻接表存储并输出各顶点的入度。二 概要设计1. 算法中用到的所有各种数据类型的定义在该程序中用邻接表作为图的存储结构。首先, 定义表结点和头结点的结构类型, 然后定义图的结构类型。创立图用邻接表存储的函数, 其中根据要求输入图的顶点和边数, 并根据要求设定每条边的起始位置, 构建邻接表依次将顶点插入到邻接表中。拓扑排序的函数在该函数中首先要对各顶点求入度, 其中要用到求入度的函数, 为了避开重复检测入度为零的顶点, 设置一个辅助栈, 因此要定义顺序栈类型, 以及栈...
