习题5-图的邻接矩阵结构转为邻接链表结构.c

关于图的邻接矩阵结构转为邻接链表结构算法的相关的用c语言编写的一个源程序代码

#include "datastru.h"
#include <stdio.h>
#include <malloc.h>

MGRAPH create_mgraph()
{/*建立图的邻接矩阵*/
   int i,j,k;
   MGRAPH mg;

   mg.kind=2;
   printf("\n\n输入顶点数和边数(用逗号隔开) : ");
   scanf("%d,%d",&i,&j);fflush(stdin);
   mg.vexnum=i;
   mg.arcnum=j;
   printf("\n\n");
   for(i=0;i<mg.vexnum;i++)
     {printf("输入顶点 %d 的值 : ",i+1);
      scanf("%d",&mg.vexs[i]);  fflush(stdin);}
   for(i=0;i<mg.vexnum;i++)
     for(j=0;j<mg.vexnum;j++)
       mg.arcs[i][j]=0;
   for(k=1;k<=mg.arcnum;k++)
    {printf("输入第 %d 条边的起始顶点和终止顶点(用逗号隔开): ",k);
     scanf("%d,%d",&i,&j);
     fflush(stdin);
     while(i<1||i>mg.vexnum||j<1||j>mg.vexnum)
      { printf("输入错，重新输入: ");
	scanf("%d,%d",&i,&j);}
     mg.arcs[i-1][j-1]=1;
     mg.arcs[j-1][i-1]=1;}
   return mg;
}

ADJGRAPH mg_to_adjg(MGRAPH mg)
{ int i,j,n;
  ADJGRAPH adjg;
  EDGENODE *p;
  n=mg.vexnum;
  adjg.vexnum=mg.vexnum;
  adjg.arcnum=mg.arcnum;
  for(i=0;i<n;i++)
    {  adjg.adjlist[i].vertex=mg.vexs[i];
       adjg.adjlist[i].link=NULL;
       for(j=0;j<n;j++)
	if(j!=i && mg.arcs[i][j]==1)
	 {  p=malloc(sizeof(EDGENODE));
	    p->adjvex=j;
	    p->next=adjg.adjlist[i].link;
	    adjg.adjlist[i].link=p;
	 }
    }
  return adjg;
}

main()
{  MGRAPH mg;
   ADJGRAPH adjg;
   int i,j,n;
   EDGENODE *p;


   printf("\n建立图的邻接矩阵并转换为图的邻接链表\n");
   mg=create_mgraph();                             /*建立图的邻接矩阵*/
   printf("\n\n图的邻接矩阵显示: \n");             /*图的邻接矩阵显示*/
   n=mg.vexnum;
   for(i=0;i<n;i++)
   { for(j=0;j<n;j++)
      printf("<%d,%d>[%d] ",i+1,j+1,mg.arcs[i][j]);
     printf("\n");
   }
   adjg=mg_to_adjg(mg);                            /*图的邻接矩阵结构转换为图的邻接链表*/
   printf("\n");
   printf("\n\n图的邻接链表显示: \n");             /*图的邻接链表显示*/
   for(i=0;i<n;i++)
    { printf("<%d> %d",i,adjg.adjlist[i].vertex);
      p=adjg.adjlist[i].link;
      while(p!=NULL)
       { printf(" -> %d",p->adjvex);
	 p=p->next;
       }
      printf(" -> NULL");
      printf("\n");
    }
}