以邻接矩阵方式确定有向网程设计报告.doc

《数据结构》 课程设计报告 设计题目：以邻接矩阵方式确定有向网 班级： 姓名： 学号： 完成日期： 一、需求分析 1、运行环境（软、硬件环境）： 处理器：英特尔酷睿(Core) i5-2410M CPU 2.30GHz 物理内存：2G 操作系统：Microsoft Windowns 7 开发环境：Microsoft Visual Studio 2008 2、程序所实现的功能： (1)建立并显示出它的邻接链表； （2）以非递归的方式进行深度优先遍历，显示遍历的结果， （并随时显示栈的入、出情况）； （3）对改图进行拓扑排序，显示拓扑排序的结果，并随时 显示入度域的变化情况； （4）给出某一确定顶点到所有其他顶点的最短路径； 3、程序的输入，包含输入的数据格式和说明： （1）输入节点数个数 （2）输入顶点信息（空格隔开） （3）输入权值信息（以弧尾值 弧头值 权值信息 ，空格  隔开 0 0 0 结束；）文档由风行播放器  /  暴风影音 2014：  / 整理 4、程序的输出，程序输出的形式：  （1）邻接链表输出 （2）深度优先遍历输出  (3)拓扑排序输出  （4）  最短路径输出 5、测试数据： （1）节点个数 ：5 个 （2）顶点信息：a b c d e （3）权值信息：a b 1 b c 2 c d 3 d e 4 a d 5 d c 6 0 0 0 二、设计说明 1 1、算法设计的思想： 建程序主要是通过建立一个图的模板类来调用相应的构造函数以及相应的 成员函数来实现其功能，首先用结构体来存储边节点和顶点节点，用邻接矩阵来 存储此有向图，遍历的过程采用双从循环来使得遍历达到最底端，最短路径采用 了递归的思想循环调用最短路径函数来完成最短路径的查找，拓扑排序中首先优 先输出入度为零的节点，然后通过删除该节点继续此过程进行排序。 2、主要的数据结构设计说明： 图的邻接矩阵结构设计：顶点数、弧数、矩阵数组、和点数组 栈结构：包括栈顶和栈底 点结构：包括顶点和弧相关的指针信息。 3、程序的主要流程图： 有向图  输 出 邻 接 表  深 度 优 先 遍  拓 扑 排 序  入 度 域 变 化  最 短 路 径 历 4、主要模块和函数:  1、 邻接矩阵创建有向网  void CreatGraph(MGraph *g)  伪码：依次存储节点数、顶点信息、权值 2、 打印有向网的邻接矩阵 void PrintGraph(MGraph *g) 伪码：依次打印邻接矩阵  3、 打印有向网的邻接表  void PrintList(MGraph *g)  2 伪码：输出矩阵每行不为零值纵坐标对应的节点  4、 非递归深度优先遍历  void DFSTraverse(MGraph *g)  伪码：1.从右向左依次把邻接矩阵第一行非零值纵坐标对应的节点数入栈，  并  将最后入栈值出栈； 2.再将最后入栈值定为横坐标，重复上述操作，直到空； 3.出栈，重复第二步操作； 4.重复第三部操作，直到栈空；  5、 获取每个节点的入度  void FindInDegree（）  伪码： 获取邻接矩阵每行非零值个数  6、 拓扑排序 伪码：  int TopologicalSort(MGraph *g) 1.先将度为零节点入栈 2.出栈，对 i 号节点的每个邻接点入度减 1 3.若入度减为 0，则入栈 4.重复 2，3 步，直至栈空  7、 任意两点最短距离  void ShortestPath_FLOYD(MGraph *g)  伪码：  先看两点之间有无直接路径，若有，则看有无通过中间点更短  若无，则看有无中间点连通 三、源程序代码： #include iostream #includestdio.h #includestdlib.h using namespace std; #define MAX_VERTEX_NUM 20 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OVERFLOW 0 #define ERROR 0 #define OK 1 #define INFINITY 100 //最大顶点个数 //存储空间初始分配量 //存储空间分配增量 typedef struct ArcCell //图的邻接矩阵结构定义 { 3 char adj; int *info; }VertexNode; typedef struct {  //顶点 //弧相关信息指针 VertexNode vexs[MAX_VERTEX_NUM]; int arcs[MAX_VERTEX_N