稀疏矩陣特性

非零元素極少（非零數 / 總元素 < 0.05）。三元組表示：每個非零元素存 (行, 列, 值)，按行優先順序存儲。

數據結構定義

template <class T>
struct Triple {
    T _value;
    size_t _row;
    size_t _col;
};

template <class T>
class SparseMatrix {
    vector<Triple<T>> _array;  // 三元組數組
    size_t _row, _col;          // 矩陣行數、列數
public:
    // 構造：從二維數組構建，invalid 為視為零的值（如 0）
    SparseMatrix(int* matrix, size_t row, size_t col, const T& invalid) 
        : _row(row), _col(col) {
        for (size_t i = 0; i < row; ++i)
            for (size_t j = 0; j < col; ++j)
                if (matrix[i*col + j] != invalid) {
                    Triple<T> t;
                    t._row = i; t._col = j; t._value = matrix[i*col + j];
                    _array.push_back(t);
                }
    }
    // ...
};

轉置算法：快速轉置（O(非零數 + 列數)）

普通轉置需掃描原三元組 列數 次（O(非零數×列數)）。快速轉置：

1. 統計每列非零個數 colCount[j]
2. 計算每列在新三元組中起始位置 colStart[j]（前綴和）
3. 掃描原三元組一次，直接放入新位置：newArray[colStart[t._col]++] = {t._col, t._row, t._value}

完整代碼（含展示與測試）

#include <iostream>
#include <vector>
using namespace std;

#define ROW 6
#define COL 5

template <class T>
struct Triple { T _value; size_t _row; size_t _col; };

template <class T>
class SparseMatrix {
    vector<Triple<T>> _array;
    size_t _row, _col;
public:
    SparseMatrix(int* matrix, size_t row, size_t col, const T& invalid)
        : _row(row), _col(col) {
        for (size_t i = 0; i < row; ++i)
            for (size_t j = 0; j < col; ++j)
                if (matrix[i*col + j] != invalid) {
                    _array.push_back({matrix[i*col + j], i, j});
                }
    }

    void Display() {
        size_t idx = 0;
        for (size_t i = 0; i < _row; ++i) {
            for (size_t j = 0; j < _col; ++j) {
                if (idx < _array.size() && _array[idx]._row == i && _array[idx]._col == j)
                    cout << _array[idx++]._value << " ";
                else
                    cout << "0 ";
            }
            cout << endl;
        }
        cout << endl;
    }

    // 快速轉置
    SparseMatrix<T> FastTranspose() {
        SparseMatrix<T> tmp(nullptr, _col, _row, 0); // 臨時矩陣
        tmp._array.resize(_array.size());
        vector colCount(_col, 0), colStart(_col, 0);
        // 1. 統計每列非零數
        for (auto& t : _array) colCount[t._col]++;
        // 2. 計算起始位置
        for (size_t j = 1; j < _col; ++j) colStart[j] = colStart[j-1] + colCount[j-1];
        // 3. 填充新三元組
        for (auto& t : _array) {
            size_t pos = colStart[t._col]++;
            tmp._array[pos] = {t._value, t._col, t._row}; // 行列互換
        }
        return tmp;
    }
};

void test() {
    int matrix[ROW][COL] = {
        {1,0,3,0,5}, {0,0,0,0,0}, {0,0,0,0,0},
        {1,0,3,0,5}, {0,0,0,0,0}, {0,0,0,0,0}
    };
    SparseMatrix<int> sm((int*)matrix, ROW, COL, 0);
    cout << "原矩陣:\n"; sm.Display();
    cout << "轉置後:\n"; sm.FastTranspose().Display();
}

int main() { test(); return 0; }

複雜度對比

nz 為非零元素數。快速轉置額外 O(cols) 空間換取線性時間，極大優化。