1. Toy模板网首页
  2. > Toy博客

【数据结构】特殊矩阵的压缩存储

9月前 作者：DAY Ⅰ 分类：Toy博客 阅读(44) 违法举报

这篇具有很好参考价值的文章主要介绍了【数据结构】特殊矩阵的压缩存储。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

🎇【数据结构】特殊矩阵的压缩存储🎇


🌈 自在飞花轻似梦,无边丝雨细如愁 🌈

【数据结构】特殊矩阵的压缩存储

 

🌟 正式开始学习数据结构啦~此专栏作为学习过程中的记录🌟

🍰一.数组的存储结构

🚀1.数组的定义

数组是由n个相同类型的数据元素所构成的有限序列

数组和线性表的关系：
数组是线性表的推广：一维数组可以看做是一个线性表，而对于二维数组而言，可以看成是有多个线性表组成的线性表

也就是每一行 / / /列视都为一个线性表，总的线性表内每一个元素也是一个定长的线性表

【数据结构】特殊矩阵的压缩存储


🚀2.数组的存储结构

  1. 对于一维数组的存储，就是线性表，一维数组的所有元素在内存空间中占用一段连续的内存空间

【数据结构】特殊矩阵的压缩存储


那么，对于多维数组的存储，在计算机中是如何实现的呢？

  1. 对于多维数组的存储，在计算机中仍表现为一维数组的形式，也就是一段连续的内存空间
    【数据结构】特殊矩阵的压缩存储

接下来，我们就要去尝试模拟计算机存放多维数组的过程：


有两种映射方式：行优先和列优先

①行优先：

以二维数组为例，以行优先存储的方式为：也就是逐行放入一维数组中
【数据结构】特殊矩阵的压缩存储

🌈 下标转换关系：

（我们默认下标从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

分解代码实现：

  1. 行优先二维转一维数组
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];
		}
	}
}

  1. 按照索引从一维数组中取值
void visit(int res[], int i, int j)
{
	if (i <= N-1 && i >= 0 && j >= 0 && j <= M-1)
	{
		int k = i * M + j;
		cout << res[k] << endl;
	}
	else
		cout << "输入违规" << endl;
}

行优先完整代码实现：

#include<iostream>
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 <= 1 && 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)" << endl;
	cin >> 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

分解代码实现：

  1. 列优先二维转一维数组
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];
		}
	}
}

  1. 按照索引从一维数组中取值
void visit1(int res[], int i, int j)
{
	if (i <= 1 && i >= 0 && j >= 0 && j <= 3)
	{
		int k = j * 2 + i;
		cout << res[k] << endl;
	}
	else
		cout << "输入违规" << endl;
}

列优先完整代码实现：

#include<iostream>
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 <= 1 && 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)" << endl;
	cin >> 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开始的

【数据结构】特殊矩阵的压缩存储

  1. 一维数组大小：
    第一行：一个元素， 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

【数据结构】特殊矩阵的压缩存储


  1. 压缩存储后的访问：

    又回到了，压缩完成之后，我们应该如何获取这些数据呢？

    我们只需要定义一个映射函数即可：

【数据结构】特殊矩阵的压缩存储

策略：

不难发现，如果我们希望取出二维数组内的元素 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<iostream>
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 << "请输入需要访问的元素aij中的下标i,j(>=1)：" << endl;
	cin >> i >> j;
	visit(res, i, j);

	system("pause");
	return 0;
}

输出结果：

【数据结构】特殊矩阵的压缩存储


🔆2.三角矩阵

三角矩阵就是有一个三角区全为常量的矩阵

【数据结构】特殊矩阵的压缩存储


策略：

其储存思维和对称矩阵类似，不同之处就在于：

✅ 存储完下三角区和主对角线后，紧接着存储对角线上方的常量，也就是要在对称矩阵构造的一维数组后面添加一个常数项

【数据结构】特殊矩阵的压缩存储


  1. 一维数组的大小：

     

    k = n ∗ ( n + 1 ) / 2 + 1 k=n*(n+1)/2+1 k=n∗(n+1)/2+1

  2. 映射函数为：

【数据结构】特殊矩阵的压缩存储


完整代码实现：

#include<iostream>
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 << "请输入需要访问的元素aij中的下标i,j(>=1)：" << endl;
	cin >> 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

【数据结构】特殊矩阵的压缩存储


策略：

将三条对角线上的元素按行优先原则存放在一维数组中(零元素不存)

【数据结构】特殊矩阵的压缩存储


  1. 一维数组的大小：
    由于只有第一行和最后一行只有两个元素，因此，一维数组大小为：
     

    l e n = 3 n − 2 len=3n-2 len=3n−2

  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<iostream>
#include<math.h>
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 << "请输入需要访问的元素aij中的下标i,j(>=1)：" << endl;
	cin >> i >> j;
	visit1(res, i, j);

	//反向访问
	int k;
	cout<<"请输入该元素在一维数组中的下标：" << endl;
	cin >> 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<iostream>
#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://www.toymoban.com/news/detail-500578.html

到了这里，关于【数据结构】特殊矩阵的压缩存储的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处： 如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：
领支付宝红包 赞助服务器费用

相关文章

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包，优惠每天领

二维码1

领取红包

二维码2

领红包