/* ======================================== */
/*    程式實例: 4_2_2.c                     */
/*    稀疏陣列的環狀鏈結串列表示法          */
/* ======================================== */
#include <stdlib.h>

struct clist                      /* 環狀串列結構宣告     */
{
   int row;                       /* 陣列的列             */
   int col;                       /* 陣列的行             */
   int data;                      /* 節點資料             */
   struct clist *right;           /* 指向同一列節點指標   */
   struct clist *down;            /* 指向同一行節點指標   */
};
typedef struct clist cnode;       /* 環狀串列新型態       */
typedef cnode *clink;             /* 環狀串列指標新型態   */

/* ---------------------------------------- */
/*  建立稀疏陣列的開頭節點陣列              */
/* ---------------------------------------- */
clink create_matrix(int row,int col)
{
   clink head;                    /* 稀疏陣列指標         */
   int len;                       /* 陣列的長度           */
   int i;

   /* 計算陣列長度,取行與列之最大值 */
   if ( row > col )
      len = row;
   else
      len = col;

   /* 配置開頭節點陣列陣列記憶體 */
   head = ( clink ) malloc(sizeof(cnode) * len);
   if ( !head )                   /* 檢查記憶體指標       */
      return NULL;
   head[0].row = row;             /* 陣列的列             */
   head[0].col = col;             /* 陣列的行             */

   for ( i = 0; i < len; i++ )    /* 用回路設定指標初值   */
   {
      head[i].right = &head[i];   /* 設定指標指向自己     */
      head[i].down = &head[i];    /* 設定指標指向自己     */
   }

   return head;                   /* 傳回稀疏陣列指標     */
}

/* ---------------------------------------- */
/*  稀疏陣列的陣列元素插入                  */
/* ---------------------------------------- */
clink insert_matrix(clink head,int row,int col,int value)
{
   clink new_node;                /* 新節點的指標         */
   clink pos;                     /* 插入的位置           */

   /* 建立新節點配置節點記憶體 */
   new_node = ( clink ) malloc(sizeof(cnode));
   if ( !new_node )               /* 檢查記憶體指標       */
      return NULL;
   /* 稀疏陣列的實際大小 */
   new_node->row = row;           /* 陣列的列             */
   new_node->col = col;           /* 陣列的行             */
   new_node->data = value;        /* 建立節點內容         */

   /* 插入由指標down接成行串列 */
   pos = &head[col];              /* 設定行串列指標       */
   /* 用回路來找插入列row */
   while ( pos->down != &head[col] && row > pos->down->row )
      pos = pos->down;            /* 指向下一個節點       */
   new_node->down = pos->down;    /* 新節點指向下一節點   */
   pos->down = new_node;          /* 前一節點指向新節點   */

   /* 插入由指標right接成列串列 */
   pos = &head[row];              /* 設定列串列指標       */
   /* 用回路來找插入行col */
   while ( pos->right != &head[row] && col > pos->right->col )
      pos = pos->right;           /* 指向下一個節點       */
   new_node->right = pos->right;  /* 新節點指向下一節點   */
   pos->right = new_node;         /* 前一節點指向新節點   */

   return head;                   /* 傳回稀疏陣列指標     */
}

/* ---------------------------------------- */
/*  稀疏陣列的列印                          */
/* ---------------------------------------- */
void print_matrix(clink head)
{
   clink ptr;
   clink now;
   int i;

   printf("  列   行     值 \n");
   printf("=================\n");

   /* 從down指標串成的串列來列印 */
   for ( i = 0; i < head[0].col; i++ )
   {
      now = head[i].down;
      ptr = &head[i];
      while  ( now != ptr )       /* 走訪指標down回路     */
      {
         printf("[%3d][%3d]=[%4d]\n",now->row,now->col,now->data);
         /* 列印節點資料 */
         now = now->down;         /* 指向下一個節點       */
      }
   }
}

/* ---------------------------------------- */
/*  主程式:                                 */
/*  使用環狀鏈結串列來建立稀疏陣列, 完成後  */
/*  將陣列內容印出.                         */
/* ---------------------------------------- */
void main()
{
   clink head;                    /* 稀疏陣列指標         */
   int sparse[5][6] = {           /* 稀疏陣列的內容       */
                         0, 0, 1, 0, 0, 0,
                         0, 3, 0, 9, 0, 0,
                         0, 4, 0, 0, 0, 2,
                         7, 0, 0, 0, 3, 0,
                         0, 0, 0, 6, 0, 0 };
   int i,j;

   head = create_matrix(5,6);     /* 建立稀疏陣列         */
   for ( i = 0; i < 5; i++ )      /* 二維陣列的走訪       */
      for ( j = 0; j < 6; j++ )
         if ( sparse[i][j] != 0 ) /* 有沒有使用           */
            /*  稀疏陣列的陣列元素插入 */
            head = insert_matrix(head,i,j,sparse[i][j]);
   print_matrix(head);            /* 列出陣列內容         */
}