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

勤奋不是嘴上说说而已,而是实际的行动,在勤奋的苦度中持之以恒,永不退却。业精于勤,荒于嬉;行成于思,毁于随。在人生的仕途上,我们毫不迟疑地选择勤奋,她是几乎于世界上一切成就的催产婆。只要我们拥着勤奋去思考,拥着勤奋的手去耕耘,用抱勤奋的心去对待工作,浪迹红尘而坚韧不拔,那么,我们的生命就会绽放火花,让人生的时光更加的闪亮而精彩。

导读:本篇文章讲解 【数据结构】特殊矩阵的压缩存储|保姆级详解+图解,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com,来源:原文

在这里插入图片描述

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

在这里插入图片描述

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

📍1.1:前言

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

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

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

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

📍1.2:规律矩阵

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

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

L

o

c

[

i

,

j

]

=

L

o

c

[

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是单个元素的字节大小)

L

o

c

[

A

(

i

)

(

j

)

]

=

L

o

c

[

A

(

1

,

1

)

]

+

(

a

(

i

)

(

j

)

)

)

s

i

z

e

Loc[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

1

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

k=2i(i1)+j1

  • 对于上三角区域,由于a(i)(j) == a(j)(i),所以直接把上面公式中的i和j互换即可

    k

    =

    j

    (

    j

    1

    )

    2

    +

    i

    1

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

    k=2j(j1)+i1

🦋扩充:

  • 当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

1

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

k=2i(i1)+j1

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

    k

    =

    n

    (

    n

    +

    1

    )

    2

    k= \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

1

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

k=2j(j1)+i1

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

    k

    =

    n

    (

    n

    +

    1

    )

    2

    k= \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],注意数组元素下标ij通常是从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

L

o

c

[

i

,

j

]

=

L

o

c

[

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(i1)+j1

📍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;

在这里插入图片描述

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/142438.html

(0)

及时掌握行业动态,欢迎加入几百人的后端技术交流群:


相关推荐

发表回复

登录后才能评论