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

./《数据结构》课程设计报告设计题目：以邻接矩阵方式确定有向网班级：：学号：完成日期：需求分析1、运行环境〔软、硬件环境：处理器：英特尔酷睿<Core>i5-2410MCPU2.30GHz物理存：2G操作系统：MicrosoftWindowns7开发环境：MicrosoftVisualStudio20082、程序所实现的功能：<1>建立并显示出它的邻接链表；〔2以非递归的方式进行深度优先遍历,显示遍历的结果,〔并随时显示栈的入、出情况；〔3对改图进行拓扑排序,显示拓扑排序的结果,并随时显示入度域的变化情况；〔4给出某一确定顶点到所有其他顶点的最短路径；3、程序的输入,包含输入的数据格式和说明：〔1输入节点数个数〔2输入顶点信息〔空格隔开〔3输入权值信息〔以弧尾值弧头值权值信息,空格隔开000结束；4、程序的输出,程序输出的形式：〔1邻接链表输出〔2深度优先遍历输出<3>拓扑排序输出〔4最短路径输出5、测试数据：〔1节点个数：5个〔2顶点信息：abcde〔3权值信息：ab1bc2cd3de4ad5dc6000设计说明1、算法设计的思想：建程序主要是通过建立一个图的模板类来调用相应的构造函数以及相应的成员函数来实现其功能,首先用结构体来存储边节点和顶点节点,用邻接矩阵来存储此有向图,遍历的过程采用双从循环来使得遍历达到最底端,最短路径采用了递归的思想循环调用最短路径函数来完成最短路径的查找,拓扑排序中首先优先输出入度为零的节点,然后通过删除该节点继续此过程进行排序。2、主要的数据结构设计说明：图的邻接矩阵结构设计：顶点数、弧数、矩阵数组、和点数组栈结构：包括栈顶和栈底点结构：包括顶点和弧相关的指针信息。3、程序的主要流程图：有向图深度优先遍历最短路径入度域变化拓扑排序输出邻接表有向图深度优先遍历最短路径入度域变化拓扑排序输出邻接表4、主要模块和函数:邻接矩阵创建有向网voidCreatGraph<MGraph*g>伪码：依次存储节点数、顶点信息、权值打印有向网的邻接矩阵voidPrintGraph<MGraph*g>伪码：依次打印邻接矩阵打印有向网的邻接表voidPrintList<MGraph*g>伪码：输出矩阵每行不为零值纵坐标对应的节点非递归深度优先遍历voidDFSTraverse<MGraph*g>伪码：1.从右向左依次把邻接矩阵第一行非零值纵坐标对应的节点数入栈,并将最后入栈值出栈；2.再将最后入栈值定为横坐标,重复上述操作,直到空； 3.出栈,重复第二步操作； 4.重复第三部操作,直到栈空；获取每个节点的入度voidFindInDegree〔伪码：获取邻接矩阵每行非零值个数拓扑排序intTopologicalSort<MGraph*g>伪码：1.先将度为零节点入栈2.出栈,对i号节点的每个邻接点入度减1 3.若入度减为0,则入栈 4.重复2,3步,直至栈空任意两点最短距离voidShortestPath_FLOYD<MGraph*g>伪码：先看两点之间有无直接路径,若有,则看有无通过中间点更短若无,则看有无中间点连通三、源程序代码：#include<iostream>#include<stdio.h>#include<stdlib.h>usingnamespacestd;#defineMAX_VERTEX_NUM20//最大顶点个数#defineSTACK_INIT_SIZE100//存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量#defineOVERFLOW0#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*top;//栈顶指针 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;}/*函数名称：InitStack函数功能描述：构造一个空栈函数调用之前的预备条件：定义邻接矩阵结构体返回后的处理：返回值〔如果有的话：OVERFLOW或OK函数的输入参数：SqStack&S函数的输出参数：函数的抽象算法〔伪码：存储分配*/intInitStack<SqStack&S>//构造一个空栈{ S.base=<int*>malloc<STACK_INIT_SIZE*sizeof<int>>; if<!S.base>//存储分配失败 returnOVERFLOW; S.top=S.base; S.stacksize=STACK_INIT_SIZE; returnOK;}/*函数名称：StackEmpty函数功能描述：判断栈是否为空栈函数调用之前的预备条件：已构造一个栈返回后的处理：返回值〔如果有的话：OK或ERROR函数的输入参数：SqStack&S函数的输出参数：函数的抽象算法〔伪码：栈底与栈顶比较*/intStackEmpty<SqStack&S>{ if<S.top==S.base>//空栈 returnOK; else returnERROR;}/*函数名称：Push函数功能描述：插入新的栈顶元素函数调用之前的预备条件：已构造一个栈返回后的处理：返回值〔如果有的话：OK函数的输入参数：SqStack&S,inte函数的输出参数：函数的抽象算法〔伪码：指针移动*/intPush<SqStack&S,inte>//插入新的栈顶元素{ 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; returnOK;}/*函数名称：GetTop函数功能描述：获取的栈顶元素函数调用之前的预备条件：已构造一个栈返回后的处理：返回值〔如果有的话：e或ERROR函数的输入参数：SqStack&S,inte函数的输出参数：函数的抽象算法〔伪码：指针移动*/intGetTop<SqStack&S,int&e>{ if<S.top==S.base> returnERROR; e=*<S.top-1>; returne;}/*函数名称：Pop函数功能描述：删除栈顶元素函数调用之前的预备条件：已构造一个栈返回后的处理：返回值〔如果有的话：e函数的输入参数：SqStack&S,int&e函数的输出参数：e函数的抽象算法〔伪码：指针移动*/intPop<SqStack&S,int&e>//删除栈顶元素{if<S.top==S.base> returnERROR; e=*--S.top; returne;}/*函数名称：CreatGraph函数功能描述：邻接矩阵创建有向网函数调用之前的预备条件：定义邻接矩阵结构体返回后的处理：返回值〔如果有的话：函数的输入参数：MGraph*g函数的输出参数：函数的抽象算法〔伪码：依次存储节点数、顶点信息、权值*/voidCreatGraph<MGraph*g>//邻接矩阵创建有向网{ inti,j,m,o,p; charr1,r2;//m权值 cout<<"请输入节点数：\n"; cin>>g->vexnum;//获取节点数 cout<<"请输入有向网顶点信息〔空格间开：\n"; for<i=1;i<=g->vexnum;i++>//获取顶点信息{ cin>>g->vexs[i].adj; } for<i=1;i<=g->vexnum;i++>//初始化邻接矩阵for<j=1;j<=g->vexnum;j++>{ g->arcs[i][j]=0;} cout<<"请输入权值信息<以弧尾值弧头值权值顺序,空格间开,000结束>:\n"; cin>>r1>>r2>>m;//权值信息 while<r1!='0'&&r2!='0'&&m!=0>//生成邻接矩阵转{ o=findnode<r1,g>; p=findnode<r2,g>; g->arcs[o][p]=m; cin>>r1>>r2>>m; }}/*函数名称：PrintList函数功能描述：打印有向网的邻接表函数调用之前的预备条件：已创建有向网CreatGraph返回后的处理：返回值〔如果有的话：函数的输入参数：MGraph*g函数的输出参数：g->vexs[j].adj函数的抽象算法〔伪码：输出矩阵每行不为零值纵坐标对应的节点*/voidPrintList<MGraph*g>//打印有向网的邻接表{ inti,j; for<i=1;i<=g->vexnum;i++>{ cout<<<g->vexs[i].adj>; for<j=1;j<=g->vexnum;j++>{ if<g->arcs[i][j]!=0>//获取非零值 { cout<<"-->"<<<g->vexs[j].adj>; }} cout<<"-->NULL\n";//一行结束,打印空}}/*函数名称：DFSTraverse函数功能描述：非递归深度优先遍历函数调用之前的预备条件：已创建有向网CreatGraph返回后的处理：返回值〔如果有的话：函数的输入参数：MGraph*g函数的输出参数：g->vexs[i].adj函数的抽象算法〔伪码：1.从右向左依次把邻接矩阵第一行非零值纵坐标对应的节点数入栈,并将最后入栈值出栈；2.再将最后入栈值定为横坐标,重复上述操作,直到空； 3.出栈,重复第二步操作； 4.重复第三部操作,直到栈空；*/voidDFSTraverse<MGraph*g>//非递归深度优先遍历{ intvisited[MAX_VERTEX_NUM],i=1,j,e=1;//visited[]标记向量,e出栈值 SqStacks; InitStack<s>; Push<s,i>;//首节点入栈 cout<<"插入栈顶元素：\n"<<i; cout<<"-->"<<g->vexs[i].adj<<endl; visited[i]=1;//有输出,即为1 while<!StackEmpty<s>> { i=e;//从e行开始 for<j=g->vexnum;j>=1;j-->//从右向左寻找 { if<g->arcs[i][j]&&<visited[j]!=1>>//非零即入栈 { Push<s,j>; cout<<"插入栈顶元素："<<j<<endl; } } Pop<s,e>;//该行最左非零值入栈 cout<<"删除栈顶元素："<<e<<endl; if<visited[e]!=1>//未被标记 { cout<<"-->"<<g->vexs[e].adj<<endl; visited[e]=1; } }}/*函数名称：FindInDegree函数功能描述：获取每个节点的入度,并存储在indegree数组中函数调用之前的预备条件：已创建有向网CreatGraph返回后的处理：返回值〔如果有的话：函数的输入参数：MGraph*g函数的输出参数：indegree[]函数的抽象算法〔伪码：获取邻接矩阵每行非零值个数*/voidFindInDegree<MGraph*g,intindegree[MAX_VERTEX_NUM]>//获取每个节点的入度,并存储在indegree数组中{ inti,j,n;//n入度 for<i=1;i<=g->vexnum;i++> { n=0; for<j=1;j<=g->vexnum;j++> if<g->arcs[j][i]>//每行非零值个数 n++; indegree[i]=n;//存储入度 }}/*函数名称：TopologicalSort函数功能描述：拓扑排序函数调用之前的预备条件：已创建有向网CreatGraph；获取每个节点的入度FindInDegree返回后的处理：返回值〔如果有的话：函数的输入参数：MGraph*g函数的输出参数：g->vexs[i].adj函数的抽象算法〔伪码：1.先将度为零节点入栈2.出栈,对i号节点的每个邻接点入度减1 3.若入度减为0,则入栈 4.重复2,3步,直至栈空*/intTopologicalSort<MGraph*g>//拓扑排序{ intindegree[MAX_VERTEX_NUM],i,j,k,count;//count输出顶点计数 SqStackS; FindInDegree<g,indegree>;//对各顶点求入度 InitStack<S>; for<i=1;i<=g->vexnum;i++>//建立零入度顶点栈 if<!indegree[i]>//入度为零入栈 Push<S,i>; count=0; while<!StackEmpty<S>> { Pop<S,i>; cout<<"\n-->"<<g->vexs[i].adj; ++count; for<j=1;j<=g->vexnum;j++> { if<g->arcs[i][j]> { k=j; if<!<--indegree[k]>> Push<S,k>; cout<<"\t此时"<<g->vexs[k].adj<<"入度："<<indegree[k];//若入度减为零,入栈 } } } if<count<g->vexnum> //有回路 returnERROR; else returnOK;}/*函数名称：ShortestPath_FLOYD函数功能描述：任意两点最短距离函数调用之前的预备条件：已创建有向网CreatGraph返回后的处理：返回值〔如果有的话：函数的输入参数：MGraph*g函数的输出参数：dist[i][j]函数的抽象算法〔伪码：先看两点之间有无直接路径,若有,则看有无通过中间点更短若无,则看有无中间点连通*/voidShortestPath_FLOYD<MGraph*g>//任意两点最短距离{intdist[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//dist[]两点间路径长度inti,j,k;for<i=1;i<=g->vexnum;i++>//初始化for<j=1;j<=g->vexnum;j++> dist[i][j]=g->arcs[i][j];for<i=1;i<=g->vexnum;i++> { for<j=1;j<=g->vexnum;j++> { cout<<g->vexs[i].adj<<"-->"<<g->vexs[j].adj<<":\t"; for<k=1;k<=g->vexnum;k++>if<i!=j&&i!=k&&j!=k>//三点互不相同 { if<dist[i][j]>//有直接路径 { if<dist[i][k]&&dist[k][j]> if<dist[i][j]>dist[i][k]+dist[k][j]>//有中间更短路径 dist[i][j]=dist[i][k]+dist[k][j]; } else { if<dist[i][k]&&dist[k][j]> dist[i][j]=dist[i][k]+dist[k][j];//取中间路径 } } cout<<dist[i][j]<<endl; } cout<<endl; }}voidmain<>//主函数{ MGraph*g=<MGraph*>malloc<sizeof<MGraph>>; CreatGraph<g>; cout<<"***********************************************\n邻接链表输出：\n"; PrintList<g>; cout<<"***********************************************\n深度优先遍历：\n"; DFSTraverse<g>; cout<<"***********************************************\n拓扑排序："; TopologicalSort<g>; cout<<"\n***********************************************\n最短路径:\n"; ShortestPath_FLOYD<g>;}输出结果：五：上机结果及体会1、实际完成情况说明：本次数据结构课程设计,在同学以及老师的帮助下,完成了实验题目所要求的〔1建立并显示出它的邻接链表；〔2以非递归的方式进行深度优先遍历,显示遍历的结果,〔并随时显示栈的入、出情况〔3对该图进行拓扑排序,显示拓扑排序的结果,并随时显示入度域的变化情况；〔4给出某一确定顶点到所有其他顶点的最短路