邻接表与邻接矩阵互换代码

#include #include typedef int InfoType; #define MAXV 100 /*最大顶点个数*/ /*以下定义邻接矩阵类型*/ typedef struct { int no; /*顶点编号*/ InfoType info; /*顶点其他信息*/ } VertexType; /*顶点类型*/ typedef struct /*图的定义*/ { int edges[MAXV][MAXV]; /*邻接矩阵*/ int vexnum,arcnum; /*顶点数，弧数*/ VertexType vexs[MAXV]; /*存放顶点信息*/ } MGraph; /*图的邻接矩阵类型*/ /*以下定义邻接表类型*/ typedef struct ANode /*弧的结点结构类型*/ { int adjvex; /*该弧的终点位置*/ struct ANode *nextarc; /*指向下一条弧的指针*/ InfoType info; /*该弧的相关信息,这里用于存放权值*/ } ArcNode;

#include 
#include 
typedef int InfoType;
#define	MAXV 100				/*最大顶点个数*/
/*以下定义邻接矩阵类型*/
typedef struct 
{  	
	int no;						/*顶点编号*/
	InfoType info;				/*顶点其他信息*/
} VertexType;					/*顶点类型*/

typedef struct  				/*图的定义*/
{  	
	int edges[MAXV][MAXV]; 		/*邻接矩阵*/
   	int vexnumarcnum;   		/*顶点数，弧数*/
	VertexType vexs[MAXV];		/*存放顶点信息*/
} 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 AdjList[MAXV];	/*AdjList是邻接表类型*/
typedef struct 
{	
	AdjList adjlist;         	/*邻接表*/
    int ne;                 	/*图中顶点数n和边数e*/
} ALGraph;                   	/*图的邻接表类型*/

#define INF 32767       /*INF表示∞*/

void MatToList（MGraph gALGraph *&G）
/*将邻接矩阵g转换成邻接表G*/
{
	int ijk=0n=g.vexnum;					/*n为顶点数*/ 
	ArcNode *p;
	G=（ALGraph *）malloc（sizeof（ALGraph））;
	for （i=0;i		G->adjlist[i].firstarc=NULL;

	for （i=0;i		for （j=n-1;j>=0;j--） // j from 0 to n-1;
			if （g.edges[i][j]!=0）				/*邻接矩阵的当前元素不为0*/
			{   
			   	p=（ArcNode *）malloc（sizeof（ArcNode））;	/*创建一个结点*p*/
				p->adjvex=j;
				p->info=g.edges[i][j];
				p->nextarc=G->adjlist[i].firstarc;		/*将*p链到链表后*/
				G->adjlist[i].firstarc=p;
				k++;
				printf（“ 边 k=%d[%d%d] “kijp->info）;
				printf（“\n“）;    /* 换行*/
			}
			
	G->n=n;
	G->e=g.arcnum;
}