欢迎来到天天文库
浏览记录
ID:55940308
大小:1.12 MB
页数:11页
时间:2020-06-17
《拓扑排序课程设计报告.doc》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、数据结构课程设计设计题目:有向图拓扑排序专业:信息与计算科学学号:021240616姓名:黄秋实指导教师:文军2013年11月28日数据结构课程设计----拓扑排序一需求分析1.问题描述本次课程设计题目是:用邻接表构造图然后进行拓扑排序,输出拓扑排序序列拓扑排序的基本思想为:1).从有向图中选一个无前驱的顶点输出;2).将此顶点和以它为起点的弧删除;3).重复1),2)直到不存在无前驱的顶点;4).若此时输出的顶点数小于有向图中的顶点数,则说明有向图中存在回路,否则输出的顶点的顺序即为一个拓扑序列。2.拓扑排序有向图拓朴排序算法的基本步骤如下:①从图中选择一个入度为0的顶点,输出该顶点;②
2、从图中删除该顶点及其相关联的弧,调整被删弧的弧头结点的入度(入度-1);③重复执行①、②直到所有顶点均被输出,拓朴排序完成或者图中再也没有入度为0的顶点(此种情况说明原有向图含有环)。3基本要求(1)输入的形式和输入值的范围;首先是输入要排序的顶点数和弧数,都为整型,中间用分隔符隔开;再输入各顶点的值,为正型,中间用分隔符隔开;然后输入各条弧的两个顶点值,先输入弧头,再输入弧尾,中间用分隔符隔开,输入的值只能是开始输入的顶点值否则系统会提示输入的值的顶点值不正确,请重新输入,只要继续输入正确的值就行。(2)输出的形式;首先输出建立的邻接表,然后是最终各顶点的出度数,再是拓扑排序的序列,并且
3、每输出一个顶点,就会输出一次各顶点的入度数。(3)程序所能达到的功能;因为该程序是求拓扑排序,所以算法的功能就是要输出拓扑排序的序列,在一个有向图中,若用顶点表示活动,有向边就表示活动间先后顺序,那么输出的拓扑序列就表示各顶点间的关系为反映出各点的存储结构,以邻接表存储并输出各顶点的入度。二概要设计1.算法中用到的所有各种数据类型的定义在该程序中用邻接表作为图的存储结构。首先,定义表结点和头结点的结构类型,然后定义图的结构类型。创建图用邻接表存储的函数,其中根据要求输入图的顶点和边数,并根据要求设定每条边的起始位置,构建邻接表依次将顶点插入到邻接表中。拓扑排序的函数在该函数中首先要对各顶点
4、求入度,其中要用到求入度的函数,为了避免重复检测入度为零的顶点,设置一个辅助栈,因此要定义顺序栈类型,以及栈的函数:入栈,出栈,判断栈是否为空。2.各程序模块之间的层次调用关系第一部分,voidALGraph*G函数构建图,用邻接表存储。这个函数没有调用函数。第二部分,voidTopologicalSort(ALGraph*G)输出拓扑排序函数,这个函数首先调用FindInDegree(G,indegree)对各顶点求入度indegree[0……vernum-1];然后设置了一个辅助栈,调用InitStack(&S)初始化栈,在调用Push(&S,i)入度为0者进栈,while(!Stac
5、kEmpty(&S))栈不为空时,调用Pop(&sS,&n)输出栈中顶点并将以该顶点为起点的边删除,入度indegree[k]--,当输出某一入度为0的顶点时,便将它从栈中删除。第三部分,主函数,先后调用voidCreatGraph(ALGraph*G)函数构建图、voidTopologicalSort(ALGraph*G)函数输出拓扑排序实现整个程序。3.设计的主程序流程(见附页)三详细设计(实现概要设计中定义的所有数据类型,对每个操作写出伪码算法;对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为;按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序);写出出函数
6、和过程的调用关系。)1.实现概要设计中定义的所有数据类型#include#include#defineMAX_VEXTEX_NUM100#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineOK1#defineM100#defineERROR0typedefintElemType;typedefstructArcNode{intadjvex;structArcNode*nextarc;}ArcNode;typedefstructVNode{intdata;ArcNode*firstarc;}VNo
7、de,AdjList[MAX_VEXTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;}ALGraph;typedefstruct{ElemType*base;ElemType*top;intstacksize;}SqStack;2.算法和各模块的代码程序中各函数算法思想如下:2.1voidInitStack(SqStack*S)初始化栈将栈的空间设为STAC
此文档下载收益归作者所有