基于链表的稀疏矩阵相加功能异常问题求助

问题根源分析 #

你的Add函数逻辑完全错误：当前的双重循环会把矩阵a的每个节点和矩阵b的每个节点逐一相加，然后将结果插入到a节点的行列位置，这不仅会导致大量重复插入，还完全违背了矩阵相加的核心规则——只有同一行同一列的元素才能相加。同时，这个逻辑完全忽略了仅在a或仅在b中存在的非零元素，这就是你得到遗漏元素错误结果的直接原因。

比如测试用例中，矩阵a的(0,1)位置值为3，矩阵b的这个位置没有节点，当前逻辑根本不会处理这个元素，导致结果中该位置为0；同理矩阵a的(1,0)位置值为2，矩阵b没有该节点，也被遗漏。

修复方案：正确的稀疏矩阵相加逻辑 #

稀疏矩阵相加需要同步遍历两个链表，按行号、列号的顺序匹配节点，处理三种核心情况：

1. 两个节点行号列号都相同：相加后插入结果（和不为0时）
2. a的节点行号更小，或行号相同但列号更小：直接插入a的节点到结果
3. b的节点行号更小，或行号相同但列号更小：直接插入b的节点到结果
   遍历结束后，把剩余的节点直接插入结果。

修正后的Add函数代码 #

void Add(Node* a, Node* b, Node** result) {
    Node* ptr_a = a;
    Node* ptr_b = b;
    Node* tail = nullptr; // 尾指针，用于尾插法保持节点顺序

    while (ptr_a != nullptr && ptr_b != nullptr) {
        if (ptr_a->row_position < ptr_b->row_position) {
            // a的节点行号更小，直接加入结果
            InsertTail(result, &tail, ptr_a->row_position, ptr_a->column_position, ptr_a->value);
            ptr_a = ptr_a->next;
        } else if (ptr_a->row_position > ptr_b->row_position) {
            // b的节点行号更小，直接加入结果
            InsertTail(result, &tail, ptr_b->row_position, ptr_b->column_position, ptr_b->value);
            ptr_b = ptr_b->next;
        } else {
            // 行号相同，比较列号
            if (ptr_a->column_position < ptr_b->column_position) {
                InsertTail(result, &tail, ptr_a->row_position, ptr_a->column_position, ptr_a->value);
                ptr_a = ptr_a->next;
            } else if (ptr_a->column_position > ptr_b->column_position) {
                InsertTail(result, &tail, ptr_b->row_position, ptr_b->column_position, ptr_b->value);
                ptr_b = ptr_b->next;
            } else {
                // 行列都相同，相加后仅保留非零值
                int sum = ptr_a->value + ptr_b->value;
                if (sum != 0) {
                    InsertTail(result, &tail, ptr_a->row_position, ptr_a->column_position, sum);
                }
                ptr_a = ptr_a->next;
                ptr_b = ptr_b->next;
            }
        }
    }

    // 处理a中剩余的节点
    while (ptr_a != nullptr) {
        InsertTail(result, &tail, ptr_a->row_position, ptr_a->column_position, ptr_a->value);
        ptr_a = ptr_a->next;
    }

    // 处理b中剩余的节点
    while (ptr_b != nullptr) {
        InsertTail(result, &tail, ptr_b->row_position, ptr_b->column_position, ptr_b->value);
        ptr_b = ptr_b->next;
    }
}

补充尾插法Insert函数（解决头插逆序问题） #

原Insert函数是头插法，会导致节点顺序和矩阵遍历顺序相反，建议改用尾插法保证顺序：

void InsertTail(Node** head, Node** tail, int row, int col, int value) {
    Node* new_node = new Node();
    new_node->value = value;
    new_node->row_position = row;
    new_node->column_position = col;
    new_node->next = nullptr;

    if (*head == nullptr) {
        *head = new_node;
        *tail = new_node;
    } else {
        (*tail)->next = new_node;
        *tail = new_node;
    }
}

其他潜在问题修复 #

1. ConstructMatrix函数笔误：代码中调用的ReadMatrix应该是Insert（或InsertTail），否则无法正确插入节点到链表中。
2. 行列索引转换：文件中读取的列索引是1-based，而矩阵代码中用的是0-based，需要转换：

   col_index = stoi(pch) - 1;
   

3. 文件读取终止条件优化：while (stoi(pch) != 0)可能导致读取异常，建议改为检查pch是否为nullptr：

   while (pch != nullptr && stoi(pch) != 0) {
       // 原有逻辑
       pch = strtok(NULL, " ");
   }
   

测试验证 #

用你的测试用例：
矩阵a对应的链表节点：(0,0,1), (0,1,3), (1,0,2), (1,1,4)
矩阵b对应的链表节点：(0,0,1), (1,1,1)
相加后结果节点：(0,0,2), (0,1,3), (1,0,2), (1,1,5)
对应矩阵就是预期的[[2,3],[2,5]]。

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