数据结构(3.9_1)——特殊矩阵的压缩存储

总览

一维数组的存储结构 

如果下标从1开始,则a[i]的存放地址=LOC +(i-1)*sizeof(ElemType); 

 二维数组的存储

二维数组也具有随机存储的特性

设起始地址为LOC 

在M行N列的二维数组b[M][N]中,若按行优先存储,

b[i][j]的存储地址的=LOC + (i*N+j) * sizeof(ElemType)

在M行N列的二维数组b[M][N]中,若按列优先存储,

b[i][j]的存储地址的=LOC + (j*N+i) * sizeof(ElemType)

行优先存储的优点:可以随机存储、

列优先存储

普通矩阵的存储

对普通矩阵存储我们可以采用二维数组存储

  1. 行优先存储(大多数编程语言,如 C/C++、Java、Python):

    position=i*n+j

  2. 列优先存储(某些语言和库,如 Fortran):

    position=j*m+i

普通矩阵的存储通常涉及到计算机内存中的数据结构。在大多数编程语言中,矩阵通常被实现为一维数组或者二维数组。

  1. 一维数组存储:在这种方法中,矩阵被 flatten 成一个一维数组。例如,一个 2x3 的矩阵:


    \begin{bmatrix} 1&2 &3 \\ 4&5 &6 \end{bmatrix}

  2. 可以被存储为一个一维数组 [1, 2, 3, 4, 5, 6]。在内存中,这个数组是连续存储的。要访问矩阵中的元素,需要通过特定的公式来计算其在数组中的位置。例如,要访问元素 (i, j),在列优先存储(Column-major order)中,其在一维数组中的位置是 i + j * rows;在行优先存储(Row-major order)中,其位置是 i * cols + j

  3. 二维数组存储:在这种方法中,矩阵被存储为一个二维数组。在大多数编程语言中,这通常是通过数组的数组或者动态分配的二维数组来实现的。例如,在 C 语言中,可以使用 int matrix[2][3] 来声明一个 2x3 的矩阵。在内存中,这个二维数组同样是连续存储的,但是以行或列的顺序。

每种存储方法都有其优缺点。一维数组存储更节省空间,因为不需要存储额外的行或列的指针信息,但是在访问特定元素时可能需要更多的计算。二维数组存储在访问元素时更直观,但是在某些编程语言中可能需要更多的内存来存储额外的指针信息。

对称矩阵的压缩存储

若n阶方阵中任意一个元素都\alpha i,j\alpha i,j=\alpha j,i,则该矩阵为对称矩阵

策略:只存储主队角线+下三角区

行优先原则将各元素存入一维数组中

数组大小应该设置为(1+n)*n/2 ,简而言之就是一个等差数列求和

,问题:对称矩阵压缩存储后该怎么样才能方便使用?

可以实现一个“映射”函数

矩阵下标—>一维数组下标

i>j(下三角)时

下标为0,从第0行开始元素个数有1个第二行元素个数2个....到最后一行有n个,所以它的元素总数为个,所以我们设置的一维数组大小应该就这么大,然后求aij在一维数组的坐标我们应该算出aij是第几个元素,按照行优先的原则,我们先得出aij前面有多少行,第一行为1,然后最后一行是i-1本身,为什么要-1呢?因为下标是从0开始的,所以转换成一维数组后需要减1如果下标从1开始则bu'xu'y,求出等差数列和为\frac{i\cdot (i-1))}{2},注意这里i-1才是项数,i是首项加末项由i-1+1得来,然后再算出aij前面有多少列元素,根据推导可得有j个元素,所以k=\frac{i\cdot(i-1))}{2}+j-1,这里-1原理同上

i<j(上三角)时

由于对称矩阵aij=aji ,所以k=\frac{j\cdot(j-1))}{2}ij-1

出题思路:

下标从0开始,先求aij前面有多少列元素,第一列是n元素,第二列n-1一值到最后一列n-(j-1-1),为什么要加1呢?因为,我们求的是i-1,i-1有n-(j-1-1)个元素,接下来再求行元素,根据图不难发现,求行元素只需将i-j便可求出除该元素之外本行有多少行元素,因为下标从0开始,所以最后再加上1得出坐标为k=\frac{i\cdot(i-j+3)}{2}+(i-j)+1

三角矩阵的压缩存储

下三角矩阵:

除了主对角线和下三角区,其余的元素都相同

 压缩存储策略:按行优先原则将橙色区元素存入一维数组中。并在最后一个位置存储常量c

映射规律下三角区的规律和对称矩阵的相同,只是访问上三角区的时候我们需要把下标映射到一维数组的最后一个位置

上三角矩阵:

除了主对角线和上三角区,其余的元素都相同 

压缩存储策略:按行优先原则将绿色区元素存入一维数组中。并在最后一个位置存储常量c 

 首先我们确定aij前面有多少行,所以我们需要知道i-1行,第一行是n个,第二行n-1个,所以第n行有n-(i-1),所以第i-1行是n-(i-1-1)=n-i+2,等差数列求和:(\frac{(i-1)\cdot(2n-i+2))}{2})得知i前面有个(\frac{(i-1)\cdot(2n-i+2))}{2})元素,我们再来计算j前面有多少列元素,就是j-i,得知j前面有j-i个元素,于是我们得知aij是第(\frac{(i-1)\cdot(2n-i+2))}{2})+j-(i-1)-1个元素,最后-1是因为下标从0开始

三对角矩阵的压缩策略

三对角矩阵是一种特殊的带状矩阵,它在矩阵中只有主对角线、主对角线上方的一条对角线和主对角线下方的一条对角线上的元素是非零的,而其他位置的元素都是零。这种矩阵在数值分析中非常常见,尤其是在求解线性方程组时。

 三对角矩阵:当|i-j|>1时,有aij=0 (1<=i,j<=n)

压缩策略:按行优先(或列优先原则,只存储带状部分)

由三队角矩阵可见除第一行和最后一行元素是两个以外其它行元素都是3个所以元素总数是3n-2如果默认下标是0开始,那么最后一个数组的下标则是3n-3

将行号和列号映射为一维数组下标

key:按行优先的原则,aij是第几个元素 

求行:前i-1行共有3(i-1)-1个元素

求列:aij是i行第j-i+2个元素(看图推理得出)

求一维数组下标:行列元素相加得k=2i+j-2,若数组下标从0开始,则k=2i+j-3

已知k求aij

 

求B[k]转换成aij的坐标,首先由于k是数组下标是从0开始的,而题目要求k+1则是从1开始

前i-1行共3(i-1)-1个元素,前i行共有 3i-1

所以得出:3(i-1)-1<k+1\leq 3i-1

可以理解为i刚好大于等于(k+2)/3 : i\geq \frac{k+2}{3}向上取整即可满足"刚好"大于等于:i=\frac{k+2}{3}

稀疏矩阵的压缩存储

稀疏矩阵:非零元素远远少于矩阵元素的个数

压缩存储策略1:

顺序存储---三元组<行,列,值>

压缩存储策略2:

链式存储---十字链表法

总结:

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

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

相关文章

【Element-UI 表格表头、内容合并单元格】

一、实现效果&#xff1a; &#x1f970; 表头合并行、合并列 &#x1f970; &#x1f970; 表格内容行、合并列 &#x1f970; thead和tbody分别有单独的合并方法 二、关键代码&#xff1a; <el-table size"mini" class"table-th-F4F6FB" align&qu…

最好的照片恢复软件是什么?您需要了解的十大照片恢复工具

在当今的数字时代&#xff0c;丢失的珍贵照片可能是一件令人心碎的事情。无论是由于意外删除、文件损坏还是意外格式&#xff0c;对专业摄影师和普通拍照爱好者的影响都是巨大的。幸运的是&#xff0c;各种照片恢复软件解决方案可以帮助您恢复这些丢失的记忆。本文根据第一手经…

论文阅读--Simple Baselines for Image Restoration

这篇文章是 2022 ECCV 的一篇文章&#xff0c;是旷视科技的一篇文章&#xff0c;针对图像恢复任务各种网络结构进行了梳理&#xff0c;最后总结出一种非常简单却高效的网络结构&#xff0c;这个网络结构甚至不需要非线性激活函数。 文章一开始就提到&#xff0c;虽然在图像复原…

微调及代码

一、微调&#xff1a;迁移学习&#xff08;transfer learning&#xff09;将从源数据集学到的知识迁移到目标数据集。 二、步骤 1、在源数据集&#xff08;例如ImageNet数据集&#xff09;上预训练神经网络模型&#xff0c;即源模型。 2、创建一个新的神经网络模型&#xff…

python基础篇(9):模块

1 模块简介 Python 模块(Module)&#xff0c;是一个 Python 文件&#xff0c;以 .py 结尾. 模块能定义函数&#xff0c;类和变量&#xff0c;模块里也能包含可执行的代码. 模块的作用: python中有很多各种不同的模块, 每一个模块都可以帮助我们快速的实现一些功能, 比如实现…

概论(二)随机变量

1.名词解释 1.1 样本空间 一次具体实验中所有可能出现的结果&#xff0c;构成一个样本空间。 1.2 随机变量 把结果抽象成数值&#xff0c;结果和数值的对应关系就形成了随机变量X。例如把抛一次硬币的结果&#xff0c;正面记为1&#xff0c;反面记为0。有变量相对应的就有自…

SpringBoot实战:轻松实现接口数据脱敏

一、接口数据脱敏概述 1.1 接口数据脱敏的定义 接口数据脱敏是Web应用程序中一种保护敏感信息不被泄露的关键措施。在API接口向客户端返回数据时&#xff0c;系统会对包含敏感信息&#xff08;如个人身份信息、财务数据等&#xff09;的字段进行特殊处理。这种处理通过应用特…

多个版本JAVA切换(学习笔记)

多个版本JAVA切换 很多时候&#xff0c;我们电脑上会安装多个版本的java版本&#xff0c;java8&#xff0c;java11&#xff0c;java17等等&#xff0c;这时候如果想要切换java的版本&#xff0c;可以按照以下方式进行 1.检查当前版本的JAVA 同时按下 win r 可以调出运行工具…

WMS系统的核心功能

WMS系统&#xff08;Warehouse Management System&#xff09;的核心功能主要包括以下几个方面&#xff1a; ———————————————————————— 1、库存管理&#xff1a; 1):跟踪库存数量、位置和状态&#xff0c;确保实时库存可见性。 2):支持批次管理、序列…

文心快码——百度研发编码助手

介绍 刚从中国互联网大会中回来&#xff0c;感受颇深吧。百度的展商亮相了文心快码&#xff0c;展商人员细致的讲解让我们一行了解到该模型的一些优点。首先&#xff0c;先来简单介绍一下文心快码吧。 文心快码&#xff08;ERNIE Code&#xff09;是百度公司推出的一个预训练…

【STM32标准库】读写内部FLASH

1.内部FLASH的构成 STM32F407的内部FLASH包含主存储器、系统存储器、OTP区域以及选项字节区域。 一般我们说STM32内部FLASH的时候&#xff0c;都是指这个主存储器区域&#xff0c;它是存储用户应用程序的空间。STM32F407ZGT6型号芯片&#xff0c; 它的主存储区域大小为1MB。其…

ppt翻译免费怎么做?5个方法让你秒懂PPT的内容

当你收到一份来自海外的PPT资料&#xff0c;眼前或许是一片陌生的语言海洋&#xff0c;但别让这成为理解与灵感之间的障碍。 这时&#xff0c;一款优秀的PPT翻译软件就如同你的私人导航员&#xff0c;能迅速将这份知识宝藏转化为你熟悉的语言&#xff0c;让每一个图表、每一段…

Unity引擎制作玻璃的反射和折射效果

Unity引擎制作玻璃球玻璃杯 大家好&#xff0c;我是阿赵。   之前做海面效果的时候&#xff0c;没做反射和折射的效果&#xff0c;因为我觉得过于复杂的效果没有太大的实际作用。这方面的效果&#xff0c;我就做了现在这个例子来补充一下。 在这个demo场景里面&#xff0c;我…

社交媒体数据分析:赋能企业营销策略的利器

一、数据&#xff1a;未来的石油与导航仪 在数字化转型的大潮中&#xff0c;数据已成为推动企业发展的新燃料。它不仅是决策的依据&#xff0c;更是预见未来的水晶球。特别是在社交媒体这片广袤的海洋里&#xff0c;每一条帖子、每一次点赞、评论都蕴藏着消费者的偏好、市场的…

thinkphp8框架源码精讲

前言 很开心你能看到这个笔记&#xff0c;相信你对thinkphp是有一定兴趣的&#xff0c;正好大家都是志同道合的人。 thinkphp是我入门学习的第一个框架&#xff0c;经过这么多年了&#xff0c;还没好好的研究它&#xff0c;今年利用了空闲的时间狠狠的深入源码学习了一把&…

Proteus + Keil单片机仿真教程(五)多位LED数码管的静态显示

Proteus + Keil单片机仿真教程(五)多位LED数码管 上一章节讲解了单个数码管的静态和动态显示,这一章节将对多个数码管的静态显示进行学习,本章节主要难点: 1.锁存器的理解和使用; 2.多个数码管的接线封装方式; 3.Proteus 快速接头的使用。 第一个多位数码管示例 元件…

Qt学生管理系统(付源码)

Qt学生管理系统 一、前言1.1 项目介绍1.2 项目目标 2、需求说明2.1 功能性说明2.2 非功能性说明 三、UX设计3.1 登录界面3.2 学生数据展示3.3 信息插入和更新 三、架构说明3.1 客户端结构如下3.2 数据流程图3.2.1 数据管理3.2.2 管理员登录 四、 设计说明3.1 数据库设计3.2 结构…

嵌入式要卷成下一个Java了吗?

嵌入式系统与Java的关系在技术发展和市场需求的影响下在逐步演变&#xff0c;但尚未达到完全替代的阶段。我收集归类了一份嵌入式学习包&#xff0c;对于新手而言简直不要太棒&#xff0c;里面包括了新手各个时期的学习方向编程教学、问题视频讲解、毕设800套和语言类教学&…

system V共享内存【Linux】

文章目录 原理shmgetftokshmat(share memory attach)shmdt&#xff0c;去关联&#xff08;share memory delete attach&#xff09;shmctl ,删除共享内存共享内存与管道 原理 共享内存本质让不同进程看到同一份资源。 申请共享内存&#xff1a; 1、操作系统在物理内存当中申请…

【鸿蒙学习笔记】通过用户首选项实现数据持久化

官方文档&#xff1a;通过用户首选项实现数据持久化 目录标题 使用场景第1步&#xff1a;源码第2步&#xff1a;启动模拟器第3步&#xff1a;启动entry第6步&#xff1a;操作样例2 使用场景 Preferences会将该数据缓存在内存中&#xff0c;当用户读取的时候&#xff0c;能够快…