/* 程式範例: Ch2-4e.c */
#include <stdio.h>
#include <stdlib.h>

#define MAX_TERMS    10  /* 稀疏矩陣的最大元素數 */
struct Term {            /* 稀疏矩陣的元素結構 */ 
   int row;              /* 元素的列數 */ 
   int col;              /* 元素的欄數 */ 
   int value;            /* 元素的值 */ 
};
struct sMatrix {         /* 稀疏矩陣的結構 */
   int rows;             /* 矩陣的列數 */ 
   int cols;             /* 矩陣的欄數 */ 
   int numOfTerms;       /* 矩陣的元素數 */ 
   struct Term smArr[MAX_TERMS];  /* 壓縮陣列的宣告 */
};
typedef struct sMatrix Matrix; /* 建立稀疏矩陣的新型態 */ 
Matrix m;                      /* 建立稀疏矩陣 */ 
/* 抽象資料型態的操作函數宣告 */
extern void createMatrix(int r,int c,int *arr);
extern void printMatrix();

/* 函數: 建立稀疏矩陣 */
void createMatrix(int r,int c,int *arr) {
   int i, j, count;
   m.rows = r;              /* 初始結構的成員變數 */
   m.cols = c; 
   count = 0;
   for ( i = 0; i < r; i++ )    /* 二維陣列的走訪 */
      for ( j = 0; j < c; j++ )
         if ( arr[i*c+j] != 0 ) {        /* 元素有值 */
            m.smArr[count].row = i;      /* 列數 */
            m.smArr[count].col = j;      /* 欄數 */
            /* 元素值 */
            m.smArr[count].value = arr[i*c+j];
            count++;
         }
   m.numOfTerms = count;
}
/* 函數: 顯示稀疏矩陣 */
void printMatrix() {
   int i;
   /* 顯示稀疏矩陣尺寸和項目數 */
   printf("尺寸: %d X %d", m.rows, m.cols);
   printf(" 項目數: %d\n", m.numOfTerms);
   printf("列row\t欄col\t值value\n");
   /* 顯示稀疏矩陣的各項目座標與值 */
   for ( i = 0; i < m.numOfTerms; i++) {
     printf(" %d\t%d",m.smArr[i].row,m.smArr[i].col);
     printf("\t%d\n", m.smArr[i].value);
   }  
}
/* 主程式 */ 
int main() {   
   /* 稀疏矩陣 */
   int sparse[6][9]  = { 0, 7, 0, 0, 0, 0, 0, 0, 0,
                                  0, 0, 0, 5, 0, 0, 0, 0, 3,
                                  0, 0, 0, 0, 0, 1, 0, 0, 0,
                                  2, 0, 0, 0, 4, 0, 0, 0, 0,
                                  0, 0, 8, 0, 0, 0, 0, 0, 0, 
                                  0, 0, 0, 0, 0, 0, 0, 9, 0};
   int *fp = &sparse[0][0];        /* 取得陣列的指標 */ 
   /* 建立稀疏矩陣物件 */
   createMatrix(6, 9, fp); 
   printMatrix();                  /* 顯示稀疏矩陣 */
   system("PAUSE");
   return 0;  
}