数据结构课程设计：有向图拓扑排序算法的实现(共22页)

1、精选优质文档-倾情为你奉上数据结构课程设计设计说明书有向图拓扑排序算法的实现学生姓名樊佳佳学号班级网络工程1301成绩指导教师申静数学与计算机科学学院2016年1月4日课程设计任务书 20152016学年第一学期课程设计名称： 数据结构课程设计 课程设计题目： 图的拓扑排序算法的实现 完 成 期 限：自 2015年 12月20日至 2016年 1 月 3 日共 2 周设计内容：1、设计任务（1）给出一个有向无环图，遍历所有的节点；（2）能够实现对所有顶点的拓扑；(3)界面友好，可操作性强。2、需求分析对系统的功能及性能要求进行分析，写出需求规格说明书（可行性分析报告、系统的分层DFD图）。3、

2、软件设计软件设计分两个阶段进行：总体设计和详细设计；总体设计：确定系统总体设计方案，完成系统的模块结构图及模块的功能说明；详细设计：对模块内部过程及数据结构进行设计，以及进行数据库设计、用户界面设计等编写出该项目的详细设计报告；4、具体编码编写程序，要求给出详细的注释，包括：模块名、模块功能、中间过程的功能、 变量说明等。同时编写用户使用手册、程序模块说明等文档；5、软件测试所有测试过程要求采用综合测试策略：先作静态分析，再作动态测试。应事先制订测试计划，并要求保留所有测试用例，完成测试报告。指导教师：申静 教研室负责人：申静课程设计评阅评语： 指导教师签名： 年 月 日专心-专注-专业摘 要

3、设计了一个对有向图进行拓扑排序的算法，该算法首先用邻接表构造有向图的存储结构，然后对此有向图进行拓扑排序，输出拓扑排序的结果。用VC+作为软件开发环境，以邻接表作为图的存储结构，将图中所有顶点排成一个线性序列，输出拓扑排序结果。拓扑排序常用来确定一个依赖关系集中，事物发生的顺序。拓扑排序是对有向无环图的顶点的一种排序，它使得如果存在一条从顶点A到顶点B的路径，那么在排序中B出现在A的后面。关键词：邻接表；有向无环图；拓扑排序目 录1 课题描述12 问题分析和任务定义23 逻辑设计33.1程序模块功能图33.2 抽象数据类型34 详细设计44.1 C语言定义的相关数据类型44.2 主要模块的伪码

4、算法44.2.1主函数伪码算法44.2.2邻接表伪码算法44.2.3拓扑排序的伪码算法：54.3 主函数流程图65 程序编码76 程序调试与测试137 结果分析168 总结17参考文献181 课题描述根根据设计要求运用C语言程序设计了一个对有向图进行拓扑排序的算法，该算法首先用邻接表构造有向图的存储结构，然后对此有向图进行拓扑排序，输出拓扑排序的结果。如给定一个有向无环图如图1.1所示。在此图中，从入度为0的顶点出发，删除此顶点和所有以它为尾的弧；重复直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。 23 1 4 5图1.1 有向无环图开发工具：Visual C+ 6.02 问题分析和

5、任务定义对一个有向无环图G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对由某个集合上的一个偏序得到该集合上的一个全序，这个操作就称之为拓扑排序。偏序集合中仅有部分成员之间颗比较，而全序指集合中全体成员之间均可比较，而由偏序定义得到拓扑有序的操作便是拓扑排序。一个表示偏序的有向图可用来表示一个流程图，通过抽象出来就是AOV-网，若从顶点i到顶点j有一条有向路径，则i是j的前驱，j是i的后继。若（i，j）是一条弧，则i是j的直接前驱；j是i的直接后继。在AOV-网中，不应该出现有向环，用拓扑排序就可以判断网中是否有环，若网中所有顶点都在它的拓扑有序序列中，则该AOV-网必定不存在

6、环。3 逻辑设计主函数3.1程序模块功能图拓扑排序节点入度栈的初始化创建邻接表有向图初始化图3.1程序模块功能图3.2 抽象数据类型ADT ALGraph数据对象：D=V|V是具有相同特性的数据元素的集合，即顶点集数据关系：R=<v,w>|v,wV,<v,w>表示顶点v到顶点w的弧基本操作P:CreatGraphlist(ALGraph *G)初始条件：成对输入顶点集V中的点。操作结果：构造图G的邻接表。FindInDegree(ALGraph G, int indegree)初始条件：图G的邻接表中存在结点V。操作结果：找到图中入度为0结点。Initgraph()操作

7、结果：完成图形初始化。TopologicalSort(ALGraph G)初始条件：构造的有向图G已初始化。操作结果：对于有向图G根据邻接存储表进行拓扑排序。4 详细设计4.1 C语言定义的相关数据类型#define max_vextex_num 20 /*宏定义最大顶点个数*/ #define stack_init_size 100 /*宏定义栈的存储空间大小*/ typedef int ElemType; typedef struct VNode /*邻接表头结点的类型*/int data; /*顶点信息,数据域*/VNode, AdjListMAX_VEXTEX_NUM; /*AdjLi

8、st是邻接表类型*/typedef struct AdjList vertices; /*邻接表*/ int vexnum, arcnum; /*图中顶点数vexn和边数arcn*/ALGraph; /*图的类型*/typedef struct /构建栈 ElemType *base; /*数据域*/ ElemType *top; /*栈指针域*/int stacksize; SqStack;4.2 主要模块的伪码算法4.2.1主函数伪码算法：开始 创建及输出邻接表CreatGraphlist(&G);输出排序后的输出序列TopologicalSort(G);结束4.2.2邻接表伪码算

9、法：#define MAX_VEXTEX_NUM 20typedef struct VNode /*邻接表头结点的类型*/ int data; /*顶点信息,数据域*/ ArcNode *firstarc; /*指向第一条弧*/VNode, AdjListMAX_VEXTEX_NUM; /*AdjList是邻接表类型*/typedef struct AdjList vertices; /*邻接表*/ int vexnum, arcnum; /*图中顶点数vexn和边数arcn*/ALGraph; /*图的类型*/开始定义一个指针P置i的初值为1邻接表中所有头结点指针置初值当i<=G-ve

10、xnum时自加，执行下面操作：输出数据域里的顶点信息使指针p指向顶点i第一条弧的头结点输出访问顶点使指针p指向顶点i的下一条弧的头结点类此循环到输出最后一个顶点结束4.2.3拓扑排序的伪码算法开始引入栈操作函数和入度操作函数访问邻接存储表中的顶点nIf该顶点入度为0顶点进栈循环操作到所有顶点入栈当栈不为空顶点出栈结束4.3 主函数流程图主函数流程图如图4.3所示开始输入顶点数和弧数N输入判断是否满足条件 Y根据输入信息建立邻接表 建栈在邻接表中寻找入度为零的顶点，使其入栈N输出栈顶元素，打印，将与栈顶元素邻接的顶点的入度减1判断是否空栈 Y 结束图4.3 主函数程序流程图5 程序编码#incl

11、ude<stdio.h>#include<stdlib.h>#define true 1#define false 0#define MAX_VEXTEX_NUM 20#define M 20#define STACK_INIT_SIZE 100#define STACKINCREMENT 10/*-图的邻接表存储结构-*/typedef struct ArcNode /*弧结点结构类型*/ int adjvex; /*该弧指向的顶点的位置*/ struct ArcNode *nextarc; /*指向下一条弧的指针*/ArcNode;typedef struct VN

12、ode /*邻接表头结点类型*/ int data; /*顶点信息*/ ArcNode *firstarc; /*指向第一条依附于该点的弧的指针*/ VNode,AdjListMAX_VEXTEX_NUM; /*AdjList为邻接表类型*/typedef struct AdjList vertices; int vexnum, arcnum;ALGraph;/*-*/void CreatGraph(ALGraph *G) /*通过用户交互产生一个图的邻接表*/ int m, n, i; ArcNode *p; printf("="); printf("n输入顶点

13、数:"); scanf("%d",&G->vexnum); printf("n输入边数:"); scanf("%d",&G->arcnum); printf("="); for (i=1; i<=G->vexnum;i+) /*初始化各顶点*/ G->verticesi.data=i; /*编写顶点的位置序号*/ G->verticesi.firstarc=NULL; for (i=1;i<=G->arcnum;i+) /*记录图中由两点确定

14、的弧*/ printf("n输入确定弧的两个顶点u，v:"); scanf("%d %d",&n,&m); while (n<0|n>G->vexnum|m<0|m>G->vexnum) printf("输入的顶点序号不正确 请重新输入:"); scanf("%d%d",&n,&m); p=(ArcNode*)malloc(sizeof(ArcNode); /*开辟新的弧结点来存储用户输入的弧信息*/ if(p=NULL) printf("

15、;ERROR!"); exit(1); p->adjvex=m; /*该弧指向位置编号为m的结点*/ p->nextarc=G->verticesn.firstarc;/*下一条弧指向的是依附于n的第一条弧*/ G->verticesn.firstarc=p; printf("="); printf("n建立的邻接表为:n"); /*打印生成的邻接表（以一定的格式）*/ for(i=1;i<=G->vexnum;i+) printf("%d",G->verticesi.data);

16、for(p=G->verticesi.firstarc;p;p=p->nextarc) printf("->%d",p->adjvex); printf("n"); printf("=");/*-*/typedef struct /*栈的存储结构*/ int *base; /*栈底指针*/ int *top; /*栈顶指针*/ int stacksize;SqStack;/*-*/void InitStack(SqStack *S) /*初始化栈*/ S->base=(int *)malloc(STACK

17、_INIT_SIZE*sizeof(int); if(!S->base) /*存储分配失败*/ printf("ERROR!"); exit(1); S->top=S->base; S->stacksize=STACK_INIT_SIZE;/*-*/void Push(SqStack *S,int e) /*压入新的元素为栈顶*/ if(S->top-S->base>=S->stacksize) S->base=(int *)realloc(S->base,(S->stacksize+STACKINCREME

18、NT)*sizeof(int); /*追加新空间*/ if(!S->base) /*存储分配失败*/ printf("ERROR!"); exit(1); S->top=S->base+S->stacksize; S->stacksize+=STACKINCREMENT; *S->top+=e; /*e作为新的栈顶元素*/*-*/int Pop(SqStack *S,int *e) /*弹出栈顶，用e返回*/ if(S->top=S->base) /*栈为空*/ return false; *e=*-S->top;ret

19、urn 0;/*-*/int StackEmpty(SqStack *S) /*判断栈是否为空，为空返回1，不为空返回0*/ if(S->top=S->base) return true; else return false;/*-*/void FindInDegree(ALGraph G, int indegree) /*对各顶点求入度*/ int i; for(i=1; i<=G.vexnum;i+) /*入度赋初值0*/ indegreei=0; for(i=1;i<=G.vexnum;i+) while(G.verticesi.firstarc) indegre

20、eG.verticesi.firstarc->adjvex+; /*出度不为零，则该顶点firstarc域指向的弧指向的顶点入度加一*/ G.verticesi.firstarc = G.verticesi.firstarc->nextarc; /*-*/void TopoSort(ALGraph G) int indegreeM; int i, k, n; int count=0; /*初始化输出计数器*/ ArcNode *p; SqStack S; FindInDegree(G,indegree); InitStack(&S); for(i=1;i<=G.vex

21、num;i+) printf("n"); printf("indegree%d = %d n",i,indegreei); /*输出入度*/ printf("n"); for(i=1;i<=G.vexnum;i+) /*入度为0的入栈*/ if(!indegreei) Push(&S,i); printf("="); printf("nn拓扑排序序列为:"); while(!StackEmpty(&S) /*栈不为空*/ Pop(&S,&n); /*弹出栈顶

22、*/ printf("%4d",G.verticesn.data); /*输出栈顶并计数*/ count+; for(p=G.verticesn.firstarc; p!=NULL;p=p->nextarc)/*n号顶点的每个邻接点入度减一*/ k=p->adjvex; if(!(-indegreek) /*若入度减为零，则再入栈*/ Push(&S,k); if(count<G.vexnum)/*输出顶点数小于原始图的顶点数，有向图中有回路*/ printf("ERROR 出现错误!"); else printf("

23、 排序成功!");/*-*/main(void) /*编写主调函数以调用上述被调函数*/ ALGraph G; CreatGraph(&G); /*建立邻接表*/ TopoSort(G); /*对图G进行拓扑排序*/printf("nn"); system("pause"); /*调用系统的dos命令：pause;显示:"按任意键继续."*/ return 0;6 程序调试与测试（1）当为有向有环图结构如图6.3所示图6.3 有向有环图结构输出结果如图6.4所示图6.4有向有环图的输出（2）输入检验图如图6.5所示：

24、图6.5 检验图由邻接表定义可以得到上图的邻接表如图6.6所示：图6.6邻接表其中一种拓扑序列： 2 7 1 3 4 6 5将图输入到程序中结果如图6.7所示：图6.8 检验图的输出所得结果与预计结果一致。7 结果分析对于算法的时间复杂度和空间复杂度， 拓扑排序实际是对邻接表表示的图G进行遍历的过程，每次访问一个入度为零的顶点，若图G中没有回路，则需扫描邻接表中的所有边结点，在算法开始时，为建立入度数组D需访问表头向量中的所有边结点，算法的时间复杂度为O(n+e)。其次在编写代码时应根据流程图进行同步编写，综合考虑需求分析进行编辑。否则会出现偏离主题的错误。当然在输出结果后，为避免输入引起的错

25、误，因该先对开始与结束结果进行先得出，与运行结果对照，小的问题应该进行尽量的避免，或减小到最小值。8 总结平时我就比较爱好编程，有时候自己也会设想一些小程序，然后通过自己的努力来实现。因此我把本次课程设计当作了又一次锻炼，拿到题目后，经过与组员的讨论便开始了程序的编写。大家都知道，编程是一件很需要耐心的事。因为几乎每一个程序的编写，都需要学习新的知识才能进行，同时程序调试过程很枯燥，有时候一点小错意味着长时间的查错。如语法错误中，“;”丢失、“”与“”不匹配等问题最难定位到出错语句；逻辑错误中，作为循环变量的“i”与“j”相互混淆、对未分配空间的节点进行操作等，都会使程序运行出错而难以找到原因。算法设计、程序调试的过程中，经常遇到看似简单但又无法解决的问题，这时候很容易灰心丧气，此时切不可烦躁，一定要冷静的思考，认真的分析；而解决问题，完成程序后，那种兴奋感与成就感也令人振奋。可以说编写程序既是一件艰苦的工作，又是一件愉快的事情。我的小组课程设计题目的核心是“拓扑排序”。虽然平时对拓扑排序有一些了解，上课也学过，但真正应用到程序中，写出算法却一点也不简单。拓扑排序，首先需要有被排序的主体，也就是有向图，于是先要实现有向图的建立及相关操作；有向图的建立，该选取怎样的数据结构，是邻接矩阵还是邻接表，本着尽量靠近实际应用的