设计算法，将已有用邻接矩阵存储的带权图转换成邻接表表示。

Question：
设计算法，将已有用邻接矩阵存储的带权图转换成邻接表表示。
给出邻接矩阵和邻接表存储结构如下：

#define INFINITY 2000    //无穷大
#define MAX_VERTEX_NUM 20    //最多顶点个数

//邻接矩阵结构定义
Typedef struct ArcCell {
                    int adj;
                    int weight; //权值
} ArcCell, AdjMatrix [MAX_VERTEX_NUM] [MAX_VERTEX_NUM];

Typedef struct {
              char vex [MAX_VERTEX_NUM];  //顶点
              AdjMatrix arcs;
              int vexnum, arcnum;   //顶点和边的个数
} Mgraph;

//邻接表结构定义
Typedef struct ArcNode {
                     int adjvex;
                     struct ArcNode *nextarc;  //下一个邻接点
int weight;   //权值
} ArcNode;

Typedef struct Vnode {
                   char data;   //顶点
                   ArcNode *firstarc;  //第一个邻接点
} Vnode, AdjList [MAX_VERTEX_NUM];

Typedef struct {
              AdjList vertices;
              int vexnum, arcnum;   //顶点和边的个数
} ALGraph;

Solution

void GraphtoList(ALGraph *G,Mgraph M) 
{
                  
    ArcNode *p;             			//存储相邻接点结构体信息
    G->vexnum=M.vexnum;    		 //设置邻接表顶点数
    G->arcnum=M.arcnum;     		//设置邻接表边数
    int i,j,k;

    for(k=0;k<G->vexnum;k++)
    {   	//初始化邻接表起始顶点
        strcpy(G->vertices[k].data,M.vex[k]);
        G->vertices[k].firstarc=NULL;
    }

    for(i=0;i<M.arcnum;i++)
    {   	//遍历矩阵
        for(j=0;j<M.arcnum;j++)
        {
            if(M.arcs[i][j].adj==1)
            {   	//找到i邻接点，插入回原表i开头
                p=(ArcNode*)malloc(sizeof(ArcNode));
                p->adjvex=j;                           		//记录i邻接点序号
                p->nextarc=G->vertices[i].firstarc;     //头插法建立i的链表
                p->weight=M.arcs[i][j].weight;          	//记录权
                G->vertices[i].firstarc=p;        
            }
        }
    }
}