没有合适的资源?快使用搜索试试~ 我知道了~
首页数据结构课设拓扑排序源代码(教学计划安排)
资源详情
资源推荐
拓扑排序
一、问题描述
在 网中为了更好地完成工程,必须满足活动之间先后关系,需要将各活动排一个
先后次序即为拓扑排序。拓扑排序可以应用于教学计划的安排,根据课程之间的依赖关系
制定课程安排计划。按照用户输入的课程数,课程间的先后关系数目以及课程间两两间的
先后关系,程序执行后会给出符合拓扑排序的课程安排计划。
二、基本要求
、选择合适的存储结构,建立有向无环图,并输出该图;
、实现拓扑排序算法;
、运用拓扑排序实现对教学计划安排的检验。
三、算法思想
、采用邻接表存储结构实现有向图;有向图需通过顶点数、弧数、顶点以及弧等信息
建立。
、拓扑排序算法 中,先输出入度为零的顶点,
而后输出新的入度为零的顶点,此操作可利用栈或队列实现。考虑到教学计划安排的实际
情况,一般先学基础课(入度为零),再学专业课(入度不为零),与队列先进先出的特
点相符,故采用队列实现。
、拓扑排序算法 ,大体思想为:
遍历有向图各顶点的入度,将所有入度为零的顶点入队列;
队列非空时,输出一个顶点,并对输出的顶点数计数;
该顶点的所有邻接点入度减一,若减一后入度为零则入队列;
重复 、,直到队列为空,若输出的顶点数与图的顶点数相等则该图可拓扑排序,
否则图中有环。
、要对教学计划安排进行检验,因此编写了检测用户输入的课程序列是否是拓扑序列
的算法 ,大体思想为:
用户输入待检测的课程序列,将其存入数组;
检查课程序列下一个元素是否是图中的顶点(课程),是则执行 ,否则输出“课程
不存在”并跳出;
判断该顶点的入度是否为零,是则执行 ,否则输出“入度不为零”并跳出;
该顶点的所有邻接点入度减一;
重复 、、直到课程序列中所有元素均被遍历,则该序列是拓扑序列,否则不
是拓扑序列。
wilyes11 收集 博客(与学习无关):http://blog.sina.com.cn/u/1810231802
四、数据结构
、链式队列的存储类型为:
!"#$ %
!&'()
* #$ %
&'()+",%
- ().+(''/%
!&'
* (''/!"%
(''/%
- "(''%
、图的类型(邻接表存储结构)为:
!, 012%33顶点信息(名称)
!&')33链表结点
* ",&%33该弧所指向的顶点在数组中的位置
&')+",%33指向当前起点的下一条弧的指针
- )%
!&')33头结点
* , "$%33顶点信息(名称)
""%33顶点入度
)+4&%33指向当前顶点的第一条弧的指针
- ).5&067#8#7)962%
!&'
* 5&,%33邻接表头结点数组
","'$."'$%33图的顶点数和弧数
- %
五、模块划分
1、链式队列操作
:"(''"(''+(
功能:初始化链式队列
参数:+(待初始化的队列
"(''#$ "(''(
功能:判断空队列
参数:(待判断的队列
返回值:队列为空返回 ;队列非空返回 1
#"(''"(''+(.#$
功能:元素入队列
参数:+(待操作的队列;要入队列的元素
wilyes11 收集 博客(与学习无关):http://blog.sina.com.cn/u/1810231802
;(''"(''+(.#$ +
功能:元素出队列
参数:+(待操作的队列;+记录出队列元素的变量
2、有向图(DAG)邻接表存储结构(ALG)的操作
",.,
功能:顶点在头结点数组中的定位
参数:待操作的图;要在图中定位的顶点
返回值:顶点存在则返回在头结点数组中的下标;否则返回图的顶点数
"+
功能:建立图
函数内包含了由用户输入顶点数、弧数、顶点以及弧的操作
参数:+待操作的图
返回值:图建立成功返回 ;图建立失败返回 1
错误判断:包含顶点数、弧数是否正确的判断;
包含用户输入的弧的顶点是否存在的判断
/"
功能:输出有向图
参数:待输出的图
"+
功能:建立预置课程图(输出函数内预置课程信息,并自动建立有向图)
参数:+待操作的图
返回值:图建立成功返回 ;图建立失败返回 1
错误判断:包含顶点数、弧数是否正确的判断
包含弧的顶点是否存在的判断
/"
功能:输出预置课程图
参数:待输出的图
3、拓扑排序及拓扑检测算法
功能:实现拓扑排序
参数:待进行拓扑排序的图
错误判断:包含有向图是否有环的判断
功能:运用拓扑排序的思想检测教学计划
函数内包含了由用户输入待检测的课程序列的操作
参数:待操作的图
wilyes11 收集 博客(与学习无关):http://blog.sina.com.cn/u/1810231802
错误判断:包含用户输入的课程是否存在的判断
包含不是拓扑序列的原因(该课程有多少个先决课程未学)
4、主函数
$"
功能:主函数
利用 < 语句和 &< 语句实现菜单化调用函数
六、源程序
="'>&?@>
="'>&@>
="'>&"@>
3+++++++++++++++++++++++++++++++++++++++++++3
3+以下为链式队列操作 +3
3+++++++++++++++++++++++++++++++++++++++++++3
3+定义链式队列类型 +3
!"#$ %
!&'()
* #$ %
&'()+",%
- ().+(''/%
!&'
* (''/!"%
(''/%
- "(''%
3+@初始化链式队列 +3
:"(''"(''+(
* (AB!"C(ABC(''/$&D!()%
!E(AB!",1%
(AB!"AB",C)9%-
3+@判断空队列 +3
"(''#$ "(''(
* !(@!"CC(@
'"%
&
'"1%-
3+@入队列 +3
#"(''"(''+(.#$
* (''/%
C(''/$&D!()%
wilyes11 收集 博客(与学习无关):http://blog.sina.com.cn/u/1810231802
剩余15页未读,继续阅读
idlesys
- 粉丝: 0
- 资源: 3
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功