【数据结构与算法】完成用十字链表存储的稀疏矩阵的加法运算_两个相同行数和列数的稀疏矩阵用十字链表实现加法运算。-程序员宅基地

技术标签： C/C++ 矩阵链表数据结构算法与数据结构

题目

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

主要思路

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

思路伪代码

在这里插入图片描述

完整代码

// 完成用十字链表存储的稀疏矩阵的加法运算。
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++; // 转移到下一行
    }
}

代码图片

在这里插入图片描述

结束语

因为是算法小菜，所以提供的方法和思路可能不是很好，请多多包涵~如果有疑问欢迎大家留言讨论，你如果觉得这篇文章对你有帮助可以给我一个免费的赞吗？我们之间的交流是我最大的动力！

本文链接：https://blog.csdn.net/Zchengjisihan/article/details/131521109

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

开源项目，毕业设计_本科毕业设计拿别人的开源代码修改-程序员宅基地

文章浏览阅读1.5w次，点赞35次，收藏385次。自己在网上找的开源项目，比较好分享给大家热门开源项目（包含小四轴、智能手环、光立方、智能车、防丢器等项目）号外！号外！（搞四轴，有这套就足够了！)科研级别的小四轴STM32F4芯片支持WIFI且android手机控制自适应控制就是牛掰！该飞机面向有科研和强烈学习意向的小伙伴们使用，如果只是想玩的话你肯定不会喜欢这套四轴的，主要设计思想是提供一个高性能的控制和姿态算法验证平台，因此..._本科毕业设计拿别人的开源代码修改

Java快速开发框架_若依——Ruoyi添加自己的业务模块_ruoyi java17-程序员宅基地

文章浏览阅读1w次，点赞2次，收藏26次。QQ 1274510382Wechat JNZ_aming商业联盟 QQ群538250800技术搞事 QQ群599020441解决方案 QQ群152889761加入我们 QQ群649347320共享学习 QQ群674240731纪年科技aming网络安全 ,深度学习,嵌入式,机器强化,生物智能,生命科学。叮叮叮：产品已上线 —>关注官方-微信公众号——济南纪年信息科技有限公司民生项目：商城加盟/娱乐交友/创业商圈/外包兼职开发-项目发布/安全项目：态势感.._ruoyi java17

CISCO 交换机配置 Web浏览器的方式-程序员宅基地

文章浏览阅读9k次，点赞2次，收藏3次。　当利用Console口为交换机设置好IP地址信息并启用HTTP服务后，即可通过支持JAVA的Web浏览器访问交换机，并可通过Web通过浏览器修改交换机的各种参数并对交换机进行管理。事实上，通过Web界面，可以对交换机的许多重要参数进行修改和设置，并可实时查看交换机的运行状态。不过在利用 Web浏览器访问交换机之前，应当确认已经做好以下准备工作：·在用于管理的计算机中安装T..._思科交换机2960s有web配置吗

ERROR - file: tracker_proto.c, line: 48, server: 127.0.0.1:22122, response status 2 != 0-程序员宅基地

文章浏览阅读2.5w次，点赞2次，收藏6次。报错信息： [2018-09-09 20:33:12] ERROR - file: tracker_proto.c, line: 48, server: 127.0.0.1:22122, response status 2 != 0 [2018-09-09 20:33:12] ERROR - file: tracker_proto.c, line: 48, server: 127.0.0.1:..._error - file: tracker_proto.c, line: 48, server: 172.17.0.1:22122, response

使用matplotlib显示图片（《深度学习入门：基于Python的理论与实现》实践笔记）_matplotlib展示图片-程序员宅基地

文章浏览阅读3.9k次。使用matplotlib显示图片（《深度学习入门：基于Python的理论与实现》实践笔记）一、安装matplotlib库二、导入matplotlib.pyplot库和matplotlib.image库里的imread函数三、实例：显示图片一、安装matplotlib库在命令行使用下面的命令即可：pip install matplotlib二、导入matplotlib.pyplot库和matplotlib.image库里的imread函数在程序开头使用：import matplotlib.pyp_matplotlib展示图片

Subversion实践案例——客户现场模式的分布式开发_开发去客户现场的案例-程序员宅基地

文章浏览阅读1.2k次。基本信息用户单位：某应用软件研发企业用户规模：100人以上组织过程水平：中等 CMMI评审等级：无 Subversion使用时间：1年客户需求由于公司每次向新客户提交软件的时候都需要派出一个小规模的团队到客户现场进行一段时间的软件定制和维护。此外，老客户系统的重大升级和功能扩展也需要一个小团队在客户现场进行一段时间的开发。因此，异地开发的配置管理就是一_开发去客户现场的案例

随便推点

（基于matlab自写代码）语音信号的短时分析，计算平均能量，短时过零数_matlab求语音信号短时过零率的函数-程序员宅基地

文章浏览阅读3.2k次。一定时宽的语音信号，其能量的大小随时间有明显的变化。清音段能量比浊音段小得多。短时过零数也可用于语音信号分析中，发浊音时，其语音能量约集中于3kHz以下，而发清音时，多数能量出现在较高频率上。可认为浊音时具有较低的平均过零数，而清音时具有较高的平均过零数，故对一短时语音段计算其短时平均能量及短时平均过零数，就可以区分其中的清音段和浊音段，从而可判别句中清、浊音转变时刻，声母韵母的分界以及无声与有声的分界。这在语音识别中有重要意义。自己编写的matlab代码，对一段语音，取帧长为240个点，计算其平均能_matlab求语音信号短时过零率的函数