【数据结构】特殊矩阵的压缩存储
🎇【数据结构】特殊矩阵的压缩存储🎇
🌈 自在飞花轻似梦,无边丝雨细如愁 🌈
🌟
正式开始学习数据结构啦~此专栏作为学习过程中的记录🌟
文章目录
- 🎇【数据结构】特殊矩阵的压缩存储🎇
- 🍰一.数组的存储结构
-
- 🚀1.数组的定义
- 🚀2.数组的存储结构
- 🍰二.特殊矩阵的存储结构
-
- 🚀1.普通矩阵的存储
- 🚀2.特殊矩阵的压缩存储
-
- 🔆1.对称矩阵
- 🔆2.三角矩阵
- 🔆3.三对角矩阵
- 🔆4.稀疏矩阵
🍰一.数组的存储结构
🚀1.数组的定义
数组是由n个相同类型的数据元素所构成的有限序列
数组和线性表的关系：
数组是线性表的推广：一维数组可以看做是一个线性表，而对于二维数组而言，可以看成是有多个线性表组成的线性表
也就是每一行
/
/
/列视都为一个线性表，总的线性表内每一个元素也是一个定长的线性表
🚀2.数组的存储结构
- 对于一维数组的存储，就是线性表，一维数组的所有元素在内存空间中占用一段连续的内存空间
那么，对于多维数组的存储，在计算机中是如何实现的呢？
- 对于多维数组的存储，在计算机中仍表现为一维数组的形式，也就是一段连续的内存空间
接下来，我们就要去尝试模拟计算机存放多维数组的过程：
有两种映射方式：行优先和列优先
①行优先：
以二维数组为例，以行优先存储的方式为：也就是逐行放入一维数组中
🌈 下标转换关系：
（我们默认下标从0开始）对于二维数组
A
[
N
]
[
M
]
A[N][M]
A[N][M] 中的元素
a
i
j
a_{ij}
aij ，若希望在行优先转化后的一维数组中访问它，我们可以确定其在一维数组中的下标为：
k
=
i
∗
M
+
j
k=i*M+j
k=i∗M+j
分解代码实现：
- 行优先二维转一维数组
void row_Reducedim(int a[][M],int *res, int row, int col)
{
int p = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
res[p++] = a[i][j];
}
}
}
- 按照索引从一维数组中取值
void visit(int res[], int i, int j)
{
if (i = 0 && j >= 0 && j <= M-1)
{
int k = i * M + j;
cout << res[k] << endl;
}
else
cout << "输入违规" << endl;
}
行优先完整代码实现：
#include
using namespace std;
void row_Reducedim(int a[][4],int *res, int row, int col)
{
int p = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
res[p++] = a[i][j];
}
}
}
void Print(int a[], int n)
{
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}cout << endl;
}
void visit(int res[], int i, int j)
{
if (i = 0 && j >= 0 && j <= 3)
{
int k = i * 4 + j;
cout << res[k] << endl;
}
else
cout << "输入违规" << endl;
}
int main() {
int martix[2][4] =
{ {1,2,3,4},
{5,6,7,8} };
int res[8];
//二维转一维
row_Reducedim(martix,res, 2, 4); //行优先
cout << "行转化后的一维数组为：" << endl;
Print(res,8);
//二维数组元素在一维数组内的映射
int i, j;
cout <=0)" <> i >> j;
visit(res, i, j);
system("pause");
return 0;
}
②列优先：
以二维数组为例，以行优先存储的方式为：也就是逐列放入一维数组中
🌈 下标转换关系：
对于二维数组
A
[
N
]
[
M
]
A[N][M]
A[N][M] 中的元素
a
i
j
a_{ij}
aij ，其在一维数组中的下标为：
k
=
j
∗
N
+
i
k=j*N+i
k=j∗N+i
分解代码实现：
- 列优先二维转一维数组
void col_Reducedim(int a[][4], int* res1, int row, int col)
{
int p = 0;
for (int j = 0; j < col; j++) {
for (int i = 0; i < row; i++) {
res1[p++] = a[i][j];
}
}
}
- 按照索引从一维数组中取值
void visit1(int res[], int i, int j)
{
if (i = 0 && j >= 0 && j <= 3)
{
int k = j * 2 + i;
cout << res[k] << endl;
}
else
cout << "输入违规" << endl;
}
列优先完整代码实现：
#include
using namespace std;
void col_Reducedim(int a[][4], int* res1, int row, int col)
{
int p = 0;
for (int j = 0; j < col; j++) {
for (int i = 0; i < row; i++) {
res1[p++] = a[i][j];
}
}
}
void Print(int a[], int n)
{
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}cout << endl;
}
void visit1(int res[], int i, int j)
{
if (i = 0 && j >= 0 && j <= 3)
{
int k = j * 2 + i;
cout << res[k] << endl;
}
else
cout << "输入违规" << endl;
}
int main() {
int martix[2][4] =
{ {1,2,3,4},
{5,6,7,8} };
int res1[8];
//二维转一维
col_Reducedim(martix, res1, 2, 4); //列优先
cout << "列转化后的一维数组为：" << endl;
Print(res1, 8);
int a, b;
cout <=0)" <> a >> b;
visit1(res1, a, b);
system("pause");
return 0;
}
输出结果：
🍰二.特殊矩阵的存储结构
🚀1.普通矩阵的存储
对于普通的矩阵，我们可以将其视为二维数组进行处理，也就是按行优先和列优先的方式存储，在之前也已经提到过
🚀2.特殊矩阵的压缩存储
压缩存储：指为多个值相同的元素所分配一个存储空间，对零元素不分配存储空间，用于节省空间
接下来，我们来看几个典型的特殊矩阵：
🔆1.对称矩阵
对于一个n阶的方阵，我们可以将其划分为主对角线，上三角区和下三角区，而对于对称矩阵来说，有
a
i
j
=
a
j
i
a_{ij}=a_{ji}
aij=aji，因此，若仍然采用二维数组存储，会造成一半的空间浪费
策略：
因此，我们其实只需要 存主对角线和下三角块 即可：
🌊 对称矩阵与存储后一维数组的映射关系：
我们规定矩阵元素的下标
i
，
j
i，j
i，j的范围为
[
1
,
n
]
[1,n]
[1,n]，而一维数组的下标默认是从0开始的
- 一维数组大小：
第一行：一个元素，
a
11
a_{11}
a11
第二行：两个元素，
a
21
,
a
22
a_{21},a_{22}
a21,a22
…
共有
n
n
n 行，则元素总数
k
=
n
∗
(
n
+
1
)
/
2
k=n*(n+1)/2
k=n∗(n+1)/2
-
压缩存储后的访问：
又回到了，压缩完成之后，我们应该如何获取这些数据呢？
我们只需要定义一个映射函数即可：
策略：
不难发现，如果我们希望取出二维数组内的元素
a
i
j
a_{ij}
aij，我们已知了它的行号和列号：
①先看行向：
在
a
i
j
a_{ij}
aij上面的元素（即前
i
−
1
i-1
i−1行）的元素个数为：
i
∗
(
i
−
1
)
/
2
i*(i-1)/2
i∗(i−1)/2
②再看列向：
在
a
i
j
a_{ij}
aij前面的元素（即前
j
−
1
j-1
j−1行）的元素个数为:
j
−
1
j-1
j−1
由于一维数组下标是从
0
0
0开始的，因此：
a
i
j
的一维数组下标
=
在
a
i
j
前的元素个数
a_{ij}的一维数组下标=在a_{ij}前的元素个数
aij的一维数组下标=在aij前的元素个数
再由
a
i
j
=
a
j
i
a_{ij}=a_{ji}
aij=aji，因此，映射函数为：
完整代码实现：
#include
using namespace std;
//打印下三角
void triangle(int a[][3], int* res, int row, int col)
{
int p = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (i >= j)
res[p++] = a[i][j];
}
}
}
//访问
void visit(int res[], int i, int j)
{
if (i >= j)
{
int k = i * (i - 1) / 2 + j - 1;
cout << res[k] << endl;
}
else
{
int k = j * (j - 1) / 2 + i - 1;
cout << res[k] << endl;
}
}
//打印一维数组
void Print(int a[], int n)
{
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}cout << endl;
}
int main() {
int martix[3][3] =
{ {1,2,3},
{2,1,2},
{3,2,1} };
int res[6];
triangle(martix, res, 3, 3);
cout << "下三角的一维数组为：" << endl;
Print(res,6);
int i, j;
cout <=1)：" <> i >> j;
visit(res, i, j);
system("pause");
return 0;
}
输出结果：
🔆2.三角矩阵
三角矩阵就是有一个三角区全为常量的矩阵
策略：
其储存思维和对称矩阵类似，不同之处就在于：
✅ 存储完下三角区和主对角线后，紧接着存储对角线上方的常量，也就是要在对称矩阵构造的一维数组后面添加一个常数项
-
一维数组的大小：
k
=
n
∗
(
n
+
1
)
/
2
+
1
k=n*(n+1)/2+1
k=n∗(n+1)/2+1
映射函数为：
完整代码实现：
#include
using namespace std;
//打印下三角
void triangle(int a[][3], int* res, int row, int col,int n)
{
int p = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (i >= j)
res[p++] = a[i][j];
}
}
//存常量
int c = a[0][n-1];
res[n * (n + 1) / 2] = c;
}
//访问
void visit(int res[], int i, int j,int n)
{
if (i >= j)
{
int k = i * (i - 1) / 2 + j - 1;
cout << res[k] << endl;
}
else
{
int k = n * (n + 1)/2;
cout << res[k] << endl;
}
}
//打印一维数组
void Print(int a[], int n)
{
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}cout << endl;
}
int main() {
int martix[3][3] =
{ {1,4,4},
{2,1,4},
{3,2,1} };
int res[6];
triangle(martix, res, 3, 3,3);
cout << "下三角的一维数组为：" << endl;
//加一个常数项
Print(res, 6+1);
int i, j;
cout <=1)：" <> i >> j;
visit(res, i, j,3);
system("pause");
return 0;
}
输出结果：
🔆3.三对角矩阵
三对角矩阵也称带状矩阵，对于n阶方阵的A中的任一元素
a
i
j
a_{ij}
aij，当
∣
i
−
j
∣
>
1
|i-j|>1
∣i−j∣>1时，
a
i
j
=
0
a_{ij}=0
aij=0
策略：
将三条对角线上的元素按行优先原则存放在一维数组中(零元素不存)
-
一维数组的大小：
由于只有第一行和最后一行只有两个元素，因此，一维数组大小为：
l
e
n
=
3
n
−
2
len=3n-2
len=3n−2
映射函数为：
由于前
i
−
1
i-1
i−1行有
3
(
i
−
1
)
−
1
3(i-1)-1
3(i−1)−1个元素，当前行前面有
j
−
i
+
1
j-i+1
j−i+1个元素
k
=
2
i
+
j
−
3
k=2i+j-3
k=2i+j−3
反之，若我们已知
a
i
j
a_{ij}
aij存放于一维数组中的第 k个位置，怎么推出行数和列数呢？
i
=
⌈
(
k
+
2
)
/
3
⌉
i=⌈(k+2)/3⌉
i=⌈(k+2)/3⌉ 再由公式
k
=
2
i
+
j
−
3
k=2i+j-3
k=2i+j−3可以推出：
j
=
k
−
2
i
+
3
j=k-2i+3
j=k−2i+3
完整代码实现：
#include
#include
using namespace std;
//转一维矩阵
void Three(int a[][4], int* res, int row, int col)
{
int p = 0;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (a[i][j] != 0)
res[p++] = a[i][j];
}
}
}
void Print(int a[],int n) {
for (int i = 0; i < n; i++) {
cout << a[i] << " ";
}cout << endl;
}
void visit1(int a[], int i, int j)
{
int k = 2*i + j - 3;
printf("a%d%d=%d\n", i,j,a[k]);
}
void visit2(int a[], int k)
{
int i, j;
i = ceil((k + 2) / 3);
j = k - 2 * i + 3;
printf("访问的元素为:a%d%d\n", i, j);
}
int main() {
int martix[4][4] =
{
{1,2,0,0},
{1,2,3,0},
{0,2,3,4},
{0,0,3,4}
};
int res[10];
//转一维
Three(martix, res, 4, 4);
cout << "三对角的一维矩阵为：" << endl;
Print(res, 10);
//正向访问
int i, j;
cout <=1)：" <> i >> j;
visit1(res, i, j);
//反向访问
int k;
cout<<"请输入该元素在一维数组中的下标：" <> k;
visit2(res, k);
system("pause");
return 0;
}
输出结果：
🔆4.稀疏矩阵
还有一种特殊矩阵，其矩阵内的非0元素远远少于零元素，则称其为稀疏矩阵
e
.
g
e.g
e.g 如下矩阵：
| 我们只存取非零元素，但其分布往往没有规律，因此，我们还应该记录它的位置 |
策略：
将非零元素的行，列，值构成一个三元组
（行标，列标，值）
（行标，列标，值）
（行标，列标，值）
✅ 我们用结构体定义这个三元组：
#define Maxsize 100
//结构体定义三元组
typedef struct {
int i;
int j;
int val;
}Triple[Maxsize]; //结构体数组
完整代码实现：
#include
#define Maxsize 100
using namespace std;
//结构体定义三元组
typedef struct {
int i;
int j;
int val;
}Triple[Maxsize]; //结构体数组
//稀疏矩阵转三元组
void triple(Triple &T,int a[][5],int row,int col,int &p)
{
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (a[i][j] != 0) {
T[p].i = i+1;
T[p].j = j+1;
T[p].val = a[i][j];
p++;
}
}
}
}
void Print(Triple &T,int len) {
for (int i = 0; i < len; i++) {
printf("a%d%d=",T[i].i,T[i].j);
cout << T[i].i<< " " << T[i].j << " " << T[i].val << endl;
}
}
int main() {
int martix[5][5] =
{
{0,2,0,0,0},
{0,0,1,0,2},
{3,0,0,0,1},
{0,5,0,0,0},
{1,0,4,0,0}
};
Triple T;
int p = 0;
//稀疏矩阵转三元组
triple(T, martix, 5, 5, p);
cout << "转化后的三元组为（矩阵元素下标从1开始）:\n" << endl;
Print(T, p);
system("pause");
return 0;
}
输出结果：
🎇本节详细讲解了数组相关操作及各种特殊矩阵的压缩存储方式~🎇
如有错误，欢迎指正~！
本文来自网络，不代表协通编程立场，如若转载，请注明出处：https://net2asp.com/99249333bf.html
相关推荐
-
Python–从PDF中提取文本的方法总结
目录 前言 一、pdfplumber 二、pdfminer 三、fitz / pymupdf 四、性能对比 前言 这段时间做了好几个关于年报的需求，其中无一例外需要从年报PDF中提…
-
【大虾送书第三期】《Python高并发与高性能编程: 原理与实践》
目录 ✨写在前面 ✨主要内容 ✨本书特色 ✨关于作者 🦐博客主页：大虾好吃吗的博客 🦐专栏地址：免费送书活动专栏地址 写在前面 …
-
Python-Django的“日志功能-日志模块(logging模块)-日志输出”的功能详解
提前说明：如果是简单的日志输出，看我的另一篇博客就够，链接如下： 提前说明：如果是简单的日志输出，看我的另一篇博客就够，链接如下： https://blog.csdn.net/we…
-
YOLOV5配置至运行（本人亲装遇见常见的错误及解决方案）
现在是2023年3月26日，由于最近有个比赛需要用到yolov5但是本人从前从未接触此方面知识，想着先给他跑起来再说。于是本人亲自装在自己电脑上，准备跑一下，并且和大家一样踩了很多…
-
Python的离线安装
原文链接 在没有外网的情况下，安装Python环境只能采用离线方式。 Windows离线安装Python Python离线安装包的下载地址：https://www.python.o…
-
【 Python ModuleNotFoundError: No module named ‘xxx‘可能的解决方案大全】
Python ModuleNotFoundError: No module named ‘xxx‘可能的解决方案大全 本文主要介绍了Python ModuleNotFoundErr…
-
C++（Qt）与Python混合编程
文章开头，请大家注意一点： 开始搭配环境之前，请大家完成对自己电脑位数的查看【32位/64位】 本篇博客适用于windows64位版本安装。当然了，32位的友友也可以对照着配置！ …
-
偏最小二乘(PLS)原理分析&Python实现
目录 1 偏最小二乘的意义 2 PLS实现步骤 3 弄懂PLS要回答的问题 4 PLS的原理分析 4.1 自变量和因变量的主成分求解原理 4.1.1 确定目标函数 …
-
数据库——ER图知识点详集
目录 一、介绍 二、ER图中的基本元素 1、实体 2、属性 3、实体集 4、键 5、联系 三、ER图中三种关联的联系 四、ER图的画图规范 五、ER图中的主键与外键 六…
-
基于Docker安装Elasticsearch【保姆级教程、内含图解】
Elasticsearch官网：欢迎来到 Elastic — Elasticsearch 和 Kibana 的开发者 | Elastic 学习任何框架和技术，一定要…
