本科毕业论文---拓扑排序课程设计论文.doc

《本科毕业论文---拓扑排序课程设计论文.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、课程设计成果学院:_计算机工程学院__________班级:XXXX学生姓名:XXXX学号:XXXXX设计地点（单位）_XXX_________________________设计题目:_________拓扑排序______________________________完成日期：2014年12月28日成绩(五级记分制):________________教师签名:_________________________课程设计任务书设计题目：拓扑排序学生姓名XXX课程名称数据结构程序设计专业班级XXX地点XX起止时间2014.12.25-2015.1.9设计内容及要求问题描述：

2、编写函数实现图的拓扑排序。设计参数进度要求两个星期内完成。参考资料[1]李素若,陈万华等编著.数据结构.北京：中国水利水电出版社,2014.7.[2]李素若，琚辉，严永松编著.数据结构习题解答及上机指导.北京：中国水利水电出版社,2014.9.[3]谭浩强.C++面向对象程序设计.北京：清华大学出版社，2006.其它说明1.本表应在每次实施前一周由负责教师填写二份，教研室审批后交学院院备案，一份由负责教师留用。2.若填写内容较多可另纸附后。3.一题多名学生共用的，在设计内容、参数、要求等方面应有所区别。教研室主任：指导教师：2015年1月9日目录1问题描述12基本要求13

3、算法思想14数据结构24.1链式队列的存储类型为24.2图的类型（邻接表存储结构）为25模块划分25.1链式队列操作25.2有向图(DAG)邻接表存储结构(ALG)的操作35.3拓扑排序及拓扑检测算法35.4主函数46测试数据46.1对“建立有向图并输出”的测试46.2对“建立有向图并求一个拓扑排序序列”的测试46.3对“检测用户输入的课程安排”的测试47测试情况57.1对“建立有向图并输出”的测试57.2对“建立有向图并求一个拓扑排序序列”的测试77.3对“检测用户输入的课程安排”的测试88系统开发所用到的技术11参考文献13附录全部代码141问题描述在AOV网中为了更

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

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

6、了检测用户输入的课程序列是否是拓扑序列的算法voidTopSortCheck(ALGraphG)，大体思想为：1)用户输入待检测的课程序列，将其存入数组；2)检查课程序列下一个元素是否是图中的顶点（课程），是则执行3)，否则输出“课程XX不存在”并跳出；3)判断该顶点的入度是否为零，是则执行4)，否则输出“入度不为零”并跳出；4)该顶点的所有邻接点入度减一；5)重复2)、3)、4)直到课程序列中所有元素均被遍历，则该序列是拓扑序列，否则不是拓扑序列。233数据结构4.1链式队列的存储类型为typedefintElemType;typedefstructQNode{Elem

7、Typedata;structQNode*next;}QNode,*QueuePtr;typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;4.2图的类型（邻接表存储结构）为typedefcharVertexType[20];//顶点信息（名称）typedefstructArcNode//链表结点{intvexpos;//该弧所指向的顶点在数组中的位置structArcNode*next;//指向当前起点的下一条弧的指针}ArcNode;typedefstructVNode//