基于链表的稀疏矩阵乘法实现困惑求助

一、重新设计链表节点结构 #

原有ListNode仅存储单个整数值，无法满足稀疏矩阵需求——每个非零元素需要同时记录列索引和值。修改节点结构如下：

struct SparseNode {
    int col;    // 元素所在列号（根据输入格式调整索引起始值）
    int val;    // 非零元素的值
    SparseNode* next;

    SparseNode() : col(0), val(0), next(nullptr) {}
    SparseNode(int c, int v) : col(c), val(v), next(nullptr) {}
};

可将原有LinkedList类重构为适配SparseNode的结构，或直接重命名为SparseRowList以明确用途。

二、用链表集合表示稀疏矩阵 #

不使用vector/array存储密集矩阵的前提下，可通过手动分配指针数组管理每行的链表（行数由输入的m确定）：

// 假设输入矩阵行数为m
SparseRowList* matrix = new SparseRowList[m];

每行对应一个SparseRowList，链表节点仅存储该行的非零元素信息。比如输入示例的第0行，非零元素为列2（值3）、列4（值4），对应链表结构为SparseNode(2,3) -> SparseNode(4,4) -> nullptr。

三、解析输入构建稀疏矩阵 #

按照给定输入格式逐行处理：

1. 先读取矩阵维度m和n；
2. 对每一行：
   • 读取第一个整数k，代表该行非零元素数量；
   • 依次读取2*k个整数，每两个一组为<列号, 值>；
   • 遇到0结束该行输入；
   • 将<列号, 值>节点插入对应行的链表（注意输入列号可能是1-index，需转为代码常用的0-index）。

示例代码片段：

int m, n;
cin >> m >> n;
SparseRowList* mat = new SparseRowList[m];

for (int i = 0; i < m; ++i) {
    int k;
    cin >> k;
    if (k == 0) continue; // 该行无任何非零元素

    for (int j = 0; j < k; ++j) {
        int col, val;
        cin >> col >> val;
        // 输入列号为1-index，转为0-index存储
        mat[i].Push_back(SparseNode(col - 1, val));
    }
    // 跳过行尾的终止符0
    int end_flag;
    cin >> end_flag;
}

四、实现稀疏矩阵乘法核心逻辑 #

假设计算A(m×n) * B(n×p) = C(m×p)，核心逻辑如下：

1. 初始化结果矩阵C为m行的空链表；
2. 遍历A的每一行i：
   • 遍历该行每个非零节点<j, a_ij>；
   • 遍历B的第j行每个非零节点<k, b_jk>；
   • 计算乘积a_ij * b_jk，将其累加到C的第i行第k列元素：
     • 若C的第i行已有列k的节点，直接更新其值；
     • 若没有，插入新的<k, 乘积>节点。

关键代码片段（需给SparseRowList添加GetHead()、FindNodeByCol()方法）：

SparseRowList* multiply(SparseRowList* A, int m, int n, SparseRowList* B, int p) {
    SparseRowList* C = new SparseRowList[m];

    for (int i = 0; i < m; ++i) {
        SparseNode* a_node = A[i].GetHead();
        while (a_node != nullptr) {
            int j = a_node->col;
            int a_val = a_node->val;

            SparseNode* b_node = B[j].GetHead();
            while (b_node != nullptr) {
                int k = b_node->col;
                int b_val = b_node->val;
                int product = a_val * b_val;

                // 更新结果矩阵C的对应位置
                SparseNode* c_node = C[i].FindNodeByCol(k);
                if (c_node != nullptr) {
                    c_node->val += product;
                } else {
                    C[i].Push_back(SparseNode(k, product));
                }

                b_node = b_node->next;
            }
            a_node = a_node->next;
        }
    }
    return C;
}

五、适配现有LinkedList类 #

需给原有LinkedList类补充以下关键方法：

• GetHead()：返回链表头节点指针，用于遍历；
• FindNodeByCol(int col)：查找链表中指定列号的节点；
• 修改Push_back、Insert等方法，使其支持存储SparseNode类型（或重构为模板类以支持泛型）。

内容的提问来源于stack exchange，提问作者Y.C.