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

🕗 发布于 2024-11-26 09:18 矩阵算法

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

一、多维数组的存储

（一）基本概念

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

（二）行优先存储

以二维数组为例，行优先存储是先存储第一行的元素，然后再存储第二行的元素，依此类推。对于一个 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 语言示例

// 存储上三角矩阵到一维数组
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;
}

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

原文地址：https://blog.csdn.net/weixin_69477306/article/details/144019824

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：实战项目 Boost 搜索引擎
下一篇：矩阵重构——reshape函数

【CSP CCF记录】201903-2第16次认证二十四点
字符转数字；字符转运算符；erase的用法。
阅读更多2024-11-27
Web 表单开发全解析：从基础到高级掌握 HTML 表单设计
在现代 Web 开发中，表单是用户与后端服务交互的重要桥梁。无论是用户登录、注册、搜索，还是提交反馈，表单都无处不在。在本文中，我们将从基础入手，全面解析表单的核心知识点，并通过示例带你轻松掌握表单
阅读更多2024-11-27
【简单好抄保姆级教学】javascript调用本地exe程序（谷歌，edge，百度，主流浏览器都可以使用....）
在本地创建一个txt文件依次输入，指明了所使用的注册表编辑器版本。这是必需的，以确保脚本能够被正确解析和执行。，用于处理文件关联、协议和其他类型的信息。这里的@符号表示command子项的默认（未命名
阅读更多2024-11-27
Spring Boot 与 Spring Cloud Alibaba 版本兼容对照
版本选择要点Spring Boot 3.x 与 Spring Cloud Alibaba 2022.0.xSpring Boot 3.x 基于 Jakarta EE，javax.* 更换为 jakar
阅读更多2024-11-27
分类算法——基于heart数据集实现
【代码】分类算法——基于heart数据集实现。
阅读更多2024-11-27
【Linux】vim的使用
进入vimvim是一款编辑器。自带，使用成本较高。我们创建一个普通文件，然后vim code.c，进入vim。想要退出vim，怎么做？（因为当前我们不知道在什么模式下），我们先按下键盘最左上角的Esc
阅读更多2024-11-27
计算机网络的类型
个人区域网是一种短距离无线通信网络，用于连接个人设备，如智能手机、智能手表、无线耳机等。
阅读更多2024-11-27
40分钟学 Go 语言高并发：Pipeline模式（一）
让我们继续完成高级Pipeline的实现。
阅读更多2024-11-27
Spring Boot教程之十：使用 Spring Boot 实现从数据库动态下拉列表
使用 Spring Boot 实现从数据库动态下拉列表动态下拉列表（或依赖下拉列表）的概念令人兴奋，但编写起来却颇具挑战性。动态下拉列表意味着一个下拉列表中的值依赖于前一个下拉列表中选择的值。一个简单
阅读更多2024-11-27
「实战应用」如何用图表控件LightningChart .NET实现散点图？（一）
本文将为大家介绍如何用图表控件LightningChart .NET实现散点图，欢迎联系我们获取新产品试用！
阅读更多2024-11-27

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