【数据结构】数组和字符串(四):特殊矩阵的压缩存储:稀疏矩阵——三元组表

文章目录

  • 4.2.1 矩阵的数组表示
  • 4.2.2 特殊矩阵的压缩存储
    • a. 对角矩阵的压缩存储
    • b~c. 三角、对称矩阵的压缩存储
    • d. 稀疏矩阵的压缩存储——三元组表
      • 结构体
      • 初始化
      • 元素设置
      • 打印矩阵
      • 主函数
      • 输出结果
      • 代码整合

4.2.1 矩阵的数组表示

【数据结构】数组和字符串(一):矩阵的数组表示

4.2.2 特殊矩阵的压缩存储

  矩阵是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵,如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等, 如果用这种方式存储,会出现大量存储空间存放重复信息或零元素的情况,这样会造成很大的空间浪费。为节约存储空间和算法(程序)运行时间,通常会采用压缩存储的方法。

  • 对角矩阵:指除了主对角线以外的元素都为零的矩阵,即对 任意 i ≠ j (1≤ i , j ≤n),都有M(i, j)=0。由于只有主对角线上有非零元素,只需存储主对角线上的元素即可。
  • 三角矩阵:指上三角或下三角的元素都为零的矩阵。同样地,只需存储其中一部分非零元素,可以节省存储空间。
  • 对称矩阵:指矩阵中的元素关于主对角线对称的矩阵。由于对称矩阵的非零元素有一定的规律,可以只存储其中一部分元素,从而减少存储空间。
  • 稀疏矩阵:指大部分元素为零的矩阵。传统的按行优先次序存储方法会浪费大量空间来存储零元素,因此采用压缩存储的方法更为合适。常见的压缩存储方法有:压缩稠密行(CSR)、压缩稠密列(CSC)、坐标列表(COO)等。

a. 对角矩阵的压缩存储

【数据结构】数组和字符串(二):特殊矩阵的压缩存储:对角矩阵——一维数组

b~c. 三角、对称矩阵的压缩存储

【数据结构】数组和字符串(三):特殊矩阵的压缩存储:三角矩阵、对称矩阵——一维数组

d. 稀疏矩阵的压缩存储——三元组表

  对于稀疏矩阵的压缩存储,由于非零元素的个数远小于零元素的个数,并且非零元素的分布没有规律,无法简单地利用一维数组和映射公式来实现压缩存储。针对稀疏矩阵,通常采用特定的数据结构来进行压缩存储,以减少存储空间的占用。

  一种常见的稀疏矩阵压缩存储方法是使用"三元组"表示法,也称为COO(Coordinate)格式,只存储非零元素的值以及它们的行列坐标。通过使用三元组(Triplet)来表示非零元素的位置和值,每个三元组包含三个信息:非零元素的行索引、非零元素的列索引以及非零元素的值。

结构体

typedef struct {int row;int col;int value;
} Triple;typedef struct {Triple data[MAX_SIZE];int rows;int cols;int length;
} TripletTable;

  定义了两个结构体:TripleTripletTable

  • Triple 结构体表示稀疏矩阵的非零元素,包含三个字段:row 表示行号,col 表示列号,value 表示元素的值。
  • TripletTable 结构体用于存储稀疏矩阵的数据,包含一个 data 数组用于存储非零元素的 Triple 结构体,以及 rowscolslength 字段分别表示矩阵的行数、列数和非零元素的数量。

初始化

void initTable(TripletTable* table, int rows, int cols) {table->rows = rows;table->cols = cols;table->length = 0;
}

   initTable 函数用于初始化 TripletTable 结构体,指定矩阵的行数和列数,并将 length 字段置为 0。

元素设置

void insertElement(TripletTable* table, int row, int col, int value) {if (table->length >= MAX_SIZE) {printf("Table is full. Cannot insert more elements.\n");return;}Triple* element = &(table->data[table->length]);element->row = row;element->col = col;element->value = value;table->length++;
}

  insertElement 函数用于向稀疏矩阵中插入一个元素,传入参数为行号、列号和元素的值。

  • 函数首先检查当前非零元素的数量是否已达到上限 MAX_SIZE
    • 如果达到上限则输出错误信息并返回。
    • 否则,将新元素插入到 data 数组的末尾,并更新 length 字段。

打印矩阵

void displayTable(TripletTable* table) {int matrix[table->rows][table->cols];for (int i = 0; i < table->rows; i++) {for (int j = 0; j < table->cols; j++) {matrix[i][j] = 0;}}printf("Row\tColumn\tValue\n");for (int i = 0; i < table->length; i++) {Triple* element = &(table->data[i]);printf("%d\t%d\t%d\n", element->row, element->col, element->value);matrix[element->row][element->col] = element->value;}printf("Matrix:\n");for (int i = 0; i < table->rows; i++) {for (int j = 0; j < table->cols; j++) {printf("%d\t", matrix[i][j]);}printf("\n");}
}

  displayTable 函数用于显示稀疏矩阵的内容:

  • 创建一个与稀疏矩阵相同大小的二维数组 matrix,并将其所有元素初始化为 0;
  • 遍历 data 数组中的非零元素,输出每个元素的行号、列号和值,并将相应位置的 matrix 数组元素更新为对应的值;
  • 输出整个矩阵的内容。

主函数

int main() {TripletTable table;initTable(&table, 3, 3);insertElement(&table, 0, 0, 1);insertElement(&table, 0, 1, 2);insertElement(&table, 1, 1, 3);insertElement(&table, 2, 2, 4);displayTable(&table);return 0;
}
  • 创建一个 TripletTable 结构体 table,并使用 initTable 函数初始化它,指定矩阵的行数和列数为3。
  • 调用 insertElement 函数向 table 中插入四个非零元素,分别位于 (0, 0)、(0, 1)、(1, 1) 和 (2, 2) 位置。
  • 通过调用 displayTable 函数,打印出稀疏矩阵的内容和对应的完整矩阵表示。

输出结果

代码整合

#include <stdio.h>
#define MAX_SIZE 10typedef struct {int row;int col;int value;
} Triple;typedef struct {Triple data[MAX_SIZE];int rows;int cols;int length;
} TripletTable;void initTable(TripletTable* table, int rows, int cols) {table->rows = rows;table->cols = cols;table->length = 0;
}void insertElement(TripletTable* table, int row, int col, int value) {if (table->length >= MAX_SIZE) {printf("Table is full. Cannot insert more elements.\n");return;}Triple* element = &(table->data[table->length]);element->row = row;element->col = col;element->value = value;table->length++;
}void displayTable(TripletTable* table) {int matrix[table->rows][table->cols];for (int i = 0; i < table->rows; i++) {for (int j = 0; j < table->cols; j++) {matrix[i][j] = 0;}}printf("Row\tColumn\tValue\n");for (int i = 0; i < table->length; i++) {Triple* element = &(table->data[i]);printf("%d\t%d\t%d\n", element->row, element->col, element->value);matrix[element->row][element->col] = element->value;}printf("Matrix:\n");for (int i = 0; i < table->rows; i++) {for (int j = 0; j < table->cols; j++) {printf("%d\t", matrix[i][j]);}printf("\n");}
}int main() {TripletTable table;initTable(&table, 3, 3);insertElement(&table, 0, 0, 1);insertElement(&table, 0, 1, 2);insertElement(&table, 1, 1, 3);insertElement(&table, 2, 2, 4);displayTable(&table);return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

双11满减大促,直播间1折抢购!

你是知道的&#xff0c;双11本来是光棍节&#xff01; 2009年&#xff0c;阿里掀起了一场网络促销活动&#xff0c;光棍节从此成了全民的购物节&#xff01; 从2009年到2021年&#xff0c;阿里双11当天的交易额&#xff0c;从仅有的0.5亿猛增至5403亿&#xff0c;以惊人的速度…

目标检测及锚框、IoU

文章目录 1. 目标检测2. 锚框3. IoU - 交并比4. 赋予锚框标号5. 使用非极大值抑制&#xff08;NMS&#xff09;输出 1. 目标检测 物体检测&#xff08;目标检测&#xff09;是计算机视觉和数字图像处理的热门方向&#xff0c;意在判断一幅图像上是否存在感兴趣物体&#xff0c…

List的add(int index,E element)陷阱,不得不防

项目场景&#xff1a; 项目中有两个List列表&#xff0c;一个是List1用来存储一个标识&#xff0c;后续会根据这个标识去重。 一个List2是用来返回对象的&#xff0c;其中对象里也有一个属性List3。现需要将重复的标识数据追加到List3 我想到的两个方案&#xff1a; 尽量不动…

C/S架构和B/S架构

1. C/S架构和B/S架构简介 C/S 架构&#xff08;Client/Server Architecture&#xff09;和 B/S 架构&#xff08;Browser/Server Architecture&#xff09;是两种不同的软件架构模式&#xff0c;它们描述了客户端和服务器之间的关系以及数据交互的方式。 C/S 架构&#xff08…

diffusion model (八) Dalle3 技术小结

paper&#xff1a;https://cdn.openai.com/papers/dall-e-3.pdf 创建时间&#xff1a; 2023-10-25 相关阅读 diffusion model&#xff08;一&#xff09;DDPM技术小结 (denoising diffusion probabilistic)diffusion model&#xff08;二&#xff09;—— DDIM技术小结diffu…

机器人入门(四)—— 创建你的第一个虚拟小车

机器人入门&#xff08;四&#xff09;—— 创建你的第一个虚拟小车 一、小车建立过程1.1 dd_robot.urdf —— 建立身体1.2 dd_robot2.urdf —— 添加轮子1.3 dd_robot3.urdf —— 添加万向轮1.4 dd_robot4.urdf —— 添加颜色1.5 dd_robot5.urdf —— 添加碰撞检测(Collision …

最近面试遇到的高频面试题

大家好&#xff0c;我是 jonssonyan 互联网寒冬&#xff1f;金九银十真的不存在了么&#xff1f;虽说现在行情是差了一些&#xff0c;面试机会少了一些&#xff0c;但是大部分公司还是或多或少的招人&#xff0c;春招秋招都在进行。有人离职就有人入职。所以如果你还没约到面试…

【Linux】安装与配置虚拟机及虚拟机服务器坏境配置与连接

目录 操作系统介绍 什么是操作系统 常见操作系统 UNIX操作系统 linux操作系统 mac操作系统 嵌入式操作系统 个人版本和服务器版本的区别 安装VMWare虚拟机 VMWare虚拟网卡 ​编辑 配置虚拟网络编辑器 ​编辑 安装配置Windows Server 2012 R2 安装Windows Server 2…

钉钉超过90天的文件需要一分钟重新激活的实现原理是什么?

具体实现原理可能包括以下几点&#xff1a; 冷热数据分类&#xff1a;系统会根据文件的访问频率将文件分为热数据和冷数据两类。热数据是经常被访问的文件&#xff0c;这些文件会被存储在快速的存储设备上&#xff0c;以便快速访问。冷数据是很少被访问的文件&#xff0c;这些…

小红书app拉新上线了 适合网推社群和校园渠道作业

小红书app签到拉新上线了可以通过“聚量推客”进行申请&#xff0c;下面大概是要求和流程 要求网推社群渠道或者地推校园渠道&#xff0c;其它类型渠道禁止

18 行为型模式-观察者模式

行为模式共有11种&#xff1a; 观察者模式 模板方法模式 策略模式 职责链模式 状态模式 命令模式 中介者模式 迭代器模式 访问者模式 备忘录模式 解释器模式 以上 11 种行为型模式&#xff0c;除了模板方法模式和解释器模式是类行为型模式&#xff0c;其他的全部属于对象行为型…

华为eNSP配置专题-策略路由的配置

文章目录 华为eNSP配置专题-策略路由的配置0、概要介绍1、前置环境1.1、宿主机1.2、eNSP模拟器 2、基本环境搭建2.1、终端构成和连接2.2、终端的基本配置 3、配置接入交换机上的VLAN4、配置核心交换机为网关和DHCP服务器5、配置核心交换机和出口路由器互通6、配置PC和出口路由器…

redis archive github

https://github.com/redis/redis/releases/tag/7.2.2https://github.com/redis/redis/releases/tag/7.2.2

塔式服务器介绍

大家都知道服务器分为机架式服务器、刀片式服务器、塔式服务器三类&#xff0c;今天小编就分别讲一讲这三种服务器&#xff0c;第三篇先来讲一讲塔式服务器的介绍。 塔式服务器定义&#xff1a;塔式服务器的外观和普通电脑差不多&#xff0c;直立放置。机箱比较大&#xff0c;服…

高数笔记04:微分方程与多元函数微分学

图源&#xff1a;文心一言 时间比较紧张&#xff0c;仅导图~~&#x1f95d;&#x1f95d; 第1版&#xff1a;查资料、画导图~&#x1f9e9;&#x1f9e9; 参考资料&#xff1a;《高等数学 基础篇》武忠祥 &#x1f9ae;思维导图 &#x1f636;‍&#x1f32b;️思维导图为整…

mysql的医院信息管理系统,数据库增删改查。

基于前端网页和后端服务的&#xff0c;mysql医院信息管理系统。 功能有&#xff1a;登录注册、首页、科室管理、科室列表、医院管理、医生列表、病人管理、护士管理、病房管理、文件管理等等。 并且引入了Echarts图标&#xff0c;可视化查看数据。 源码下载地址 支持&#xff…

Java——Spring的控制反转(一文详解IOC)

Spring&#xff0c;Spring MVC&#xff0c;Spring Boot 三者比较 答&#xff1a; 这三者专注的领域不同&#xff0c;解决的问题也不一样&#xff1b;总的来说&#xff0c;Spring 就像一个大家族&#xff0c;有众多衍生产品例如 Boot&#xff0c;Security&#xff0c;JPA等等。…

DeOldify 接口化改造 集成 Flask

类似的图片修复项目 GFPGAN 的改造见我另一篇文 https://blog.csdn.net/weixin_43074462/article/details/132497146 DeOldify 是一款开源软件&#xff0c;用于给黑白照片或视频上色&#xff0c;效果还不错。 安装部署教程请参考别的文章&#xff0c;本文基于你给项目跑通&…

Flask Run运行机制剖析

一、前言 已经玩了一段时间Flask &#xff0c;每次调用app.run(或flask run)就可以启动应用&#xff0c;今天我们就来了解一下run背后究竟做了些什么事情。 注&#xff1a;通过上面几行代码就可以启动一个Flask服务器&#xff0c;打开浏览器输入http://127.0.0.1:5000, 页面上…