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

沈阳航空航天大学 课 程 设 计 报 告 课程设计名称 数据结构课程设计 课程设计题目 拓扑排序算法 院 系 计算机学院 专 业 计算机科学与技术 嵌入式系统方向 班 级 14010105班 学 号 2011040101221 姓 名 王芃然 指导教师 丁一军 目 录 1 课程设计介 绍 1 1 1 课程设计 内容 1 1 2 课 程设计要求 1 2 课程设计原理 2 2 1 课设题目粗略分析 2 2 2 原理图介绍 2 2 2 1 功能模块图 2 2 2 2 流程图分析 3 3 数据结构分析 7 3 1 存储结构 7 3 2 算 法描述 7 4 调试与分析 12 4 1 调试过程 12 4 2 程序执行过程 12 参考文献 14 附 录 关 键部分程序清单 15 1 课程设计介绍 1 1 课程设计内容 由某个集合上的一个偏序得到该集合上的一个全序 这个操作称之为拓扑 排序 若在图一的有向图上人为的加一个表示 V2 V3 的弧 表示 V2 领先于 V3 则图一表示的亦为全序且这个全序称为拓扑有序 而由偏序定义得 到拓扑有序的操作便是拓扑排序 在 AOV 网中为了更好地完成工程 必须满 足活动之间先后关系 需要将各活动排一个先后次序即为拓扑排序 编写算 法建立有向无环图 主要功能如下 1 能够求解该有向无环图的拓扑排序并输出出来 2 拓扑排序应该能处理出现环的情况 3 顶点信息要有几种情况可以选择 1 2 课程设计要求 1 输出拓扑排序数据外 还要输出邻接表数据 2 参考相应的资料 独立完成课程设计任务 3 交规范课程设计报告和软件代码 2 课程设计原理 2 1 课设题目粗略分析 本课设题目要求编写算法能够建立有向无环图 有向无环图 顾名思义 即一个 无环的有向图 是一类较有向图更一般的特殊有向图 其功能要求及个人在写程序时对该功能的实现作如下分析 1 将图以合适的方式存储起来 图有多种存储方式 其中最常用的存储方式有 图的邻接矩阵和邻接表 本人在构思时使用邻接表来建立有向无环图 将其存储 起来 2 求解该有向无环图的拓扑排序 并将其输出出来 若通过构造 建立了一个 有向无环图 那么一定可以求出其拓扑排序 其原理比较简单 即统计每个节点 的入度 将入度为 0 的结点提取出来 然后再统计剩下的结点的入度 再次将入 度为零的结点提取出来 以此类推 这样就形成了一个序列 这样的序列就是该 图的拓扑排序序列 3 拓扑排序算法应能够处理出现环的情况 个人在写程序时 考虑到构造图时 会有构造成有向有环图的情况 应该在运行程序时 试着统计依次按照入读为零 的节点输出的节点数是否为整个节点的总数 如果是 那么拓扑排序成功 输出 拓扑排序的结果 否者输出 有环出现 4 输出除拓扑排序外 还要求输出邻接表数据 由于图是用邻接表存储的 所 以将邻接表按照顺序依次打印输出 2 2 原理图介绍 2 2 1 功能模块图 图 2 1 功能模块图 2 2 2 流程图分析 1 如图 2 2 所示 根据题目要求建立一个有向无环图 按照提示 依次输 入节点数和变数 然后输入两个联通的节点 前者指向后者 当输入边数为 所要输入的数目时 输入结束 有向图建立完成 未判断是否有环 N Y 图 2 2 建立有向无环图 拓扑排序打印邻接表 图的建立 邻接表 入读为零的依次输出有向无环图可进行 拓扑排序算法 邻接矩阵 开始 建立有向无环图 j n 结束 j j 1 输入节点数 i 边数 n j 0 输入确定弧的两点 2 如图 2 3 所示 判断有向图是否为有向无环图 按照输入的有向图建立 一个邻接表 将图储存在邻接表中 并将邻接表打印 然后对该邻接表进行拓扑 排序 依次取入度为零的节点 入栈 并删除该节点和该节点有关的所边 若入 栈节点个数与节点数相同 则全部入栈 该图为无环图 可以进行拓扑排序 若 该图节点数大于入栈节点数 则该图为有环图 N Y 图 2 3 判断是否为无环图 开始 建立邻接表并打印 取入度为零的节点入 栈 删除该节点 继 续遍历其他节点 入栈节点数等 于节点总数 该图为无环图 该图为有环图 结束 3 此时该图为有向无环图 可进行拓扑排序 在上一过程中 所有节点已 经入栈 将栈顶弹出进入另一个空栈 然后依次输出栈顶 拓扑排序成功 如 图 2 4 所示 开始 将栈顶依次输出 拓扑排序成功 结束 将弹出的栈顶进入 新的空栈 输出栈顶元素 图 2 4 输出拓扑排序结果 4 具体内容 开始 符合条件 根据输入信息建立邻接表 建栈 寻找入度为零的节点入栈 弹出栈顶 打印 将与栈顶元 素邻接的节点入度减一 栈是否为空 结束 输入节点及弧的信息 图 2 5 拓扑排序 3 数据结构分析 3 1 存储结构 一个无环的有向图叫做有向无环图 简称 DAG 图 本算法首先要建立一个 有向无环图 即通过输入各边的数据 搭建图的结构 对于图的存储 用到邻接 表 是一种链式存储结构 弧结点结构类型 typedef struct ArcNode int adjvex 该弧指向的顶点的位置 struct ArcNode nextarc 指向下一条弧的指针 ArcNode 邻接表头结点类型 typedef struct VNode int data 顶点信息 ArcNode firstarc 指向第一条依附于该点的弧的指针 VNode AdjList MAX VEXTEX NUM 3 2 算法描述 1 邻接表的构建 创建一个邻接表 首先要输入节点数和边数 然后输入确定一条边的两个节 点 通过输入顺序来确定边的方向 构成有向图 具体方法如下 初始化头结点 for i 1 ivexnum i G vertices i data i 编写顶点的位置序号 G vertices i firstarc NULL 先将头结点清零 编写顶点位置序号 输入确定弧的两点 如果输入数字大于节点数或者小于零 则输出错误信息 并重新输入一组节点 申请新的节点来储存新的节点信息 该弧指向位置编号为 m 的节点 下一条弧指向的是依附于 n 的第一条弧 最后打印生成的邻接表 for i 1 iarcnum i printf n 输入确定弧的两个顶点 u v scanf d d while nG vexnum mG vexnum printf 输入的顶点序号不正确 请重新输入 scanf d d p ArcNode malloc sizeof ArcNode 开辟新的弧结点 if p NULL printf ERROR exit 1 p adjvex m 该弧指向位置编号为 m的结点 p nextarc G vertices n firstarc G vertices n firstarc p printf n 建立的邻接表为 n 打印生成的邻接表 以一定的格式 for i 1 ivexnum i printf d G vertices i data for p G vertices i firstarc p p p nextarc printf d p adjvex printf n 邻接表构建完成 2 入栈操作 在本算法中栈主要用来构造拓扑排序序列 由于栈具有先入后出的特点 所 以 将每次选择入度为零的结点入栈 这样当结点都入栈的时候 再依次出栈 进入另一个新栈 这样 排序序列显而易见 它将图这样的非线性结构转化为栈 这样的线性结构 建立空栈 typedef struct int base 栈底指针 int top 栈顶指针 int stacksize SqStack 初始化栈 void InitStack SqStack S S base int malloc STACK INIT SIZE sizeof int if S base 存储分配失败 printf ERROR exit 1 S top S base S stacksize STACK INIT SIZE 入栈操作 压入新的元素为栈顶 e 为新的栈顶元素 void Push SqStack S int e 压入新的元素为栈顶 if S top S base S stacksize S base int realloc S base S stacksize STACKINCREMENT sizeof int if S base printf ERROR exit 1 S top S base S stacksize S stacksize STACKINCREMENT S top e 3 拓扑排序 本程序的拓扑排序 必须在图的邻接表已知的情况下 它还有另外一个功能 判断一个图是不是无环图 确切的说 不能单纯的叫拓扑排序 但考虑它主要的 作用 在不引起误解的情况下就叫拓扑排序算法 判断一个图是否为有向无环图并进行拓扑排序 对于本题目来说 由于本题 要求是对有向无环图进行拓扑排序 其主要方法是将入度为零的结点依次输出出 来 知道图的所有定点全部输出为止 那么若图为有环图 在环上的结点在其他 结点都选择出来后 入度都不为零 即无法被输出出来 那么就可以认为按照拓 扑排序的方法输出结点后 若不是将节点全部输出出来的 则此图为有环图 输 出有向图有环 拓扑排序失败 若无环 则进行拓扑排序 通过入栈出栈的操作 来完成拓扑排序 主要算法如下 void TopoSort ALGraph G int indegree M int i k n int count 0 初始化输出计数器 ArcNode p SqStack S FindInDegree G indegree InitStack printf n for i 1 inextarc k p adjvex if indegree k 若入度减为零 则再入栈 Push if count G vexnum printf 有向图中有环 else printf 排序成功 4 调试与分析 4 1 调试过程 在调试程序是主要遇到一下几类问题 1 数组的数据容易出现混乱 比如节点用数字标识 数组结点的位置是从 0 开始 而标识符往往从 1 开始 这在程序的开始就应该注意到 2 各函数的形参和实参的区别 全局变量 局部变量的区别 特别是在做 大型程序的时候 如果多个函数都要用到一个变量 那么就应把该变量定义为全 局变量 若错误的定义为局部变量 很容易出现错误 3 程序应该调理清晰 结构明朗 各个函数代表各个模块 起到不同的作 用 并协调运作 形成含有不同功能的程序 开始时因为程序的结构混乱而导致 很难调试 无法找到错误的根源 4 2 程序执行过程 系统使用说明 1 图的创建 2 打印邻接表 3 进行拓扑排序 4 退出程序 具体内容 输入边数及节点数 如图 4 1 所示 图 4 1 主菜单 图的创建 如图 4 2 所示 图 4 2 图的创建 打印邻接表 如图 4 3 所示 图 4 3 打印邻接表 进行拓扑排序 如图 4 4 所示 图 4 4 进行拓扑排序 退出程序 如图 4 5 所示 图 4 5 退出程序 参考文献 1 严蔚敏 吴伟民 数据结构 M 北京 清华大学出版社 2007 2 张长海 陈娟 C 程序设计 M 北京 高等教育出版社 2004 3 谭浩强 C 程序设计 M 北京 清华大学出版社 2005 4 严蔚敏 数据结构 C 语言版 M 清华大学出版社 2005 5 高婷 杨明莉 实用数据结构习题与实践 M 北京 清华大学出版社 2011 6 殷人昆 数据结构 用面向对象方法与 C 描述 M 北京 清华大学出版社 2007 7 宁正元 算法与数据结构习题精解和实验指导 M 北京 清华大学出版社 2005 附 录 关键部分程序清单 程序代码 include include define true 1 define false 0 define MAX VEXTEX NUM 20 define M 20 define STACK INIT SIZE 100 define STACKINCREMENT 10 typedef struct ArcNode 弧结点结构类型 int adjvex 该弧指向的顶点的位置 struct ArcNode nextarc 指向下一条弧的指针 ArcNode typedef struct VNode 邻接表头结点类型 int data 顶点信息 ArcNode firstarc 指向第一条依附于该点的弧 的指针 VNode AdjList MAX VEXTEX NUM AdjList 为邻接表类型 typedef struct AdjList vertices int vexnum arcnum ALGraph void CreatGraph ALGraph G 创建一个图的邻接表 int m n i j ArcNode p printf printf n 输入顶点数 scanf d printf n 输入边数 scanf d printf for i 1 ivexnum i 初始化各顶点 G vertices i data i 编写顶点的位置序号 G vertices i firstarc NULL for i 1 iarcnum i 记录图中由两点确定的弧 printf n 输入确定弧的两个顶点 u v scanf d d while nG vexnum mG vexnum printf 输入的顶点序号不正确 请重新输入 scanf d d p ArcNode malloc sizeof ArcNode 申请新的弧结点来存储用户 输入的弧信息 if p NULL printf ERROR exit 1 p adjvex m 该弧指向位置编号为 m 的结点 p nextarc G vertices n firstarc 下一条弧指向的是依附 于 n 的第一条弧 G vertices n firstarc p printf printf n 请输入指令 scanf d if j 3 printf n 进行拓扑排序 n if j 2 printf n 建立的邻接表为 n 打印生成的邻接表 以一定 的格式 for i 1 ivexnum i printf d G vertices i data for p G vertices i firstarc p p p nextarc printf d p adjvex printf n printf n 请输入指令 scanf d if j 0 printf 感谢您的使用 exit 0 else if j 3 printf n 进行拓扑排序 else printf n 指令错误 printf typedef struct 栈的存储结构 int base 栈底指针 int top 栈顶指针 int stacksize SqStack void InitStack SqStack S 初始化栈 S base int malloc STACK INIT SIZE sizeof int if S base 存储分配失败 printf ERROR exit 1 S top S base S stacksize STACK INIT SIZE void Push SqStack S int e 压入新的元素为栈顶 if S top S base S stacksize S base int realloc S base S stacksize STACKINCREMENT sizeof int 追 加新空间 if S base 存储分配失败 printf ERROR exit 1 S top S base S stacksize S stacksize STACKINCREMENT S top e e 作为新的栈顶元素 int Pop SqStack S int e 弹出栈顶 用 e 返回 if S top S base 栈为空 return false e S top return 0 int StackEmpty SqStack S 判断栈是否为空 为空返回 1 不为空返回 0 if S top S base return true else return false void FindInDegree ALGraph G int indegree 对各顶点求入度 int i for i 1 i G vexnum i 入度赋初值 0 indegree i 0 for i 1 iadjvex 出度不为零 则该顶点 firstarc 域指向的弧指向的顶点入度加一 G vertices i firstarc G vertices i firstarc nextarc void TopoSort ALGraph G int indegree M int i k n int count 0 初始化输出计数器 ArcNode p SqStack S FindInDegree G indegree InitStack printf n for i 1 inextarc n 号顶点的每个邻接点入度减一 k p adjvex if indegree k 若入度减为零 则再入栈 Push if count G vexnum 输出顶点数小于原始图的顶点数 有向图中有回 路 printf 有向图中有环 else printf 排序成功 void main ALGraph G int n printf 拓扑排序 n printf 1 图的建立 n printf 2 打印邻接表 n printf 3 进行拓扑排序 n printf 0 退出程序 n while 1 printf n 请输入指令 scanf d if n 0 printf 感谢您的使用 n exit 0 任意键结束 else if n 1 CreatGraph 建立邻接表 else printf n 错误 请先构建图 n TopoSort G 对图 G 进行拓扑排序 printf n n 课程设计总结 每一次课设都是对自己综合能力的提高 这次也不例外 数据结构是一门 应用性很高的课程 通过课设 我收获了以下几个方面 1 通过这次课设 我恢复了基础的 C 语言能力编程 并在此基础上 利用 数据结构 能够写出更具有实用性 也具有更复杂功能的程序 很多以前想不 到的功能都通过数据结构巧妙的安排 可以轻松实现 2 通过此次课设 我锻炼了自己独立思考的能力 以前总是不相信自己 能够把一个问题思考的有多深 现在 通过独立的思考 哪怕是一段漫长的时 间得到的是对知识更为深刻的理解 3 通过此次课设 我能够借阅资料 通过更为广泛的寻找来为自己获得启 发 懂得了理论与实际相结合的重要性 只有理论知识是远远不够的 理论知 识是为将来的实践服务的 理论知识很重要 实践活动更重要 4 通过这次设计 我看到自身学习方法存在很多错误 我决心在以后的学 习过程中 要多锻炼自己处理实际问题的能力 要提高独立分析问题和解决问 题的能力 多动手多上机操作 虽然课设时间很短 但收获却是别的方式无法 拥有的 因为它让我把只是运用于实践 把思考当做一种享受 其乐趣是无穷 的 它对我的影响很深远 指导教师评语 指导教师 签字 2013 年 1 月 6 日 课程设计成绩