《数据结构与算法》课程设计成果报告-拓扑排序算法实现.doc

河南工程学院数据结构与算法课程设计成果报告拓扑排序算法实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程-1342 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目拓扑排序算法实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务12 分析与设计22.1 拓扑排序分析22.2 原理图介绍22.2.1功能模块图32.2.2 流程图分析32.3 数据结构分析42.3.1 存储结构42.3.2 算法描述43 程序清单94 测试134.1 调试过程134.2 测试结果分析135 总结15参考文献1631 课程设计目标与任务1.1课程设计目标（1）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。 （2）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。 （3）提高综合运用所学的理论知识和方法独立分析和解决问题的能力。（4）训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。（5）训练自己动手分析，解决问题的能力，掌握调试程序，排除错误的常用技巧。（6）增强动手能力，学会结合实际解决问题。1.2 课程设计任务编写算法，建立有向无环图，系统主要功能如下：1. 能够求解该有向无环图的拓扑排序并输出出来；2. 拓扑排序应能够处理出现环的情况。3. 顶点信息要有几种情况可以选择4. 选择合适的结构存储图，在此基础上实现拓扑排序算法。5. 输出除拓扑排序数据外，还要求输出邻接表数据。2 分析与设计2.1 拓扑排序分析本课设题目要求编写算法能够建立有向无环图，有向无环图，顾名思义，即一个无环的有向图，是一类较有向图更一般的特殊有向图。其功能的实现作如下分析：1. 将图以合适的方式存储起来。图有多种存储方式，其中最常用的存储方式有图的邻接矩阵和邻接表。2. 求解该有向无环图的拓扑排序，并将其输出出来。若通过构造，建立了一个有向无环图，那么一定可以求出其拓扑排序，其原理比较简单。即统计每个节点的入度，将入度为0的结点提取出来，然后再统计剩下的结点的入度，再次将入度为零的结点提取出来，以此类推，这样就形成了一个序列，这样的序列就是该图的拓扑排序序列。3. 输出除拓扑排序外，还要求输出邻接表数据。由于图是用邻接表存储的，所以很容易将其邻接表输出出来。2.2 原理图介绍2.2.1 功能模块图实现拓扑排序的功能模块图如图2.1。拓扑排序算法 拓扑排序图的遍历 图的存储有环图遍历全部 邻接表 输出队列入度为零入队列无环图无法遍历 邻接矩阵图2.1 功能模块图2.2.2 流程图分析根据程序的总的步骤，拟将整个流程分为三个模块。三个模块既相互独立又相互联系。具体分析如下：1. 图像输入，根据题目要求，要能够建立一个有向无环图，这就要我们在程序中去建立。考虑到输入方式要尽量方便全面，采用输入弧的方式，输入每条弧的链接的两个结点，当输入-1时结束输入。这样再输入的时候，与相邻的两个结点的邻接矩阵对应的位置也做相应改变。2. 判断图是不是有向无环图。当图为有向无环图时，则挑选完毕后，队列应该是满的，进行后续步骤。对于结点入队列的顺序，需要借助于数组。选取入度为零的结点，入队列，调整数组，循环进行。3. 拓扑排序。此时，所输入的弧应该是有向无环图了，下面进行拓扑排序。在判断它是否为无环图的过程中已经形成了一个满队列。接下来所要做的事情就是循环出队列，按照队列固有的顺序进行输出即可，排序完成。 开始 图形输入构造邻接表，并将其输出无环图 否是 入度为零入队列满队列是 循环出队列 调整visited否 结束图2.2 程序流程图2.3数据结构分析2.3.1 存储结构一个无环的有向图叫做有向无环图，简称DAG图。本算法首先要建立一个有向五环图，即通过输入各边的数据，搭建图的结构。对于图的存储，用到邻接表，是一种链式存储结构。typedef struct Nodeint data;struct Node *next;GraphNode;GraphNode vexsmaximum;对于用来排序的队列，则用到了顺序存储结构的队列，用数组表示。 int Queuemaximum;2.3.2 算法描述1. 邻接表的构造：本算法借用图的邻接矩阵构造邻接表，其形式如下：int Graphmaximummaximum;对于相邻的结点i和j，Graphij=1，若不相邻，则Graphij=0；对于邻接表的存储结构，上面已作说明，定义一个GraphNode类型的数组变量vexsmaximum和一个GraphNode类型的指针变量*newnode。若两个结点i和j相邻（由i指向j，Graphij=1），则在vexsmaximum第i行添加以j为值的newnode数据，即vexsi-1-next=*newnode。其中newnode-data=j，newnode-next=NULL。直到遍历完整个邻接矩阵，邻接表随即建立完成。简单算法说明如下：for(i=0;il;i+)for(j=0;jl;j+)if(Graphij)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 delqueue(int *queue)/出队操作int e;if(rear=front)return -2; front+;e=queuefront;queuefront=0;return e;3. 拓扑排序本程序的拓扑排序，必须在图的邻接表已知的情况下。它还有另外一个功能：判断一个图是不是无环图。确切的说，不能单纯的叫拓扑排序，但考虑它主要的作用，在不引起误解的情况下就叫拓扑排序算法。判断一个图是否为有向无环图并进行拓扑排序，判定方法有很多种，检查一个有向图是否存在环要比无向图复杂。对于无向图来说，若深度优先遍历过程中遇到回边（即指向已访问过的顶点的边），则必存在环；而对于有向图来说，这条回边有可能指向深度优先森林中另一棵生成树上顶点的弧。但是，如果从有向图上某个顶点v出发的遍历，在dfs(v)结束之前出现一条从顶点u到顶点v的回边，由于u在生成树上是v的子孙，则有向图中必定存在包含顶点v和u的环。另一种判断是否有环的方法则显得简单的多，尤其是对于本题目来说，由于本题要求是对有向无环图进行拓扑排序，其主要方法是将入度为零的结点依次输出出来，知道图的所有定点全部输出为止。那么若图为有环图，在环上的结点在其他结点都选择出来后，入度都不为零，即无法被输出出来。那么就可以认为按照拓扑排序的方法输出结点后，若不是将节点全部输出出来的，则此图为有环图。判断好图是否为有向图后，考虑到题目要求，要能够处理出现环的情况，若构造的图为有环图，则折回开始重新输入图的数据，重新构造图，直到该图为无环图为止。若图已经是无环图，则进行拓扑排序，排序方法前面已经讲过，在此主要诉说用到的辅助存储。数组visited存储各结点的入度，对入度为零的结点，依次入队列Queue，调整visited数组，结点全部入队列后，然后依次出队列，拓扑排序完成。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;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);3 程序清单#include stdafx.h#include stdio.h#include stdlib.h#define maximum 20int Graphmaximummaximum;int distmaximum; / 表示当前点到源点的最短路径长度int visitedmaximum;int Queuemaximum;int l;int jj=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=queuefront;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 topnum=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) printf(拓扑排序为：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=source)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); 4 测试4.1 调试过程在调试程序是主要遇到以下几类问题：1. 数组的数据容易出现混乱，比如结点用数字标识，数组结点的位置是从0开始，而标识符往往从1开始，这在程序的开始就应该注意到；2. 各函数的形参，实参的区别，全局变量，局部变量的区别，特别是在做大型程序的时候，如果多个函数都要用到一个变量，那么就应把该变量定义为全局变量，若错误的定义为局部变量，很容易出现错误；3. 对于一个程序，对于出现不同情况应能够正确处理，比如对本题而言，是对有向无环图进行拓扑排序。若经过错误的构造，该图是有环图，则应该提示该图是有环图，并自动重新输入该图，开始的时候由于缺乏考虑，会导致有环图也像无环图一样进行“拓扑排序”。4. 程序应该条例清晰，结构明朗，各个函数代表各个模块，起到不同的作用，并协调运作，形成含有不同功能的程序。开始时因为程序的结构混乱而导致很难调试，无法找到错误的根源。4.2 测试结果分析1. 对于有向无环图，以图4.2.1为例进行拓扑排序： 1 24356图4.2.1 有向无环图程序运行结果如图4.2.2所示：图4.2.2 有向无环图拓扑排序2. 对于有向有环图，以图4.2.3为例： 1 24356图4.2.3 有向有环图程序运行结果如图4.2.4所示：图4.2.4 有向有环图程序运行结果5 总结每一次课设都是对自己综合能力的提高，这次也不例外。数据结构是一门应用性很高的基础课程。通过课设，我收到到了一下几个方面1. 通过此次课设，我恢复了基础的C语言编程能力，并在此基础上，利用数据结构，能够变出更具有实用性，也具有更复杂功能的程序。很多以前想象不到的功能，通过数据结构巧妙的安排，也可以轻松实现。2. 通过此次课设，我锻炼了自己独立思考的能力。以前总是不相信自己，能够把一个问题思考的有多深。现在，通过独立的思考，哪怕是一段漫长的时间得到的是对知识更为深刻的理解。3. 通过此次课设，我能够借阅资料。通过更为广泛的寻找来为自己获得启发。通过请教他人，运用合作意识，让自己的做事效率更高。为自己增添信心。它让我学到很多。虽然课设时间很短，但收获却是别的方式无法拥有的，因为它让我把只是运用于实践，把思考当做一种享受，其乐趣是无穷的，它对我的影响很深远。参考文献1 严蔚敏，吴伟民.数据结构M.北京：清华大学出版社，2007.2 张长海，陈娟.C程序设计M.北京：高等教育出版社，2004. 3 谭浩强.C程序设计M.北京：清华大学出版社，2005.#include stdafx.h#include stdio.h#include stdlib.h#define maximum 20int Graphmaximummaximum;int distmaximum; / 表示当前点到源点的最短路径长度int visitedmaximum;int Queuemaximum;int l;int jj=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=queuefront;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 topnum=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;topn