稀疏矩陣的十字鏈表存儲與加法運算 C++ 實現

稀疏矩陣定義：「非零元較少且分布無規律」。清華 2000 考研題曾引發爭議：1000 階、1000 邊的鄰接矩陣是否稀疏？舊教材（嚴蔚敏版）強調「分布無規律」，故答案為「不一定」（可能為特殊矩陣）；新教材（黃皮書）取消特殊矩陣概念，統稱非零元少者為稀疏矩陣。筆者傾向新定義：統一建模雖犧牲微小空間/效率，卻大幅降低認知負擔。

十字鏈表邏輯結構

類比圍棋盤：行/列表頭節點構成網格線，非零元節點為棋子。每個非零元節點含 data、row、col、right（同行下一非零元）、down（同列下一非零元）。行/列表頭節點同樣鏈接成鏈表，最終由一總頭指針訪問。

註：row/col 域雖非邏輯必需（可走鏈表定位），但為加法/乘法運算效率，必須保留。

節點與矩陣類定義

class MatNode {
public:
    int data, row, col;
    union { Node<MatNode> *down; List<MatNode> *downrow; };
    MatNode(int v=0, Node<MatNode>* p=NULL, int i=0, int j=0)
        : data(v), down(p), row(i), col(j) {}
    friend ostream& operator<<(ostream& strm, MatNode& mtn) {
        return strm << '(' << mtn.row << ',' << mtn.col << ')' << mtn.data;
    }
};
class Matrix : List<MatNode> {
public:
    Matrix() : row(0), col(0), num(0) {}
    Matrix(int r, int c, int n) : row(r), col(c), num(n) {}
    ~Matrix() { MakeEmpty(); }
    void MakeEmpty() { /* 釋放所有行列表頭及數據節點 */ }
    void Input();      // 按列序輸入非零元
    void Print();      // 輸出各行鏈表
    Matrix& Add(Matrix& matB); // 矩陣加法
private:
    int row, col, num;
};

關鍵算法：矩陣加法

類比一元多項式相加，但雙變元（行、列）導致指針維護更複雜。採用輔助指針陣列 pAT、pBT 記錄各列當前處理節點，實現同列合併、異列插入/銜接。核心邏輯：

1. 初始化：檢查維度一致，建立列指針陣列指向兩矩陣各列首節點。
2. 逐行處理：對每一行，同步遍歷兩矩陣該行鏈表。
3. 同列合併：數值相加，若結果為 0 則雙向刪除節點；否則更新列指針。
4. 矩陣 B 獨有列：將節點從 B 移至 A，維護行/列雙向鏈接。
5. 矩陣 A 獨有列：僅更新列指針陣列。
6. 行尾收尾：若 B 仍有剩餘節點，整體掛接到 A 行尾。

Matrix& Add(Matrix& matB) {
    if (row != matB.row || col != matB.col || matB.num == 0) return *this;
    Node<MatNode> **pAT = new Node<MatNode>*[col+1];
    Node<MatNode> **pBT = new Node<MatNode>*[matB.col+1];
    // 初始化列指針陣列...
    for (int i=1; i<=row; i++) {
        // 逐行合併邏輯...
    }
    delete []pAT; delete []pBT;
    return *this;
}

設計感悟

十字鏈表核心在於「每個節點操作必須同步維護行、列兩個指針域」。書中為省表頭節點將行/列頭合併，反而增加理解難度，教學不如分離清晰。本實現雖未極致優化，但邏輯直觀，便於教學與擴展。矩陣乘法同理可構建，留待讀者嘗試。