实现图的邻接矩阵和邻接表存储.doc

#include#include#define MAXV 100/以下定义邻接矩阵类型typedef struct int no; /顶点编号 int info; /顶点其余的信息 VertexType;typedef struct int edgesMAXVMAXV; /邻接矩阵 int n,e; /顶点数，弧数 VertexType vexsMAXV; /存放顶点信息MGraph;/一下定义邻接表类型typedef struct ANode /弧的节点结构类型 int adjvex; /该弧的终点位置 struct ANode *nextarc; int info; /弧的相关信息 ArcNode;typedef struct Vnode /邻接表头结点类型 int data; /顶点信息 ArcNode *firstarc; /指向第一条弧VNode;typedef VNode AdjListMAXV;typedef struct AdjList adjlist; int n,e;ALGraph;void MatToList(MGraph g,ALGraph *&G) /将邻接矩阵 g 转换为邻接表 G int i,j,n=g.n; ArcNode *p; G=(ALGraph *)malloc(sizeof(ALGraph); for(i=0;iadjlisti.firstarc=NULL; for(i=0;i=0;j-) if(g.edgesij) p=(ArcNode *)malloc(sizeof(ArcNode); p-adjvex=j; p-info=g.edgesij; p-nextarc=G-adjlisti.firstarc; G-adjlisti.firstarc=p; G-n=n; G-e=g.e;void ListToMat(ALGraph *G,MGraph &g) /邻接表G转换为邻接矩阵g int i,j,n=G-n; ArcNode *p; for(i=0;in;i+) for(j=0;jn;j+) g.edgesij=0; for(i=0;iadjlisti.firstarc; while(p) g.edgesip-adjvex=p-info; p=p-nextarc; g.n=n; g.e=G-e;void DispMat(MGraph g) /输出邻接矩阵 int i,j; for(i=0;ig.n;i+) for(j=0;jg.n;j+) if(g.edgesij) printf(%3d,g.edgesij); else if(i=j) printf(%3d,0); else printf(%3s,*); printf(n); void DispAdj(ALGraph *G) /输出邻接表 int i; ArcNode *p; for(i=0;in;i+) p=G-adjlisti.firstarc; if(p) printf(%3d:,i); while(p) printf(%3d,p-adjvex); p=p-nextarc; printf(n); int main() int i,j; MGraph g,g1; ALGraph *G; int AMAXV6= 0,5,0,7,0,0, 0,0,4,0,0,0, 8,0,0,0,0,9, 0,0,5,0,0,6, 0,0,0,5,0,0, 3,0,0,0,1,0 ; g.n=6; g.e=10; for(i=0;ig.n;i+) for(j=0;jg.n;j+) g.edgesij=Aij; printf(n); printf(有向图G的邻接矩阵是：n); DispMat(g); G=(ALGraph *)malloc(sizeof(ALGraph); printf(图G的邻接矩阵转换成邻接表：n); MatToList(g,G); D