图的邻接表和邻接矩阵的相互转换.doc

#include#include#includetypedef int InfoType;typedef int Vertex;#define MAXV 5typedef struct int 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 struct Vnode Vertex data;ArcNode *firstarc;VNode;typedef VNode AdjListMAXV;typedef struct AdjList adjlist;int n,e;ALGraph;void InitialMG(MGraph *&MG) MG=new MGraph;MG-e=0;MG-n=5;int j;for(int i=0;ivexsi.no=i;for(i=0;iMAXV;i+)for(j=0;jedgesij=0;void InitialALG(ALGraph *&ALG) ALG=new ALGraph;ALG-n=5;ALG-e=0;for(int i=0;iadjlisti.data=i; ALG-adjlisti.firstarc=NULL;void InputALG(ALGraph *&ALG) int ch;ArcNode *p;coutendl请输入邻接表,以-1结束输入(形式如：4 ：5 5 6 -1)：endl;for(int i=0;in;i+) coutadjlisti.datach;if(ch!=-1) ALG-adjlisti.firstarc=new ArcNode;p=ALG-adjlisti.firstarc;p-adjvex=ch;p-nextarc=NULL; cinch;while(ch!=-1)p-nextarc=new ArcNode;p=p-nextarc;p-adjvex=ch;p-nextarc=NULL;cinch;void OutputALG(ALGraph *&ALG) ArcNode *p;cout邻接表如下：endl;for(int i=0;in;i+)coutadjlisti.dataadjlisti.firstarc;while(p!=NULL) coutadjvexnextarc;coutendl;void InputMG(MGraph *&MG) char H;cout请输入（H/N）(有向/无向):H;cout 请以矩阵的方式输入顶点关系：n;int j=0;for(int i=0;in;i+)for(j=0;jn;j+) cinMG-edgesij;for(i=0;in;i+)for(j=0;jn;j+)if(MG-edgesij=1) MG-e+;if(H=N) MG-e=MG-e/2;void OutputMG(MGraph *&MG) int j;coutendl图的邻接矩阵如下：endl;for(int i=0;in;i+)for(j=0;jn;j+)coutedgesijt;coutendl;coutn=MG-n;ALG-e=MG-e;for(i=0;in;i+) for(j=0;jn;j+) if(MG-edgesij!=0) p=new ArcNode;p-adjvex=j;p-nextarc=ALG-adjlisti.firstarc;ALG-adjlisti.firstarc=p;void ALGtoMG(ALGraph *&ALG,MGraph *MG) int i,j;ArcNode *p;MG-n=ALG-n;for(i=0;in;i+) if(ALG-adjlisti.firstarc!=NULL) p=ALG-adjlisti.firstarc;while(p!=NULL) MG-edgesip-adjvex=1;p=p-nextarc;for(i=0;in;i+) for(j=0;jn;j+) if(MG-edgesij!=1) MG-edgesij=0;void MatToList(MGraph g,ALGraph *&G) /将临街矩阵g转换成邻接表G int 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) p=(ArcNode *)malloc(sizeof(ArcNode);p-adjvex=j;p-nextarc=G-adjlisti.firstarc;G-adjlisti.firstarc=p;G-n=g.n;G-e=g.e;void ListToMat(ALGraph *G,MGraph &g) /将邻接表G转换为邻接矩阵g int i;ArcNode *p;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 main() / MGraph *MG;ALGraph *ALG;InitialALG(ALG);/InitialMG(MG);/InputMG(MG);/OutputMG(MG); InputALG(ALG); OutputALG(ALG);/Transchange(MG,ALG);/OutputALG(ALG);/