数组与特殊压缩矩阵

一、数组的基本特性

• 定义：

  int arr[3][3]; // 3x3二维数组

• 存储方式：

  • 行优先存储（C语言默认）：元素按行连续存储。

  • 列优先存储：需手动实现（如科学计算中的Fortran风格）。

• 访问元素：

arr[i][j] = value; // 直接访问

二、 特殊矩阵的压缩存储

针对特定规律的矩阵（如对称、稀疏），可通过压缩存储减少空间占用。

(1) 对称矩阵

• 特点：a[i][j] = a[j][i]，只需存储上三角或下三角。

• 压缩存储：

  • 将下三角元素存入一维数组，元素总数：n(n+1)/2。

  • 下标转换公式（行优先）：

    • 当 i ≥ j 时，一维数组索引 k = i*(i+1)/2 + j。

    • 当 i < j 时，交换 i 和 j。

示例代码：

// 压缩对称矩阵
int compressSymmetric(int matrix[][N], int n, int compressed[]) {
    int k = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) { // 存储下三角
            compressed[k++] = matrix[i][j];
        }
    }
    return k; // 返回压缩后长度
}

// 访问压缩后的元素
int getElement(int compressed[], int i, int j) {
    if (i < j) { // 上三角转下三角
        int temp = i;
        i = j;
        j = temp;
    }
    return compressed[i*(i+1)/2 + j];
}

(2) 三角矩阵

• 上三角矩阵：只存储主对角线及以上元素。

• 下三角矩阵：只存储主对角线及以下元素。

• 压缩存储：类似对称矩阵，但需额外存储剩余部分的常量（如0）。

示例代码（下三角矩阵）：

// 压缩下三角矩阵（包含对角线）
void compressLowerTriangular(int matrix[][N], int n, int compressed[]) {
    int k = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= i; j++) {
            compressed[k++] = matrix[i][j];
        }
    }
}

(3) 稀疏矩阵

• 特点：绝大多数元素为0，通过压缩存储非零元素。

• 存储方式：

  1. 三元组表示法：存储非零元素的行、列、值。

  2. 十字链表：适合频繁插入/删除操作（如图像处理）。

三元组表示法示例：

typedef struct {
    int row, col, value;
} Triple;

// 压缩稀疏矩阵
void compressSparse(int matrix[][M], int rows, int cols, Triple compressed[]) {
    int k = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (matrix[i][j] != 0) {
                compressed[k].row = i;
                compressed[k].col = j;
                compressed[k].value = matrix[i][j];
                k++;
            }
        }
    }
}

// 访问稀疏矩阵元素
int getSparseElement(Triple compressed[], int size, int i, int j) {
    for (int k = 0; k < size; k++) {
        if (compressed[k].row == i && compressed[k].col == j) {
            return compressed[k].value;
        }
    }
    return 0; // 未找到则返回0
}

三、对比与选择

四、操作复杂度

• 普通数组：

  • 访问：O(1)

  • 插入/删除：不适用（需重构数组）

• 压缩存储矩阵：

  • 访问：O(1)（对称/三角）或 O(non_zero)（稀疏矩阵遍历）

  • 插入/删除：仅稀疏矩阵支持高效操作（如十字链表）

五、实际应用

• 图像处理：稀疏矩阵存储图像的非零像素。

• 科学计算：对称矩阵用于物理模拟中的刚度矩阵。

• 机器学习：三角矩阵用于LU分解加速计算。

六、总结

在C语言中，数组是基础数据结构，而特殊矩阵通过压缩存储可显著优化空间和操作效率。根据矩阵特性和应用场景选择合适的存储方式：

• 对称/三角矩阵：用一维数组压缩存储。

• 稀疏矩阵：用三元组或十字链表实现动态操作。