C++大数据结构以邻接矩阵方式确定有向网.doc

《C++大数据结构以邻接矩阵方式确定有向网.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构》课程设计报告设计题目：以邻接矩阵方式确定有向网班级：：学号：完成日期：一、需求分析1、运行环境（软、硬件环境）：处理器：英特尔酷睿(Core)i5-2410MCPU2.30GHz物理存：2G操作系统：MicrosoftWindowns7开发环境：MicrosoftVisualStudio20082、程序所实现的功能：(1)建立并显示出它的邻接链表；（2）以非递归的方式进行深度优先遍历，显示遍历的结果，（并随时显示栈的入、出情况）；（3）对改图进行拓扑排序，显示拓扑排序的结果，并随时显示入度域的变化情况；（4）给出某一确定顶点到所有其他顶点的最短路径；3、程序的输入，包含

2、输入的数据格式和说明：（1）输入节点数个数（2）输入顶点信息（空格隔开）（3）输入权值信息（以弧尾值弧头值权值信息，空格隔开000结束；）4、程序的输出，程序输出的形式：（1）邻接链表输出（2）深度优先遍历输出(3)拓扑排序输出（4）最短路径输出5、测试数据：（1）节点个数：5个（2）顶点信息：abcde（3）权值信息：ab1bc2cd3de4ad5dc6000二、设计说明1、算法设计的思想：建程序主要是通过建立一个图的模板类来调用相应的构造函数以及相应的成员函数来实现其功能，首先用结构体来存储边节点和顶点节点，用邻接矩阵来存储此有向图，遍历的过程采用双从循环来使得遍历达到最底端，

3、最短路径采用了递归的思想循环调用最短路径函数来完成最短路径的查找，拓扑排序中首先优先输出入度为零的节点，然后通过删除该节点继续此过程进行排序。2、主要的数据结构设计说明：图的邻接矩阵结构设计：顶点数、弧数、矩阵数组、和点数组栈结构：包括栈顶和栈底点结构：包括顶点和弧相关的指针信息。3、程序的主要流程图：有向图深度优先遍历最短路径入度域变化拓扑排序输出邻接表4、主要模块和函数:1、邻接矩阵创建有向网voidCreatGraph(MGraph*g)伪码：依次存储节点数、顶点信息、权值2、打印有向网的邻接矩阵voidPrintGraph(MGraph*g)伪码：依次打印邻接矩阵3、打印有

4、向网的邻接表voidPrintList(MGraph*g)伪码：输出矩阵每行不为零值纵坐标对应的节点4、非递归深度优先遍历voidDFSTraverse(MGraph*g)伪码：1.从右向左依次把邻接矩阵第一行非零值纵坐标对应的节点数入栈，并将最后入栈值出栈；2.再将最后入栈值定为横坐标，重复上述操作，直到空；3.出栈，重复第二步操作；4.重复第三部操作，直到栈空；1、获取每个节点的入度voidFindInDegree（）伪码：获取邻接矩阵每行非零值个数2、拓扑排序intTopologicalSort(MGraph*g)伪码：1.先将度为零节点入栈2.出栈，对i号节点的每个邻接点入

5、度减13.若入度减为0，则入栈4.重复2，3步，直至栈空3、任意两点最短距离voidShortestPath_FLOYD(MGraph*g)伪码：先看两点之间有无直接路径，若有，则看有无通过中间点更短若无，则看有无中间点连通三、源程序代码：#include#include#includeusingnamespacestd;#defineMAX_VERTEX_NUM20//最大顶点个数#defineSTACK_INIT_SIZE100//存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量#de

6、fineOVERFLOW0#defineERROR0#defineOK1#defineINFINITY100typedefstructArcCell//图的邻接矩阵结构定义{charadj;//顶点int*info;//弧相关信息指针}VertexNode;typedefstruct{VertexNodevexs[MAX_VERTEX_NUM];//顶点向量intarcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//邻接矩阵intvexnum,arcnum;//定点数和弧数}MGraph;typedefstruct{int*base;//栈底指针int*to

7、p;//栈顶指针intstacksize;//存储空间}SqStack;/*函数名称：findnode函数功能描述：返回结点在数组位置函数调用之前的预备条件：定义并赋值结点数组返回后的处理：返回值（如果有的话）：int函数的输入参数：SqStack&S，结点字符a函*/intfindnode(chara,MGraph*S){for(inti=1;i<(S->vexnum+1);i++){if(S->vexs[i].adj==a)returni;}return-1;}/