多维数组与特殊矩阵:存储与压缩

ops/2024/11/26 21:10:51/

多维数组与特殊矩阵:存储与压缩

一、多维数组的存储

(一)基本概念

多维数组是线性表的推广,例如二维数组可以看作是元素为一维数组的线性表,三维数组可以看作是元素为二维数组的线性表,以此类推。在内存中,多维数组需要按照一定的顺序进行存储,常见的存储方式有行优先存储和列优先存储。

(二)行优先存储

以二维数组为例,行优先存储是先存储第一行的元素,然后再存储第二行的元素,依此类推。对于一个 mn 列的二维数组 a[m][n],其元素 a[i][j] 在内存中的地址计算(假设每个元素占用 k 个字节,数组首地址为 base):
[LOC(a[i][j]) = base + (i * n + j) * k]

(三)列优先存储

列优先存储则是先存储第一列的元素,再存储第二列的元素等。对于上述二维数组,元素 a[i][j] 在列优先存储下的内存地址计算:
[LOC(a[i][j]) = base + (j * m + i) * k]

(四)C 语言示例

以下是一个在 C 语言中对二维数组进行初始化并计算其元素地址的示例:

#include <stdio.h>// 假设元素为 int 类型,每个 int 占 4 个字节
#define ELEMENT_SIZE 4// 计算行优先存储下元素的地址
int rowMajorAddress(int a[][100], int i, int j, int m, int n) {int base = (int)a;return base + (i * n + j) * ELEMENT_SIZE;
}// 计算列优先存储下元素的地址
int colMajorAddress(int a[][100], int i, int j, int m, int n) {int base = (int)a;return base + (j * m + i) * ELEMENT_SIZE;
}int main() {// 声明一个 3 行 4 列的二维数组并初始化int matrix[3][4] = {{1, 2, 3, 4},{5, 6, 7, 8},{9, 10, 11, 12}};// 计算并打印行优先存储下元素 matrix[1][2] 的地址int rowAddr = rowMajorAddress(matrix, 1, 2, 3, 4);printf("行优先存储下 matrix[1][2] 的地址: %d\n", rowAddr);// 计算并打印列优先存储下元素 matrix[1][2] 的地址int colAddr = colMajorAddress(matrix, 1, 2, 3, 4);printf("列优先存储下 matrix[1][2] 的地址: %d\n", colAddr);return 0;
}

二、特殊矩阵的存储与压缩

(一)对称矩阵

  1. 存储特点
    • 对称矩阵是指 a[i][j] = a[j][i]矩阵。对于一个 n 阶对称矩阵,我们只需要存储其下三角(或上三角)部分的元素即可,因为根据对称性可以得到另一半元素的值。
  2. 存储方式
    • 可以将下三角部分按行优先存储到一个一维数组 sa 中。对于下三角元素 a[i][j]i >= j),其在一维数组中的下标 k 计算如下:
      [k=\frac{i(i + 1)}{2}+j]
  3. C 语言示例
// 存储对称矩阵的下三角部分到一维数组
void storeSymmetricMatrix(int a[][100], int sa[], int n) {int k = 0;for (int i = 0; i < n; i++) {for (int j = 0; j <= i; j++) {sa[k++] = a[i][j];}}
}// 根据一维数组恢复对称矩阵
void restoreSymmetricMatrix(int a[][100], int sa[], int n) {int k = 0;for (int i = 0; i < n; i++) {for (int j = 0; j <= i; j++) {a[i][j] = sa[k];a[j][i] = sa[k++];}}
}int main() {// 声明一个 4 阶对称矩阵并初始化int symmetricMatrix[4][4] = {{1, 2, 3, 4},{2, 5, 6, 7},{3, 6, 8, 9},{4, 7, 9, 10}};int sa[10];  // 用于存储对称矩阵下三角部分的一维数组// 存储对称矩阵下三角部分storeSymmetricMatrix(symmetricMatrix, sa, 4);// 恢复对称矩阵int restoredMatrix[4][4];restoreSymmetricMatrix(restoredMatrix, sa, 4);// 打印恢复后的对称矩阵,验证正确性for (int i = 0; i < 4; i++) {for (int j = 0; j < 4; j++) {printf("%d ", restoredMatrix[i][j]);}printf("\n");}return 0;
}

(二)三角矩阵

  1. 上三角矩阵
    • 存储特点:上三角矩阵是主对角线以下元素全为 0 的矩阵。对于 n 阶上三角矩阵,我们可以只存储其主对角线及以上的元素。
    • 存储方式:按行优先存储主对角线及以上元素到一维数组 ua 中。对于上三角元素 a[i][j]i <= j),其在一维数组中的下标 k 计算如下:
      [k=\frac{(2n - i - 1)i}{2}+j - i]
    • C 语言示例
// 存储上三角矩阵到一维数组
void storeUpperTriangularMatrix(int a[][100], int ua[], int n) {int k = 0;for (int i = 0; i < n; i++) {for (int j = i; j < n; j++) {ua[k++] = a[i][j];}}
}// 根据一维数组恢复上三角矩阵
void restoreUpperTriangularMatrix(int a[][100], int ua[], int n) {int k = 0;for (int i = 0; i < n; i++) {for (int j = i; j < n; j++) {a[i][j] = ua[k++];if (j > i) {a[j][i] = 0;}}}
}int main() {// 声明一个 4 阶上三角矩阵并初始化int upperTriangularMatrix[4][4] = {{1, 2, 3, 4},{0, 5, 6, 7},{0, 0, 8, 9},{0, 0, 0, 10}};int ua[10];  // 用于存储上三角矩阵的一维数组// 存储上三角矩阵storeUpperTriangularMatrix(upperTriangularMatrix, ua, 4);// 恢复上三角矩阵int restoredUpperMatrix[4][4];restoreUpperTriangularMatrix(restoredUpperMatrix, ua, 4);// 打印恢复后的上三角矩阵,验证正确性for (int i = 0; i < 4; i++) {for (int j = 0; j < 4; j++) {printf("%d ", restoredUpperMatrix[i][j]);}printf("\n");}return 0;
}
  1. 下三角矩阵
    • 存储特点:下三角矩阵是主对角线以上元素全为 0 的矩阵
    • 存储方式:类似对称矩阵下三角存储,按行优先存储下三角元素到一维数组 la 中。对于下三角元素 a[i][j]i >= j),其在一维数组中的下标 k 计算同对称矩阵下三角元素存储下标计算:
      [k=\frac{i(i + 1)}{2}+j]
    • C 语言示例
// 存储下三角矩阵到一维数组
void storeLowerTriangularMatrix(int a[][100], int la[], int n) {int k = 0;for (int i = 0; i < n; i++) {for (int j = 0; j <= i; j++) {la[k++] = a[i][j];}}
}// 根据一维数组恢复下三角矩阵
void restoreLowerTriangularMatrix(int a[][100], int la[], int n) {int k = 0;for (int i = 0; i < n; i++) {for (int j = 0; j <= i; j++) {a[i][j] = la[k++];if (j < i) {a[j][i] = 0;}}}
}int main() {// 声明一个 4 阶下三角矩阵并初始化int lowerTriangularMatrix[4][4] = {{1, 0, 0, 0},{2, 5, 0, 0},{3, 6, 8, 0},{4, 7, 9, 10}};int la[10];  // 用于存储下三角矩阵的一维数组// 存储下三角矩阵storeLowerTriangularMatrix(lowerTriangularMatrix, la, 4);// 恢复下三角矩阵int restoredLowerMatrix[4][4];restoreLowerTriangularMatrix(restoredLowerMatrix, la, 4);// 打印恢复后的下三角矩阵,验证正确性for (int i = 0; i < 4; i++) {for (int j = 0; j < 4; j++) {printf("%d ", restoredLowerMatrix[i][j]);}printf("\n");}return 0;
}

(三)对角矩阵

  1. 存储特点
    • 对角矩阵是指除主对角线及其相邻若干条对角线上的元素外,其余元素均为 0 的矩阵。以三对角矩阵为例,其主对角线以及主对角线上下各一条对角线上有非零元素。
  2. 存储方式
    • 可以将三对角矩阵的非零元素按行优先存储到一维数组 da 中。对于三对角矩阵中的元素 a[i][j],当 |i - j| <= 1 时为非零元素。其在一维数组中的下标 k 计算如下:
      [k = 3i - 1 + j - i = 2i + j - 1](当 (i = 0) 时,(k = j))
  3. C 语言示例
// 存储三对角矩阵到一维数组
void storeTriDiagonalMatrix(int a[][100], int da[], int n) {int k = 0;for (int i = 0; i < n; i++) {for (int j = i - 1; j <= i + 1; j++) {if (j >= 0 && j < n) {da[k++] = a[i][j];}}}
}// 根据一维数组恢复三对角矩阵
void restoreTriDiagonalMatrix(int a[][100], int da[], int n) {int k = 0;for (int i = 0; i < n; i++) {for (int j = i - 1; j <= i + 1; j++) {if (j >= 0 && j < n) {a[i][j] = da[k++];} else {a[i][j] = 0;}}}
}int main() {// 声明一个 5 阶三对角矩阵并初始化int triDiagonalMatrix[5][5] = {{1, 2, 0, 0, 0},{3, 4, 5, 0, 0},{0, 6, 7, 8, 0},{0, 0, 9, 10, 11},{0, 0, 0, 12, 13}};int da[14];  // 用于存储三对角矩阵的一维数组// 存储三对角矩阵storeTriDiagonalMatrix(triDiagonalMatrix, da, 5);// 恢复三对角矩阵int restoredTriMatrix[5][5];restoreTriDiagonalMatrix(restoredTriMatrix, da, 5);// 打印恢复后的三对角矩阵,验证正确性for (int i = 0; i < 5; i++) {for (int j = 0; j < 5; j++) {printf("%d ", restoredTriMatrix[i][j]);}printf("\n");}return 0;
}

(四)稀疏矩阵

  1. 存储特点
  2. 存储方式 - 三元组顺序表
    • 可以使用三元组顺序表来存储稀疏矩阵。三元组顺序表包含三个一维数组,分别存储非零元素的行下标、列下标和值。
    • 首先定义三元组结构体:
typedef struct {int row;int col;int value;
} Triple;
  • 然后定义三元组顺序表结构体:
typedef struct {Triple data[100];int num;  // 非零元素个数
} SparseMatrix;
  • 存储稀疏矩阵到三元组顺序表的函数:
// 存储稀疏矩阵到三元组顺序表
void storeSparseMatrix(int a[][100], SparseMatrix *sm, int m, int n) {sm->num = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (a[i][j]!= 0) {sm->data[sm->num].row = i;sm->data[sm->num].col = j;sm->data[sm->num].value = a[i][j];sm->num++;}}}
}
  • 根据三元组顺序表恢复稀疏矩阵的函数:
// 根据三元组顺序表恢复稀疏矩阵
void restoreSparseMatrix(int a[][100], SparseMatrix sm, int m, int n) {for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {a[i][j] = 0;}}for (int k = 0; k < sm.num; k++) {a[sm.data[k].row][sm.data[k].col] = sm.data[k].value;}
}
  • C 语言示例
int main() {// 声明一个稀疏矩阵并初始化int sparseMatrix[5][5] = {{0, 0, 3, 0, 0},{0, 0, 0, 0, 0},{0, 6, 0, 0, 0},{0, 0, 0, 0, 9},{0, 0, 0, 0, 0}};SparseMatrix sm;// 存储稀疏矩阵到三元组顺序表storeSparseMatrix(sparseMatrix, &sm, 5, 5);// 恢复稀疏矩阵int restoredSparseMatrix[5][5];restoreSparseMatrix(restoredSparseMatrix, sm, 5, 5);// 打印恢复后的稀疏矩阵,验证正确性for (int i = 0; i < 5; i++) {for (int j = 0; j < 5; j++) {printf("%d ", restoredSparseMatrix[i][j]);}printf("\n");}return 0;
}

通过对多维数组和各种特殊矩阵的存储与压缩方式的深入理解和掌握,能够在处理大规模数据矩阵相关的问题时,有效地减少存储空间的占用并提高数据处理的效率。在实际应用中,例如在图像处理、科学计算(如有限元分析中的矩阵运算)、数据挖掘等领域,这些技术都有着广泛的应用前景。
在图像处理中,图像可以看作是一个二维矩阵,当处理一些具有特定对称性或稀疏性的图像数据时,利用相应的矩阵存储和压缩技术,可以减少内存的占用,加快图像的处理速度,如对一些纹理具有对称性的图像进行压缩存储以便后续的传输或分析。
在科学计算里,很多物理问题的数学模型最终会转化为大规模的矩阵运算。例如在结构力学的有限元分析中,得到的刚度矩阵往往是对称矩阵或稀疏矩阵,采用合适的存储方式能够显著降低存储需求,提高计算效率,使得在有限的计算机资源下能够处理更复杂的结构模型。
在数据挖掘领域,一些关联矩阵或相似度矩阵可能具有稀疏性的特点,运用稀疏矩阵的存储和处理方法,可以高效地挖掘数据之间的潜在关系,发现有价值的信息模式,如在社交网络分析中处理用户之间的关联矩阵,挖掘用户群体的特征和行为模式。


http://www.ppmy.cn/ops/136925.html

相关文章

【高阶数据结构】图论

> 作者&#xff1a;დ旧言~ > 座右铭&#xff1a;松树千年终是朽&#xff0c;槿花一日自为荣。 > 目标&#xff1a;了解什么是图&#xff0c;并能掌握深度优先遍历和广度优先遍历。 > 毒鸡汤&#xff1a;有些事情&#xff0c;总是不明白&#xff0c;所以我不会坚持…

【论文解析】HAQ: Hardware-Aware Automated Quantization With Mixed Precision

作者及发刊详情 inproceedings{haq, author {Wang, Kuan and Liu, Zhijian and Lin, Yujun and Lin, Ji and Han, Song}, title {HAQ: Hardware-Aware Automated Quantization With Mixed Precision}, booktitle {IEEE Conference on Computer Vision and Pattern Recognit…

丹摩征文活动|实现Llama3.1大模型的本地部署

文章目录 1.前言2.丹摩的配置3.Llama3.1的本地配置4. 最终界面 丹摩 1.前言 Llama3.1是Meta 公司发布的最新开源大型语言模型&#xff0c;相较于之前的版本&#xff0c;它在规模和功能上实现了显著提升&#xff0c;尤其是最大的 4050亿参数版本&#xff0c;成为开源社区中非常…

CSS 样式入门:属性全知晓

CSS&#xff08;层叠样式表&#xff09;是一种用于控制网页样式和布局的语言。它包含了一系列属性&#xff0c;用于定义元素的外观和行为。下面将详细介绍一些常见的 CSS 属性&#xff0c;以及通过实例展示它们的使用方法和效果。 字体样式属性&#xff1a; font-family&…

【C++篇】深度解析 C++ List 容器:底层设计与实现揭秘

文章目录 须知 &#x1f4ac; 欢迎讨论&#xff1a;如果你在学习过程中有任何问题或想法&#xff0c;欢迎在评论区留言&#xff0c;我们一起交流学习。你的支持是我继续创作的动力&#xff01; &#x1f44d; 点赞、收藏与分享&#xff1a;觉得这篇文章对你有帮助吗&#xff1…

可视化建模与UML《活动图实验报告》

你当像鸟飞往你的山。 一、实验目的&#xff1a; 1、熟悉活动图的基本功能和使用方法。 2、掌握使用建模工具软件绘制协作图的方法 二、实验环境&#xff1a; window7 | 10 | 11 EA15 三、实验内容&#xff1a; <1>绘制学生选课系统中添加课程(Add Course)用例的活动图…

es写入磁盘的过程以及相关优化

数据写入到内存buffer同时写入到数据到translog buffer,这是为了防止数据不会丢失每隔1s数据从buffer中refresh到FileSystemCache中,生成segment文件,这是因为写入磁盘的过程相对耗时,借助FileSystemCache,一旦生成segment文件,就能通过索引查询到了refresh完,memory bu…

STM32端口模拟编码器输入

文章目录 前言一、正交编码器是什么&#xff1f;二、使用步骤2.1开启时钟2.2配置编码器引脚 TIM3 CH1(PA6) CH2 (PA7)上拉输入2.3.初始化编码器时基2.4 初始化编码器输入2.5 配置编码器接口2.6 开启定时器2.7获取编码器数据 三、参考程序四、测试结果4.1测试方法4.2串口输出结果…