【数据结构与算法】完成用十字链表存储的稀疏矩阵的加法运算-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构与算法】完成用十字链表存储的稀疏矩阵的加法运算。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

Qestion: 完成用十字链表存储的稀疏矩阵的加法运算。

主要思路

获取两个稀疏矩阵总有多少个非零元素，记作cnt。
当cnt 不为零时一直循环，每循环一次i++，也就是行循环，每循环一次就转移至下一行。
先从第一行开始循环，使得两个工作指针p、q分别指向两个稀疏矩阵的第一行第一个非零元。对当前行p、q有无元素个数进行判断，下面是会遇到的四种情况：
- p当前行无元素并且q有元素：则将赋值给p，也就是q当前行的元素全部都接在了p之后
- p、q当前行均无元素：则跳出当前循环，令i+1，进入下一行也就是下一个循环
- p当前行有元素、q无元素：则跳出当前循环，转移至下行
- p、q当前行均有元素：则进行下述循环。

思路伪代码

【数据结构与算法】完成用十字链表存储的稀疏矩阵的加法运算,算法与数据结构,C/C++,链表,矩阵,数据结构

完整代码

// 完成用十字链表存储的稀疏矩阵的加法运算。
typedef struct OLNode
{
    int i;
    int j;
    int e;
    struct OLNode *right;
    struct OLNode *down;
} OLNode, *OLink;

typedef struct
{
    OLink *rhead;
    OLink *chead;
    int mu; // 行数
    int nu; // 列数
    int tu;
} CrossList;

void addArray(CrossList &a, CrossList b)
{
    int cnt = a.tu + b.tu; // 统计一共有多少个非零数
    int i = 1;
    // int j1, j2;
    while (cnt > 0) // 当还有数没加时继续循环
    {
        OLink p = a.rhead[i];
        OLink q = b.rhead[i];

        if (!p && q) // p当前行无元素，q有元素，则将q赋给p
            p = q;
        if (!p && !q) // p、q当前行均无元素，则跳转下一行
            continue;
        if (p && !q) // p有元素，q无元素，则跳转下一行
            continue;
        if (p && q) // p、q均有元素，则进行加法
        {
            do
            {
                if (p->j < q->j)
                {
                    cnt--;        // cnt减一
                    if (p->right) // p的右元素不为空
                    {
                        p = p->right; // 工作指针p向右移
                    }
                    else
                    {
                        p->right = q; // q当前行的所有元素接到p的后面
                    }
                }
                else if (p->j == q->j)
                {
                    p->e = p->e + q->e;
                    p = p->right;
                    q = q->right;  // p、q同时向右移动
                    cnt = cnt - 2; // cnt减二
                }
                else
                {
                    OLink tmp1 = p;
                    p = q;                 // a.rhead[i]指向q的节点
                    OLink tmp2 = q->right; // 将q的右节点的指针保存
                    q->right = tmp1;       // q的右指针指向p
                    cnt--;
                    if (tmp2) // 若q的右节点不为空
                    {
                        q = tmp2; // 工作指针q向右移
                    }
                }
            } while (!p->right); // 当工作指针为当前行的最后一个元素时退出循环
        }

        i++; // 转移到下一行
    }
}