《数据结构课程设计拓扑排序.doc》由会员分享，可在线阅读，更多相关《数据结构课程设计拓扑排序.doc（19页珍藏版）》请在三一办公上搜索。
1、 数据结构 课程设计报告题目： 拓扑排序算法 院（系）：理学院专 业：信息与计算科学 班 级： 94140101学 号： 姓 名： 指导教师： 2011年12月目 录1 课程设计介绍11.1 课程设计内容11.2 课程设计要求12 课程设计原理22.1 课设题目粗略分析22.2 原理图介绍32.2.1 功能模块图32.2.2 流程图分析33 数据结构分析53.1 存储结构53.2 算法描述54 调试与分析94.1 调试过程94.2 程序执行过程9参考文献11总结12附 录（关键部分程序清单）13 1 课程设计介绍1.1 课程设计内容编写算法，建立有向无环图，系统主要功能如下：1. 能够求解该有
2、向无环图的拓扑排序并输出出来；2. 拓扑排序应能够处理出现环的情况。3. 顶点信息要有几种情况可以选择。1.2 课程设计要求1. 输出除拓扑排序数据外，还要求输出邻接表数据；2. 参考相应资料，独立完成课程设计任务；3. 交规范课程设计报告和软件代码。2 课程设计原理2.1 课设题目粗略分析本课设题目要求编写算法能够建立有向无环图，有向无环图，顾名思义，即一个无环的有向图，是一类较有向图更一般的特殊有向图。其功能要求及个人在写程序时对该功能的实现作如下分析：1. 将图以合适的方式存储起来。图有多种存储方式，其中最常用的存储方式有图的邻接矩阵和邻接表。本人在构思时使用邻接表来建立有向无环图，将其
3、存储起来；2. 求解该有向无环图的拓扑排序，并将其输出出来。若通过构造，建立了一个有向无环图，那么一定可以求出其拓扑排序，其原理比较简单。即统计每个节点的入度，将入度为0的结点提取出来，然后再统计剩下的结点的入度，再次将入度为零的结点提取出来，以此类推，这样就形成了一个序列，这样的序列就是该图的拓扑排序序列；3. 拓扑排序算法应能够处理出现环的情况。个人在写程序时，考虑到构造图时，会有构造成有向有环图的情况，应该在运行程序时，提醒出来，然后重新输入有向无环图，知道输入正确为止。这样就有多次构造邻接表的问题，每一次构造邻接表时，都应该将原来错误的（不是无环图的）邻接表空间释放掉，否则，会变得混乱
4、；4. 输出除拓扑排序外，还要求输出邻接表数据。由于图是用邻接表存储的，所以很容易将其邻接表输出出来。2.2 原理图介绍2.2.1 功能模块图拓扑排序算法 拓扑排序图的遍历 图的存储有环图遍历全部 邻接表 输出队列入度为零入队列无环图无法遍历 邻接矩阵图2.1 功能模块图2.2.2 流程图分析根据程序的总的步骤，拟将整个流程分为三个模块。三个模块既相互独立又相互联系。具体分析如下：1. 图像输入，根据题目要求，要能够建立一个有向无环图，这就要我们在程序中去建立。考虑到输入方式要尽量方便全面，采用输入弧的方式，输入每条弧的链接的两个结点，当输入-1时结束输入。这样再输入的时候，与相邻的两个结点的
5、邻接矩阵对应的位置也做相应改变。2. 判断图是不是有向无环图。当图为有向无环图时，则挑选完毕后，队列应该是满的，进行后续步骤。对于结点入队列的顺序，需要借助于数组。选取入度为零的结点，入队列，调整数组，循环进行。若队列不满，则输入的图不符合要求，应该重新输入。在程序中应做适当提醒，然后自动转模块1.，进行图的重新编辑。3. 拓扑排序。此时，所输入的弧应该是有向无环图了，下面进行拓扑排序。在判断它是否为无环图的过程中已经形成了一个满队列。接下来所要做的事情就是循环出队列，按照队列固有的顺序进行输出即可，排序完成。 开始 图形输入构造邻接表，并将其输出无环图 否是 入度为零入队列满队列是 循环出队
6、列 调整visited否 结束图2.2 程序流程图3 数据结构分析3.1 存储结构一个无环的有向图叫做有向无环图，简称DAG图。本算法首先要建立一个有向五环图，即通过输入各边的数据，搭建图的结构。对于图的存储，用到邻接表，是一种链式存储结构。typedef struct Nodeint data;struct Node *next;GraphNode;GraphNode vexsmaximum;对于用来排序的队列，则用到了顺序存储结构的队列，用数组表示。 int Queuemaximum;3.2 算法描述1. 邻接表的构造：本算法借用图的邻接矩阵构造邻接表，其形式如下：int Graphmax
7、imummaximum;对于相邻的结点和，Graphij=1，若不相邻，则Graphij=0；对于邻接表的存储结构，上面已作说明，定义一个GraphNode类型的数组变量vexsmaximum和一个GraphNode类型的指针变量*newnode。若两个结点和相邻（由指向，Graphij=1），则在vexsmaximum第行添加以为值的newnode数据，即vexsi-1-next=*newnode。其中newnode-data=j，newnode-next=NULL。直到遍历完整个邻接矩阵，邻接表随即建立完成。简单算法说明如下：for(i=0;il;i+)for(j=0;jl;j+)if(G
8、raphij)CreateAdjacentTable(i,j); /当邻接矩阵Graphij有值时，则构造邻接表2. 队列初始化（入队操作）及出队操作在本算法中队列主要用来，构造拓扑排序序列。由于队列具有先入先出的特点，所以，将每次选择入度为零的结点入队，这样当结点都入队的时候，再依次出队，这样，排序序列显而易见。它将图这样的非线性结构转化为队列这样的线性结构。（1） 队列初始化：void addqueue(int *queue,int x)/入队操作if(rear=l-1)printf(队列已满n); return;rear+;queuerear=x;return;（2） 出队操作：int
9、delqueue(int *queue)/出队操作int e;if(rear=front)return -2; front+;e=queuefront;queuefront=0;return e;3. 拓扑排序本程序的拓扑排序，必须在图的邻接表已知的情况下。它还有另外一个功能：判断一个图是不是无环图。确切的说，不能单纯的叫拓扑排序，但考虑它主要的作用，在不引起误解的情况下就叫拓扑排序算法。判断一个图是否为有向无环图并进行拓扑排序，判定方法有很多种，检查一个有向图是否存在环要比无向图复杂。对于无向图来说，若深度优先遍历过程中遇到回边（即指向已访问过的顶点的边），则必存在环；而对于有向图来说，这条
10、回边有可能指向深度优先森林中另一棵生成树上顶点的弧。但是，如果从有向图上某个顶点出发的遍历，在结束之前出现一条从顶点到顶点的回边，由于在生成树上是的子孙，则有向图中必定存在包含顶点和的环。另一种判断是否有环的方法则显得简单的多，尤其是对于本题目来说，由于本题要求是对有向无环图进行拓扑排序，其主要方法是将入度为零的结点依次输出出来，知道图的所有定点全部输出为止。那么若图为有环图，在环上的结点在其他结点都选择出来后，入度都不为零，即无法被输出出来。那么就可以认为按照拓扑排序的方法输出结点后，若不是将节点全部输出出来的，则此图为有环图。判断好图是否为有向图后，考虑到题目要求，要能够处理出现环的情况，
11、若构造的图为有环图，则折回开始重新输入图的数据，重新构造图，直到该图为无环图为止。若图已经是无环图，则进行拓扑排序，排序方法前面已经讲过，在此主要诉说用到的辅助存储。数组存储各结点的入度，对入度为零的结点，依次入队列，调整数组，结点全部入队列后，然后依次出队列，拓扑排序完成。void TopoSort(int *visited,int *Queue)int i; rear=-1; front=-1; int topnum=0,mlmaximum,n=0; GraphNode *p;for(i=0;inext; while(p!=NULL)visited(p-data)-1+; p=p-next
12、;while(topnum!=l)for(i=0;inext;while(p!=NULL)visited(p-data)-1-; p=p-next;visitedi=-1;topnum+;for(i=0;il;i+)mli=delqueue(Queue);for(i=0;il;i+)if(mli=-2)printf(您输入的图为有环图,请重新输入!n);break;elsen=n+1;if(n=l) printf(拓扑排序为：n);for(i=0;i);jj=1;printf(n);4 调试与分析4.1 调试过程在调试程序是主要遇到以下几类问题：1. 数组的数据容易出现混乱，比如结点用数字标识
13、，数组结点的位置是从0开始，而标识符往往从1开始，这在程序的开始就应该注意到；2. 各函数的形参，实参的区别，全局变量，局部变量的区别，特别是在做大型程序的时候，如果多个函数都要用到一个变量，那么就应把该变量定义为全局变量，若错误的定义为局部变量，很容易出现错误；3. 对于一个程序，对于出现不同情况应能够正确处理，比如对本题而言，是对有向无环图进行拓扑排序。若经过错误的构造，该图是有环图，则应该提示该图是有环图，并自动重新输入该图，开始的时候由于缺乏考虑，会导致有环图也像无环图一样进行“拓扑排序”。4. 程序应该条例清晰，结构明朗，各个函数代表各个模块，起到不同的作用，并协调运作，形成含有不同
14、功能的程序。开始时因为程序的结构混乱而导致很难调试，无法找到错误的根源。4.2 程序执行过程1. 对于有向无环图，以图4.2.1为例进行拓扑排序： 1 24356图4.1 有向无环图程序运行结果如图4.2.2所示：图4.2 有向无环图拓扑排序2. 对于有向有环图，以图4.2.3为例： 1 24356图4.3 有向有环图程序运行结果如图4.2.4所示：图4.4 有向有环图程序运行结果参考文献1 严蔚敏，吴伟民.数据结构M.北京：清华大学出版社，2007.2 张长海，陈娟.C程序设计M.北京：高等教育出版社，2004. 3 谭浩强.C程序设计M.北京：清华大学出版社，2005.总结课程设计总结：每
15、一次课设都是对自己综合能力的提高，这次也不例外。数据结构是一门应用性很高的基础课程。通过课设，我收到到了一下几个方面1. 通过此次课设，我恢复了基础的C语言编程能力，并在此基础上，利用数据结构，能够变出更具有实用性，也具有更复杂功能的程序。很多以前想象不到的功能，通过数据结构巧妙的安排，也可以轻松实现。2. 通过此次课设，我锻炼了自己独立思考的能力。以前总是不相信自己，能够把一个问题思考的有多深。现在，通过独立的思考，哪怕是一段漫长的时间得到的是对知识更为深刻的理解。3. 通过此次课设，我能够借阅资料。通过更为广泛的寻找来为自己获得启发。通过请教他人，运用合作意识，让自己的做事效率更高。为自己
16、增添信心。4. 它让我学到很多。虽然课设时间很短，但收获却是别的方式无法拥有的，因为它让我把只是运用于实践，把思考当做一种享受，其乐趣是无穷的，它对我的影响很深远。指导教师评语：指导教师(签字)： 年 月 日课程设计成绩附 录（关键部分程序清单）程序代码#include stdafx.h#include stdio.h#include stdlib.h#define maximum 20int Graphmaximummaximum;int distmaximum; / 表示当前点到源点的最短路径长度int visitedmaximum;int Queuemaximum;int l;int j
17、j=0;typedef struct Nodeint data;struct Node *next;GraphNode;GraphNode vexsmaximum; /顶点数组int rear=-1;int front=-1;int queuemaximum;void addqueue(int *queue,int x)/入队操作if(rear=l-1)printf(队列已满n);return;rear+;queuerear=x;return;int delqueue(int *queue)/出队操作int e;if(rear=front)return -2; front+;e=queuefr
18、ont;queuefront=0;return e;void CreateAdjacentTable(int v1,int v2)GraphNode *newnode;newnode=(GraphNode *)malloc(sizeof(GraphNode);newnode-data=v2+1;newnode-next=NULL;GraphNode *p;p=&vexsv1;while(p-next!=NULL)p=p-next;p-next=newnode;void TopoSort(int *visited,int *Queue)int i;rear=-1;front=-1;int top
19、num=0;int mlmaximum;int n=0;GraphNode *p;for(i=0;inext;while(p!=NULL)visited(p-data)-1+;p=p-next;while(topnum!=l)for(i=0;inext;while(p!=NULL)visited(p-data)-1-;p=p-next;visitedi=-1;topnum+;for(i=0;il;i+)mli=delqueue(Queue);for(i=0;il;i+)if(mli=-2)printf(您输入的图为有环图,请重新输入!n);break;elsen=n+1;if(n=l) pri
20、ntf(拓扑排序为：n);for(i=0;i);jj=1;printf(n);void main()int Graphmaximummaximum;GraphNode *kk,*dd;int source,destination;int i,j; printf(输入图的顶点个数：); scanf(%d,&l); while(jj=0) for(i=0;il;i+)for(j=0;jl)printf(超出范围请重新输入：);scanf(%d,&source);printf(输入边的第二个顶点：);scanf(%d,&destination);printf(n);if(destination=so
21、urce)printf(出现循环请重新输入：);scanf(%d,&destination);if(destinationl)printf(顶点超出范围，重新输入：);scanf(%d,&destination);Graphsource-1destination-1=1;printf(输入边的第一个顶点：);scanf(%d,&source);printf(n);for(i=0;inext!=NULL) dd=kk-next; kk-next=dd-next;free(dd);visitedi=0;Queuei=0;for(i=0;il;i+)for(j=0;jl;j+)if(Graphij)CreateAdjacentTable(i,j);printf(输出邻接表：n);for(i=0;inext!=NULL) kk=kk-next;printf(%d,kk-data);printf(n); TopoSort(visited,Queue);
