拓扑排序课程设计报告

《拓扑排序课程设计报告》由会员分享，可在线阅读，更多相关《拓扑排序课程设计报告（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(有向图中有环)

14、;else printf(排序成功!);4调试与分析4.1调试过程在调试程序是主要遇到一下几类问题：1. 数组的数据容易出现混乱，比如节点用数字标识，数组结点的位置是从 0 开始，而标识符往往从1开始，这在程序的开始就应该注意到；2. 各函数的形参和实参的区别，全局变量，局部变量的区别，特别是在做大 型程序的时候，如果多个函数都要用到一个变量，那么就应把该变量定义为全局 变量，若错误的定义为局部变量，很容易出现错误；3. 程序应该调理清晰，结构明朗，各个函数代表各个模块，起到不同的作用， 并协调运作，形成含有不同功能的程序。开始时因为程序的结构混乱而导致很难 调试，无法找到错误的根源。4.2程

15、序执行过程系统使用说明:1. 图的创建;2. 打印邻接表；3. 进行拓扑排序；4. 退出程序。具体容：输入边数及节点数，如图4.1所示r匸找U汩巧 CarfDesfctcp,JqH2字DeoJC诔漣丈京立弓和壬一一 S序V累丹臺黑程KE3退一更 更 更 更 1 2 3 O情输入指令:图4.1主菜单图的创建，如图4.2所示：图4.2图的创建打印邻接表，如图4.3所示:青输入指令工2 注立的邻接表为；1 322 4图4.3打印邻接表进行拓扑排序，如图4.4所示：请输入指令：3进行拓扑排序= =“ =黑觀愿翼为：1 2 耳 4 排序成功图4.4进行拓扑排序退出程序，如图4.5所示：g| J TLI7

16、 I FZ J4排序成功TPress any ke to continue图4.5退出程序参考文献1 严蔚敏，吴伟民数据结构M.北京：清华大学，2007.2 长海，娟.C程序设计M.北京：高等教育，2004.3 谭浩强.C程序设计M.北京：清华大学，2005.4 严蔚敏.数据结构（C语言版）M.清华大学，2005. 高婷,明莉.实用数据结构习题与实践M.北京：清华大学,2011.6 殷人昆.数据结构（用面向对象方法与 C+苗述）M.北京：清华大学,20077 宁正元.算法与数据结构习题精解和实验指导M.北京：清华大学,2005附 录（关键部分程序清单）程序代码#i nclude#in clud

17、e#defi ne true 1#defi ne false 0#defi ne MAX_VEXTEX_NUM 20#defi ne M 20#defi ne STACK_INIT_SIZE 100#defi ne STACKINCREMENT 10typedef struct ArcNode int adjvex;*/*/*struct ArcNode *n extarc;/*ArcNode;弧结点结构类型*/该弧指向的顶点的位置指向下一条弧的指针*/typedef struct VNode/*int data;/*ArcNode *firstarc;/*的弧的指针*/VNode,AdjLi

18、stMAX_VEXTEX_NUM; */邻接表头结点类型*/顶点信息*/指向第一条依附于该点/*AdjList为邻接表类型typedef structAdjList vertices; int vex num, arcnum;ALGraph;void CreatGraph(ALGraph *G) int m, n, i,j;ArcNode *p;/*创建一个图的邻接表*/printf();prin tf(n输入顶点数:）;sea nf(%d,&G-vex nu m); printf(n输入边数:);scan f(%d,&G-arcnum);prin tf(=： for (i=1; ivex n

19、u m;i+)G-verticesi.data=i;G-verticesi.firstarc=NULL; for (i=1;iarc nu m;i+)弧*/*/*/*prin tf(n输入确定弧的两个顶点u, v:);=);初始化各顶点*/编写顶点的位置序号*/记录图中由两点确定的申请新的弧结点来存储该弧指向位置编号为下一条弧指向的是依附scan f(%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);

20、 /* 用户输入的弧信息*/if(p=NULL)prin tf(ERROR!);exit(1);p-adjvex=m;/*的结点*/p-n extarc=G-vertices n.firstarc;/*于n的第一条弧*/G-vertices n.firstarc=p;prin tf(=); prin tf(n 请输入指令：);scan f(%d,&j);if(j=3)printf( n进行拓扑排序n);if(j=2)printf(n建立的邻接表为：n);/*定的格式)*/for(i=1;ivex nu m;i+)prin tf(%d,G-verticesi.data); for(p=G-ver

21、ticesi.firstarc;p;p=p-n extarc) prin tf(-%d,p-adjvex);prin tf(n);打印生成的邻接表（以prin tf(n请输入指令：);scan f(%d,&j);if(j=0)printf( 感谢您的使用!); exit(0);elseif(j=3)printf(n进行拓扑排序);elseprintf(n指令错误);prin tf(=); typedef struct/*int *base;/*int *top;/*int stacksize;SqStack;栈的存储结构*/栈底指针*/栈顶指针*/void In itStack(SqStack

22、 *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=STACK_INIT_SIZE;初始化栈*/存储分配失败*/void Push(SqStack *S,i nt e)/*if(S-top-S-base=S-stacksize)压入新的元素为栈顶*/S-base=(i nt*)realloc(S-base,(S-stacksize+STACKINCREMENT)*sizeof(i nt);/*追加新空间*/i

23、f(!S-base)/*prin tf(ERROR!);exit(1);S-top=S-base+S-stacksize; S-stacksize+=STACKINCREMENT;*S-top+=e;/*e存储分配失败*/作为新的栈顶元素*/int Pop(SqStack *S,i nt *e)/*if(S-top=S-base)/*return false;*e=*-S-top;return 0;弹出栈顶，用e返回*/栈为空*/int StackEmpty(SqStack *S)/*返回1,不为空返回0*/if(S-top=S-base)return true;elsereturn fals

24、e;判断栈是否为空，为空void Fin dI nDegree(ALGraph G, i nt in degree)/*对各顶点求入度 */int i;初始化输出计数器*/入度为0的入栈*/栈不为空*/弹出栈顶*/输出栈顶并计数*/for(i=1; i=G.vexnum;i+)/*入度赋初值 0*/in degreei=0;for(i=1;iadjvex+;/*出度不为零，则该顶点firstarc域指向的弧指向的顶点入度加一 */G.verticesi.firstarcG.verticesi.firstarc- n extarc; void TopoSort(ALGraph G)int in

25、degreeM;int i, k, n;int coun t=0;/*ArcNode *p;SqStack S;Findln Degree(G,i ndegree);In itStack(&S);prin tf(n);for(i=1;inextarc)/*n号顶点的每个邻接点入度减一 */若入度减为零，则再入栈*/ k=p-adjvex; if(!(-i ndegreek)/*Push(&S,k);有向图中有回if（cou ntvG.vex num） /*输出顶点数小于原始图的顶点数,路*/printf（有向图中有环）;elseprintf（排序成功!）; void main()ALGraph

26、 G;int n;拓扑排图的建打印邻接进行拓扑 排退出程序立 表 序 序prin tf(= =n);prin tf(=1 =n);prin tf(=2 =n);prin tf(=3 =n);prin tf(=0=n);while(1)prin tf(n请输入指令：);sca nf(%d,&n);if(n=0)printf（感谢您的使用!n）;exit(O); /*任意键结束*/elseif(n=1)CreatGraph(&G);/* 建立邻接表 */elseprintf(n错误，请先构建图n);TopoSort(G);/*对图G进行拓扑排序*/ prin tf(nn);课程设计总结：每一次课设

27、都是对自己综合能力的提高， 这次也不例外。数据结构是一门应 用性很高的课程，通过课设，我收获了以下几个方面：1. 通过这次课设，我恢复了基础的 C语言能力编程，并在此基础上，利用 数据结构，能够写出更具有实用性，也具有更复杂功能的程序。很多以前想不到 的功能都通过数据结构巧妙的安排，可以轻松实现。2. 通过此次课设，我锻炼了自己独立思考的能力。以前总是不相信自己， 能够把一个问题思考的有多深，现在，通过独立的思考，哪怕是一段漫长的时间 得到的是对知识更为深刻的理解。3. 通过此次课设，我能够借阅资料。通过更为广泛的寻找来为自己获得启发。懂得了理论与实际相结合的重要性， 只有理论知识是远远不够的，理论知识 是为将来的实践服务的，理论知识很重要，实践活动更重要。4. 通过这次设计，我看到自身学习方法存在很多错误，我决心在以后的学 习过程中，要多锻炼自己处理实际问题的能力，要提高独立分析问题和解决问题 的能力，多动手多上机操作。虽然课设时间很短，但收获却是别的方式无法拥有 的，因为它让我把只是运用于实践，把思考当做一种享受，其乐趣是无穷的，它 对我的影响很深远。指导教师评语：指导教师（签字）:2013年1月6日课程设计成绩