《拓扑排序课程设计报告》由会员分享，可在线阅读，更多相关《拓扑排序课程设计报告（28页珍藏版）》请在金锄头文库上搜索。
1、下载可编辑航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：拓扑排序算法院（系）：计算机学院专业：计算机科学与技术（嵌入式系统方向）班 级：14010105班学 号：2011040101221姓 名：王芃然指导教师：丁一军1课程设计介绍1.1课程设计容11.2课程设计要求12课程设计原理2.1课设题目粗略分析22.2原理图介绍22.2.1功能模块图22.2.2流程图分析33 数据结构分析3.1存储结构73.2算法描述7.专业.整理.4调试与分析124.1调试过程124.2 程序执行过程12参考文献1516附录（关键部分程序清单）1 课程设计介绍1.1课程设计容由某个集合上的一
2、个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。若在图一的有向图上人为的加一个表示V2=V3的弧（“=”表示V2领先于V3）则图一表示的亦为全序且这个全序称为拓扑有序,而由偏序定义得 到拓扑有序的操作便是拓扑排序。在 AOV网中为了更好地完成工程，必须满 足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。编写算 法建立有向无环图，主要功能如下：1. 能够求解该有向无环图的拓扑排序并输出出来；2. 拓扑排序应该能处理出现环的情况；3. 顶点信息要有几种情况可以选择。1.2课程设计要求1. 输出拓扑排序数据外，还要输出邻接表数据；2. 参考相应的资料，独立完成课程设计任务；3. 交
3、规课程设计报告和软件代码。2课程设计原理2.1课设题目粗略分析本课设题目要求编写算法能够建立有向无环图，有向无环图，顾名思义，即一个 无环的有向图，是一类较有向图更一般的特殊有向图。其功能要求及个人在写程序时对该功能的实现作如下分析：1. 将图以合适的方式存储起来。图有多种存储方式，其中最常用的存储方式有图 的邻接矩阵和邻接表。本人在构思时使用邻接表来建立有向无环图，将其存储起 来；2. 求解该有向无环图的拓扑排序，并将其输出出来。若通过构造，建立了一个有 向无环图，那么一定可以求出其拓扑排序，其原理比较简单。即统计每个节点的 入度，将入度为0的结点提取出来，然后再统计剩下的结点的入度，再次将
4、入度 为零的结点提取出来，以此类推，这样就形成了一个序列，这样的序列就是该图 的拓扑排序序列；3. 拓扑排序算法应能够处理出现环的情况。个人在写程序时，考虑到构造图时， 会有构造成有向有环图的情况，应该在运行程序时，试着统计依次按照入读为零 的节点输出的节点数是否为整个节点的总数，如果是，那么拓扑排序成功，输出 拓扑排序的结果，否者输出“有环出现”；4. 输出除拓扑排序外，还要求输出邻接表数据。由于图是用邻接表存储的，所以 将邻接表按照顺序依次打印输出。2.2原理图介绍2.2.1功能模块图图2.1功能模块图2.2.2流程图分析1. 如图2.2所示，根据题目要求建立一个有向无环图，按照提示，依次
5、输入节点数和变数，然后输入两个联通的节点vu,v，前者指向后者，当输入边数为 所要输入的数目时，输入结束，有向图建立完成（未判断是否有环）开始N建立有向无环图/ 结束图2.2建立有向无环图2. 如图2.3所示，判断有向图是否为有向无环图。按照输入的有向图建立 一个邻接表，将图储存在邻接表中，并将邻接表打印，然后对该邻接表进行拓扑 排序，依次取入度为零的节点，入栈，并删除该节点和该节点有关的所边，若入 栈节点个数与节点数相同，则全部入栈，该图为无环图，可以进行拓扑排序，若 该图节点数大于入栈节点数，则该图为有环图。Y图2.3判断是否为无环图3. 此时该图为有向无环图，可进行拓扑排序，在上一过程中
6、，所有节点已 经入栈，将栈顶弹出进入另一个空栈，然后依次输出栈顶，拓扑排序成功。如图 2.4所示。图2.4输出拓扑排序结果4.具体容- 图2.5拓扑排序3数据结构分析3.1存储结构一个无环的有向图叫做有向无环图，简称DAGS。本算法首先要建立一个有向无环图，即通过输入各边的数据，搭建图的结构。对于图的存储，用到邻接表, 是一种链式存储结构。弧结点结构类型:typedef struct ArcNode/*该弧指向的顶点的位置*/*指向下一条弧的指针*/*顶点信息*/*指向第一条依附于该点的弧的指针*/int adjvex; struct ArcNode *n extarc;ArcNode; 邻接
7、表头结点类型：typedef struct VNodeint data;ArcNode *firstarc;VNode,AdjListMAX_VEXTEX_NUM;3.2算法描述1. 邻接表的构建创建一个邻接表，首先要输入节点数和边数，然后输入确定一条边的两个节点，通过输入顺序来确定边的方向，构成有向图，具体方法如下：初始化头结点for (i=1; ivex nu m;i+)G-verticesi.data=i;/*编写顶点的位置序号*/G-verticesi.firstarc=NULL;先将头结点清零，编写顶点位置序号。输入确定弧的两点，如果输入数字大于节点数或者小于零，则输出错误信息,并重
8、新输入一组节点，申请新的节点来储存新的节点信息，该弧指向位置编号为 m的节点，下一条弧指向的是依附于n的第一条弧，最后打印生成的邻接表。for (i=1;iarc nu m;i+)printf(n输入确定弧的两个顶点u，v:);scanf(%d %d,&n,&m);while (n G-vex nu m|mG-vex num)printf(输入的顶点序号不正确请重新输入:);sca nf(%d%d,&n,&m);p=(ArcNode*)malloc(sizeof(ArcNode);/* 开辟新的弧结点 */if(p=NULL)prin tf(ERROR!);exit(1);p-adjvex=m
9、;/*该弧指向位置编号为 m的结点*/p-n extarc=G-vertices n.firstarc;G-vertices n.firstarc=p;printf(n建立的邻接表为:n);/*打印生成的邻接表(以一定的格式)*/for(i=1;ivex nu m;i+)prin tf(%d,G-verticesi.data);for(p=G-verticesi.firstarc;p;p=p-n extarc)prin tf(-%d,p-adjvex);prin tf(n); 邻接表构建完成。2. 入栈操作在本算法中栈主要用来构造拓扑排序序列。由于栈具有先入后出的特点，所 以，将每次选择入度为
10、零的结点入栈，这样当结点都入栈的时候，再依次出栈， 进入另一个新栈，这样，排序序列显而易见。它将图这样的非线性结构转化为栈 这样的线性结构。建立空栈typedef structint *base;/* 栈底指针 */int *top;/*栈顶指针*/int stacksize;SqStack;初始化栈void In itStack(SqStack *S)S-base=(i nt *)malloc(STACK_INIT_SIZE*sizeof(i nt);if(!S-base)/*存储分配失败*/prin tf(ERROR!);exit(1);S-top=S-base;S-stacksize=S
11、TACK_INIT_SIZE;入栈操作，压入新的元素为栈顶，e为新的栈顶元素。void Push(SqStack *S,int e)/* 压入新的元素为栈顶 */if(S-top-S-base=S-stacksize)S-base=(i nt*)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(i nt);if(!S-base)prin tf(ERROR!);exit(1);S-top=S-base+S-stacksize;S-stacksize+=STACKINCREMENT;*S-top+=e;3. 拓扑排序本程序的拓扑排序，必须在图的邻
12、接表已知的情况下。它还有另外一个功能: 判断一个图是不是无环图。确切的说，不能单纯的叫拓扑排序，但考虑它主要的 作用，在不引起误解的情况下就叫拓扑排序算法。判断一个图是否为有向无环图并进行拓扑排序，对于本题目来说，由于本题 要求是对有向无环图进行拓扑排序，其主要方法是将入度为零的结点依次输出出 来，知道图的所有定点全部输出为止。那么若图为有环图，在环上的结点在其他 结点都选择出来后，入度都不为零，即无法被输出出来。那么就可以认为按照拓 扑排序的方法输出结点后，若不是将节点全部输出出来的，则此图为有环图。输 出有向图有环，拓扑排序失败。若无环，则进行拓扑排序。通过入栈出栈的操作 来完成拓扑排序。
13、主要算法如下：void TopoSort(ALGraph G) in t in degreeM;int i, k, n;int count=O;/*初始化输出计数器*/ArcNode *p;SqStack S;Fin di nDegree(G,i ndegree);In itStack(&S);prin tf(n);/*入度为0的入栈*/*栈不为空*/*弹出栈顶*/*输出栈顶并计数*/for(i=1;in extarc)k=p-adjvex;if(!(-indegreek)/*若入度减为零，则再入栈 */Push(& S,k);if(countvG.vexnum) printf(有向图中有环);else printf(排序成功!);4调试与分析4.1调试过程在
