当前位置：首页 > news >正文

【数据结构】稀疏矩阵的快速转置

news 来源：原创 2025/7/14 10:59:26

稀疏矩阵的快速转置

如图给出一个稀疏矩阵，要求表示出它的转置矩阵

在这里插入图片描述

由这个矩阵我们能轻松得到它的三元组顺序表

6行（x坐标）	7列（y坐标）	8个元素
1	2	12
1	3	9
3	1	-3
3	6	14
4	3	24
5	2	18
6	1	15
6	4	-7

接下来我们同样把转置后的矩阵的三元组顺序表表示出来

在这里插入图片描述

7行（x坐标）	6列（y坐标）	8个元素
1	3	-3
1	6	15
2	1	12
2	5	18
3	1	9
3	4	24
4	6	-7
6	3	14

我们要如何才能通过第一个三元组顺序表得到第二个三元组顺序表呢

按照最简单的思路，我们一般会通过双重循环

朴素的双重循环

按照列坐标从头到尾遍历，遇到1的时候，将i j互换放入到第二个三元组顺序表第一个位置

按照这样的方法，每一次都有可能需要遍历n次，一共需要走n趟，时间复杂度会是O(n²）级别

那么有没有一种方法能一步到位呢

快速转置

为实现快速转置，我们引入num数组和cpot数组

num[col]:表示矩阵M中第col列中非零元个数

cpot[col]:指示M中第col列第一个非零元在转置后的三元组顺序表中位置

显然有：

cpot[1] = 1;
cpot[col] = cpot[col - 1] + num[col - 1]; //第col - 1列第一个非零元的位置加上第col - 1列非零元的个数

由此，我们能构建出col、num[col]、cpot[col]的一个表

col	1	2	3	4	5	6	7
num[col]	2	2	2	1	0	1	0
cpot[col]	1	3	5	7	8	8	9

这样我们遍历最开始的三元组顺序表

第一个列是2，我们查找 co l为 2 的 cpot[col] ,为 3，那么将原表第一行放入到转置后的第三个位置，同时 col 为 2 的 cpot[col] += 1

cpot[col] + 1 是因为若这一列还有非零元，那么肯定会是它的下一个位置

代码如下

Status FastTransposeSMatrix( TSMatrix M, TSMatrix &T ) {  // 采用三元组顺序表存储表示，求稀疏矩阵 M 的转置矩阵 TT.mu = M.nu; T.nu = M.mu; T.tu = M.tu; if (T.tu) { // mu行 nu列for (col=1; col<=M.nu; ++col)    num[col] = 0; for (t=1; t<=M.tu; ++t)   ++ num[M.data[t].j];  // 求 M 中各列非零元的个数cpot[1] = 1;for (col=2; col<=M.nu; ++col)  cpot[col] = cpot[col -1] + num[col -1]; // 求 M 中各列的第一个非零元在 T.data 中的序号 for (p=1; p<=M.tu; ++p) {  // 转置矩阵元素  col = M.data[p].j;    q = cpot[col]; T.data[q].i = M.data[p].j;    T.data[q].j = M.data[p].i; T.data[q].e = M.data[p].e;   ++ cpot[col];  } // for} // ifreturn OK;
} // FastTransposeSMatrix

【数据结构】稀疏矩阵的快速转置

稀疏矩阵的快速转置如图给出一个稀疏矩阵，要求表示出它的转置矩阵由这个矩阵我们能轻松得到它的三元组顺序表 6行（x坐标）7列（y坐标）8个元素121213931-3361443245218611564-7 接下来我们同样把转置后的矩阵的三元组…...

编程日记 2025/7/14 10:59:26

【Godot】使用 Shader 实现可调节的精确切角效果

今天我们要实现的是一个四角精确切割Shader，可以在UI元素或Sprite的四个角分别切割出不同大小的三角形区域。文章目录什么是Godot Shader？数学原理详解左上角切割右上角切割右下角切割左下角切割四角切割Shader完整代码使用方法在Godot编辑器中设置通过代码控制进阶技巧1. …...

编程日记 2025/7/15 2:04:30

在CentOS环境中安装MySQL数据库保姆级教程

一.确认当前系统版本 1.1登录系统，切换至root账户如图所示： 1.2：在终端中执行如下命令查看系统版本 cat /etc/redhat-release 二.添加 MySQL Yum 源 2.1访问MySQL开发者专区 https://dev.mysql.com/downloads/repo/yum/ TIPS: 1.发布包命…...

编程日记 2025/7/15 1:49:42

分布式系统中的 ActiveMQ：异步解耦与流量削峰（二）

四、流量削峰 （一）流量削峰原理深入解析在当今互联网应用中，高并发场景屡见不鲜。例如，电商平台的促销活动、在线票务系统的抢票时刻以及社交平台的热点事件爆发期等，都会在短时间内迎来大量用户请求。这些瞬间涌入…...

编程日记 2025/6/28 20:04:48

JAVA设计模式——（十）抽象工厂模式（Abstract Factory Pattern）

JAVA设计模式——（十）抽象工厂模式（Abstract Factory Pattern） 介绍理解实现工厂接口工厂实现类应用类应用类实现测试改造工厂类应用介绍抽象工厂模式在工厂模式的基础上，适配的对象变为一组相关的对象&#xff0c…...

编程日记 2025/6/28 20:04:47

STM32的定时器

定时器的介绍介绍：STM32F103C8T6微控制器内部集成了多种类型的定时器，这些定时器在嵌入式系统中扮演着重要角色，用于计时、延时、事件触发以及PWM波形生成、脉冲捕获等应用。 *几种定时器（STM32F103系列）&#xff1…...

编程日记 2025/6/29 5:12:14

ubuntu-PyQt5安装+PyCharm配置QtDesigner + QtUIC

个人环境 ubuntu22.04 pycharm 2024.3 python 3.10 1)先使用apt命令在线安装 1)sudo apt install pyqt5* 2)sudo apt install qttools5-dev-tools2）Pycharm配置Pycharm External Tool 在设置—工具——外部工具中配置QtDesigner Name ：QtDesigne…...

编程日记 2025/6/29 6:07:42

测试基础笔记第十九天

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档文章目录一、接口的概念二、接口的类型三、接口测试1.概念2.原理：3.特点:4.实现方式:5.什么是自动化接口测试？ 二、HTTP协议1.HTTP协议简介2.URL格式…...

编程日记 2025/6/29 8:17:02

Ubuntu 系统上广受好评的浏览器推荐

日常使用与开发者首选 Firefox 特点：开源、隐私保护强大，支持丰富扩展（如开发者工具、广告拦截），默认预装且跨平台兼容368。适用场景：日常浏览、开发者调试（支持实时 CSS/JS 编辑）、…...

编程日记 2025/7/4 10:51:00

第 13 届蓝桥杯 C++ 青少组省赛中 / 高级组真题解析

一、选择题第 1 题题目：下列关于类中声明的变量描述正确的是 ( )｡ 选项： A. 只属于该类 B. 属于全局变量 C. 任何情况下都可被该类所有实例共享 D. 属于该类，某些情况下也可被该类不同实例所共享答案：D 解析&…...

编程日记 2025/6/29 7:34:41

Win10下安装Linux-Ubuntu24.04双系统

0 引言 Ubuntu 24.04 LTS（代号“Noble Numbat”）是 Canonical 于 2024 年 4 月 25 日发布的第 10 个长期支持版本，专注于性能优化、企业安全和开发者体验提升 Windows 10 是微软于 2015 年 7 月发布的跨平台操作系统，融合了传统桌…...

编程日记 2025/6/29 5:12:06

express 怎么搭建 WebSocket 服务器

一：使用 express-ws var express require(express); var app express(); var expressWs require(express-ws)(app);app.use(function (req, res, next) {console.log(middleware);req.testing testing;return next(); });app.get(/, function(req, res, next){…...

编程日记 2025/6/29 6:15:25

模型部署——cuda编程入门

CUDA中的线程与线程束 kernel是在device上线程中并行执行的函数，核函数用__global__符号声明，在调用时需要用<<<grid_size, block_size>>>来指定kernel要执行的线程数量。在CUDA中，每一个线程都要执行核函数，并…...

编程日记 2025/6/29 5:12:09

llfc项目TCP服务器笔记

ChatServer 一个TCP服务器必然会有连接的接收，维持，收发数据等逻辑。那我们就要基于asio完成这个服务的搭建。主服务是这个样子的 #include "LogicSystem.h"#include <csignal>#include <thread>#include <mutex>#include "AsioIOServiceP…...

编程日记 2025/6/29 5:22:29

NPP库中libnppi模块介绍

1. libnppi 模块简介 libnppi 是 NPP 库中专门用于图像处理的模块，提供高度优化的 GPU 加速函数，支持： 图像滤波（卷积、形态学操作） 几何变换（旋转、缩放、透视变换） 颜色空间转换&#xf…...

编程日记 2025/6/29 7:27:26

从头训练小模型: 3 传统RLHF与DPO的区别

这个步骤我其实是忽略了。如果我的目标是建立一个安全领域的模型，我个人理解这步骤并不太必要。关于人类偏好对齐：在前面的训练步骤中，模型已经具备了基本的对话能力。此时模型还不知道什么是好的回答，什么是不好的回答。我们希…...

编程日记 2025/7/14 10:28:46

Python-Django系列—视图

一、通用显示视图以下两个基于类的通用视图旨在显示数据。在许多项目中，它们通常是最常用的视图。 1、DetailView class django.views.generic.detail.DetailView 当该视图执行时，self.object 将包含该视图正在操作的对象。祖先（MRO&a…...

编程日记 2025/6/29 8:06:02

el-input Vue 3 focus聚焦

https://andi.cn/page/622173.html...

编程日记 2025/6/29 6:25:33

动态规划（5）路径问题--剑指offer -珠宝的最大值

题目： 现有一个记作二维矩阵 frame 的珠宝架，其中 frame[i][j] 为该位置珠宝的价值。拿取珠宝的规则为： 只能从架子的左上角开始拿珠宝每次可以移动到右侧或下侧的相邻位置到达珠宝架子的右下角时，停止拿取注意&#xff1…...

编程日记 2025/6/29 7:57:50

ZArchiver正版：高效文件管理，完美解压体验

在使用安卓设备的过程中，文件管理和压缩文件的处理是许多用户常见的需求。无论是解压下载的文件、管理手机存储中的文件，还是进行日常的文件操作，一款功能强大且操作简便的文件管理工具都能极大地提升用户体验。今天，我们要介绍的…...

编程日记 2025/6/29 6:54:08

Netlink在SONiC中的应用

Netlink在SONiC中的应用 Netlink介绍 Netlink 是 Linux 内核态程序与用户空间程序之间进行通信的机制之一，原本是用于传递网络协议栈中的各种控制消息。它采用和套接字（socket）编程接口相同的形式，常用于配置内核网络子系统&…...

编程日记 2025/6/29 5:50:13

ReentrantLock实现公平锁和非公平锁

在 Java 里，公平锁和非公平锁是多线程编程中用于同步的两种锁机制，它们的主要差异在于获取锁的顺序规则。下面是对二者的详细介绍： 公平锁公平锁遵循 “先来先服务” 原则，也就是线程获取锁的顺序和请求锁的顺序一致。先请求锁…...

编程日记 2025/6/29 5:12:08

【C++】 —— 笔试刷题day_25

一、笨小猴题目解析这道题，给定一个字符str，让我们找到这个字符串中出现次数最多字母的出现次数maxn和出现次数最少字母的出现次数minn； 然后判断maxn - minn是否是一个质数，如果是就输出Lucky Word和maxn - minn；如…...

编程日记 2025/6/29 7:34:42

terraform resource创建了5台阿里云ecs，如要使用terraform删除其中一台主机，如何删除？

在 Terraform 中删除阿里云 5 台 ECS 实例中的某一台，具体操作取决于你创建资源时使用的多实例管理方式（count 或 for_each）。以下是详细解决方案： 方法一：使用 for_each（推荐） 如果创建时使…...

编程日记 2025/6/29 8:09:28

Office 三大组件Excel、Word、Access 里 VBA 区别对比

以下是Excel、Word和Access在VBA中的主要区别对比及详细说明：核心对象模型 Excel Workbook（工作簿）→ Worksheet（工作表）→ Range（单元格区域）核心围绕单元格数据处理，如 Cells(1,1).Value = "数据" Word Document（文档）→ Range（文本范围）→ Paragrap…...

编程日记 2025/6/29 5:12:12

Linux 进程基础（二）：操作系统

目录一、什么是操作系统：用户和电脑之间的「翻译官」🌐 OS 的层状结构🧩 案例解析：双击鼠标的「跨层之旅」二、操作系统的必要性探究：缺乏操作系统的环境面临的挑战剖析🔑 OS 的「管理者」属性&#xff1…...

编程日记 2025/6/29 5:12:15

Java高并发处理核心技术详解：从理论到实战

高并发处理能力是衡量系统性能的重要指标。Java作为企业级开发的主力语言，提供了丰富的并发编程工具和框架。一、Java并发基础 1.1 Java内存模型（JMM） 主内存与工作内存：每个线程拥有独立的工作内存，通过JMM协议与主…...

编程日记 2025/6/29 6:14:25

单细胞测序数据分析试验设计赏析（二）

单细胞测序数据分析试验设计赏析（二） 这次的单细胞测序数据分析的试验设计是单细胞测序分析机器学习（with SHAP分析），也是常见的试验设计之一，重点是可以用于筛选鉴定基因调控网络，也可以是构建…...

编程日记 2025/7/15 2:52:38

Docker 服务搭建

💢欢迎来到张翊尘的开源技术站 💥开源如江河，汇聚众志成。代码似星辰，照亮行征程。开源精神长，传承永不忘。携手共前行，未来更辉煌💥 文章目录 Docker 服务搭建在 Ubuntu 上安装 Docker更新软件…...

编程日记 2025/7/3 11:40:35

4电池_基于开关电容的均衡

基于开关电容的均衡系统（Switched-Capacitor Equalization System） 开关电容均衡（Switched-Capacitor Equalization, SCE）是一种广泛应用于电池组（如锂电池、超级电容组） 的主动均衡技术，通过电…...

编程日记 2025/6/29 5:12:11

Matlab/Simulink - BLDC直流无刷电机仿真基础教程（七） - 波形解析专题P2

Matlab/Simulink - BLDC直流无刷电机仿真基础教程（七） - 波形解析专题P2 前言一、缺相与相线错接解析二、电源电压波动三、电机感量及磁链变化四、负载突变及堵转五、换相时机不当及换相错误参考链接前言本系列文章分享如何使用Matlab的Simulink功能来…...

编程日记 2025/7/13 17:20:19

如何从GitHub上调研优秀的开源项目，并魔改应用于工作中？

在 Go 语言学习中，我们经常会去学习一些优秀的开源项目。但是学完之后，发现很快就忘记了或者学习效果并不好。学习一个开源项目最好的方式就是围绕这个开源项目进行实战。例如，直接魔改这个开源项目并应用于工作中。本文来介绍下如何调用&…...

编程日记 2025/6/29 7:19:20

【Java学习笔记】构造器

构造器(constructor)（又名构造方法） 作用：可以在创建对象时就初始化属性，注意不是创建基本结构 [修饰符] 方法名（形参列表）{方法体； }代码示例 public class 构造器 {public static void m…...

编程日记 2025/6/29 7:16:54

Redis 数据类型详解（一）：String 类型全解析

文章目录前言一、什么是 Redis 的 String 类型？二、常用命令1.SET2.GET3.MSET4.MGET5.INCR6.INCRBY7.INCRBYFLOAT8.SETNX9.SETEX 三、注意事项总结前言提示：这里可以添加本文要记录的大概内容： 在学习 Redis 的过程中，最基础也…...

编程日记 2025/6/29 5:22:38

JAVA---多态

面向对象三大特征：封装、继承、多态多态定义：同类型的对象，表现出的不同形态。它允许不同类的对象通过同一个接口进行调用，并且在运行时根据实际对象类型执行不同的方法。多态主要通过继承、接口和方法重写来实现。表现形式…...

编程日记 2025/6/29 5:39:45

K8S的使用（部署pod\service）+安装kubesphere图形化界面使用和操作

master节点中通过命令部署一个tomcat 查看tomcat被部署到哪个节点上在节点3中进行查看在节点3中进行停止容器，K8S会重新拉起一个服务如果直接停用节点3（模拟服务器宕机），则K8S会重新在节点2中拉起一个服务暴露tomcat访…...

编程日记 2025/6/29 7:16:17

【Linux系统】第二节—基础指令（2）

hello ~ 好久不见自己想要的快乐要自己好好争取！ 云边有个稻草人-个人主页 Linux—本篇文章所属专栏—欢迎订阅—持续更新中目录本节课核心指令知识点总结本节基本指令详解 07.man 指令 08.cp 指令 09.mv 指令 10.cat 指令 11.more 指令 12.less 指令 …...

编程日记 2025/6/29 7:39:06

Java设计模式: 实战案例解析

Java设计模式: 实战案例解析在软件开发中，设计模式是一种用来解决特定问题的可复用解决方案。它们是经过实践验证的最佳实践，能够帮助开发人员设计出高质量、易于维护的代码。本文将介绍一些常见的Java设计模式，并通过实战案例解析它们在实际…...

编程日记 2025/6/29 8:27:24

ASP.NET MVC 入门与提高指南九

51. 时空数据处理与 MVC 应用拓展 51.1 时空数据概念时空数据是指与时间和空间相关的数据，如地理信息系统（GIS）数据、交通流量数据、气象数据等，这些数据随时间和空间变化而变化。 51.2 在 MVC 应用中处理时空数据地理信息系…...

编程日记 2025/6/29 5:12:10

算法学习时段效能分布

算法学习时段效能分布晨间时段（06:00-09:00）核心优势最佳任务午后时段（14:00-17:00）核心优势最佳任务夜间时段（20:00-23:00）核心优势最佳任务实证数据支持晨间时段（06:00-09:00&#xff09…...

编程日记 2025/7/3 10:46:50

Linux环境部署iview-admin项目

环境：阿里云服务系统：CentOS7.X系统 1、下载源码安装包 wget https://nodejs.org/dist/v14.17.3/node-v14.17.3-linux-x64.tar.xz2、解压并放入指定目录 tar -xf node-v14.17.3-linux-x64.tar.xz && mv node-v14.17.3-linux-x64 /usr/local/no…...

编程日记 2025/6/29 5:56:05

在 Ubuntu 系统中，查看已安装程序的方法

在 Ubuntu 系统中，查看已安装程序的方法取决于软件的安装方式（如通过 apt、snap、flatpak 或手动安装）。以下是几种常见方法： 通过 apt 包管理器安装的软件适用于通过 apt 或 dpkg 安装的 .deb 包。列出所有已安装的软件包&…...

编程日记 2025/6/29 5:30:33

c++26新功能——Pack indexing

一、模板编程在模板编程中，有一个问题比较突出，就是对变参模板中参数的控制，比较麻烦。因为是变参，所以想把参数单独拿出来处理，就需要借助一些特殊的技巧，而这种特殊的技巧，往往为大多数开发…...

编程日记 2025/6/29 5:22:57

VSCode通过SSH连接VMware虚拟机

以下是关于VSCode通过SSH连接VMware虚拟机的原理、必要条件及注意事项的说明： 一、连接原理 SSH协议通信：SSH（Secure Shell）是一种加密网络协议，VSCode通过Remote-SSH插件将本地开发环境与虚拟机终端绑定&a…...

编程日记 2025/7/9 17:34:38

7 微调黑盒蒸馏突破伦理限制

简介 SecGPT-Distill 是我自己做的一个实验模型, 开源地址: 主要功能是进行模型微调和知识蒸馏而来这次是运用微调技术，来突破现有模型在处理安全相关问题时的各种限制和约束代码开源: https://github.com/godzeo/SecGPT-distill-boundless 不回答原理大部…...

编程日记 2025/6/29 8:16:00

基于51单片机的温湿度控制器proteus仿真

地址： https://pan.baidu.com/s/1cENHPmF0XobqKg_7baZX3Q 提取码：1234 仿真图： 芯片/模块的特点： AT89C52/AT89C51简介： AT89C51 是一款常用的 8 位单片机，由 Atmel 公司（现已被 Microchip 收…...

编程日记 2025/6/29 6:52:41

牛客月赛115 C题-命运之弹题解

原题链接 https://ac.nowcoder.com/acm/contest/107879/C 题目描述解题思路记录每个数字出现的次数。枚举使用「转瞬即逝」的位置，统计后边比当前数字更大的数的数量，进而统计、更新答案。详细细节见代码，代码里有详细的注释解释。代…...

编程日记 2025/6/29 7:51:25

视频转GIF

视频转GIF 以下是一个使用 Python 将视频转换为 GIF 的脚本，使用了 imageio 和 opencv-python 库： import cv2 import imageio import numpy as np """将视频转换为GIF图参数:video_path -- 输入视频的路径gif_path -- 输出GIF的路径fp…...

编程日记 2025/6/29 5:12:51

day15 python 复习日

作业： 尝试找到一个kaggle或者其他地方的结构化数据集，用之前的内容完成一个全新的项目，这样你也是独立完成了一个专属于自己的项目。要求： 1.有数据地址的提供数据地址，没有地址的上传网盘贴出地址即可。 2.尽可能与…...

编程日记 2025/6/29 7:35:28

性能优化实践：渲染性能优化

性能优化实践：渲染性能优化在Flutter应用开发中，渲染性能直接影响用户体验。本文将从渲染流程分析入手，深入探讨Flutter渲染性能优化的关键技术和最佳实践。一、Flutter渲染流程解析 1.1 渲染流水线 Flutter的渲染流水线主要包含以下几…...

编程日记 2025/7/7 6:24:48

稀疏矩阵的快速转置

朴素的双重循环

快速转置

相关文章：