没有合适的资源?快使用搜索试试~ 我知道了~
数据结构课程设计报告——拓扑排序.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 106 浏览量
2021-10-06
08:09:35
上传
评论
收藏 116KB DOC 举报
温馨提示
试读
24页
数据结构课程设计报告——拓扑排序.doc
资源推荐
资源详情
资源评论
- .
课程设计任务书
学生:专业班级:
指导教师:工作单位:计算机科学系
题目: 拓扑排序
初始条件:
〔〕采用邻接表作为有向图的存储构造;
〔〕给出所有可能的拓扑序列。
〔〕测试用例见严蔚敏数据构造习题集 语言版 题 图
要求完成的主要任务:〔包括课程设计工作量及其技术要求,以及说明书撰写等具体要
求〕
课程设计报告按学校规定格式用 纸打印〔书写〕,并应包含如下容:
问题描述
简述题目要解决的问题是什么。
设计
存储构造设计、主要算法设计〔用类 语言或用框图描述〕、测试用例设计;
调试报告
调试过程中遇到的问题是如何解决的;对设计和编码的讨论和分析。
经历和体会〔包括对算法改良的设想〕
附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据,那么运行结果要包
含这些测试数据和运行输出。
说明:
设计报告、程序不得相互抄袭和拷贝;假设有雷同,那么所有雷同者成绩均为 分。
凡拷贝往年任务书或课程设计充数者,成绩一律无效,以 0 分记。
时间安排:
.第 周完成,验收时间由指导教师指定
.验收地点:实验中心
.验收容:可执行程序与源代码、课程设计报告书。
指导教师签名: 2013 年 6 月 14 日
. -可修遍-
- -
系主任〔或责任教师〕签名:年月日
拓扑排序
目录
1 问题描述
2 具体设计
2.1 存储构造设计
2.2 主要算法设计
2.2.1 拓扑排序的算法总体设计
2.2.2 将有向图表示为邻接表
2.2.3 拓扑排序函数的设计
2.2.4 顺序表的运算设计
2.3 测试用例设计
3 调试报告
3.1 设计和编码的分析
3.2 调试过程问题及解决
4 经历与体会
5 用户使用说明
- - word.zl-
- -
6 参考文献
7 附录源代码与运行结果
1 问题描述
题目:拓扑排序
如果用有向图表示一个工程,在这种有向图中,用顶点表示活动,用有向边
表示活动 必须先于活动 进展,这种有向图叫做顶点表示活动的网络,
记作 网络。
对一个有向无环图 进展拓扑排序,是将 中所有顶点排成一个线性序列,使
得 网络中的所有应存在前驱和后继的关系都能得到满足,这种构造 网络全
部顶点的拓扑有序序列的运算叫做拓扑排序。
在 网中,不应该出现有向环,用拓扑排序就可以判断网中是否有环,假设
网中所有顶点都在它的拓扑有序序列中,那么该 网必定不存在环。
进展拓扑排序步骤如下:
、输入 网络即有向图。令 为顶点个数。
、从有向图上选择一个没有入度的节点并输出。
、从网中删去该点,同时删去从该顶点发出的全部有向边。
、重复上述 ,,直到
〔〕、全部顶点均已输出,拓扑有序序列形成,拓扑排序完成。
〔〕、图中还有未输出的顶点,但已跳出处理循环。这说明图中还剩下一些顶
点,它们都有直接前驱,再也找不到没有前驱的顶点了,这时 网络中必定存在
有向环。
要求:
〔〕、采用邻接表作为有向图的存储构造;
〔〕、给出所有可能的拓扑序列。
2 具体设计
2.1 存储构造设计
- - word.zl-
- -
本问题中,我将采用三种数据构造:邻接表,顺序表和数组。
邻接表:邻接表是图的链式存储构造,在邻接表的存储构造中,图中的每个
顶点对应一个单链表。从拓扑排序的步骤个方法来看,在整个排序过程中需要频繁地
检查顶点的前驱以及作删除顶点和边的操作、恢复顶点和顶点前驱入度的操作。所以,
可以采用邻接表作为有向无环图的存储构造。
为了快速的判断顶点是否有前驱,可以在表头结点中增加一个“入度域〔 〕〞
用来指示顶点当前的入度。当 域的值为 时,说明该顶点没有前驱,可以参加到
结果序列中。而删除顶点及以它为起点的边操作时,可以通过把该顶点的所有邻接点
的入度域减一来完成,恢复那么入度域加一。
邻接表的定义如下:
!"#"$%&'()*+,表结点
-#"./邻接点的位置
)*+0".-&(/指向下一个结点
1)*+/邻接表中的结点类型
!"#"$%&'(+23*+,头结点
".#--/顶点信息
/每个顶点的入度
)*+04&%-&(/指向第一个邻接结点
1+23*+#5%6728/邻接表的表头结点类型
!"#"$%&'(,
#5%".%/表头结点数组
".'9-&'9/顶点数、边数
15&-:/邻接表类型
顺序表:在整个拓扑排序的过程中,把满足条件〔在 此轮中未访问过
%"#68; 以及入度为 〕的顶点参加到顺序表的末尾,使 <-% 加 。当一轮排序
完毕后,输出顺序表中的排序。接着,是恢复局部,每恢复一步,都要把 %68置
并且相应的入度加 ,把这个顶点从顺序表中删除,重新参加到图中,进展下一轮的
拓扑排序。
- - word.zl-
- -
邻接表的顺序表定义如下:
!"#"$%&'(,
+23*+#--6728/
<-%/
1=">'"<%/顺序表类型
数组:产生所有的拓扑排序是一个递归〔回溯〕过程。其中,定义的
%"#6728数组是一个辅助变量,数组元素的初值为 ,当第 个顶点被访问后,
便置 %"#68为 记录该顶点是否被访问过。
%"#6728;
2.2 主要算法设计
2.2.1 拓扑排序的算法总体设计
因为这个课程设计题目是让 网络产生所有的拓扑排序,所以我想必然要用到递
归或者回溯的思想。
考虑到要不断的对数据进展删除,恢复,所以考虑了顺序表,单链表,堆栈,发现用
顺序表删除和插入都很简单,好实施,只要在表尾插入或是删除即可。
在整个过程中主要用到三局部:一、从图中删除,添加到顺序表中;二、递归;
三、把删除的顶点和边恢复到图中并从顺序表中删除。
首先,在整个图中搜索即没有被访问过而且入度为 的顶点 ,进展拓扑排序。
在拓扑排序的函数里,首先将这个顶点参加到顺序表中,然后将这个顶点标志为被访
问过,即 %"#68;。把以这个顶点为起点的邻接点的入度均减
然后,判断顺序表的表长是否等于图的顶点数。如果不相等的话,那么继续判断
图中是否还存在满足拓扑排序条件的顶点,假设存在就再次调用拓扑排序函数。
接下来,就是使刚排序过的顶点 的标志恢复到原始状态 ,每个以 为起点
的邻接点的入度加 ,恢复到原来的状态。把顶点 从顺序表中删除。
如果,顺序表的表长等于图的顶点数,那么就输出这一种拓扑排序序列。计数器
( ' 加 之后,就是采用递归,不断的调用拓扑排序函数,不断的恢复、删除,直
到排出所有的拓扑序列。
最后,如果 ( ' 大于 的话,那么就输出有 ( ' 种拓扑排序。否那么,输
- - word.zl-
剩余23页未读,继续阅读
资源评论
gjmm89
- 粉丝: 13
- 资源: 19万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功