《C++数据结构以邻接矩阵方式确定有向网.doc》由会员分享，可在线阅读，更多相关《C++数据结构以邻接矩阵方式确定有向网.doc（16页珍藏版）》请在金锄头文库上搜索。
1、 数据结构 课程设计报告设计题目：以邻接矩阵方式确定有向网班级：姓名：学号：完成日期：1、 需求分析 1、运行环境（软、硬件环境）： 处理器：英特尔酷睿(Core) i5-2410M CPU 2.30GHz 物理内存：2G 操作系统：Microsoft Windowns 7 开发环境：Microsoft Visual Studio 2008 2、程序所实现的功能： (1)建立并显示出它的邻接链表； （2）以非递归的方式进行深度优先遍历，显示遍历的结果， （并随时显示栈的入、出情况）； （3）对改图进行拓扑排序，显示拓扑排序的结果，并随时 显示入度域的变化情况； （4）给出某一确定顶点到所有其他
2、顶点的最短路径； 3、程序的输入，包含输入的数据格式和说明： （1）输入节点数个数 （2）输入顶点信息（空格隔开） （3）输入权值信息（以弧尾值 弧头值 权值信息 ，空格 隔开 0 0 0结束；） 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 02、 设计说明 1、算法设计的思想： 建程序主要是通过建立一个图的模板类来调用相应的构造函数以及相应的成员函数
3、来实现其功能，首先用结构体来存储边节点和顶点节点，用邻接矩阵来存储此有向图，遍历的过程采用双从循环来使得遍历达到最底端，最短路径采用了递归的思想循环调用最短路径函数来完成最短路径的查找，拓扑排序中首先优先输出入度为零的节点，然后通过删除该节点继续此过程进行排序。 2、主要的数据结构设计说明：图的邻接矩阵结构设计：顶点数、弧数、矩阵数组、和点数组栈结构：包括栈顶和栈底点结构：包括顶点和弧相关的指针信息。 3、程序的主要流程图： 有向图深度优先遍历最短路径入度域变化拓扑排序输出邻接表 4、主要模块和函数:1、 邻接矩阵创建有向网 void CreatGraph(MGraph *g) 伪码：依次存储
4、节点数、顶点信息、权值2、 打印有向网的邻接矩阵 void PrintGraph(MGraph *g) 伪码：依次打印邻接矩阵 3、 打印有向网的邻接表 void PrintList(MGraph *g) 伪码：输出矩阵每行不为零值纵坐标对应的节点4、 非递归深度优先遍历 void DFSTraverse(MGraph *g) 伪码： 1.从右向左依次把邻接矩阵第一行非零值纵坐标对应的节点数入栈，并 将最后入栈值出栈； 2.再将最后入栈值定为横坐标，重复上述操作，直到空； 3.出栈，重复第二步操作； 4.重复第三部操作，直到栈空；5、 获取每个节点的入度 void FindInDegree（）
5、 伪码： 获取邻接矩阵每行非零值个数6、 拓扑排序 int TopologicalSort(MGraph *g) 伪码： 1.先将度为零节点入栈 2.出栈，对i号节点的每个邻接点入度减13.若入度减为0，则入栈 4.重复2，3步，直至栈空7、 任意两点最短距离 void ShortestPath_FLOYD(MGraph *g) 伪码： 先看两点之间有无直接路径，若有，则看有无通过中间点更短 若无，则看有无中间点连通三、源程序代码：#include #include#includeusing namespace std;#define MAX_VERTEX_NUM 20 /最大顶点个数#def
6、ine STACK_INIT_SIZE 100 /存储空间初始分配量#define STACKINCREMENT 10 /存储空间分配增量#define OVERFLOW 0 #define ERROR 0#define OK 1#define INFINITY 100typedef struct ArcCell /图的邻接矩阵结构定义char adj; /顶点int *info; /弧相关信息指针VertexNode;typedef struct VertexNode vexsMAX_VERTEX_NUM; /顶点向量int arcsMAX_VERTEX_NUMMAX_VERTEX_NUM;
7、 /邻接矩阵int vexnum,arcnum; /定点数和弧数MGraph;typedef struct int *base; /栈底指针int *top; /栈顶指针int stacksize; /存储空间SqStack;/*函数名称： findnode函数功能描述： 返回结点在数组位置函数调用之前的预备条件：定义并赋值结点数组返回后的处理：返回值（如果有的话）： int函数的输入参数： SqStack &S，结点字符a函*/int findnode(char a,MGraph *S)for(int i=1;ivexnum+1);i+)if (S-vexsi.adj =a)return i
8、; return -1;/*函数名称： InitStack函数功能描述： 构造一个空栈函数调用之前的预备条件：定义邻接矩阵结构体返回后的处理：返回值（如果有的话）： OVERFLOW或OK函数的输入参数： SqStack &S函数的输出参数：函数的抽象算法（伪码）：存储分配*/int InitStack(SqStack &S) /构造一个空栈S.base = (int *)malloc(STACK_INIT_SIZE *sizeof(int); if(!S.base) /存储分配失败return OVERFLOW;S.top=S.base;S.stacksize=STACK_INIT_SIZE
9、;return OK;/*函数名称： StackEmpty 函数功能描述： 判断栈是否为空栈函数调用之前的预备条件：已构造一个栈返回后的处理：返回值（如果有的话）： OK或ERROR函数的输入参数： SqStack &S函数的输出参数：函数的抽象算法（伪码）：栈底与栈顶比较*/int StackEmpty(SqStack &S) if(S.top=S.base) /空栈return OK;else return ERROR;/*函数名称： Push 函数功能描述： 插入新的栈顶元素函数调用之前的预备条件：已构造一个栈返回后的处理：返回值（如果有的话）： OK函数的输入参数： SqStack &
10、S,int e函数的输出参数：函数的抽象算法（伪码）：指针移动*/int Push(SqStack &S,int e) /插入新的栈顶元素if(S.top-S.base=S.stacksize) /栈满，追加存储空间S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT) *sizeof(int); if(!S.base) /存储分配失败 return(OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;/*函数名称：
11、GetTop 函数功能描述： 获取的栈顶元素函数调用之前的预备条件：已构造一个栈返回后的处理：返回值（如果有的话）： e或ERROR函数的输入参数： SqStack &S,int e函数的输出参数：函数的抽象算法（伪码）：指针移动*/int GetTop(SqStack &S,int &e)if(S.top=S.base)return ERROR;e=*(S.top-1);return e;/*函数名称： Pop 函数功能描述： 删除栈顶元素函数调用之前的预备条件：已构造一个栈返回后的处理：返回值（如果有的话）： e函数的输入参数： SqStack &S,int &e函数的输出参数： e函数的
12、抽象算法（伪码）：指针移动*/int Pop(SqStack &S,int &e) /删除栈顶元素 if(S.top=S.base) return ERROR;e=*-S.top;return e;/*函数名称： CreatGraph 函数功能描述： 邻接矩阵创建有向网函数调用之前的预备条件：定义邻接矩阵结构体返回后的处理：返回值（如果有的话）： 函数的输入参数： MGraph *g函数的输出参数：函数的抽象算法（伪码）：依次存储节点数、顶点信息、权值*/void CreatGraph(MGraph *g)/邻接矩阵创建有向网int i,j,m,o, p;char r1,r2;/m权值coutg-vexnum; /获取节点数cout请输入有向网顶点信息（空格间开）：n;for(i=1
