拓扑排序课程设计报告[1]

《拓扑排序课程设计报告[1]》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课程设计课程设计题目：拓扑排序姓名：学号：班级：20091141组长：指导老师：解德祥计算机与信息学院数据结构课程设计----拓扑排序一需求分析1.问题描述本次课程设计题目是：用邻接表构造图然后进行拓扑排序，输出拓扑排序序列拓扑排序的基本思想为：1).从有向图中选一个无前驱的顶点输出；2).将此顶点和以它为起点的弧删除；3).重复1),2)直到不存在无前驱的顶点；4).若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑序列。2.基于邻接表的存储结构入度为零的顶点即为没有前驱的顶点，我们可以附设一个存放

2、各顶点入度的数组indegree[]，于是有（1）找G中无前驱的顶点——查找indegree[i]为零的顶点vi；（2）删除以i为起点的所有弧——对链在顶点i后面的所有邻接顶点k，将对应的indegree[k]减1。为了避免重复检测入度为零的顶点，可以再设置一个辅助栈，若某一顶点的入度减为0，则将它入栈。每当输出某一入度为0的顶点时，便将它从栈中删除。3基本要求(1)输入的形式和输入值的范围；首先是输入要排序的顶点数和弧数，都为整型，中间用分隔符隔开；再输入各顶点的值，为正型，中间用分隔符隔开；然后输入各条弧的两个顶点值，先输入弧头，再输入弧尾，中间用分

3、隔符隔开，输入的值只能是开始输入的顶点值否则系统会提示输入的值的顶点值不正确，请重新输入，只要继续输入正确的值就行。(2)输出的形式；首先输出建立的邻接表，然后是最终各顶点的出度数，再是拓扑排序的序列，并且每输出一个顶点，就会输出一次各顶点的入度数。(3)程序所能达到的功能；因为该程序是求拓扑排序，所以算法的功能就是要输出拓扑排序的序列，在一个有向图中，若用顶点表示活动，有向边就表示活动间先后顺序，那么输出的拓扑序列就表示各顶点间的关系为反映出各点的存储结构，以邻接表存储并输出各顶点的入度。二概要设计1.算法中用到的所有各种数据类型的定义在该程序中用邻接

4、表作为图的存储结构。首先，定义表结点和头结点的结构类型，然后定义图的结构类型。创建图用邻接表存储的函数，其中根据要求输入图的顶点和边数，并根据要求设定每条边的起始位置，构建邻接表依次将顶点插入到邻接表中。拓扑排序的函数在该函数中首先要对各顶点求入度，其中要用到求入度的函数，为了避免重复检测入度为零的顶点，设置一个辅助栈，因此要定义顺序栈类型，以及栈的函数：入栈，出栈，判断栈是否为空。2.各程序模块之间的层次调用关系第一部分，voidCreatGraph(ALGraph*G)函数构建图，用邻接表存储。这个函数没有调用函数。第二部分，voidTopologi

5、calSort(ALGraph*G)输出拓扑排序函数，这个函数首先调用FindInDegree(G,indegree)对各顶点求入度indegree[0……vernum-1];然后设置了一个辅助栈，调用InitStack(&S)初始化栈，在调用Push(&S,i)入度为0者进栈，while(!StackEmpty(&S))栈不为空时，调用Pop(&sS,&n)输出栈中顶点并将以该顶点为起点的边删除，入度indegree[k]--,当输出某一入度为0的顶点时，便将它从栈中删除。第三部分，主函数，先后调用voidCreatGraph(ALGraph*G)函数

6、构建图、voidTopologicalSort(ALGraph*G)函数输出拓扑排序实现整个程序。3.设计的主程序流程(见附页)三详细设计（实现概要设计中定义的所有数据类型,对每个操作写出伪码算法；对主程序和其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为；按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序);写出出函数和过程的调用关系。）1.实现概要设计中定义的所有数据类型#include#include#include#defineMAX_VEXTEX_NUM20//*定义点最

7、大的数值为顶30*//#defineM20#defineSTACK_INIT_SIZE100//*定义点最大的数值为顶30*//#defineSTACKINCREMENT10//*定义栈的增量为10*//#defineOK1#defineERROR0typedefcharElemType;//*定义栈顶元素类型*//typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置//structArcNode*nextarc;//指向下一条弧的指针//}ArcNode;//*表结点*//typedefstructVNode{cha

8、rdata;//顶点信息ArcNode*firstarc;//指向第一条依附该顶