《数据结构实验六》由会员分享，可在线阅读，更多相关《数据结构实验六（8页珍藏版）》请在金锄头文库上搜索。
1、输出编写一个程序algo8-1,实现不带权图和带权图的邻接矩阵和邻接表的相互转换算法、 邻接矩阵与邻接表的运算，并在此基础上设计一个主程序完成如下功能：（1）建立如图所示的有向图G的邻接矩阵，并输出之；（2）由有向图G的邻接矩阵产生邻接表，并输出之；（3）再由（2）的邻接表产生对应的邻接矩阵，并输出之。/最大顶点个数/INF表示8顶点编号顶点其它信息顶点类型图的定义邻接矩阵顶点数，边数/存放顶点信息图的邻接矩阵类型边的节点结构类型该边的终点位置/指向下一条边的指针该边的相关信息，这里用于存放权值图8. 1 一个带权有向图G文件graph.h定义了图的邻接矩阵表示类型和邻接表表示类型，该头文件在
2、代码如下:typedef int InfoType;#define MAXV 100#define INF 32767以下定义邻接矩阵类型typedef structint no;InfoType info; VertexType;typedef structint edgesMAXVMAXV; int n,e;VertexType vexsMAXV; MGraph;以下定义邻接表类型typedef struct ANodeint adjvex;struct ANode * nextarc;InfoType info; ArcNode;邻接表头节点的类型顶点信息/指向第一条边/AdjList是
3、邻接表类型/邻接表图中顶点数n和边数e图的邻接表类型typedef int Vertex;typedef struct VnodeVertex data;ArcNode * firstarc; VNode;typedef VNode AdjListMAXV;typedef structAdjList adjlist;int n,e; ALGraph;Algo8-1.cpp的代码如下：#include#include #includegraph.h”/不带权图的算法/void MatToList(MGraph g,ALGraph * &G)int i,j;ArcNode * p;G=(ALGra
4、ph * )malloc(sizeof(ALGraph);for(i=0;iadjlisti.firstarc=NULL;for(i=0;i=0;j-)if(g.edgesij!=0)/将邻接矩阵g转换成邻接表G给邻接表中所有节点的指针域置初值检查邻接矩阵中每个元素邻接矩阵的当前元素不为0创建一个节点* p/将* p链到链表后/将邻接表G转换成邻接矩阵g/ g.edgesij赋初值 0p=(ArcNode * )malloc(sizeof(ArcNode);p-adjvex=j;p-nextarc=G-adjlisti.firstarc;G-adjlisti.firstarc=p;G-n=g.
5、n;G-e=g.e;void ListToMat(ALGraph * GMGraph &g)int i,j;ArcNode * p;for(i=0;in;i+)for(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)int i,j;for(i=0;ig.n;i+)for(j=0;jg.n;j+)printf(%3d,g.edgesij);printf(n);vo
6、id DispAdj(ALGraph * G)int 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) int i,j;ArcNode * p;输出邻接矩阵g输出邻接表G/将邻接矩阵g转换成邻接表GG=(ALGraph *)malloc(sizeof(ALGraph);for(i=0;iadjlisti.f
7、irstarc=NULL;for(i=0;i=0;j-)/存在一条边创建一个节点* p/将* p链到链表后if(g.edgesij!=0&g.edgesij!=INF)p=(ArcNode * )malloc(sizeof(ArcNode);p-adjvex=j;p-info=g.edgesij;p-nextarc=G-adjlisti.firstarc;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;
8、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”,”8”)；el
9、seprintf(%3d”,g.edgesij);printf(n); void DispAdj1(ALGraph * G)输出邻接表 G int 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.h”extern void MatToList1(MGraph,ALGraph *
10、 &);以下外部函数在 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
11、;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 * )malloc(sizeof(ALGraph);printf(”图G的邻接矩阵转换成邻接表:n);MatToList1(g,G);DispAdj1(G);printf(”图G的邻接表转换成邻接矩阵:n);ListToMat1(Gg1);DispMat1(g1);连编本工程可生成可执行文件Proj8_1.exe。执行结果如下:/ , D: D-ebugP roj 8_1. exeH|有向图晞邻接矩障7CO I0 oo5 aOO 5co co5 OO a 4 co co co coCOcococoa1COco9I图啪邻接矩阵转换成邻接表;1 （5）3 （7）2& （8）5 （?）2 （5）5 （6）5； S(3)4 (1)图曲邻接表转换成邻接矩阵;：S 8 7 1 0 4 1 ；co a oo Q OO S 回 oo oo 5； co co co*res：s keyco co oo oo01I tococooo0continue
