基於 C++ 十字鏈表的稀疏矩陣乘法運算器實現

問題背景

稀疏矩陣非零元素極少。採用十字鏈表 (Orthogonal List) 儲存非零元，按行列雙向鏈接，大幅節省空間並加速乘法運算。

資料結構定義

typedef struct OLNode {
    int i, j;           // 行、列索引
    ElemType e;         // 非零值
    struct OLNode *right, *down; // 同行下一個、同列下一個
} OLNode, *OLink;

typedef struct {
    OLink *rhead, *chead; // 行頭、列頭指標陣列
    int mu, nu, tu;       // 行數、列數、非零元總數
} CrossList;

核心演算法

1. 建立稀疏矩陣 CreateSMatrix_OL

• 輸入三元組 (i, j, e)，以 i=0 結束。
• 分配行頭陣列 rhead[mu+1]、列頭陣列 chead[nu+1]，初始化為 NULL。
• 插入節點時，維持行列有序：行鏈按 j 遞增，列鏈按 i 遞增。

2. 稀疏矩陣乘法 MultSMatrix (三元組順序表法)

雖儲存用十字鏈表，運算轉換為三元組順序表 (RLSMatrix) 以利隨機存取：

Status MultSMatrix(RLSMatrix M, RLSMatrix N, RLSMatrix &Q) {
    if (M.nu != N.mu) return ERROR;  // 維度不合
    Q.mu = M.mu; Q.nu = N.nu; Q.tu = 0;
    if (M.tu * N.tu == 0) return OK; // 零矩陣

    // 累加器陣列，大小 N.nu
    ElemType *ctemp = new ElemType[N.nu + 1];

    for (int arow = 1; arow <= M.mu; ++arow) {
        memset(ctemp, 0, sizeof(ElemType) * (N.nu + 1));
        Q.rpos[arow] = Q.tu + 1;  // 記錄 Q 第 arow 行起始位置

        // 遍歷 M 第 arow 行非零元
        for (int p = M.rpos[arow]; p < M.rpos[arow+1]; ++p) {
            int brow = M.data[p].j;  // M 的列 = N 的行
            int t = (brow < N.nu) ? N.rpos[brow+1] : N.tu + 1;

            // 遍歷 N 第 brow 行非零元
            for (int q = N.rpos[brow]; q < t; ++q) {
                int ccol = N.data[q].j;
                ctemp[ccol] += M.data[p].e * N.data[q].e; // 累加乘積
            }
        }

        // 壓縮存儲 Q 第 arow 行非零結果
        for (int ccol = 1; ccol <= Q.nu; ++ccol) {
            if (ctemp[ccol]) {
                if (++Q.tu > MAXSIZE) return ERROR;
                Q.data[Q.tu] = {arow, ccol, ctemp[ccol]};
            }
        }
    }
    return OK;
}

複雜度分析

• 初始化累加器：O(M.mu * N.nu)
• 核心乘法累加：O(M.tu * N.tu / N.mu) (平均每行非零元數)
• 壓縮存儲：O(M.mu * N.nu)
• 總時間：O(M.mu * N.nu + M.tu * N.tu / N.mu)

調試關鍵點

• 十字鏈表插入時，區分矩陣列索引與鏈表節點列屬性，避免混淆。
• 行列頭陣列大小取決於 mu、nu，須正確分配 mu+1、nu+1。
• 乘法中 brow 對應 N 的行，邊界檢查 brow < N.nu 決定 t 取值。

測試案例驗證

M = [4 -3 0 0]   N = [1 3 0 0 0]
    [1 3 0 0 0]      [-6 0 0 0 8]
    [0 0 1 0 0]      [0 1 0 0 0]
    [0 0 0 0 7]      [0 0 0 0 0]

Q = M × N = [22 6 0 0 32]
            [0 1 0 0 0]
            [0 0 1 0 0]
            [0 0 0 0 0]

教學價值總結

本實作完整展示：稀疏矩陣儲存選型 (十字鏈表)、建立過程有序插入、乘法核心累加器模式、三元組順序表轉換運算、邊界條件處理。為初學者理解「資料結構服務於演算法」提供絕佳範例。