/* ======================================== */
/*    程式實例: 8_2_2.c                     */
/*    圖形的鄰接鏈表表示法                  */
/* ======================================== */
#include <stdlib.h>

struct node                       /* 圖形頂點結構宣告    */
{
   int vertex;                    /* 頂點資料            */
   struct node *nextnode;         /* 指下一頂點的指標    */
};
typedef struct node *graph;       /* 圖形的結構新型態    */
struct node head[6];              /* 圖形頂點結構數組    */

/* ---------------------------------------- */
/*  建立圖形                                */
/* ---------------------------------------- */
void creategraph(int *node,int num)
{
   graph newnode;                 /* 新頂點指標          */
   graph ptr;
   int from;                      /* 邊線的起點          */
   int to;                        /* 邊線的終點          */
   int i;

   for ( i = 0; i < num; i++ )    /* 讀取邊線的回路      */
   {
      from = node[i*2];           /* 邊線的起點          */
      to = node[i*2+1];           /* 邊線的終點          */
      /* 建立新頂點記憶體 */
      newnode = ( graph ) malloc(sizeof(struct node));
      newnode->vertex = to;       /* 建立頂點內容        */
      newnode->nextnode = NULL;   /* 設定指標初值        */
      ptr = &(head[from]);        /* 頂點位置            */
      while ( ptr->nextnode != NULL ) /* 遍歷至鏈表尾    */
         ptr = ptr->nextnode;     /* 下一個頂點          */
      ptr->nextnode = newnode;    /* 插入結尾            */
   }
}

/* ---------------------------------------- */
/*  主程式: 建立圖形后,將鄰接鏈表印出.      */
/* ---------------------------------------- */
void main()
{
   graph ptr;
   int node[12][2] = { {1, 2}, {2, 1},   /* 邊線數組     */
                       {1, 3}, {3, 1},
                       {2, 3}, {3, 2},
                       {2, 4}, {4, 2},
                       {3, 5}, {5, 3},
                       {4, 5}, {5, 4} };
   int i;

   for ( i = 1; i <= 5; i++ )
   {
      head[i].vertex = i;         /* 設定頂點值          */
      head[i].nextnode = NULL;    /* 清除圖形指標        */
   }
   creategraph(node,12);          /* 建立圖形            */
   printf("圖形的鄰接鏈表內容:\n");
   for ( i = 1; i <= 5; i++ )
   {
      printf("頂點%d =>",head[i].vertex);/* 頂點值       */
      ptr = head[i].nextnode;            /* 頂點位置     */
      while ( ptr != NULL )              /* 遍歷至鏈表尾 */
      {
         printf(" %d ",ptr->vertex);     /* 印出頂點內容 */
         ptr = ptr->nextnode;            /* 下一個頂點   */
      }
      printf("\n");                      /* 換行         */
   }
}