稀疏矩阵的三元组表表示法及其转置

1. 什么是稀疏矩阵

稀疏矩阵是指矩阵中大多数元素为零的矩阵。

从直观上讲,当元素个数低于总元素的30%时,这样的矩阵被称为稀疏矩阵。

由于该种矩阵的特点,我们在存储这种矩阵时,如果直接采用二维数组,就会十分浪费空间,因为其中大多数元素都是重复的零。

稀疏矩阵的三元组表表示法

对于稀疏矩阵的压缩存储,采用只存储非零元素的方法。

由于稀疏矩阵中非零元素a_{ij}的分布没有规律,因此在存储非零元素值得同时,还必须存储该非零元素在矩阵中的位置信息,即行号和列号。

也就是采用三元组的结构存储:

为处理方便,将稀疏矩阵中非零元素对应的三元组行号依次增大进行存放。

这也就解释了,为什么稀疏矩阵是非零元素占比小于30%的矩阵。

因为采取三元组的结构储存,一个元素会占用三个单元的空间,只有当零元素占比小于30%时,这种存储结构才能在空间上有较明显的收益。

稀疏矩阵三元组表的类型定义

#define ElementType int

//一个三元组元素
typedef struct 
{
    int row, col;//非零元素行下标和列下标
    ElementType e;
}Triple;

//稀疏矩阵
typedef struct 
{
    Triple* data;//非零元素的三元组表
    int m, n, len;//矩阵行数,列数,非零元素个数
    int capacity;//容量
}TSMatrix;

 2. 对稀疏矩阵进行基本操作

//初始化稀疏矩阵
void TSMInite(TSMatrix* ps)
{
    assert(ps);
    ps->data = NULL;
    ps->m = TSM_ROWMAX;
    ps->n = TSM_COLMAX;
    ps->len = 0;
    ps->capacity = 0;
}

//销毁稀疏矩阵
void TSMDestroy(TSMatrix* ps)
{
    assert(ps);
    free(ps->data);
    ps->data = NULL;
    ps->len = 0;
    ps->capacity = 0;
}

//检查扩容
void CheckCapacity(TSMatrix* ps)
{
    assert(ps);
    if(ps->capacity == ps->len)
    {
        int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        Triple* tmp = (Triple*)realloc(ps->data, newcapacity * sizeof(Triple));
        if(tmp == NULL)
        {
            perror("realloc");
            exit(-1);
        }
        ps->data = tmp;
        ps->capacity = newcapacity;
    }
}

//插入元素
void ElemInsert(TSMatrix* ps, Triple x)
{
    assert(ps);
    CheckCapacity(ps);
    if(ps->len == 0)
    {
        ps->data[ps->len] = x;
    }
    if(x.row < ps->data[0].row)
    {
        for(int j = ps->len; j > 0; j--)
        {
            ps->data[j] = ps->data[j - 1];
        }
        ps->data[0] = x;
    }
    else
    for(int i = 0; i < ps->len; i++)
    {
        if(x.row >= ps->data[i].row&&x.row <= ps->data[i + 1].row||i == ps->len - 1)
        {
            for(int j = ps->len; j > i + 1; j--)
            {
                ps->data[j] = ps->data[j - 1];
            }
            ps->data[i + 1] = x;
            break;
        }
    }
    ps->len++;
}

//打印元素
void TSMPrint(TSMatrix ps)
{
    for(int i = 0; i < ps.len; i++)
    {
        printf("row = %d col = %d e = %d\n", ps.data[i].row, ps.data[i].col, ps.data[i].e);
    }
    printf("\n");
}

这些函数基本是以顺序表操作函数为蓝本写的,目的是为了方便我们实现稀疏矩阵的转置。

只不过插入元素的函数需要确保插入之后,三元组的行号是依次递增的。

3. 稀疏矩阵的转置

需要强调的是,矩阵的常规存储是二维的,而三元组表存储是一维的,由于矩阵存储结构的变化,也带来了运算方法的不同,必须认真分析。

3.1 稀疏矩阵转置的经典算法

void TransMatrix(ElementType source[m][n], ElementType dest[n][m])
{
    int i, j;
    for(i = 0; i < m; i++)
    for(j = 0; j < n; j++)
    dest[j][i] = source[i][j];
}

这个算法是针对传统的二维数组的存储方式。

3.2 用三元组表实现稀疏矩阵的转置

假设A和B是稀疏矩阵source和dest的三元组表,则实现转置的简单方法如下:

1. 三元组表A的行,列互换就可以得到B中的元素。

2. 转置后的矩阵的三元组表B中的三元组不是以“行序为主序”存储的,为保证三元组表B也是以“行序为主序”进行存放的,则需要对该三元组表B按行下标(即A的列下标)以递增顺序重新排列。

 上图中的步骤很容易实现,但是重新排序势必会大量移动元素,从而影响算法的效率。

为避免上述简单转置算法中重新排序引起的元素移动,可采取接下来的两种处理方法。

3.2.1 列序递增转置法

算法思想

这里的列序指的是A的列,也就是按照A的列序来将元素转置到B中。

即将A的第一列全部转置到B中(得到B的第一行)后,再将A的第二列全部转置到B中,以此类推。

代码

//列序递增转置法
void TSMSwitch1(TSMatrix A, TSMatrix* B)
{
    assert(B);
    TSMDestroy(B);
    B->data = (Triple*)malloc(A.capacity * sizeof(Triple));
    B->capacity = A.capacity;
    B->len = A.len;
    B->m = A.n;
    B->n = A.m;
    int j = 0;//记录B当前空位
    for(int k = 0; k < A.n; k++)
    {
        for(int i = 0; i < A.len; i++)
        {
            if(A.data[i].col == k)
            {
                B->data[j].row = A.data[i].col;
                B->data[j].col = A.data[i].row;
                B->data[j].e = A.data[i].e;
                j++;
            }
        }
    }
}

分析

这种算法确实使得我们不用再单独进行排序,但是双重循环依然造成了较高的时间复杂度(O(A.n * A.len))。

那么我们能否降低该算法的时间复杂度呢?

如果能,那么我们的着手点一定是想办法优化掉二重循环。

可以发现,该算法中二重循环出现的原因在于,必须将A的第一列全部转置之后才能转置第二列,每列转置需要重新扫描一次A。

那么,我们有没有办法使得各列同时进行存放呢,这样就只用扫描一次A了。

3.2.2 一次定位快速转置法

算法思想

如果我们知道A的每一列有多少个元素,那么就可以推知B中每一行的起始位置。

这样一来,假如某次在A中扫描到第n列的元素,我们就可以直接将其放到B中的第n行所在位置,而不用先放完一列再放下一列。

所以,我们准备进行三次循环:

1. 定义数组num,数组的下标表示A的列,遍历A并将每一列元素的个数记录在num中。

2. 定义数组position,数组下标表示B的行,遍历position,根据A每一列元素的个数得到对应行的起始位置。

3. 遍历A,根据position数组,将A中的元素转置到B的对应行。

代码 

//一次定位快速转置算法
void TSMSwitch2(TSMatrix A, TSMatrix* B)
{
    assert(B);
    TSMDestroy(B);
    B->data = (Triple*)malloc(A.capacity * sizeof(Triple));
    B->capacity = A.capacity;
    B->len = A.len;
    B->m = A.n;
    B->n = A.m;
    int num[B->m];
    int position[B->m];
    memset(num, 0, B->m * sizeof(int));
    memset(num, 0, B->m * sizeof(int));
    for(int i = 0; i < A.len; i++)
    {
        num[A.data[i].col]++;
    }
    position[0] = 0;
    for(int row = 1; row < B->m; row++)
    {
        position[row] = position[row - 1] + num[row - 1];
    }
    for(int i = 0; i < A.len; i++)
    {
        B->data[position[A.data[i].col]].row = A.data[i].col;
        B->data[position[A.data[i].col]].col = A.data[i].row;
        B->data[position[A.data[i].col]].e = A.data[i].e;
        position[A.data[i].col]++;
    }
}

算法分析

显然,一次定位快速转置算法的时间效率要高得多,它在时间性能上由于列序递增转置法,但在空间耗费上增加了两个辅助向量空间,即num和position。

由此可见,算法在时间上的节省是以更多的储存空间为代价的。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/515136.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Kubernetes(k8s)核心资源解析:Pod详解

Kubernetes核心资源解析&#xff1a;Pod详解 1、什么是Pod&#xff1f;2、Pod 的组成3、Pod 如何管理多个容器4、Pod 的网络5、Pod 的存储方式6、Pod 的工作方式6.1 自主式 Pod6.2 监控和管理 Pod6.3 Pod 的创建流程 &#x1f496;The Begin&#x1f496;点点关注&#xff0c;收…

基于单片机的测时仪系统设计

**单片机设计介绍&#xff0c;基于单片机的测时仪系统设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机的测时仪系统设计是一个结合了单片机技术与测时技术的综合性项目。该设计的目标是创建一款精度高、稳定性强且…

前端学习<四>JavaScript基础——03-常量和变量

常量&#xff08;字面量&#xff09;&#xff1a;数字和字符串 常量也称之为“字面量”&#xff0c;是固定值&#xff0c;不可改变。看见什么&#xff0c;它就是什么。 常量有下面这几种&#xff1a; 数字常量&#xff08;数值常量&#xff09; 字符串常量 布尔常量 自定义…

重磅!openGauss6.0创新版本,带着新特性正式发布了!

&#x1f4e3;&#x1f4e3;&#x1f4e3; 哈喽&#xff01;大家好&#xff0c;我是【IT邦德】&#xff0c;江湖人称jeames007&#xff0c;10余年DBA及大数据工作经验 一位上进心十足的【大数据领域博主】&#xff01;&#x1f61c;&#x1f61c;&#x1f61c; 中国DBA联盟(ACD…

编程生活day6--回文子串、蛇形填充数组、笨小猴、单词排序

回文子串 题目描述 给定一个字符串&#xff0c;输出所有长度至少为2的回文子串。 回文子串即从左往右输出和从右往左输出结果是一样的字符串&#xff0c;比如&#xff1a;abba&#xff0c;cccdeedccc都是回文字符串。 输入 一个字符串&#xff0c;由字母或数字组成。长度5…

求m和n的最大公约数(C语言)

一、运行结果&#xff1b; 二、源代码&#xff1b; # define _CRT_SECURE_NO_WARNINGS # include <stdio.h>int main() {//初始化变量值&#xff1b;int remainder 1;int m 0;int n 0;int middle 0;//提示用户&#xff1b;printf("请输入整数m和n的值&#xff…

处理SAP报错:消息GLT2076 没有项目种类分配到科目 1481010102/1000

财务新建了个科目入账时报错&#xff1a;没有项目种类分配到科目。 查了下原因。原来是我们公司实施时启用了凭证分割功能。其中有个配置是这样的&#xff1a;给总账科目分类&#xff1a;IMG-财务会计&#xff08;新&#xff09;-总账会计核算-业务交易-凭证分解-为文档拆分给总…

分布式架构中一些常用算法的理解

对分布式算法 - 一致性Hash算法的理解 一致性哈希算法是一种分布式算法&#xff0c;用于解决数据分布和负载均衡问题。它通过将数据和节点映射到一个哈希环上&#xff0c;实现了数据在节点之间的均匀分布和最小化数据迁移。 一致性哈希算法的核心思想是将数据和节点都映射到哈…

1.数据结构和算法

文章目录 数据结构逻辑结构集合结构线性结构树形结构图形结构 物理结构顺序存储结构链式存储结构 算法基本特性目标 总结数据结构总结算法总结 数据结构 「数据结构」指的是&#xff1a;数据的组织结构&#xff0c;用来组织、存储数据。 逻辑结构 逻辑结构&#xff08;Logic…

Dubbo入门项目搭建【Dubbo3.2.9、Nacos2.3.0、SpringBoot 2.7.17、Dubbo-Admin 0.6.0】

B站学习视频 基于Dubbo3.2.9、Nacos2.3.0、SpringBoot 2.7.17、Dubbo-Admin 0.6.0、Jdk1.8 搭建的Dubbo学习Demo 一、前置安装 1-1、Nacos 安装 我本地是通过docker-compose来安装nacos的&#xff0c;如果需要其它方式安装可以去百度找下教程&#xff0c;版本是2.3.0的 docker…

C语言要点细细梳理(下)

10. 运算符补充 10.1 位运算 位运算符&#xff1a;<< >> & | ~ ^ << >> &#xff1a;按位左移右移&#xff0c;移出去的数直接丢掉&#xff0c;符号不动 &&#xff1a;按位与 |&#xff1a; 按位或 ~&#xff1a;按位非 ^&#xff1a;按…

iOS使用CoreML运用小型深度神经网络架构对图像进行解析

查找一个图片选择器 我用的是ImagePicker 项目有点老了&#xff0c;需要做一些改造&#xff0c;下面是新的仓库 platform :ios, 16.0use_frameworks!target learnings dosource https://github.com/CocoaPods/Specs.gitpod ImagePicker, :git > https://github.com/KevinS…

基于VUE实现的餐厅经营游戏项目源码

WebMOOC 餐厅游戏 项目介绍 实现了一个类游戏的餐厅经营模拟&#xff0c;涉及的前端知识有移动端 HTML 页面布局及样式实现。实现了厨师、顾客等角色的关键操作&#xff0c;完成从顾客等位、点菜、烹饪、用餐、支付的一系列状态变更的数据、信息、交互、展现的变化及处理。 …

巨控560:走向国际,我们的设备如何拥抱远程控制技术?

走向国际&#xff0c;我们的设备如何拥抱远程控制技术&#xff1f; 描述&#xff1a;随着国内设备走向国际市场&#xff0c;客户需求的多样性和不确定性大大增加。本文将深入探讨在这一背景下&#xff0c;是否有必要为我们的设备加装远程PLC控制模块&#xff0c;以及如何应对频…

分布式系统架构中的相关概念

1.1、衡量网站的性能指标 响应时间&#xff1a;指执行一个请求从开始到最后收到响应数据所花费的总体时间。并发数&#xff1a;指系统同时能处理的请求数量。 并发连接数&#xff1a;指的是客户端向服务器发起请求&#xff0c;并建立了TCP连接。每秒钟服务器连接的总TCP数量请…

基于SSM+Jsp+Mysql的图书仓储管理系统

开发语言&#xff1a;Java框架&#xff1a;ssm技术&#xff1a;JSPJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包…

ospf的路由计算

LSA是链路状态信息&#xff08;描述接口信息&#xff09;&#xff0c;路由器将接口信息发给其他路由器&#xff0c;LSA有6个分类&#xff0c;1&#xff0c;2类描述区域内信息&#xff0c;3类是区域间的&#xff0c;5类是外部路由&#xff0c;4类是对5类的补充&#xff0c;7类是…

企微知识库优缺点解析:如何让其效益最大化

企业搭建企微知识库&#xff0c;作为企业内部知识的集中存储和共享平台&#xff0c;为企业带来了很多便利。但是&#xff0c;任何事物都有其两面性&#xff0c;企微知识库也不例外。今天我们就来详细探讨搭建企微知识库的优点和缺点&#xff0c;如何在使用企微知识库时使其发挥…

【群晖】NASTOOL-自动化处理影音视频工具

【群晖】NASTOOL-自动化处理影音视频 本文主要从获取、部署、使用、配置等方面进行手把手教学如何使用nastool工具进行影音视频自动化处理。从此靠别繁琐的网上各个网址找资源-下载-复制-改名-刮削等操作。 准备 DSM 7.1 &#xff08;我使用的是群晖 7.1 系统&#xff0c;不管…

【一站式学会Kotlin】第一节 kotlin 介绍

作者介绍&#xff1a; 百度资深Android工程师T6&#xff0c;在百度任职7年半。 目前&#xff1a;成立赵小灰代码工作室&#xff0c;欢迎大家找我开发Android、微信小程序、鸿蒙项目。 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默。给大家…