資料結構入門-稀疏矩陣

前導

稀疏矩陣（Sparse Matrix）是指在大多數元素為零的矩陣。由於存儲完整的稀疏矩陣會浪費大量內存，因此通常使用特殊的數據結構來存儲和操作稀疏矩陣。在 C 語言中，可以將稀疏矩陣的非零元素以row、column、value的方式存放。

如下圖所示:

程式碼實作

#include <stdio.h>

#define MAX 100  // 最大非零元素數量

// 三元組結構
typedef struct {
    int row, col, value;
} SparseMatrix;

// 輔助函式，列印稀疏矩陣
void displaySparseMatrix(SparseMatrix mat[], int size) {
    printf("Row\tCol\tValue\n");
    for (int i = 0; i < size; i++) {
        printf("%d\t%d\t%d\n", mat[i].row, mat[i].col, mat[i].value);
    }
}

int main() {
    int rows = 4, cols = 5;
    int sparseArray[4][5] = {
        {0, 0, 3, 0, 4},
        {0, 0, 5, 7, 0},
        {0, 0, 0, 0, 0},
        {0, 2, 6, 0, 0}
    };

    SparseMatrix sparse[MAX];
    int k = 0;

    // 轉換為三元組格式
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (sparseArray[i][j] != 0) {
                sparse[k].row = i;
                sparse[k].col = j;
                sparse[k].value = sparseArray[i][j];
                k++;
            }
        }
    }

    printf("Sparse Matrix (Triplet Representation):\n");
    displaySparseMatrix(sparse, k);

    return 0;
}

• 結構體定義 SparseMatrix
  • 透過 typedef 定義了一個名為 SparseMatrix 的結構體，包含 row、col、value 三個欄位，用來儲存稀疏矩陣中每個「非零」元素的位置與數值。
• 常數 MAX
  • 使用 #define MAX 100 定義最大非零元素數量，代表三元組陣列 SparseMatrix sparse[MAX] 最多能夠儲存 100 個非零元素。
• 輔助函式 displaySparseMatrix()
  • 接收存有三元組的陣列 mat[] 以及其中非零元素的總數 size。
  • 透過 for 迴圈，列印出所有三元組的 (row, col, value)，方便檢視稀疏矩陣內容。
• 主程式 main()
  • 設定 rows = 4, cols = 5，並建立一個 4×5 的二維陣列 sparseArray，其中僅部分元素非零。
  • 宣告 SparseMatrix sparse[MAX] 以及計數器 k = 0。
  • 使用雙層 for 迴圈走訪 sparseArray 每一個元素。
  • • 若元素不是 0，便將其列索引、行索引與實際值記錄到 sparse[k] 結構體中，並將 k++ 。
  • 最後，呼叫 displaySparseMatrix(sparse, k) 將三元組表示法印出來。

Sparse Matrix (Triplet Representation):
Row	Col	Value
0	2	3
0	4	4
1	2	5
1	3	7
3	1	2
3	2	6