C++ 數組應用：特殊矩陣壓縮存儲完全指南

矩陣壓縮存儲的動機

數值計算中常遇到高階矩陣，包含大量相同值或零值元素。為節省儲存空間，需進行壓縮存儲：不存或少存這些元素。對象包括：

• 稀疏矩陣：非零元素極少。
• 特殊矩陣：零元素或相同值元素分布有規律（對稱、三角、帶狀等）。

特殊矩陣壓縮存儲

1. 對稱矩陣

滿足 a[i][j] == a[j][i]。僅存下三角（含對角線），空間 n(n+1)/2。一維陣列 sa[k] 映射公式：

// 行優先映射下三角
k = i*(i+1)/2 + j  (i ≥ j)
// 例：a[4][2] → k = 4*5/2 + 2 = 12

2. 三角矩陣

上/下三角矩陣存儲方式類似對稱矩陣，同樣只需 n(n+1)/2 空間。

3. 帶狀矩陣

非零元素集中在主對角線兩側帶寬 d 內。非零元素數 (2d+1)n - (1+d)d。為計算方便，每行固定分配 2d+1 空間，總大小 n(2d+1)。映射公式：

k = i*(2d+1) + d + (j - i)
// i*(2d+1)：前 i 行元素數
// d+(j-i)：第 i 行中第 j 列前的偏移（i=j 為分水嶺）

稀疏矩陣：三元組順序表

僅存儲非零元素的 (row, col, value) 三元組。

抽象資料型別定義

template <class Type>
class Trituple {
    friend class SparseMatrix<Type>;
private:
    int row, col;
    Type value;
};

template <class Type>
class SparseMatrix {
    int Rows, Cols, Terms;
    Trituple<Type> smArray[MaxTerms];
public:
    SparseMatrix(int MaxRow, int MaxCol);
    SparseMatrix<Type> Transpose();      // 轉置
    SparseMatrix<Type> Add(SparseMatrix<Type> b);      // 相加
    SparseMatrix<Type> Multiply(SparseMatrix<Type> b); // 相乘
};

稀疏矩陣轉置演算法

簡單轉置（O(Cols × Terms)）

掃描 Cols 次，每次找列號為 k 的三元組，交換 row/col 存入結果。

template <class Type>
SparseMatrix<Type> SparseMatrix<Type>::Transpose() {
    SparseMatrix<Type> b(Cols, Rows);
    b.Rows = Cols; b.Cols = Rows; b.Terms = Terms;
    if (Terms > 0) {
        int CurrentB = 0;
        for (int k = 0; k < Cols; k++)
            for (int i = 0; i < Terms; i++)
                if (smArray[i].col == k) {
                    b.smArray[CurrentB].row = k;
                    b.smArray[CurrentB].col = smArray[i].row;
                    b.smArray[CurrentB].value = smArray[i].value;
                    CurrentB++;
                }
    }
    return b;
}

快速轉置（O(Terms + Cols)）

引入兩個輔助陣列：

• rowSize[col]：統計各列非零元素數（轉置後各行非零數）。
• rowStart[row]：各行在轉置三元組表中的起始位置。

// 統計 rowSize
for (int i = 0; i < Cols; i++) rowSize[i] = 0;
for (int j = 0; j < Terms; j++) rowSize[smArray[j].col]++;

// 計算 rowStart
rowStart[0] = 0;
for (int i = 1; i < Cols; i++) rowStart[i] = rowStart[i-1] + rowSize[i-1];

// 一掃描完成轉置
for (int i = 0; i < Terms; i++) {
    int j = rowStart[smArray[i].col];
    b.smArray[j].row = smArray[i].col;
    b.smArray[j].col = smArray[i].row;
    b.smArray[j].value = smArray[i].value;
    rowStart[smArray[i].col]++;
}

複雜度對比

例：Rows=500, Cols=100, Terms=10000 → 簡單 O(5,000,000) vs 快速 O(10,100)，效率差距百倍。