《拓扑排序课程设计.docx》由会员分享，可在线阅读，更多相关《拓扑排序课程设计.docx（18页珍藏版）》请在三一办公上搜索。
1、长沙理工大学数据结构课程设计报告赵思雨学院计算机与通信工程专业网络工程班级网络IlOl班学号*学生姓名赵思雨指导教师乐晓波课程成绩完成日期2013年7月12日课程设计任务书计算机与通信工程学院网络工程专业课程名称数据结构课程设计时间2012-2013学年第2学期19周-20周学生姓名赵思雨指导老师乐晓波题目拓扑排序算法的研究与实现主要内容：研究图的存储结构，研究AoV网（活动在顶点的网，有向网）的存储结构与输入算法，并研究拓扑排序算法的实现方法，在此基础上对该算法进行分析。要求：（1）研究AOV网（活动在顶点的网，有向网）的存储结构与输入算法，并研究拓扑排序算法的实现方法。（2）通过对拓扑排序
2、问题的分析、设计、编码、测试等工作，掌握针对实际应用问题设计数据结构，结合C语言解决实际应用问题的一般方法和过程，初步掌握利用数据结构解决实际应用问题的一般方法。（3）对所设计的算法要求进行认真的分析、测试与调试，所提交的相关程序要能正确运行。（4）按要求认真撰写课程设计报告书。应当提交的文件：（I）课程设计报告书打印稿一份。（2）课程设计相关电子文档一套（含任务书、报告书、可正确执行的程序等）。课程设计成绩评定学院计算机与通信工程专业网络工程班级网络11-01学号*学生姓名赵思雨指导教师乐晓波完成日期2013年7月12日指导教师对学生在课程设计中的评价评分项目中及格不及榭悚程设计中的创造性成
3、果!11!I学生掌握课程内容的程度11111IlI悚程设计完成情况！111111j1I课程设计动手能力!I文字表达111111lI学习态度规范要求I课程设计论文的质量InnnIlI指导教师对课程设计的评定意见综合成绩指导教师签字年月日拓扑排序算法的研究与实现学生姓名：赵思雨指导老师：乐晓波摘要该课程设计研究AOV网。研究图的存储结构，研究AOV网（活动在顶点的网，有向网）的存储结构与输入算法，并研究拓扑排序算法的实现方法，在此基础上对该算法进行分析。通过对拓扑排序问题的分析、设计、编码、测试等工作，掌握针对实际应用问题设计数据结构，结合C语言解决实际应用问题的一般方法和过程，初步掌握利用数据结
4、构解决实际应用问题的一般方法。关键字AOV网；拓扑排序；算法设计；C语言；数据结构1引言课程设计是培养学生综合运用所学知识，发现，提出，分析和解决实际问题，锻炼实践能力的重要环节，是对学生实际工作能力的具体训练和考察过程。数据结构是学习计算机相关专业的非常重要的知识，所谓结构就是组织形式，数据的结构就是数据怎么组织，即怎么描述,怎么在电脑中存储。不同类型的数据，它们的组织形式（数据结构）是不同的，在程序设计中，除了应精心设计算法外，还应精心组织数据（包括原始数据、中间结果、最终结果），使之形成一定的组织形式（数据结构），以便让计算机尽可能高效率地处理。数据结构是计算机科学与工程的基础研究之一，
5、掌握该领域的知识对于我们进一步进行高效率的计算机程序开发非常重要。无论在中国还是在美国，数据结构一直是大学的计算机专业重要的专业基础课。数据结构的课程设计要求学生熟练掌握数据结构的逻辑特性和物理表示，具有分析问题的能力，可以根据问题选择合适的数据结构，运用该数据结构结合相应的算法解决实际问题。1.1 课程设计的目的为了更好的学习数据结构，深刻理解数据结构在解决实际问题中的应用，体会其重要性，熟练掌握线性表、栈和队列、串、数组、树、图等常用的数据结构，熟悉各自的特点和应用场合。同时锻炼自己独立分析理解问题的能力，学会根据不同的问题选择合适的数据结构，然后结合适当的算法解决问题。锻炼自己的设计和编
6、写程序的技巧，进一步调试和测试自己所写的程序,使其功能更加完善，养成较好的编写程序习惯。提高综合运用所学的理论知识和方法独立分析和解决问题的能力1,训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能2。1.2 课程设计的内容本次课程设计要求对于给定的AoV网求出它所有拓扑序列。AOV网（是一个更向无环图（DirectedAcydineGraph,DAG图）。AOV网中，如果顶
7、点Vi表示的活动在和顶点Vj表示的活动之前进行，则称Vi是Vj的前驱顶点，Vj是Vi后继顶点。拓扑排序就是将有向无环图中的各个顶点排成一个序列，使得所有的前去后继关系都得到满足。对于相互之间没有次序关系的顶点，在拓扑排序的序列中可以处在任意的位置。因此，拓扑排序的结果往往是不唯一的。本次课程设计的主要任务就是将给定的一个AOV网输出所有的该种序列4。1.3 课程设计的目标通过对拓扑排序问题的分析、设计、编码、测试等工作，掌握针对实际应用问题设计数据结构，结合C语言解决实际应用问题的一般方法和过程，初步掌握利用数据结构解决实际应用问题的一般方法。2设计内容2.1 问题描述在AOV网中为了更好地完
8、成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。拓扑排序可以应用于教学计划的安排，根据课程之间的依赖关系，制定课程安排计划。按照用户输入的课程数，课程间的先后关系数目以及课程间两两间的先后关系，程序执行后会给出符合拓扑排序的课程安排计划。2.2 思路分析一种拓扑序列的生成一般有一下步骤：(1)、从有向无环图中选择一个没有前驱结点的顶点并加入到结点的序列中；(2)、从有向无环图中删除该顶点以及该顶点为尾的所有的弧；(3)、重复(1)(2)的步骤。在整个拓扑排序的过程中需要频繁的检查顶点的前驱以及作删除顶点和弧的操作，在这里我们用两个全局变量rudumax_vertex_
9、num和ViSitedmax_vertex_num来分别实现这两个操作，如果rudui为零则表示无前驱结点，如果ViSitedi为零则表示没有被访问过。如果每删除一个结点就检查，那样的话时间复杂度将很大(等于遍历所有的顶点一遍)，因此设计一个堆栈，把检测到的入度为零的结点入栈。每次删除顶点只要从栈中取出一个结点即可。但是如果需要实现一个AOV网所有拓扑序列的生成则不止如此。在每找到一个符合要求的结点后入栈，从而实现一种拓扑排序。在一趟拓扑排序结束后，应该进行恢复删除的结点和删除的弧，并标记己经有过的序列，在恢复某几个个结点后进行下一次的拓扑排序。2.3过程演示该部分给出了算法执行的流程，如图2
10、-1所示。图2-1算法流程图3算法分析及详细实现3.1 算法分析首先建立空栈，并从第一个顶点开始进行拓扑排序。将该结点初始化为被访问过,并将图类的结点指针指向该编号的结点的表头数组firstarc域,把该顶点入栈后，将所有的以它为起点的弧都删掉，即将弧的终点的入度都减一。接着判断栈里面的数据个数是否和图顶点的个数一样，如果一样，则说明已经有一次拓扑排序完成，若不一样，则往下进行递归，再将符合条件的顶点入栈，直到一次拓扑排序完成的条件成立。最后将顶点出栈，恢复所有结点的入度，并准备下一趟拓扑排序。3.2 算法中用到的函数声明在该程序中用到了很多函数，具体声明如表3所示。print(ALGraph
11、*T)输出图的邻接表SinsertfStack*Lzintx)入栈SdeIetefStack*L)I出栈ISoutputfStack*L)输出栈中元素topusort(Stack*L,ALGraph*GJnt拓扑排序表3-1算法中用到的函数声明3.3 部分程序编写实现该算法的具体编码如下：voidtopusort(Stack*LzALGraph*Gzinti)拓扑排序1.istNode*P;intj,k;Soutput(L);SinSert(L,i);把顶点Vi加入到栈中P=G-headi.firstarc;visitedi=l;把排序过的点标记while(P)j=P-number;ruduU
12、-；把以Vi为头的终止结点入度减1P=P-next;)if(L-top+l=G-vexnum)判断栈中一种拓扑排序完成Soutput(L);printf();flag+;for(k=0;kvexnum;k+)调用部分if(visitedk=O)&(ruduk=O)/如果Vk在此轮中未被访问过且入度为0topusort(L,Gzk);ViSitedi=0;使Vi恢复为未访问P=G-headi.firstarc;while(P)j=P-number;ruduj+;使Vj的入度恢复,加1P=P-next;)SdeIete(L);4程序的运行环境及运行结果4.1 程序运行的环境一个程序需要一个良好的环
13、境才能运行，该课程设计中的程序运行的硬件、软件环境如下。（1）硬件环境1）学生用微机2）局域网（2）软件环境1） Windows8旗舰版系统2） VS2O1O4. 2运行结果程序的运行结果将从三个方面予以介绍。（1）图的输入输入图，结果如图4-1所示。在这里首先输入顶点数和边数，然后输入没条边的起点终点编号和权值。CKD:VS2010项目VS才卜其、的DebUgVQ才卜扫E序exe欢迎使用AoU网拓扑序列显示程序！ X汪矢邱下国酋骤输入您的AoV网！1、建数您盛薮=5/I奥舍矍鹭值的顺序一次输入边的序列:请输入第1三021请输入第2索边21请输入第3条边：231请输入第4条边;241微软拼音简
14、捷半：图4-1图的输入（2）图邻接表的输出输出图的邻接矩阵。输入图过后按回车键显示图的邻接表，如图4-2所示。EKD:VS2010项目V5才卜抖EDebugV才卜扫E序.exe卜欢迎使用AOU网拓扑序列显示程序！XXXXXXXXXX与之有边的节点（该弧的权值）U2U2U4V31）微软拼音简捷半：图4-2图邻接表的输出(3)拓扑序列的输出CK在显示完拓扑序列后按回车输出该图的所有拓扑排序序列，如图4-3所示。D:VS2010项目V才卜扫E的DebUgvfi寸卜扫E序.exeU0U0U0U0U0UlUlMlUlU2U2U2U3U3U4UOU0U0UlUlUlU2U2U2U4U4U3U4游同: 梨捷
15、 zr Ao圜图4-3拓扑序列的输出5总结5.1课程设计总结课程设计可以检验学生对知识的掌握程度。同时更反映了一个学生对课程设计的态度，对待任何事都要认真，可以不会，可以做的不是最好的，但是一定要尽自己最大的努力去完成一件哪怕再小的事。在这次课程设计中学到了很多新的知识,同时也巩固了之前学过知识。对静态链表有了更深的理解，对哈夫曼树及哈夫曼编码更是印象深刻。虽然，最后根据要求完成了任务，但期间还是出现了种种的问题，比如在编写完函数时，运行结果总是不对，调试了好多遍，也没有发现错误，没有想到是选择函数除了差错，一个简单的函数，怎么也没有想到会是这里出了错，是因为我给si,s2变量赋初值时出了错误
16、。同时，为了更好的完成任务还查阅了好多资料，不懂的就到处搜索，去图书馆借相应的书籍来看，锻炼了自己查阅资料的能力。5. 2心得与体会我觉得本此课程设计最大的收获就是学会按部就班的完成任务。首先想好用什么数据结构，主要的思想要明确的认定。然后选一个简单的例子，按照你选定的思想，一步一步的走程序，才能更早的发现程序还存在那些没有考虑到的缺陷。特别忌讳的是到写程序的时候，对主要思想和数据结构还不是很确定。最后在调试程序的阶段，这次我开始用设置断点的方法，一步一步看是否达到你要的理想结果，从而来找出程序中出错的地方。还有，一种方法也是用一个输出语句，分别放在程序的不同位置，通过输出结果，也可以快速判断
17、出程序不能运行的是那一个语句了。从而方便你修改，快速得到正确的结果。还有，这次调试的过程中，我表现的比以前要更有耐心，这也是一个很好的收获。还有一个更重要的体会就是，遇到不会的地方，我开始习惯到图书馆或是网上去找资料。这是一个很好的学习过程，它不仅仅是可以解决这个问题，关键是你会从找资料学习的过程中，会学好很多很多意想不到的知识。可能会比你手头上要学习的知识多得多。参考文献严蔚敏，吴伟民.数据结构（C语言版）M.北京:清华大学出版社,2012.5李春葆，尹为民.数据结构教程上机指导M.北京:清华大学出版社,20083AndrewBinstock,JohnRex.程序员实用算法（第二版乂M.北京
18、:机械工业出版社,2009.064ThomasH.Cormen,CharlesE.LeisersonzRonaIdL.RiverstzClffordSteinJntroductiontoAlogrithmsSecondEditionM.US:MachinePress,2012附件程序清单#includestdio.h#includemalloc.h#includestdlib.hndefinemax_vertex_numIoO顶点的最大个数typedefstructnode邻接表中的结点类型intnumber;结点编号structnode*next;指向下一个结点intinfo;与表头结点边的
19、信息、JListNode;typedefStrUCt定义表头结点数组intnumber;顶点信息1.istNode*firstarc;指向第一个邻接点AdjList;表头结点类型typedefstruct邻接表类型AdjUstheadmax_vertex_num;邻接表的组intvexnum;顶点个数表头数intedgnum;边的个数ALGraph;typedefstructintdatamax_vertex_num;堆栈数组inttop;栈顶标志Stack;顺序表类型intrudumax_vertex_num;定义一个存储每个顶点入度的全局数组intViSitedmax_vertex_num
20、;定义全局数组标志拓扑排序过程中是否访问过intflag=。;接受拓扑排序的次数，若为0,则该图不是AOV网ALGraph*CreateeAdjListGraph()ALGraph*T;ListNode*p;定义指向结点的指针intizj;输入边是的起点和终点T=(ALGraph*)malloc(sizeof(ALGraph);定义图Printf(1、请输入顶点数58中(“十,&*6*11111)；输入顶点个数for(i=0;ivexnum;i+)初始化表头结点数组T-headi.number=i;初始化结点编号rudui=O;将每个节点的荼毒初始化为visitedi=O;T-headi.fi
21、rstarC=NULL;将表头结点数组的每个结点的指针域置空)Printf(U2、请输入边数巧;SCanf(%cT,&T-edgnum);输入边的个数printf(3按起点终点权值的顺序一次输入边的序列:n“)；for(i=0;iedgnum;i+)Printf(请输入第%d条边:，i+l);p=(ListNode*)malloc(sizeof(ListNode);SCanfd%d，&j);输入这条边起始节点的编号SCanf(”d”,&p-number);输入这条边的终点的编号SCanfd%d”,&p-info);输入这条边的权值printf(n);rudup-number+;将插入边中结点的
22、入度加1p-next=T-headj.firstarc;T-headj.firstarc=p;将该结点插入到单链表中创建条边returnT;voidprint(ALGraph*T)输出图的邻接表1.istNode*p;inti;Printf(表头数组(该结点的入度)与之有边的节点(该弧的权值)n);for(j=0;ivexnum;i+)printf(V%d(%d)zT-headi.numberzrudui);p=T-headi.firstarc;while(p)printf(V%d(%d)zp-number,p-info);p=p-next;)printf(n);)Stack*Setnull(
23、)置栈空Stack*L;1.=(Stack*)malloc(sizeof(Stack);1.-top=-l;return(L);)voidSinsert(Stack*L,intx)入栈1.-top=L-top+l;1.-dataL-top=x;voidSdeIetefStack*。出栈1.-top=L-top-l;)voidSOUtPUt(StaCk*D输出栈中元素inti;for(i=0;itop+l;i+)printf(V%d,L-datai);printf(n);)voidtopusort(Stack*L,ALGraph*G,inti)拓扑排序1.istNode*P;intj,k;SOU
24、tPUt(L);SinSert(L,i);把顶点Vi加入到顺序表中P=G-headi.firstarc;ViSited把排序过的点标记while(P)j=P-number;ruduj-;把以Vi为头的终止结点入度减1P=P-next;)if(L-top+l=G-vexnum)/判断顺序表中一种拓扑排序完成Soutput(L);printf();flag+;for(k=0;kvexnum;k+)调用部分if(visitedk=O)&(ruduk=O)/如果Vk在此轮中未被访问过且入度为Otopusort(L,G,k);ViSitedi=0;使Vi恢复为未访问P=G-headi.firstarc;
25、while(P)j=P-number;ruduj+;使Vj的入度恢复,加1P=P-next;)SdeIete(L);)voidcaidan()printf(tnn);printf(t00n);printf(t0n);printf(t*欢迎使用AOV网拓扑序列显示程序！*0n);printf(t0n);printf(t0n);printf(tn);)voidcaidanl()printf(nnnnn);printf(tnn);printf(t00n);printf(t0n);printf(t000S谢谢使用！能睡10n);printf(t0n);printf(t00n);printf(tn);)
26、voidmain()inti;ALGraph*G;Stack*L;intn=l;1.=Setnull();While(n=l)循环显示拓扑排序system(,cls);caidan();Printf(,注意：请按下列步骤输入您的AOV网！n);G=create_AdjListGraph();system(cls);caidan();Printf(该图的邻接表为：n);print(G);system(,pause);system(cls);caidan();Printf(,以下是该图所有的拓扑序列:n);for(i=0;ivexnum;i+)if(rudui=O&visitedi=O)topusort(L,G,i);if(flag0)Printf(该AOV图有d种拓扑排序n,fag);fag=O;)elseprintf(nnt出错!nn此图不是AOV网，无拓扑排序序列.nnn);system(,pause);system(cls);caidan();PrirItf(,按1继续显示下一个图的拓扑序列，按0结束程序！n);scanf(%dn);system(cls);if(n=O)caidanl();)
