拓扑排序课程设计

长沙理工大学《数据结构》课程设计报告赵思雨学院计算机与通信工程专业网络工程班级网络1101班学号201158080110学生姓名赵思雨指导教师乐晓波课程成绩完成日期2013年7月12日赵思雨《拓扑排序算法的研究与实现》第1页共23页课程设计任务书计算机与通信工程学院网络工程专业课程名称数据结构课程设计时间2012-2013学年第2学期19周--20周学生姓名赵思雨指导老师乐晓波题目拓扑排序算法的研究与实现主要内容：研究图的存储结构，研究AOV网（活动在顶点的网，有向网）的存储结构与输入算法，并研究拓扑排序算法的实现方法，在此基础上对该算法进行分析。要求：（1）研究AOV网（活动在顶点的网，有向网）的存储结构与输入算法，并研究拓扑排序算法的实现方法。（2）通过对拓扑排序问题的分析、设计、编码、测试等工作，掌握针对实际应用问题设计数据结构，结合C语言解决实际应用问题的一般方法和过程，初步掌握利用数据结构解决实际应用问题的一般方法。（3）对所设计的算法要求进行认真的分析、测试与调试，所提交的相关程序要能正确运行。（4）按要求认真撰写课程设计报告书。应当提交的文件：（1）课程设计报告书打印稿一份。（2）课程设计相关电子文档一套（含任务书、报告书、可正确执行的程序等）。赵思雨《拓扑排序算法的研究与实现》第2页共23页课程设计成绩评定学院计算机与通信工程专业网络工程班级网络11-01学号201158080110学生姓名赵思雨指导教师乐晓波完成日期2013年7月12日指导教师对学生在课程设计中的评价评分项目优良中及格不及格课程设计中的创造性成果学生掌握课程内容的程度课程设计完成情况课程设计动手能力文字表达学习态度规范要求课程设计论文的质量指导教师对课程设计的评定意见综合成绩指导教师签字年月日赵思雨《拓扑排序算法的研究与实现》第3页共23页拓扑排序算法的研究与实现学生姓名：赵思雨指导老师：乐晓波摘要该课程设计研究AOV网。研究图的存储结构，研究AOV网（活动在顶点的网，有向网）的存储结构与输入算法，并研究拓扑排序算法的实现方法，在此基础上对该算法进行分析。通过对拓扑排序问题的分析、设计、编码、测试等工作，掌握针对实际应用问题设计数据结构，结合C语言解决实际应用问题的一般方法和过程，初步掌握利用数据结构解决实际应用问题的一般方法。关键字AOV网；拓扑排序；算法设计；C语言；数据结构赵思雨《拓扑排序算法的研究与实现》第4页共23页目录摘要..................................................................31引言................................................................51.1课程设计的目的...............................................51.2课程设计的内容...............................................61.3课程设计的目标...............................................62设计内容............................................................72.1问题描述.....................................................72.2思路分析.....................................................72.3过程演示.....................................................83算法分析及详细实现..................................................93.1算法分析.....................................................93.2算法中用到的函数声明.........................................93.3部分程序编写.................................................94程序的运行环境及运行结果...........................................114.1程序运行的环境..............................................114.2运行结果....................................................115总结...............................................................145.1课程设计总结................................................145.2心得与体会..................................................14参考文献.............................................................15附件.................................................................16赵思雨《拓扑排序算法的研究与实现》第5页共23页1引言课程设计是培养学生综合运用所学知识，发现，提出，分析和解决实际问题，锻炼实践能力的重要环节，是对学生实际工作能力的具体训练和考察过程。数据结构是学习计算机相关专业的非常重要的知识，所谓结构就是组织形式，数据的结构就是数据怎么组织，即怎么描述，怎么在电脑中存储。不同类型的数据，它们的组织形式（数据结构）是不同的，在程序设计中，除了应精心设计算法外，还应精心组织数据（包括原始数据、中间结果、最终结果），使之形成一定的组织形式（数据结构），以便让计算机尽可能高效率地处理。《数据结构》是计算机科学与工程的基础研究之一，掌握该领域的知识对于我们进一步进行高效率的计算机程序开发非常重要。无论在中国还是在美国，《数据结构》一直是大学的计算机专业重要的专业基础课。数据结构的课程设计要求学生熟练掌握数据结构的逻辑特性和物理表示，具有分析问题的能力，可以根据问题选择合适的数据结构，运用该数据结构结合相应的算法解决实际问题。1.1课程设计的目的为了更好的学习数据结构，深刻理解数据结构在解决实际问题中的应用，体会其重要性，熟练掌握线性表、栈和队列、串、数组、树、图等常用的数据结构，熟悉各自的特点和应用场合。同时锻炼自己独立分析理解问题的能力，学会根据不同的问题选择合适的数据结构，然后结合适当的算法解决问题。锻炼自己的设计和编写程序的技巧，进一步调试和测试自己所写的程序，使其功能更加完善，养成较好的编写程序习惯。提高综合运用所学的理论知识和方法独立分析和解决问题的能力[1]，训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对赵思雨《拓扑排序算法的研究与实现》第6页共23页象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能[2]。1.2课程设计的内容本次课程设计要求对于给定的AOV网求出它所有拓扑序列。AOV网（是一个有向无环图（DirectedAcyclineGraph，DAG图）[3]。AOV网中，如果顶点Vi表示的活动在和顶点Vj表示的活动之前进行，则称Vi是Vj的前驱顶点，Vj是Vi后继顶点。拓扑排序就是将有向无环图中的各个顶点排成一个序列，使得所有的前去后继关系都得到满足。对于相互之间没有次序关系的顶点，在拓扑排序的序列中可以处在任意的位置。因此，拓扑排序的结果往往是不唯一的。本次课程设计的主要任务就是将给定的一个AOV网输出所有的该种序列[4]。1.3课程设计的目标通过对拓扑排序问题的分析、设计、编码、测试等工作，掌握针对实际应用问题设计数据结构，结合C语言解决实际应用问题的一般方法和过程，初步掌握利用数据结构解决实际应用问题的一般方法。赵思雨《拓扑排序算法的研究与实现》第7页共23页2设计内容2.1问题描述在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。拓扑排序可以应用于教学计划的安排，根据课程之间的依赖关系，制定课程安排计划。按照用户输入的课程数，课程间的先后关系数目以及课程间两两间的先后关系，程序执行后会给出符合拓扑排序的课程安排计划。2.2思路分析一种拓扑序列的生成一般有一下步骤：（1）、从有向无环图中选择一个没有前驱结点的顶点并加入到结点的序列中；（2）、从有向无环图中删除该顶点以及该顶点为尾的所有的弧；（3）、重复（1）（2）的步骤。在整个拓扑排序的过程中需要频繁的检查顶点的前驱以及作删除顶点和弧的操作，在这里我们用两个全局变量rudu[max_vertex_num]和visited[max_vertex_num]来分别实现这两个操作，如果rudu[i]为零则表示无前驱结点，如果visited[i]为零则表示没有被访问过。如果每删除一个结点就检查，那样的话时间复杂度将很大（等于遍历所有的顶点一遍），因此设计一个堆栈，把检测到的入度为零的结点入栈。每次删除顶点只要从栈中取出一个结点即可。但是如果需要实现一个AOV网所有拓扑序列的生成则不止如此。在每找到一个符合要求的结点后入栈，从而实现一种拓扑排序。在一趟拓扑排序结束后，应该进行恢复删除的结点和删除的弧，并标记已经有过的序列，在恢复某几个个结点后进行下一次的拓扑排序。赵思雨《拓扑排序算法的研究与实现》第8页共23页2.3过程演示该部分给出了算法执行的流程，如图2-1所示。图2-1算法流程图赵思雨《拓扑排序算法的研究与实现》第9页共23页3算法分析及详细实现3.1算法分析首先建立空栈，并从第一个顶点开始进行拓扑排序。将该结点初始化为被访问过，并将图类的结点指针指向该编号的结点的表头数组firstarc域，把该顶点入栈后，将所有的以它为起点的弧都删掉，即将弧的终点的入度都减一。接着判断栈里面的数据个数是否和图顶点的个数一样，如果一样，则说明已经有一次拓扑排序完成，若不一样，则往下进行递归，再将符合条件的顶点入栈，直到一次拓扑排序完成的条件成立。最后将顶点出栈，恢复所有结点的入度，并准备下一趟拓扑排序。3.2算法中用到的函数声明在该程序中用到了很多函数，具体声明如表3-1所示。print(ALGraph*T)输出图的邻接表Sinsert(Stack*L,intx)入栈Sdelete(Stack*L)出栈Soutput(Stack*L)输出栈中元素topusort(Stack*L,ALGraph*G,int拓扑排序表3-1算法中用到的函数声明3.3部分程序编写赵思雨《拓扑排序算法的研究与实现》第10页共23页实现该算法的具体编码如下：voidtopusort(Stack*L,ALGraph*G,inti){//拓扑排序ListNode*P;intj,k;Soutput(L);Sinsert(L,i);//把顶点Vi加入到栈中P=G-head[i].firstarc;visited[i]=1;//把排序过的点标记while(P){j=P-number;rudu[j]--;//把以Vi为头的终止结点入度减1P=P-next;}if(L-top+1==G-vexnum){//判断栈中一种拓扑排序完成Soutput(L);printf(\n);flag++;}for(k=0;kG-vexnum;k++)//调用部分if((visited[k]==