数据结构优秀课程设计有向图拓扑排序算法的实现.docx

数据结构课程设计设计说明书有向图拓扑排序算法实现学生姓名樊佳佳学号班级网络工程1301成绩指导老师申静数学和计算机科学学院1月4日课程设计任务书 第一学期课程设计名称： 数据结构课程设计 课程设计题目： 图拓扑排序算法实现 完 成 期 限：自 12月20日至 1 月 3 日共 2 周设计内容：1、设计任务（1）给出一个有向无环图，遍历全部节点；（2）能够实现对全部顶点拓扑；(3)界面友好，可操作性强。2、需求分析对系统功效及性能要求进行分析，写出需求规格说明书（可行性分析汇报、系统分层DFD图）。3、软件设计软件设计分两个阶段进行：总体设计和具体设计；总体设计：确定系统总体设计方案，完成系统模块结构图及模块功效说明；具体设计：对模块内部过程及数据结构进行设计，和进行数据库设计、用户界面设计等编写出该项目标具体设计汇报；4、具体编码编写程序，要求给出具体注释，包含：模块名、模块功效、中间过程功效、 变量说明等。同时编写用户使用手册、程序模块说明等文档；5、软件测试全部测试过程要求采取综合测试策略：先作静态分析，再作动态测试。应事先制订测试计划，并要求保留全部测试用例，完成测试汇报。指导老师：申静 教研室责任人：申静课程设计评阅评语： 指导老师署名： 年 月 日摘 要设计了一个对有向图进行拓扑排序算法，该算法首先用邻接表结构有向图存放结构，然后对此有向图进行拓扑排序，输出拓扑排序结果。用VC+作为软件开发环境，以邻接表作为图存放结构，将图中全部顶点排成一个线性序列，输出拓扑排序结果。拓扑排序常见来确定一个依靠关系集中，事物发生次序。拓扑排序是对有向无环图顶点一个排序，它使得假如存在一条从顶点A到顶点B路径，那么在排序中B出现在A后面。关键词：邻接表；有向无环图；拓扑排序目 录1 课题描述12 问题分析和任务定义23 逻辑设计33.1程序模块功效图33.2 抽象数据类型34 具体设计44.1 C语言定义相关数据类型44.2 关键模块伪码算法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 问题分析和任务定义对一个有向无环图G进行拓扑排序，是将G中全部顶点排成一个线性序列，使得图中任意一对由某个集合上一个偏序得到该集合上一个全序，这个操作就称之为拓扑排序。偏序集合中仅有部分组员之间颗比较，而全序指集合中全体组员之间均可比较，而由偏序定义得到拓扑有序操作便是拓扑排序。一个表示偏序有向图可用来表示一个步骤图，经过抽象出来就是AOV-网，若从顶点i到顶点j有一条有向路径，则i是j前驱，j是i后继。若（i，j）是一条弧，则i是j直接前驱；j是i直接后继。在AOV-网中，不应该出现有向环，用拓扑排序就能够判定网中是否有环，若网中全部顶点全部在它拓扑有序序列中，则该AOV-网肯定不存在环。3 逻辑设计主函数3.1程序模块功效图拓扑排序节点入度栈初始化创建邻接表有向图初始化图3.1程序模块功效图3.2 抽象数据类型ADT ALGraph数据对象：D=V|V是含有相同特征数据元素集合，即顶点集数据关系：R=|v,wV,表示顶点v到顶点w弧基础操作P:CreatGraphlist(ALGraph *G)初始条件：成对输入顶点集V中点。操作结果：结构图G邻接表。FindInDegree(ALGraph G, int indegree)初始条件：图G邻接表中存在结点V。操作结果：找到图中入度为0结点。Initgraph()操作结果：完成图形初始化。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; /*AdjList是邻接表类型*/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邻接表伪码算法：#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-vexnum时自加，实施下面操作：输出数据域里顶点信息使指针p指向顶点i第一条弧头结点输出访问顶点使指针p指向顶点i下一条弧头结点类此循环到输出最终一个顶点结束4.2.3拓扑排序伪码算法开始引入栈操作函数和入度操作函数访问邻接存放表中顶点nIf该顶点入度为0顶点进栈循环操作到全部顶点入栈当栈不为空顶点出栈结束4.3 主函数步骤图主函数步骤图图4.3所表示开始输入顶点数和弧数N输入判定是否满足条件 Y依据输入信息建立邻接表 建栈在邻接表中寻求入度为零顶点，使其入栈N输出栈顶元素，打印，将和栈顶元素邻接顶点入度减1判定是否空栈 Y 结束图4.3 主函数程序步骤图5 程序编码#include#include#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 VNode /*邻接表头结点类型*/ 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输入顶点数:); scanf(%d,&G-vexnum); printf(n输入边数:); scanf(%d,&G-arcnum); printf(=); for (i=1; ivexnum;i+) /*初始化各顶点*/ G-verticesi.data=i; /*编写顶点位置序号*/ G-verticesi.firstarc=NULL; for (i=1;iarcnum;i+) /*统计图中由两点确定弧*/ printf(n输入确定弧两个顶点u，v:); scanf(%d %d,&n,&m); while (nG-vexnum|mG-vexnum) printf(输入顶点序号不正确 请重新输入:); scanf(%d%d,&n,&m); p=(ArcNode*)malloc(sizeof(ArcNode); /*开辟新弧结点来存放用户输入弧信息*/ if(p=NULL) printf(ERROR!); exit(1); p-adjvex=m; /*该弧指向位置编号为m结点*/ p-nextarc=G-verticesn.firstarc;/*下一条弧指向是依附于n第一条弧*/ G-verticesn.firstarc=p; printf(=); printf(n建立邻接表为:n); /*打印生成邻接表（以一定格式）*/ for(i=1;ivexnum;i+) printf(%d,G-verticesi.data); 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_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+STACKINCREMENT)*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;return 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;iadjvex+; /*出度不为零，则该顶点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.vexnum;i+) printf(n); printf(indegree%d = %d n,i,indegreei); /*输出入度*/ printf(n); for(i=1;inextarc)/*n号顶点每个邻接点入度减一*/ k=p-adjvex; if(!(-indegreek) /*若入度减为零，则再入栈*/ Push(&S,k); if(countG.vexnum)/*输出顶点数小于原始图顶点数，有向图中有回路*/ printf(ERROR 出现错误!); else printf( 排序成功!);/*-*/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所表示：图6.5 检验图由邻接表定义能够得到上图邻接表图6.6所表示：图6.6邻接表其中一个拓扑序列： 2 7 1 3 4 6 5将图输入到程序中结果图6.7所表示：图6.8 检验图输出所得结果和估计结果一致。7 结果分析对于算法时间复杂度和空间复杂度， 拓扑排序实际是对邻接表表示图G进行遍历过程，每次访问一个入度为零顶点，若图G中没有回路，则需扫描邻接表中全部边结点，在算法开始时，为建立入度数组D需访问表头向量中全部边结点，算法时间复杂度为O(n+e)。其次在编写代码时应依据步骤图进行同时编写，综合考虑需求分析进行编辑。不然会出现偏离专题错误。当然在输出结果后，为避免输入引发错误，因该先对开始和结束结果进行先得出，和运行结果对照，小问题应该进行尽可能避免，或减小到最小值。8 总结平时我就比较爱好编程，有时候自己也会设想部分小程序，然后经过自己努力来实现。所以我把此次课程设计看成了又一次锻炼，拿到题目后，经过和组员讨论便开始了程序编写。大家全部知道，编程是一件很需要耐心事。因为几乎每一个程序编写，全部需要学习新知识才能进行，同时程序调试过程很枯燥，有时候一点小错意味着长时间查错。如语法错误中，“;”丢失、“”和“”不匹配等问题最难定位到犯错语句；逻辑错误中，作为循环变量“i”和“j”相互混淆、对未分配空间节点进行操作等，全部会使程序运行犯错而难以找到原因。算法设计、程序调试过程中，常常碰到看似简单但又无法处理问题，这时候很轻易气馁丧气，此时切不可烦躁，一定要冷静思索，认真分析；而处理问题，完成程序后，那种兴奋感和成就感也令人振奋。能够说编写程序既是一件艰苦工作，又是一件愉快事情。我小组课程设计题目标关键是“拓扑排序”。即使平时对拓扑排序有部分了解，上课也学过，但真正应用到程序中，写出算法却一点也不简单。拓扑排序，首先需要有被排序主体，也就是有向图，于是先要实现有向图建立及相关操作；有向图建立，该选择怎样数据结构，是邻接矩阵还是邻接表，本着尽可能靠近实际应用态度，我选择了节省存放空间邻接表；拓扑排序要将图中零入度顶点先输出，可利用栈或队列实现，而本程序一个应用是实现教学计划安排，考虑到教学计划安排实际情况，通常先学各门基础课（入度为零），再学专业课（入度不为零），和队列优异先出特点相符，故采取队列实现。总而言之，什么地方该用什么数据结构，该写出怎样算法，全部要经过精心分析和仔细考虑。课程设计不是一个人任务，而是一个小组三个组员共同任务，不仅要能完成程序，而且在完成过程中也要让团体有效地协作起来。在此次课程设计过程中，我认识到以下几点：第一，要有奉献精神，不要怕自己多做了，不要怕自己负担任务有多重，而其它组员做极少。多去做一点不会吃亏，还能学到更多东西。团体组员之间应团结互助，不计功过得失；第二，分工上不能马虎，要具体到个人，每个人负责哪部分任务，什么时候完成，全部要有明确说明，应各尽其能，做到资源优化配置；第三，具体工作时，各组员应频繁交流，避免各自为政，最终造成函数功效不符要求，参数调用不方便，或是论文作者无从下手；第四，当工作出现问题时，各组员应仔细商讨，立即找到问题症结，决不应推卸责任，更不能相互埋怨。在完成课程设计过程中，我加深了对程序结构了解程度，对多种语句了解也更透彻，学会了灵活利用。同时体会到了团体合作乐趣，一向惯于“独立思索”我们学会了主动地同团体组员交流，取长补短，共同进步，只有和同学多交流多学习才能不停地提升本身水平。 总而言之，这学期数据结构课程设计，让我们学到了很多，受益匪浅。参考文件1 严蔚敏，吴伟民.数据结构(C语言版)M. 北京：清华大学出版社,2 李春葆.数据结构(C语言版)习题和解析M. 北京：清华大学出版社,3 钱能.C+程序设计教程M. 北京：清华大学出版社,4 谭浩强.C程序设计.第三版M. 北京.清华大学出版社,.5 张晓莉，刘振鹏，许百成数据结构和算法M. 北京：机械工业出版社,6 叶核亚数据结构（C+版）M北京：机械工业出版社，