拓扑排序(算法与数据结构课程设计)

拓扑排序(算法与数据结构课程设计)

ID:16208154

大小:375.00 KB

页数:16页

时间:2018-08-08

拓扑排序(算法与数据结构课程设计)_第1页
拓扑排序(算法与数据结构课程设计)_第2页
拓扑排序(算法与数据结构课程设计)_第3页
拓扑排序(算法与数据结构课程设计)_第4页
拓扑排序(算法与数据结构课程设计)_第5页
资源描述:

《拓扑排序(算法与数据结构课程设计)》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库

1、拓扑排序一、问题描述在AOV网中为了更好地完成工程,必须满足活动之间先后关系,需要将各活动排一个先后次序即为拓扑排序。拓扑排序可以应用于教学计划的安排,根据课程之间的依赖关系,制定课程安排计划。按照用户输入的课程数,课程间的先后关系数目以及课程间两两间的先后关系,程序执行后会给出符合拓扑排序的课程安排计划。二、基本要求1、选择合适的存储结构,建立有向无环图,并输出该图;2、实现拓扑排序算法;3、运用拓扑排序实现对教学计划安排的检验。三、算法思想1、采用邻接表存储结构实现有向图;有向图需通过顶点数、弧数、顶点以及弧等信息建立。2、拓扑排序算法voidTopologicalSort(A

2、LGraphG)中,先输出入度为零的顶点,而后输出新的入度为零的顶点,此操作可利用栈或队列实现。考虑到教学计划安排的实际情况,一般先学基础课(入度为零),再学专业课(入度不为零),与队列先进先出的特点相符,故采用队列实现。3、拓扑排序算法voidTopologicalSort(ALGraphG),大体思想为:1)遍历有向图各顶点的入度,将所有入度为零的顶点入队列;2)队列非空时,输出一个顶点,并对输出的顶点数计数;3)该顶点的所有邻接点入度减一,若减一后入度为零则入队列;4)重复2)、3),直到队列为空,若输出的顶点数与图的顶点数相等则该图可拓扑排序,否则图中有环。4、要对教学计划

3、安排进行检验,因此编写了检测用户输入的课程序列是否是拓扑序列的算法voidTopSortCheck(ALGraphG),大体思想为:1)用户输入待检测的课程序列,将其存入数组;2)检查课程序列下一个元素是否是图中的顶点(课程),是则执行3),否则输出“课程XX不存在”并跳出;3)判断该顶点的入度是否为零,是则执行4),否则输出“入度不为零”并跳出;4)该顶点的所有邻接点入度减一;5)重复2)、3)、4)直到课程序列中所有元素均被遍历,则该序列是拓扑序列,否则不是拓扑序列。wilyes11收集博客(与学习无关):http://blog.sina.com.cn/u/1810231802

4、四、数据结构1、链式队列的存储类型为:typedefintElemType;typedefstructQNode{ElemTypedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;2、图的类型(邻接表存储结构)为:typedefcharVertexType[20];//顶点信息(名称)typedefstructArcNode//链表结点{intvexpos;//该弧所指向的顶点在数组中的位置structArcNode*next;//指向当前起点的下一条

5、弧的指针}ArcNode;typedefstructVNode//头结点{VertexTypename;//顶点信息(名称)intindegree;//顶点入度ArcNode*firstarc;//指向当前顶点的第一条弧的指针}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvexhead;//邻接表头结点数组intvexnum,arcnum;//图的顶点数和弧数}ALGraph;五、模块划分1、链式队列操作1)voidInitQueue(LinkQueue*Q)功能:初始化链式队列参数:*Q待初始化的队列2)intQueueE

6、mpty(LinkQueueQ)功能:判断空队列参数:Q待判断的队列返回值:队列为空返回1;队列非空返回03)voidEnQueue(LinkQueue*Q,ElemTypee)功能:元素入队列参数:*Q待操作的队列;e要入队列的元素4)voidDeQueue(LinkQueue*Q,ElemType*e)wilyes11收集博客(与学习无关):http://blog.sina.com.cn/u/1810231802功能:元素出队列参数:*Q待操作的队列;*e记录出队列元素的变量2、有向图(DAG)邻接表存储结构(ALG)的操作1)intLocateVex(ALGraphG,Ver

7、texTypev)功能:顶点在头结点数组中的定位参数:G待操作的图;v要在图中定位的顶点返回值:顶点存在则返回在头结点数组中的下标;否则返回图的顶点数2)intCreateGraph(ALGraph*G)功能:建立图函数内包含了由用户输入顶点数、弧数、顶点以及弧的操作参数:*G待操作的图返回值:图建立成功返回1;图建立失败返回0错误判断:包含顶点数、弧数是否正确的判断;包含用户输入的弧的顶点是否存在的判断3)voidPrintGraph(ALGraphG)功能:输出有

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。