数据结构课程设计拓扑排序(顺序,逆序输出)分析.doc

目 录 一．需求分析说明……………………………………………………………1 二．概要设计说明……………………………………………………………1 三．详细设计说明……………………………………………………………2 四．调试分析…………………………………………………………………6 五．用户使用说明……………………………………………………………6 六．课程设计总结……………………………………………………………7 七．测试结果…………………………………………………………………8 八．参考书目…………………………………………………………………9 九. 附录………………………………………………………………………10一、需求分析说明 为了更好的学习数据结构，深刻理解数据结构在解决实际问题中的应用，体会其重要性，熟练掌握线性表、栈和队列、串、数组、树、图等常用的数据结构，熟悉各自的特点和应用场合。 同时锻炼自己独立分析理解问题的能力，学会根据不同的问题选择合适的数据结构，然后结合适当的算法解决问题。锻炼自己的设计和编写程序的技巧，进一步调试和测试自己所写的程序，使其功能更加完善，养成较好的编写程序习惯。 提高综合运用所学的理论知识和方法独立分析和解决问题的能力，训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。本课程设计的目的就是要达到理论与实际应用相结合，使同学们能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养基本的、良好的程序设计技能。 设计的基本要求：1）选择邻接表作为有向图的存储结构模拟整个过程，并输出拓扑排序的顶点序列。2）给出逆向的拓扑有序序列。 概要设计说明 2.1 算法思想 采用邻接表存储结构实现有向图；有向图需通过顶点数、边数、顶点以及边等信息建立。 拓扑排序算法大体思想为： 遍历有向图各顶点的入度，将所有入度为零的顶点入栈； 栈非空时，输出一个顶点，并对输出的顶点数计数； 该顶点的所有邻接点入度减一，若减一后入度为零则入栈； 重复2)、3)，直到栈为空，若输出的顶点数与图的顶点数相等则该图可拓扑排序，否则图中有环； 重复2)、3)、4)直到序列中所有元素均被遍历，则该序列是拓扑序列， 否则不是拓扑序列。 2.2 系统功能模块结构图 本程序包括拓扑排序模块和拓扑排序核心算法模块。  三、详细设计说明 3.1 系统流程设计 3.2 数据结构 1）图 typedef struct stack{ int *base; int *top; int stacksize; }sqstack;//栈的结构，存储图的顶点序号 typedef struct lnode { int adjvex; struct lnode *next; }ArcNode;//弧结点 typedef struct node2 { int data; ArcNode *fristarc; }VNode,AdjList[MAX];//顶点数组,fristarc指向与顶点邻接的第一条弧 typedef struct{ AdjList vertices; int vexnum,arcnum; }Graph;//邻接表图 void CreatGraph(Graph G,int *indegree) { cout请输入图的顶点数和边数(且顶点数不能超过MAX个)endl; cinG.vexnumG.arcnum; cout请输入各个顶点值(整形):endl; for(int i=0;iG.vexnum;i++)//输入图的顶点 { cinG.vertices[i].data; G.vertices[i].fristarc=NULL; indegree[i]=0; } for(i=0;iG.arcnum;i++)//输入图的边 { int m,n; ArcNode *p; cout请输入第i+1条边的头结点和尾结点:endl; cinmn; p=new ArcNode; if(!p) exit(0); indegree[n-1]++;//求每个顶点的入度值 p-adjvex=n-1; p-next=G.vertices[m-1].fristarc; G.vertices[m-1].fristarc=p; } } 栈 void Initstack(sqstack s) { s.base=new int; if(!s.base) exit(0);