【数据结构】特殊矩阵的压缩存储|保姆级详解+图解

news/2024/11/29 14:52:59/

在这里插入图片描述

  • 作者：努力学习的大一在校计算机专业学生，热爱学习和创作。目前在学习和分享：算法、数据结构、Java等相关知识。
  • 博主主页： @是瑶瑶子啦
  • 所属专栏: 【数据结构】：该专栏专注于数据结构知识，持续更新，每一篇内容优质，浅显易懂，不失深度！
  • 近期目标：写好专栏的每一篇文章

在这里插入图片描述

目录

  • 📌一、特殊矩阵的压缩存储
    • 📍1.1：前言
    • 📍1.2：规律矩阵
      • 1.2.1：三角矩阵
          • 📪1.2.1.1：对称矩阵
          • 📪1.2.1.2：下三角矩阵
          • 📪1.2.1.3：上三角矩阵
          • 📍：三角矩阵——题目01
      • 1.2.2：带状矩阵（三对角矩阵）
    • 📍1.2：稀疏矩阵
      • 1.2.1：三元组法存储稀疏矩阵
      • 1.2.1：十字链表法存储稀疏矩阵

📌一、特殊矩阵的压缩存储

📍1.1：前言

在线性代数这门学科中已经学习了矩阵。在高级计算机语言中，矩阵常用二维数组表示。
所谓**“压缩存储”**，目的在于节省空间！体现在，为多个值相同的元素只分配一个存储空间，多元素值为0的元素不分配空间

  • 二维数组A[n][n]和A[0...n-1][0...n-1]的写法是等价的。如果数组写法为A[1..n]A[1..n],则说明指定了下标是从1开始存储元素。二维数组元素写为a[i][j],注意数组元素下标i和j通常是从0开始的。矩阵元素通常写为a i,j或者a(i),(j)，注意这时的i和j代表的行号和列号，都是从1开始的！

这里我们讨论两种特殊矩阵

  1. 元素分布有特殊规律的矩阵，寻找规律对应的公式实现压缩存储
    • 三角矩阵（上三角、下三角、对称矩阵）
    • 带状矩阵
  2. 稀疏矩阵
    • 三元组表示法
    • 十字链表

📍1.2：规律矩阵

💥这里给出实现压缩（矩阵元素A(i)(j)在压缩后一维数组B[]中的下标对应关系）的核心公式：

  • 矩阵非零元素A(i)(j)在一维数组B中求对应下标

Loc[i,j]=Loc[1,1]+(a(i)(j)前面的非零元素个数））Loc[i,j] = Loc[1,1] + ( a(i)(j)前面的非零元素个数）） Loc[i,j]=Loc[1,1]+(a(i)(j)前面的非零元素个数））

  • 矩阵非零元素a(i)(j)在一维数组B中地址(size是单个元素的字节大小）

Loc[A(i)(j)]=Loc[A(1,1)]+(a(i)(j)前面的非零元素个数))∗sizeLoc[A(i)(j)] = Loc[A(1,1)] + ( a(i)(j)前面的非零元素个数))*size Loc[A(i)(j)]=Loc[A(1,1)]+(a(i)(j)前面的非零元素个数))∗size

由于通常Loc[1,1]即A(1)(1)在一维数组B中下标是0（下面给的公式也是按照B数组下标从0开始），所以0就被省略，没有写出来

1.2.1：三角矩阵

🍊对于一个n阶矩阵A来说：

  • 对称矩阵

    • 矩阵中所有元素都满足a(i)(j) = a(j)(i)

  • 下三角矩阵

    • i < j时（在对角线之上），有a(i)(j) = c (当 c = 0，时，上三角区域元素均为0）

  • 上三角矩阵

    • i > j时（在对角线之下），有a(i)(j) = c (当 c = 0，时，下三角区域元素均为0）

在这里插入图片描述

📪1.2.1.1：对称矩阵

对于对称矩阵，我们知道在下三角区域和上三角区域存在a(i)(j) = a(j)(i)，我们其实只用存储下三角（或者上三角）+ 对角线这部分区域的元素即可，节省了上三角区域元素所占用空间。

所以，我们可以将一个n阶的对称矩阵A，存储在一个一维数组B[(n + 1)*n /2]中（下面以下三角矩阵存储为例，注意，一维数组B的下标设为从0开始！）

那么我们只用知道元素a(i)(j)元素在B数组中的下标，即可实现压缩！而a(i)(j)在B数组中的下标和其i和j有关（类似于把二维数组中元素按行优先或者按列优先，转存到一维数组中！）

在这里插入图片描述
🌳压缩核心：求出a(i)(j)前面有多少个元素，0 + 相差元素个数（指针跳过中间相差元素个数），得到的就是a(i)(j)在B数组中的下标（其实也是地址的映射）
🥕公式 |a(i)(j)在B数组中的下标K：

  • i >= j,下三角区域和主对角线元素

k=i(i−1)2+j−1k= \frac{i(i-1)}{2}+j -1 k=2i(i−1)​+j−1

  • 对于上三角区域，由于a(i)(j) == a(j)(i),所以直接把上面公式中的i和j互换即可
    k=j(j−1)2+i−1k= \frac{j(j-1)}{2}+i -1 k=2j(j−1)​+i−1

🦋扩充：

  • 当B数组下标从0开始，求出的a(i)(j)的下标，是和首元素相隔元素个数
  • 数组下标其实是地址（指针）的映射，知道相差元素个数，再 * 单个元素字节大小，再加上起始地址（这里就是B[0]的地址），即可求得a(i)(j)在内存中的地址
📪1.2.1.2：下三角矩阵

下三角矩阵和对称矩阵存储思路大致相同，不同的在于：对上三角区域元素的存储上。因为上三角区域元素值均为相同的常值C，所以只用开一个存储空间来存储即可。所以相应的，三角矩阵的对应的B数组会多一个空间，来存储。也就是B数组的容量为：n(n+1)/2 + 1
在这里插入图片描述
🌳压缩核心：求出a(i)(j)前面有多少个元素，0 + 相差元素个数（指针跳过中间相差元素个数），得到的就是a(i)(j)在B数组中的下标（其实也是地址的映射）;对于上三角区域的常值元素在B数组中都公用一个坐标
🥕公式 |a(i)(j)在B数组中的下标K：

  • i >= j,下三角区域和主对角线元素

k=i(i−1)2+j−1k= \frac{i(i-1)}{2}+j -1 k=2i(i−1)​+j−1

  • 对于上三角区域（j > i),a(i)(j) = c,这些元素全部在B数组的尾部的一个空间存储;前面有n(n+1)/2个元素，相应的坐标也是这么多
    k=n(n+1)2k= \frac{n(n+1)}{2} k=2n(n+1)​
📪1.2.1.3：上三角矩阵

对于上三角矩阵，求解元素在B数组中的坐标的核心思路不变；上面求解比如a(i)(j)前面有多少个元素，都是按照行优先的规则（第一行填满，再接着下一行）；而对于上三角，我们采用列优先的方法
在这里插入图片描述

🥕公式 |a(i)(j)在B数组中的下标K：

  • i <= j,上三角区域和主对角线元素

k=j(j−1)2+i−1k= \frac{j(j-1)}{2}+i -1 k=2j(j−1)​+i−1

  • 对于上三角区域（j > i),a(i)(j) = c,这些元素全部在B数组的尾部的一个空间存储;前面有n(n+1)/2个元素，相应的坐标也是这么多
    k=n(n+1)2k= \frac{n(n+1)}{2} k=2n(n+1)​
📍：三角矩阵——题目01

某n*n的矩阵A中，对角线以上的元素全为0。因此我们将对角线以下的元素 按行
存储在一个一维数组B中（下标均从1开始）。那么A[i][j]在一维数组B中的下标为（ ）。

A、 i*(i+1)/2 + j
B、i*(i-1)/2 + j - 1
C、i*(i+1)/2 + j - 1
D、i*(i-1)/2 + j✅

🌳思路
因为B数组下标也是从1开始（我个人是这样理解的，如果一维数组的下标是从1开始，那么下标同时具有的含义是：这个元素为第几个元素）；所以，我们只用知道A[i][j]在下三角排列时，它是按行排列的第几个元素即可。那么就是先把行排满：(1 + i - 1) * (i - 1) / 2,再加上列的：j;所以i*(i-1)/2 + j即表示A[i][j]是第几个元素，同样表示它在B数组中的下标和第几个元素。

🙇‍♀️注意

  • 一定要注意，不管是矩阵A还是数组B，下标都是从1开始的！这点确实有点坑。如果A矩阵（看作二维数组）的第一个元素是从a[1][1]开始的话，且B数组下标从0开始，那么这题答案就是i*(i-1)/2 + j - 1！
  • 这里因为是下三角，我们采用行优先的方式存储矩阵中的元素（从上到下，存完一行再存下一行）
  • 如果是上三角（存储的元素位于矩阵的对角线以上包括对角线），采用列优先的方式存储（从右向左，存满一列再存下一列）
  • 二维数组A[n][n]和A[0...n-1][0...n-1]的写法是等价的。如果数组写法为A[1..n]A[1..n],则说明指定了下标是从1开始存储元素。二维数组元素写为a[i][j],注意数组元素下标i和j通常是从0开始的。矩阵元素通常写为a i,j或者a(i),(j)，注意这时的i和j代表的行号和列号，都是从1开始的！
    在这里插入图片描述

1.2.2：带状矩阵（三对角矩阵）

📪1)：描述

在矩阵中，所有非零元素都集中在以主对角线为中心的带状区域中。其中，最常见的是三对角带状矩阵
在这里插入图片描述

📪2)：非零a(i)(j)特点；

  • i = 1(第一行，只有两个元素）：j = 1, 2
  • 1 < i < n（中间行，每行有三个元素，j有三个取值）：j = i - 1, i , i +1
  • i = n (最后一行，只有两个元素）： j = n-1, n

📪3)：压缩方法；
🕵️‍♀️①：确定存储该矩阵所需的一维存储空间（即一维数组B）的空间大小
每一行假设都有3个元素，但是由于第一行和最后一行只有两个，所以一维数组的容量为：3n - 2
🕵️‍♀️②：确定非零元素a(i)(j)在一维空间的下标（地址)
这里假设一维数组B的下标是从0开始，即首元素A[1][1]在B数组的下标是0，由此得出A[i][j]在B数组的下标为它前面的元素个数（A[i][j]和A[1][1]间隔的元素个数）

  • 第i行中a(i)(j)前非0元素个数为：前 i - 1 行非零元素个数 + 第i行中非零元素个数 = 3（i-1）-1 + 第i行中非零元素个数
  • 第i行中非零元素个数: j - i + 1
    • j - i = - 1 (j < i)
    • j - i = 0 (j = i)
    • j - i = 1 (j > i)

由此得到：A(i)(j)在B数组中的下标为（其中Loc(1)(1) = 0
Loc[i,j]=Loc[1,1]+(2(i−1)+j−1）Loc[i,j] = Loc[1,1] + (2(i-1) + j -1） Loc[i,j]=Loc[1,1]+(2(i−1)+j−1）

📍1.2：稀疏矩阵

稀疏矩阵是指矩阵中大多数元素为0的矩阵。从直观上来讲，当非零元素低于总元素的30%时，这样的矩阵称为稀疏矩阵

🤷‍♀️稀疏矩阵有两种压缩存储方式：

  • 三元组法
  • 十字链表法

接下来我们分别来详细介绍这2种方法

1.2.1：三元组法存储稀疏矩阵

📪1)：三元组法的存储表示

🤔我们知道，稀疏矩阵中有许多0元素，存储这些非零元素大大浪费了空间。所以我们只用把非零元素存储下来，即可大大节省空间。那么如何存储呢？

三元组法，再通俗来说，就是给每个非零元素在存储自身的值的基础上再加两个域

  • 行域：存储这个非零元素在原来的的矩阵中所占的行号
  • 列域：存储这个非零元素在原来的矩阵中所占的列号

在这里插入图片描述

说明：为了处理方便，将稀疏矩阵中非零元素的三元组，按照行序为主序（行号为排序的第一关键字）、列号为第二关键字，进行排序。得到相应矩阵的三元组表
在这里插入图片描述
在这里插入图片描述

📪2)：三元组表类型定义

#define MAXSIZE 1000	//非零元素个数最多为1000//三元组的定义，用于存储一个非零元素
typedef struct{int row,col;	//存储该非零元素的行和列ElementType e;	//存储该非零元素的值
} Triple;//三元组表的定义
typedef struct{Triple data[MAXSIZE + 1];	//非零元素的三元组表。data[0]未用int m, n, len;	//原来矩阵的行数、列数、非零元素的个数
}TSMatrix;

1.2.1：十字链表法存储稀疏矩阵

🥕和用二维数组来存储稀疏矩阵相比，三元组表来存储稀疏矩阵大大节约了空间，且使得矩阵的某些运算（比如：矩阵的转置）的算法效率也提高。
🤔但是，当需要进行矩阵的加减乘除运算时，矩阵中非零元素的个数和位置可能会发变化甚至极大，那么三元组表为了保持：存储非零元素且以行序为第一关键字、列序为第二关键字，势必要移动、增加大量元素，这样是十分麻烦的。

🙋‍♀️为了避免大量移动、增加元素，采用一种新的，压缩存储稀疏链表的方法：十字链表法。

📪1)：十字链表的存储表示

和三元组法存储矩阵相比，你可以把十字链表法叫作“五元组法”。为何这么说呢？
因为每一个非零元素节点，不仅有这3个域：（row , col , value).还增加了两个链域：

  • right:链接同一行中的下一个非零元素
  • down:链接同一列中的下一个非零元素

在十字链表中，同一行的的非零元素由于right指针，链接称为一个单链表。同一列的非零元素通过down指针链接成一个单链表。
所以某一个非零元素，既会属于某一行，也会属于某一列，行和列在这一点相交，像一个十字路口，所以这种方法根据这种形象的感觉，命名为：十字链表法。
同时，还需要设两个一维数组：

  • 一个负责存储行的单链表的头指针
  • 一个负责存储列的单链表的头指针
    在这里插入图片描述
    🦋十字链表简单来说是通过链表来存储元素的。我们知道，和数组相比，链表在删除、移动、插入元素方面可是杠杠的，效率要比数组的效率高很多。正是这一点，解决了这一part开始所说的，由于非零元素的插入，需要大规模移动元素的问题。
    综上，十字链表能够灵活的插入由于矩阵的运算而产生的非零元素，删除因为矩阵运算而产生的新的零元素，实现矩阵的各种运算！

📪2)：十字链表类型定义

typedef struct OLNode{int row, col;	//非零元素的行号和列号ElementType value;struct OLNode *right, *down;	//非零元素所在行链、列链的后继指针域
}OLNode; * OLink;typedef struct{OLink * row_head, *col_head;	//两个辅助一维数组，存储行链表、列链表的头节点//CrossList.row_head = (OLink *)malloc ( (m+1) ,sizeof (OLink));int m, n, len;	//存储原矩阵的行数、列数、非零元素个数
}CrossList;

在这里插入图片描述

  • Java岛冒险记【从小白到大佬之路】
  • LeetCode每日一题–进击大厂
  • 算法

http://www.ppmy.cn/news/39171.html

相关文章

Java 核心技术 - 异常处理机制

Java 核心技术 - 异常处理机制

一、异常分类 Java 异常可以分为三类&#xff1a;受检查异常&#xff08;checked exception&#xff09;、运行时异常&#xff08;runtime exception&#xff09;和错误&#xff08;error&#xff09;。 受检查异常是在编译时就需要处理的异常&#xff0c;如果没有处理会导致…
阅读更多...
RPC

RPC

#什么是RPC RPC是指远程过程调用&#xff0c;也就是说两台服务器A&#xff0c;B&#xff0c;一个应用部署在A服务器上&#xff0c;想要调用B服务器上应用提供的函数/方法&#xff0c;由于不在一个内存空间&#xff0c;不能直接调用&#xff0c;需要通过网络来表达调用的语义和传…
阅读更多...
Ae：表达式语法基础

Ae：表达式语法基础

Ae 中所有的属性都有一个或多个值 Value。通过表达式更改属性的初值&#xff0c;在过程中可以使用不同类型的数据或方法&#xff0c;但最终的值必须跟初值同类型。了解四种值类型是学好表达式的基础及关键。单值Number只有一个值的数据。比如&#xff0c;整数 5 或者是实数 3.1…
阅读更多...
机器学习：基于逻辑回归对超市销售活动预测分析

机器学习：基于逻辑回归对超市销售活动预测分析

系列文章目录 作者&#xff1a;i阿极 作者简介&#xff1a;Python领域新星作者&#xff1a;博主个人首页 &#x1f60a;&#x1f60a;&#x1f60a;如果觉得文章不错或能帮助到你学习&#xff0c;可以点赞&#x1f44d;收藏&#x1f4c1;评论&#x1f4d2;关注哦&#xff01;&a…
阅读更多...
C enum(枚举)

C enum(枚举)

C enum(枚举) 枚举是 C 语言中的一种基本数据类型&#xff0c;用于定义一组具有离散值的常量。&#xff0c;它可以让数据更简洁&#xff0c;更易读。 枚举类型通常用于为程序中的一组相关的常量取名字&#xff0c;以便于程序的可读性和维护性。 定义一个枚举类型&#xff0c…
阅读更多...
TS的装饰器原理

TS的装饰器原理

对于前端而言&#xff0c;装饰器是一个陌生的概念&#xff0c;但是对于 Java、C# 等语言来说装饰器这一概念并不陌生。 所谓装饰器&#xff0c;就是一种特殊的类型声明&#xff0c;它可以被附加到「属性」、「类声明」、「方法」、「方法参数」上。 他的好处就是可以编写元信…
阅读更多...
最优控制中不同情形下泛函取到极值的必要条件

最优控制中不同情形下泛函取到极值的必要条件

最优控制中不同情形下泛函取到极值的必要条件最优控制中不同情形下泛函取到极值的必要条件引言一般问题1. t0t_0t0​ 固定&#xff0c;t1t_1t1​ 固定&#xff0c;x0x(t0)x_0x(t_0)x0​x(t0​) 固定&#xff0c;x1x(t1)x_1x(t_1)x1​x(t1​) 固定2. t0t_0t0​ 固定&#xff0c;…
阅读更多...
【计算机组成原理】王道中央处理器学习笔记

【计算机组成原理】王道中央处理器学习笔记

声明&#xff1a;本文在经过 努力的clz同意的情况下进行了一定的借鉴。图片来源于王道&#xff0c;本文仅用于学习所用&#xff01;王道计算机组成原理课代表 - 考研计算机 第五章 中央处理器 究极精华总结笔记_努力的clz的博客-CSDN博客CPU的功能和基本结构cpu的功能&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023