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

技术标签： 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

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

智能推荐

一个ngrok如何穿透多个端口？_ngrok多个端口-程序员宅基地

文章浏览阅读2.7k次，点赞2次，收藏4次。如何不充钱就可以穿透多个端口？./ngrok authtoken 授权码之前这个操作的生成的yml文件中修改端口可添加多个addr：port端口可随意配置_ngrok多个端口

C语言 char转uint8_t-程序员宅基地

文章浏览阅读5.9k次。char转uint8_t：static int char2uint(char *input, uint8_t *output){ for(int i = 0; i < 24; i++) { output[i] &= 0x00; for (int j = 1; j >= 0; j--) { char hb = input[i*2 + 1 - j]; if (hb >= '0' &..._char转uint8_t

android 陀螺仪简单使用，判读手机是否静止状态_安卓陀螺仪多少才算静止-程序员宅基地

文章浏览阅读6.5k次，点赞5次，收藏13次。陀螺仪允许您在任何给定时刻确定Android设备的角速度。简单来说，它告诉您设备绕X，Y和Z轴旋转的速度有多快。最近，即使是预算手机正在制造，陀螺仪内置，增强现实和虚拟现实应用程序变得如此受欢迎。通过使用陀螺仪，您可以开发可以响应设备方向的微小更改的应用程序。创建陀螺仪对象和管理器manager// Register it, specifying the polling interv..._安卓陀螺仪多少才算静止

lib静态库逆向分析_libtersafe-程序员宅基地

文章浏览阅读4.7k次，点赞3次，收藏16次。当我们要分析一个lib库里的代码时，首先需要判断这是一个静态库还是一个导入库。库类型判断lib文件其实是一个压缩文件。我们可以直接使用7z打开lib文件，以查看里面的内容。如果里面的内容是obj文件，表明是静态库。如果里面的内容是dll文件，表明是导入库。导入库里面是不包含代码的，代码包含在对应的dll文件中。从lib中提取obj静态库是一个或者多个obj文件的打包，这里有两个方法从中提取obj：Microsoft 库管理器 7z解压Microsoft 库管理器(li_libtersafe

Linux的网络适配器_linux 查询网络适配器-程序员宅基地

文章浏览阅读5.3k次，点赞3次，收藏3次。了解一下，省的脑壳痛桥接模式对应的虚拟网络名称“VMnet0” 桥接模式下，虚拟机通过主机的网卡进行通信，若物理主机有多块网卡（有线的和无线网卡），应选择桥结哪块物理网卡桥接模式下，虚拟机和物理主机同等地位，可以通过物理主机的网卡访问外网（局域网），一个局域网的其他计算机可以访问虚拟机。为虚拟机设置一个与物理网卡在同个网段的IP，则虚拟机就可以与物理主机以及局域..._linux 查询网络适配器

【1+X Web前端等级考证】 | Web前端开发中级理论 (附答案)_1+xweb前端开发中级-程序员宅基地

文章浏览阅读3.4w次，点赞77次，收藏438次。# 前言2020 12月 1+X Web 前端开发中级模拟题大致就更这么多,我的重心不在这里,就不花太多时间在这里面了。但是，说说1+X Web前端开发等级考证这个证书,总有人跑到网上问：这个证书有没有用？这个证书含金量高不高？# 关于考不考因为这个是工信部从2019年才开始实施试点的，目前还在各大院校试点中，就目前情况来看，知名度并不是很高，有没有用现在无法一锤定音，看它以后办的怎么样把，软考以前也是慢慢地才知名起来。能考就考吧，据所知，大部分学校报考，基本不用交什么报考费(小部分学校，个别除._1+xweb前端开发中级