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

数据结构 课程设计报告设计题目：以邻接矩阵方式确定有向网班级：姓名：学号：完成日期：1、 需求分析 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结束；） 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、算法设计的思想： 建程序主要是通过建立一个图的模板类来调用相应的构造函数以及相应的成员函数来实现其功能，首先用结构体来存储边节点和顶点节点，用邻接矩阵来存储此有向图，遍历的过程采用双从循环来使得遍历达到最底端，最短路径采用了递归的思想循环调用最短路径函数来完成最短路径的查找，拓扑排序中首先优先输出入度为零的节点，然后通过删除该节点继续此过程进行排序。 2、主要的数据结构设计说明：图的邻接矩阵结构设计：顶点数、弧数、矩阵数组、和点数组栈结构：包括栈顶和栈底点结构：包括顶点和弧相关的指针信息。 3、程序的主要流程图： 有向图深度优先遍历最短路径入度域变化拓扑排序输出邻接表 4、主要模块和函数:1、 邻接矩阵创建有向网 void CreatGraph(MGraph *g) 伪码：依次存储节点数、顶点信息、权值2、 打印有向网的邻接矩阵 void PrintGraph(MGraph *g) 伪码：依次打印邻接矩阵 3、 打印有向网的邻接表 void PrintList(MGraph *g) 伪码：输出矩阵每行不为零值纵坐标对应的节点4、 非递归深度优先遍历 void DFSTraverse(MGraph *g) 伪码： 1.从右向左依次把邻接矩阵第一行非零值纵坐标对应的节点数入栈，并 将最后入栈值出栈； 2.再将最后入栈值定为横坐标，重复上述操作，直到空； 3.出栈，重复第二步操作； 4.重复第三部操作，直到栈空；5、 获取每个节点的入度 void FindInDegree（） 伪码： 获取邻接矩阵每行非零值个数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 /最大顶点个数#define 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; /邻接矩阵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; 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;return OK;/*函数名称： StackEmpty 函数功能描述： 判断栈是否为空栈函数调用之前的预备条件：已构造一个栈返回后的处理：返回值（如果有的话）： OK或ERROR函数的输入参数： SqStack &S函数的输出参数：函数的抽象算法（伪码）：栈底与栈顶比较*/int StackEmpty(SqStack &S) if(S.top=S.base) /空栈return OK;else return ERROR;/*函数名称： Push 函数功能描述： 插入新的栈顶元素函数调用之前的预备条件：已构造一个栈返回后的处理：返回值（如果有的话）： OK函数的输入参数： SqStack &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;/*函数名称： 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函数的抽象算法（伪码）：指针移动*/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;ivexnum;i+) /获取顶点信息 cing-vexsi.adj;for(i=1;ivexnum;i+) /初始化邻接矩阵 for(j=1;jvexnum;j+) g-arcsij=0; coutr1r2m; /权值信息while(r1!=0&r2!=0&m!=0) /生成邻接矩阵转 o=findnode(r1,g); p=findnode(r2,g);g-arcsop=m;cinr1r2m; /*函数名称： PrintList 函数功能描述： 打印有向网的邻接表函数调用之前的预备条件：已创建有向网CreatGraph返回后的处理：返回值（如果有的话）： 函数的输入参数： MGraph *g函数的输出参数： g-vexsj.adj函数的抽象算法（伪码）：输出矩阵每行不为零值纵坐标对应的节点*/void PrintList(MGraph *g)/打印有向网的邻接表int i,j;for(i=1;ivexnum;i+) coutvexsi.adj); for(j=1;jvexnum;j+) if(g-arcsij!=0) /获取非零值coutvexsj.adj); coutNULLn; /一行结束，打印空 /*函数名称： DFSTraverse 函数功能描述： 非递归深度优先遍历函数调用之前的预备条件：已创建有向网CreatGraph返回后的处理：返回值（如果有的话）： 函数的输入参数： MGraph *g函数的输出参数： g-vexsi.adj函数的抽象算法（伪码）：1.从右向左依次把邻接矩阵第一行非零值纵坐标对应的节点数入栈，并将最后入栈值出栈； 2.再将最后入栈值定为横坐标，重复上述操作，直到空；3.出栈，重复第二步操作；4.重复第三部操作，直到栈空；*/void DFSTraverse(MGraph *g) /非递归深度优先遍历int visitedMAX_VERTEX_NUM,i=1,j,e=1; /visited标记向量，e出栈值SqStack s;InitStack(s);Push(s,i); /首节点入栈cout插入栈顶元素：ni; coutvexsi.adjvexnum;j=1;j-) /从右向左寻找if(g-arcsij&(visitedj!=1) /非零即入栈Push(s,j);cout插入栈顶元素：jendl;Pop(s,e); /该行最左非零值入栈cout删除栈顶元素：eendl; if(visitede!=1) /未被标记coutvexse.adjendl;visitede=1;/*函数名称： FindInDegree函数功能描述： 获取每个节点的入度，并存储在indegree数组中函数调用之前的预备条件：已创建有向网CreatGraph返回后的处理：返回值（如果有的话）：函数的输入参数： MGraph *g函数的输出参数： indegree函数的抽象算法（伪码）：获取邻接矩阵每行非零值个数*/void FindInDegree(MGraph *g,int indegreeMAX_VERTEX_NUM) /获取每个节点的入度，并存储在indegree数组中int i,j,n; /n入度for(i=1;ivexnum;i+)n=0;for(j=1;jvexnum;j+)if(g-arcsji) /每行非零值个数n+;indegreei=n; /存储入度/*函数名称： TopologicalSort函数功能描述： 拓扑排序函数调用之前的预备条件：已创建有向网CreatGraph；获取每个节点的入度FindInDegree返回后的处理：返回值（如果有的话）： 函数的输入参数： MGraph *g函数的输出参数： g-vexsi.adj函数的抽象算法（伪码）：1.先将度为零节点入栈 2.出栈，对i号节点的每个邻接点入度减13.若入度减为0，则入栈4.重复2，3步，直至栈空*/int TopologicalSort(MGraph *g) / 拓扑排序 int indegreeMAX_VERTEX_NUM,i,j,k,count; /count输出顶点计数SqStack S;FindInDegree(g,indegree); /对各顶点求入度 InitStack(S);for(i=1;ivexnum;i+) /建立零入度顶点栈 if(!indegreei) /入度为零入栈Push(S,i); count=0;while(!StackEmpty(S)Pop(S,i);coutvexsi.adj; +count;for(j=1;jvexnum;j+)if(g-arcsij)k=j;if(!(-indegreek)Push(S,k);coutt此时vexsk.adj入度：indegreek;/若入度减为零，入栈if (countvexnum)/有回路return ERROR;else return OK;/*函数名称： ShortestPath_FLOYD函数功能描述： 任意两点最短距离函数调用之前的预备条件：已创建有向网CreatGraph返回后的处理：返回值（如果有的话）：函数的输入参数： MGraph *g函数的输出参数： distij函数的抽象算法（伪码）：先看两点之间有无直接路径，若有，则看有无通过中间点更短 若无，则看有无中间点连通 */void ShortestPath_FLOYD(MGraph *g)/任意两点最短距离 int distMAX_VERTEX_NUMMAX_VERTEX_NUM;/dist两点间路径长度 int i,j,k; for(i=1;ivexnum;i+) /初始化 for(j=1;jvexnum;j+) distij=g-arcsij; for(i=1;ivexnum;i+)for(j=1;jvexnum;j+)coutvexsi.adjvexsj.adj:t;for(k=1;kvexnum;k+) if(i!=j&i!=k&j!=k) /三点互不相同if(distij) /有直接路径if(distik&distkj)if(distijdistik+distkj) /有中间更短路径distij=distik+distkj;elseif(distik&distkj)distij=distik+distkj;/取中间路径coutdistijendl;coutendl;void main()/主函数MGraph *g=(MGraph *)malloc(sizeof(MGraph);CreatGraph(g);cout*n邻接链表输出：n;PrintList(g);cout*n深度优先遍历：n;DFSTraverse(g);cout*n拓扑排序：;TopologicalSort(g);coutn*n最短路径:n;ShortestPath_FLOYD(g);4、 输出结果：五：上机结果及体会 1、实际完成情况说明： 本次数据结构课程设计，在同学以及老师的帮助下，完成了实验题目所要求的（1）建立并显示出它的邻接链表；（2）以非递归的方式进行深度优先遍历，显示遍历的结果，（并随时显示栈的入、出情况）（3）对该图进行拓扑排序，显示拓扑排序的结果，并随时 显示入度域的变化情况；（4）给出某一确定顶点到所有其他顶点的最短路径；四个基本功能要求。虽然在算法的选择上可能还有不足之处，但总体完成情况和进度还行，所以本次课程设计总体上还是成功的。2、课程设计遇到的问题及解决方法： 1.语法错误太多，由于大部分函数都是按照书上的思想进行设计的，思想是没问题的，可是书上存在印刷错误，语法错误比较容易，只需要根据说明逐个修改即可，此外还有大括号匹配错误。 2.出现了死循环，在输出邻接表的过程中出现了死循环，主要是循环过程中的条件出现了问题，修改后已经解决了，还要注意的是:必须按照输入格式进行输入，不然也可能出现错误。 3.