多维数组与特殊矩阵：存储与压缩
一、多维数组的存储
（一）基本概念
多维数组是线性表的推广，例如二维数组可以看作是元素为一维数组的线性表，三维数组可以看作是元素为二维数组的线性表，以此类推。在内存中，多维数组需要按照一定的顺序进行存储，常见的存储方式有行优先存储和列优先存储。
（二）行优先存储
以二维数组为例，行优先存储是先存储第一行的元素，然后再存储第二行的元素，依此类推。对于一个 m 行 n 列的二维数组 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;
}
二、特殊矩阵的存储与压缩
（一）对称矩阵
- 存储特点
- 对称矩阵是指
a[i][j] = a[j][i]的矩阵。对于一个n阶对称矩阵，我们只需要存储其下三角（或上三角）部分的元素即可，因为根据对称性可以得到另一半元素的值。
- 对称矩阵是指
- 存储方式
- 可以将下三角部分按行优先存储到一个一维数组
sa中。对于下三角元素a[i][j]（i >= j），其在一维数组中的下标k计算如下：
[k=\frac{i(i + 1)}{2}+j]
- 可以将下三角部分按行优先存储到一个一维数组
- 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;
}
（二）三角矩阵
- 上三角矩阵
- 存储特点：上三角矩阵是主对角线以下元素全为 0 的矩阵。对于
n阶上三角矩阵，我们可以只存储其主对角线及以上的元素。 - 存储方式：按行优先存储主对角线及以上元素到一维数组
ua中。对于上三角元素a[i][j]（i <= j），其在一维数组中的下标k计算如下：
[k=\frac{(2n - i - 1)i}{2}+j - i] - C 语言示例
- 存储特点：上三角矩阵是主对角线以下元素全为 0 的矩阵。对于
// 存储上三角矩阵到一维数组
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;
}
- 下三角矩阵
- 存储特点：下三角矩阵是主对角线以上元素全为 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;
}
（三）对角矩阵
- 存储特点
- 对角矩阵是指除主对角线及其相邻若干条对角线上的元素外，其余元素均为 0 的矩阵。以三对角矩阵为例，其主对角线以及主对角线上下各一条对角线上有非零元素。
- 存储方式
- 可以将三对角矩阵的非零元素按行优先存储到一维数组
da中。对于三对角矩阵中的元素a[i][j]，当|i - j| <= 1时为非零元素。其在一维数组中的下标k计算如下：
[k = 3i - 1 + j - i = 2i + j - 1]（当 (i = 0) 时，(k = j)）
- 可以将三对角矩阵的非零元素按行优先存储到一维数组
- 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;
}
（四）稀疏矩阵
- 存储特点
- 稀疏矩阵是指非零元素个数远小于矩阵元素总个数的矩阵。
- 存储方式 - 三元组顺序表
- 可以使用三元组顺序表来存储稀疏矩阵。三元组顺序表包含三个一维数组，分别存储非零元素的行下标、列下标和值。
- 首先定义三元组结构体：
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;
}
通过对多维数组和各种特殊矩阵的存储与压缩方式的深入理解和掌握，能够在处理大规模数据矩阵相关的问题时，有效地减少存储空间的占用并提高数据处理的效率。在实际应用中，例如在图像处理、科学计算（如有限元分析中的矩阵运算）、数据挖掘等领域，这些技术都有着广泛的应用前景。
在图像处理中，图像可以看作是一个二维矩阵，当处理一些具有特定对称性或稀疏性的图像数据时，利用相应的矩阵存储和压缩技术，可以减少内存的占用，加快图像的处理速度，如对一些纹理具有对称性的图像进行压缩存储以便后续的传输或分析。
在科学计算里，很多物理问题的数学模型最终会转化为大规模的矩阵运算。例如在结构力学的有限元分析中，得到的刚度矩阵往往是对称矩阵或稀疏矩阵，采用合适的存储方式能够显著降低存储需求，提高计算效率，使得在有限的计算机资源下能够处理更复杂的结构模型。
在数据挖掘领域，一些关联矩阵或相似度矩阵可能具有稀疏性的特点，运用稀疏矩阵的存储和处理方法，可以高效地挖掘数据之间的潜在关系，发现有价值的信息模式，如在社交网络分析中处理用户之间的关联矩阵，挖掘用户群体的特征和行为模式。
