数据结构实验六.doc

编写一个程序algo8-1，实现不带权图和带权图的邻接矩阵和邻接表的相互转换算法、输出邻接矩阵与邻接表的运算，并在此基础上设计一个主程序完成如下功能：（1） 建立如图所示的有向图G的邻接矩阵，并输出之；（2） 由有向图G的邻接矩阵产生邻接表，并输出之；（3） 再由（2）的邻接表产生对应的邻接矩阵，并输出之。文件graph.h定义了图的邻接矩阵表示类型和邻接表表示类型，该头文件在代码如下：typedef int InfoType;#define MAXV 100 /最大顶点个数#define INF 32767 /INF表示/以下定义邻接矩阵类型typedef structint no; /顶点编号InfoType info; /顶点其它信息 VertexType; /顶点类型typedef struct /图的定义int edgesMAXVMAXV; /邻接矩阵int n,e; /顶点数，边数VertexType vexsMAXV; /存放顶点信息 MGraph; /图的邻接矩阵类型/以下定义邻接表类型typedef struct ANode /边的节点结构类型int adjvex; /该边的终点位置struct ANode * nextarc; /指向下一条边的指针InfoType info; /该边的相关信息，这里用于存放权值 ArcNode;typedef int Vertex;typedef struct Vnode /邻接表头节点的类型Vertex data; /顶点信息ArcNode * firstarc; /指向第一条边 VNode;typedef VNode AdjListMAXV; /AdjList是邻接表类型typedef structAdjList adjlist; /邻接表int n,e; /图中顶点数n和边数e ALGraph; /图的邻接表类型Algo8-1.cpp的代码如下：#include#include#includegraph.h/-/-不带权图的算法-/-void MatToList(MGraph g,ALGraph * &G) /将邻接矩阵g转换成邻接表Gint i,j;ArcNode * p;G=(ALGraph * )malloc(sizeof(ALGraph);for(i=0;iadjlisti.firstarc=NULL;for(i=0;i=0;j-)if(g.edgesij!=0) /邻接矩阵的当前元素不为0p=(ArcNode * )malloc(sizeof(ArcNode); /创建一个节点 * pp-adjvex=j;p-nextarc=G-adjlisti.firstarc; /将* p链到链表后G-adjlisti.firstarc=p;G-n=g.n;G-e=g.e;void ListToMat(ALGraph * G,MGraph &g) /将邻接表G转换成邻接矩阵gint i,j;ArcNode * p; for(i=0;in;i+) / g.edgesij赋初值0for(j=0;jn;j+)g.edgesij=0;for(i=0;in;i+)p=G-adjlisti.firstarc;while(p!=NULL)g.edgesip-adjvex=1;p=p-nextarc;g.n=G-n;g.e=G-e;void DispMat(MGraph g) /输出邻接矩阵gint i,j;for(i=0;ig.n;i+)for(j=0;jg.n;j+)printf(%3d,g.edgesij);printf(n);void DispAdj(ALGraph * G) /输出邻接表Gint i;ArcNode * p;for(i=0;in;i+) p=G-adjlisti.firstarc;printf(%3d:,i);while(p!=NULL)printf(%3d,p-adjvex);p=p-nextarc;printf(n);/-/-带权图的算法-/-void MatToList1(MGraph g,ALGraph * &G) /将邻接矩阵g转换成邻接表Gint i,j;ArcNode * p;G=(ALGraph *)malloc(sizeof(ALGraph);for(i=0;iadjlisti.firstarc=NULL;for(i=0;i=0;j-)if(g.edgesij!=0&g.edgesij!=INF) /存在一条边p=(ArcNode * )malloc(sizeof(ArcNode); /创建一个节点 * pp-adjvex=j;p-info=g.edgesij;p-nextarc=G-adjlisti.firstarc; /将* p链到链表后G-adjlisti.firstarc=p;G-n=g.n;G-e=g.e;void ListToMat1(ALGraph * G,MGraph &g) /将邻接表G转换成邻接矩阵gint i,j;ArcNode * p;for(i=0;in;i+) / g.edgesij赋初值0for(j=0;jn;j+)if(i=j)g.edgesij=0;elseg.edgesij=INF;for(i=0;in;i+)p=G-adjlisti.firstarc;while(p!=NULL)g.edgesip-adjvex=p-info;p=p-nextarc;g.n=G-n;g.e=G-e;void DispMat1(MGraph g) /输出邻接矩阵gint i,j;for(i=0;i,g.n;i+)for(i=0;ig.n;i+)for(j=0;jg.n;j+)if(g.edgesij=INF)printf(:%3d,);elseprintf(%3d,g.edgesij);printf(n);void DispAdj1(ALGraph * G) /输出邻接表Gint i;ArcNode * p;for(i=0;in;i+)p=G-adjlisti.firstarc;printf(%3d:,i);while(p!=NULL)printf(%3d(%d),p-adjvex,p-info);p=p-nextarc;printf(n);主程序exp8-1.cpp代码如下：#include#include#includegraph.hextern void MatToList1(MGraph,ALGraph * &); /以下外部函数在algo8-1.cpp中extern void ListToMat1(ALGraph * ,MGraph &);extern void DispMat1(MGraph);extern void DispAdj1(ALGraph * );void mian()int i,j;MGraph g,g1;ALGraph * G;int AMAXV6=0,5,INF,7,INF,INF,INF,0,4,INF,INF,INF,8,INF,0,INF,INF,9,INF,INF,5,0,INF,6,INF,INF,INF,5,0,INF,3,INF,INF,INF,1,0;g.n=6;g.e=10; /建立图8-1中有带向标图G的邻接矩阵for(i=0;ig.n;i+)for(j=0;jg.n;j+)g.edgesij=Aij;printf(有向图G的邻接矩阵:n);DispMat1(g);G=(ALGraph