c++对称矩阵压缩存储

在C++中，对称矩阵是一种特殊的矩阵，它的元素满足上三角（或下三角）的所有元素与其对角线上的元素相等。由于对称矩阵有这个特性，我们可以只存储下三角或者上三角的部分，再加上对角线上的元素，这样就能实现空间的高效压缩存储。

具体实现方法通常有以下两种：

1. **压缩行存储（Compressed Row Storage, CRS）**:
- 只存储下三角部分的非零元素，每个行从左到右存储，对角线上的元素单独记录。
- 用一个一维数组表示所有行的元素，另一个一维数组指示每个元素在原矩阵中的列位置（即列索引减去当前行号）。

2. **压缩列存储（Compressed Column Storage, CCS）**:
- 只存储下三角部分的非零元素，但按照列进行压缩，每个列从上到下存储。
- 类似于CRS，一个一维数组存放元素值，另一个一维数组标识元素所在的行索引。

这两种方法都能节省存储空间，特别是当矩阵很稀疏时，效果显著。在C++中，使用标准库如`std::vector`和自定义数据结构可以方便地实现这些存储策略。

相关问题

设计算法将对称矩阵、三角矩阵、对角矩阵压缩存储到一维数组中（c++语言）

为了高效地压缩存储对称矩阵、三角矩阵和对角矩阵，我们可以利用它们特殊的结构。这里以C++为例，给出一种可能的方法：

1. 对称矩阵（Symmetric Matrix）[^4]:
对称矩阵的上半部分（包括对角线）已经包含了所有非对角元素，所以可以只保存其中的一半。例如，对于一个N×N的对称矩阵，可以存储从下标0到(N-1)/2的行和列。

   std::vector<int> compressSymmetricMatrix(int N, const std::vector<std::vector<int>>& matrix) {
       std::vector<int> compressed(N * (N + 1) / 2);
       int index = 0;
       for (int i = 0; i < N; ++i) {
           for (int j = i; j < N; ++j) {
               compressed[index++] = matrix[i][j];
           }
       }
       return compressed;
   }   

2. 上三角矩阵（Upper Triangular Matrix）[^5]:
只需存储主对角线上的元素和上三角区域的元素。同样，可以通过迭代来填充压缩后的向量。

   std::vector<int> compressUpperTriangularMatrix(const std::vector<std::vector<int>>& matrix) {
       std::vector<int> compressed(matrix.size());
       int index = 0;
       for (int i = 0; i < matrix.size(); ++i) {
           for (int j = i; j < matrix[i].size(); ++j) {
               compressed[index++] = matrix[i][j];
           }
       }
       return compressed;
   } 

3. 对角矩阵（Diagonal Matrix）[^6]:
对角矩阵的非对角元素全为0，所以只需要存储对角线上的元素。

   std::vector<int> compressDiagonalMatrix(const std::vector<std::vector<int>>& matrix) {
       std::vector<int> compressed(matrix.size());
       for (int i = 0; i < matrix.size(); ++i) {
           compressed[i] = matrix[i][i];
       }
       return compressed;
   } 

用C++创建一个压缩存储的对称矩阵，以二维方式显示所创建的对称矩阵。

以下是一个示例代码：

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n, i, j;
    printf("请输入对称矩阵的阶数：");
    scanf("%d", &n);

    // 创建动态数组存储对称矩阵
    int **matrix = (int **)malloc(n * sizeof(int *));
    for (i = 0; i < n; i++) {
        matrix[i] = (int *)malloc(n * sizeof(int));
    }

    // 随机生成对称矩阵的上三角元素
    for (i = 0; i < n; i++) {
        for (j = i; j < n; j++) {
            matrix[i][j] = rand() % 100;
        }
    }

    // 将上三角元素赋值给下三角元素
    for (i = 0; i < n; i++) {
        for (j = i+1; j < n; j++) {
            matrix[j][i] = matrix[i][j];
        }
    }

    // 以二维方式显示对称矩阵
    printf("生成的对称矩阵为：\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            printf("%d ", matrix[i][j]);
        }
        printf("\n");
    }

    // 释放动态数组
    for (i = 0; i < n; i++) {
        free(matrix[i]);
    }
    free(matrix);

    return 0;
}

这段代码中，我们首先从用户输入中获取对称矩阵的阶数，然后动态创建一个二维数组来存储对称矩阵。接下来，我们随机生成对称矩阵的上三角元素，并将其赋值给下三角元素。最后，我们以二维方式显示对称矩阵，并释放动态数组的内存。