数据结构课程设计报告拓扑排序.docx

1、数据结构课程设计报告拓扑排序课程设计任务书学生：专业班级：指导教师：工作单位：计算机科学系题目: 拓扑排序初始条件：1采用邻接表作为有向图的存储构造；2给出所有可能的拓扑序列。3测试用例见严蔚敏?数据构造习题集(C语言版)?p48题7.9图要求完成的主要任务:包括课程设计工作量及其技术要求，以及说明书撰写等具体要求课程设计报告按学校规定格式用A4纸打印书写，并应包含如下容：1. 问题描述简述题目要解决的问题是什么。2. 设计存储构造设计、主要算法设计用类C/C+语言或用框图描述、测试用例设计；3. 调试报告调试过程中遇到的问题是如何解决的；对设计和编码的讨论和分析。4. 经历和体会包括对算法改

2、良的设想5. 附源程序清单和运行结果。源程序要加注释。如果题目规定了测试数据，那么运行结果要包含这些测试数据和运行输出。说明：1. 设计报告、程序不得相互抄袭和拷贝；假设有雷同，那么所有雷同者成绩均为0分。2. 凡拷贝往年任务书或课程设计充数者，成绩一律无效，以0分记。时间安排：1第17周完成，验收时间由指导教师指定2验收地点：实验中心3验收容：可执行程序与源代码、课程设计报告书。指导教师签名： 2013年6月14日系主任或责任教师签名：年月日拓扑排序1问题描述2具体设计2.1存储构造设计2.2主要算法设计 2.2.1拓扑排序的算法总体设计2.2.2将有向图表示为邻接表2.2.3拓扑排序函数的

3、设计2.2.4顺序表的运算设计2.3测试用例设计3调试报告3.1设计和编码的分析3.2调试过程问题及解决4经历与体会5用户使用说明6参考文献7附录源代码与运行结果1问题描述题目：拓扑排序如果用有向图表示一个工程，在这种有向图中，用顶点表示活动，用有向边表示活动vi必须先于活动vj进展，这种有向图叫做顶点表示活动的网络，记作AOV网络。对一个有向无环图G进展拓扑排序，是将G中所有顶点排成一个线性序列，使得AOV网络中的所有应存在前驱和后继的关系都能得到满足，这种构造AOV网络全部顶点的拓扑有序序列的运算叫做拓扑排序。在AOV-网中，不应该出现有向环，用拓扑排序就可以判断网中是否有环，假设网中所有

4、顶点都在它的拓扑有序序列中，那么该AOV-网必定不存在环。进展拓扑排序步骤如下：1、输入AOV网络即有向图。令n为顶点个数。2、从有向图上选择一个没有入度的节点并输出。3、从网中删去该点，同时删去从该顶点发出的全部有向边。4、重复上述2，3，直到1、全部顶点均已输出，拓扑有序序列形成，拓扑排序完成。2、图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了，这时AOV网络中必定存在有向环。要求：1、采用邻接表作为有向图的存储构造；2、给出所有可能的拓扑序列。2具体设计2.1存储构造设计本问题中，我将采用三种数据构造：邻接表，顺序表和数组。

5、邻接表：邻接表是图的链式存储构造，在邻接表的存储构造中，图中的每个顶点对应一个单链表。从拓扑排序的步骤个方法来看，在整个排序过程中需要频繁地检查顶点的前驱以及作删除顶点和边的操作、恢复顶点和顶点前驱入度的操作。所以，可以采用邻接表作为有向无环图的存储构造。为了快速的判断顶点是否有前驱，可以在表头结点中增加一个“入度域into用来指示顶点当前的入度。当into域的值为0时，说明该顶点没有前驱，可以参加到结果序列中。而删除顶点及以它为起点的边操作时，可以通过把该顶点的所有邻接点的入度域减一来完成，恢复那么入度域加一。邻接表的定义如下：typedef struct ARODE /表结点int adj

6、vex; /邻接点的位置ARODE *nextarc;/指向下一个结点ARODE; /邻接表中的结点类型typedef struct VEXNODE /头结点int vexdata; /顶点信息int into; /每个顶点的入度ARODE *firstarc; /指向第一个邻接结点VEXNODE,AdjListMAX;/邻接表的表头结点类型typedef structAdjList vexs; /表头结点数组int vexnum,arum;/顶点数、边数ALGraph; /邻接表类型顺序表：在整个拓扑排序的过程中，把满足条件在此轮中未访问过visitedi=0以及入度为0的顶点参加到顺序表的

7、末尾，使last加1。当一轮排序完毕后，输出顺序表中的排序。接着，是恢复局部，每恢复一步，都要把visiti置0并且相应的入度加1，把这个顶点从顺序表中删除，重新参加到图中，进展下一轮的拓扑排序。邻接表的顺序表定义如下：typedef struct VEXNODE dataMAX;int last;Sequenlist; /顺序表类型数组：产生所有的拓扑排序是一个递归回溯过程。其中，定义的visitedMAX数组是一个辅助变量，数组元素的初值为0，当第i个顶点被访问后，便置visitedi为1.记录该顶点是否被访问过。VisitedMAX；2.2主要算法设计2.2.1拓扑排序的算法总体设计因为

8、这个课程设计题目是让AOV网络产生所有的拓扑排序，所以我想必然要用到递归或者回溯的思想。考虑到要不断的对数据进展删除，恢复，所以考虑了顺序表，单链表，堆栈，发现用顺序表删除和插入都很简单，好实施，只要在表尾插入或是删除即可。在整个过程中主要用到三局部：一、从图中删除，添加到顺序表中；二、递归；三、把删除的顶点和边恢复到图中并从顺序表中删除。首先，在整个图中搜索即没有被访问过而且入度为0 的顶点Vi，进展拓扑排序。在拓扑排序的函数里，首先将这个顶点参加到顺序表中，然后将这个顶点标志为被访问过，即Visitedi=1。把以这个顶点为起点的邻接点的入度均减1.然后，判断顺序表的表长是否等于图的顶点数

9、。如果不相等的话，那么继续判断图中是否还存在满足拓扑排序条件的顶点，假设存在就再次调用拓扑排序函数。接下来，就是使刚排序过的顶点Vi的标志恢复到原始状态0，每个以Vi为起点的邻接点的入度加1，恢复到原来的状态。把顶点Vi从顺序表中删除。如果，顺序表的表长等于图的顶点数，那么就输出这一种拓扑排序序列。计数器count加1之后，就是采用递归，不断的调用拓扑排序函数，不断的恢复、删除，直到排出所有的拓扑序列。最后，如果count大于0的话，那么就输出有count种拓扑排序。否那么，输出此图不是AOV网，无拓扑排序序列产生。2.2.2将有向图表示为邻接表在产生拓扑排序的算法设计中，首先要将有向图用邻接

10、表表示，主要流程如下：2.2.3拓扑排序函数的设计2.2.4顺序表的运算设计2.3测试用例设计图1图2图3图43调试报告3.1设计和编码的分析 1、邻接表实现拓扑序列shixian()在本函数里，首先定义一个顺序表，然后把它置空。接着，以邻接表创立一个图，并且把它赋给图G。接着，把全局变量数组visited初始化。对于整个图中，没被访问过的而且入度为0的顶点进展拓扑排序。如果常量count等于0的话，说明图有回路，不能拓扑排序。否那么，在拓扑排序函数中会输出所有的拓扑排序序列。void shixian() Sequenlist A,*L=&A; L=(Sequenlist *)malloc(s

11、izeof(Sequenlist); Setnull(L); ALGraph G; G=creatGraph(); for(int n=1;n=G.vexnum;n+) visitedn=0; int i; cout该图的所有拓扑排序为：endl; for(i=1;i=G.vexnum;i+) if(G.vexsi.into=0)&(visitedi=0) topusort(L,G,i);if(count=0)cout您输入的图不是有向无环图，故无拓扑排序序列产生.endl;else cout此图有countadjvex; G.vexsj.into-; /把以Vi为头的终止结点入度减1 P=P

12、-nextarc; for(k=1;klast=G.vexnum) /判断顺序表中一种拓扑排序完成 output(L); coutadjvex; G.vexsj.into+; /使Vj的入度恢复 P=P-nextarc; SqLdelete(L,G.vexsi);3、顺序表函数在这个设计中，只有顺序表的简单应用，置空，插入，删除和输出。插入和删除都只是在表尾插入和删除。即只要把表长加1或是减1.Sequenlist *Setnull(Sequenlist *L)/顺序表置空 L-last=0; return(L);void SqLinsert(Sequenlist *L,VEXNODE x)/

13、在顺序表尾插入新接点 L-last=L-last+1; L-dataL-last=x;void SqLdelete(Sequenlist *L,VEXNODE x)/删除顺序表中的最后一个节点 L-last=L-last-1;int count=0;void output(Sequenlist *L) /输出顺序表中的元素 int i; for(i=1;ilast;i+) if(ilast) coutVdatai.vexdata; else coutVdatai.vexdata; coutendlendl;3.2调试过程问题及解决在调试的过程中出现了很多语法错误，如：开场没有申明iostrea

14、m头文件，导致所有的输入输出流都是错误的，还有error C2562: main : void function returning a value，发现main函数被我定义为了void返回类型，可是我在函数语句里又使用了return 0；把main函数的返回值改成int即可，还有其他的语法错误都根据提示一一改良了。接着，我发现无论如何输出的结果都是零种排序，于是找到了ALGraph creatGraph()函数的一组赋值语句，开场我是这样写的“G.vexs=al;后来改成for(i=0;ialg.vexnum;i+) alg.vexsi.vexdata=ali.vexdata;alg.vex

15、si.indegree=ali.indegree; alg.vexsi.firstarc=ali.firstarc;再次运行时，输出结果还是不对。最后发现在for语句前少了alg.vexnum=n;alg.arum=e;赋值语句。在topusort函数中以下语句使得运行结果一直为您输入的图不是有向无环图，故无拓扑排序序列产生.for(k=1;klast=G.vexnum) /判断顺序表中一种拓扑排序完成 output(L); coutendl; count+; topusort(L,G,k); 改成如下代码即可：for(k=1;klast=G.vexnum) /判断顺序表中一种拓扑排序完成 o

16、utput(L); coutendl; count+; 4经历与体会此次课程设计为拓扑排序，利用c+语言实现的，此算法还有多发面可以改良，比方图的表示利用的是邻接表，还可以在代码中增加邻接矩阵的表示方法，使得对于两种形式表示的图都可以进展拓扑排序，还有在代码中并没有把邻接表很直观的输出给用户，如果可以编写代码把邻接表很直观的输出，会更有可读性。在执行的过程中发现对于大量的数据，比方边比拟复杂的情况，程序执行就有可能会崩溃，说明程序的强健性还有待提高。通过五天的课程设计，我稳固了以前学过的知识，懂得了理论与实际相结合的重要性，只有理论知识是远远不够的，理论知识是为将来的实践效劳的，理论知识很重要

17、，实践活动更重要。通过课程设计我看到自己实际操作能力的严重缺乏，知识理解不够深刻，掌握不够结实，编程根底薄弱，没有耐心。在同学和相关资料的帮助下，最终完成了代码。通过这次设计，我看到自身学习方法存在很多错误，我决心在以后的学习过程中，要多锻炼自己处理实际问题的能力，要提高独立分析问题和解决问题的能力，多动手多上机操作。并且利用假期时间进一步稳固数据构造课程与C+语言根底，为今后的学习打下比拟坚实的根底。5用户使用说明运行后，根据提示，“请输入结点数,即输入图的顶点数目，“请入边总数数，即输入图的边数；接着依次输入每条边的起始点序号和终止点序号即可，输出结果就可以一目了然。例如：请输入顶点数：4

18、请输入弧数：4请输入边的信息：请输入第一条边：1 2请输入第二条边：1 3请输入第三条边：2 3请输入第四条边：3 46参考文献：1.严蔚敏，吴伟民。数据构造题集(c语言)。清华大学，2011年11月。2.殷人昆。数据构造(用面向对象方法与C+语言描述)(第2版)。清华大学，2007年6月7附录源代码与运行结果源程序代码c+语言#include #include #include #include #define NULL 0#define maxlen 100typedef struct ARODE /表结点 int adjvex;/接邻点的位置 ARODE *nextarc;/指向下一个结

19、点ARODE; /邻接表中的结点类型typedef struct VEXNODE /头结点 int vexdata;/顶点的位置 int into; /顶点的入度 ARODE *firstarc;/指向第一个邻接结点VEXNODE,AdjListmaxlen;/表头结点类型typedef struct AdjList vexs;/表头结点数组 int vexnum,arum;/顶点数、边数ALGraph;/邻接表类型typedef struct VEXNODE datamaxlen; int last;Sequenlist; /顺序表类型typedef struct int datamaxle

20、n; int last;Seqlist; /顺序表ALGraph creatGraph() int n,e,i,j,k; ARODE *p; AdjList al; coutendl; cout-拓扑排序-endlendl; coutn;for(i=1;i=n;i+) /初始化表头结点数组 ali.vexdata=i; ali.into=0; ali.firstarc=NULL; coute; cout请依次输入边的信息:endl; for(i=1;i=e;i+) cout请输入第ijk; /依次读入边的信息 p=(ARODE *)malloc(sizeof(ARODE); p-adjvex=

21、k; alk.into+; /把终止结点的入度加1 p-nextarc=alj.firstarc; /用头插法把p插入到链表中 alj.firstarc=p; coutendl; ALGraph alg; alg.vexnum=n; alg.arum=e; for(i=1;ilast=0; return(L);void SqLinsert(Sequenlist *L,VEXNODE x)/在顺序表尾插入新接点 L-last=L-last+1; L-dataL-last=x;void SqLdelete(Sequenlist *L,VEXNODE x)/删除顺序表中的最后一个节点 L-last=

22、L-last-1;int count=0;void output(Sequenlist *L) /输出顺序表中的元素 int i; for(i=1;ilast;i+) if(ilast) coutVdatai.vexdata; else coutVdatai.vexdata; coutendladjvex; G.vexsj.into-; /把以Vi为头的终止结点入度减1 P=P-nextarc; for(k=1;klast=G.vexnum) /判断顺序表中一种拓扑排序完成 output(L); coutadjvex; G.vexsj.into+; /使Vj的入度恢复 P=P-nextarc;

23、 SqLdelete(L,G.vexsi);void shixian() Sequenlist A,*L=&A; L=(Sequenlist *)malloc(sizeof(Sequenlist); Setnull(L); ALGraph G; G=creatGraph(); for(int n=1;n=G.vexnum;n+) visitedn=0; int i; cout该图的所有拓扑排序为：endl; for(i=1;i=G.vexnum;i+) if(G.vexsi.into=0)&(visitedi=0) topusort(L,G,i);if(count=0)cout您输入的图不是有向无环图，故无拓扑排序序列产生.endl;else cout此图有count种拓扑排序nn; count=0; int main() shixian(); return 0;运行结果截图如下：本科生课程设计成绩评定表班级：学号：序号评分工程总分值实得分1学习态度认真、遵守纪律102设计分析合理性103设计方案正确性、可行性、创造性204设计结果正确性405设计报告的规性106设计验收10总得分/等级评语：注：最终成绩以五级分制记。优90-100分、良80-89分、中70-79分、及格60-69分、60分以下为不及格指导教师签名：201 年月日