#include <stdio.h>

#include <malloc.h>

#include <time.h>

#define MAX 100

typedef char DataType;

typedef int VectorRelationType;

typedef char VectorType;

typedef struct arcell

{

   VectorRelationType adj;

   //DataType * data;

}arcell, adjmatrix[MAX][MAX];

//鄰接矩陣定義

typedef struct

{

   VectorType vexs[MAX]; //頂點向量

   adjmatrix arcs;       //鄰接矩陣

   int vexnum, arcnum;   //圖的當(dāng)前頂點數(shù)和邊數(shù)

// GraphType kind;

}MGraph;           

typedef struct ArcNode

{

   int adjvex;           //鄰接點在頭結(jié)點數(shù)組中的位置(下標)

   struct ArcNode * nextarc; //指向下一個表結(jié)點

   DataType * date;

}ArcNode;

//頂點結(jié)點

typedef struct VNode

{

   VectorType vexdata;

   ArcNode * firstarc;

}VNode, Adjlist[MAX];

//鄰接表類型定義

typedef struct

{

   Adjlist vexs;

   int vexnum, arcnum;

   //GraphType gtype;

}ALGraph;

//打印鄰接表

void TraverseG(ALGraph G)

{

   ArcNode * p;

   int i;

   printf("圖的鄰接表如下:\n");

   for(i = 0; i < G.vexnum; i++)

   {

      printf("%c ->", G.vexs[i].vexdata);

      p = G.vexs[i].firstarc;

      while(p)

      {

        printf("%d ->", p->adjvex);

        p = p->nextarc;

      }

      printf("NULL\n");

   }

}

//確定v在鄰接矩陣中位置

int Locatevex(ALGraph * G, VectorType v)

{

   int i;

   for(i = 0; i < G->vexnum; i++)

      if(G->vexs[i].vexdata == v)

        return (i);

   return -1;

}

int locatevexM(MGraph * G, VectorType v)

{

   int i;

   for(i = 0; i < G->vexnum; i++)

      if(G->vexs[i] == v)

        return (i);

   return -1;

}

//建立鄰接矩陣

void CreateMGraph(MGraph * G)

{

   int i, j, k, w;

   VectorType u, v;

   printf("創(chuàng)建有向圖的鄰接矩陣\n");

   printf("請輸入當(dāng)前的頂點數(shù)和弧數(shù)(vex arc): \n");

   fflush(stdin);        //清空輸入緩沖區(qū)，確保不影響后面的數(shù)據(jù)讀取

   scanf("%d %d", &G->vexnum, &G->arcnum);

   for(i = 0; i < G->vexnum; i++)

   {

      printf("請輸入第%d個頂點(vertex): \n", i+1);

      fflush(stdin);

      scanf("%c", &G->vexs[i]);

   }

   for(i = 0; i < G->vexnum; i++)

   {

      for(j = 0; j < G->vexnum; j++)

      {

        G->arcs[i][j].adj = 0;

      }

   }

   for(k = 0; k < G->arcnum; k++)

   {

      printf("請輸入頂點和權(quán)值<u v w): \n");

      fflush(stdin);

      scanf("%c %c %d", &u, &v, &w);

      i = locatevexM(G, u);

      j = locatevexM(G, v);

      G->arcs[i][j].adj = w;

   }

}

void CreateALGraph(ALGraph * G)

{

   int i, j, k;

   ArcNode * s;

   char u, v;

   printf("請輸入當(dāng)前頂點數(shù)和弧數(shù)(vex arc):\n");

   fflush(stdin);

   scanf("%d %d", &G->vexnum, &G->arcnum);

   printf("首先輸入頂點:\n");

   for(i = 0; i < G->vexnum; i++)

   {

      printf("請輸入頂點%d,回車輸入下一個頂點\n", i);

      fflush(stdin);

      scanf("%c", &(G->vexs[i].vexdata));

      G->vexs[i].firstarc = NULL;

   }

   printf("接下來輸入弧:\n");

   for(k = 0; k < G->arcnum; k++)

   {

      printf("請輸入弧%d, 回車輸入下一條弧\n", k);

      fflush(stdin);

      scanf("%c %c", &u, &v);

      i = Locatevex(G, u);

      j = Locatevex(G, v);

      s = (ArcNode *)malloc(sizeof(ArcNode));

      s->adjvex = j;

      s->nextarc = G->vexs[i].firstarc;

      G->vexs[i].firstarc = s;

   }

}

void Print_MGraph(MGraph * G)

{

   int i, j;

   printf("\n");

   printf("鄰接矩陣輸入如下: \n");

   printf("[]");

   for(i = 0; i < G->vexnum; i++)

      printf("%c ", G->vexs[i]);

   printf("\n");

   for(i = 0; i < G->vexnum; i++)

   {

      printf("%c ", G->vexs[i]);

      for(j = 0; j < G->vexnum; j++)

        printf("%d ", G->arcs[i][j].adj);

      printf("\n");

   }

}

//鄰接表轉(zhuǎn)換為鄰接矩陣

void list_to_mat(ALGraph * AG, MGraph * MG)

{

   int i, j;

   ArcNode * p;

   MG->vexnum = AG->vexnum;

   for(i = 0; i < AG->vexnum; i++)

   {

      for(j = 0; j < AG->vexnum; j++)

      {

        MG->arcs[i][j].adj = 0;

      }

   }

   for(i = 0; i < AG->vexnum; i++)

   {

      MG->vexs[i] = AG->vexs[i].vexdata;

   }

   printf("圖的頂點向量如下:\n");

   for(i = 0; i < AG->vexnum; i++)

   {

      printf("%d %c\n", i, MG->vexs[i]);

   }

   for(i = 0; i < AG->vexnum; i++)

   {

      p = AG->vexs[i].firstarc;

      while(p != NULL)

      {

        MG->arcs[i][p->adjvex].adj = 1;

        p = p->nextarc;

      }

   }

}

void main()

{

   MGraph  MG;

   ALGraph AG;

   CreateALGraph(&AG);

   TraverseG(AG);

   list_to_mat(&AG, &MG);

   Print_MGraph(&MG);

   CreateMGraph(&MG);

   Print_MGraph(&MG);

}