C语言数组中如何压缩存储特殊矩阵

# C语言数组中如何压缩存储特殊矩阵

## 引言

在计算机科学和数值计算中，特殊矩阵（如对称矩阵、三角矩阵、稀疏矩阵等）因其独特的数学性质常常出现。传统二维数组存储方式会浪费大量空间存储重复元素或零值。本文详细介绍如何使用C语言的一维数组实现特殊矩阵的压缩存储，包括5种典型场景的实现方法和代码示例。

## 一、对称矩阵的压缩存储

### 1. 数学特性
n阶对称矩阵满足a~ij~=a~ji~，只需存储主对角线及以下/以上元素。

### 2. 压缩方法
将n×n矩阵压缩为长度n(n+1)/2的一维数组：
- **行优先存储**：按行顺序存储下三角元素
- **列优先存储**：按列顺序存储上三角元素

```c
// 下三角存储示例
void storeSymmetric(int mat[][N], int arr[]) {
    int k = 0;
    for(int i=0; i<N; i++)
        for(int j=0; j<=i; j++)
            arr[k++] = mat[i][j];
}

// 元素访问公式
// a[i][j] = (i >= j) ? arr[i*(i+1)/2 + j] : arr[j*(j+1)/2 + i]

二、三角矩阵的压缩

1. 上三角矩阵

仅存储主对角线及以上元素，其余视为0。

// 上三角压缩存储
void storeUpperTri(int mat[][N], int arr[]) {
    int k = 0;
    for(int i=0; i<N; i++)
        for(int j=i; j<N; j++)
            arr[k++] = mat[i][j];
}

2. 下三角矩阵

存储主对角线及以下元素，附加常量存储区（当矩阵包含非零常量时）。

// 下三角+常量存储
void storeLowerTri(int mat[][N], int arr[], int c) {
    int k = 0;
    for(int i=0; i<N; i++) {
        for(int j=0; j<=i; j++)
            arr[k++] = mat[i][j];
    }
    arr[k] = c; // 存储常量
}

三、三对角矩阵的压缩

1. 矩阵特性

非零元素仅出现在主对角线及其相邻对角线。

2. 存储方案

使用长度为3n-2的一维数组，按对角线顺序存储：

void storeTridiagonal(int mat[][N], int arr[]) {
    int k = 0;
    for(int i=0; i<N; i++) {
        for(int j=max(0,i-1); j<=min(N-1,i+1); j++) {
            arr[k++] = mat[i][j];
        }
    }
}

// 访问公式
// a[i][j] = (|i-j| <= 1) ? arr[2i+j] : 0

四、稀疏矩阵的压缩

1. 三元组表示法

存储非零元素的行、列和值：

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

void compressSparse(int mat[][M], Triple arr[], int *count) {
    *count = 0;
    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) {
            if(mat[i][j] != 0) {
                arr[*count].row = i;
                arr[*count].col = j;
                arr[*count].value = mat[i][j];
                (*count)++;
            }
        }
    }
}

2. CSR格式（压缩稀疏行）

更高效的存储格式：

typedef struct {
    double *values;   // 非零值
    int *col_ind;     // 列索引
    int *row_ptr;     // 行指针
} CSRMatrix;

五、应用实例对比

存储效率比较

代码示例：对称矩阵乘法

void symMatrixMultiply(int a[], int b[], int result[], int n) {
    for(int i=0; i<n; i++) {
        for(int j=0; j<n; j++) {
            int sum = 0;
            for(int k=0; k<n; k++) {
                int a_val = (i>=k) ? a[i*(i+1)/2+k] : a[k*(k+1)/2+i];
                int b_val = (k>=j) ? b[k*(k+1)/2+j] : b[j*(j+1)/2+k];
                sum += a_val * b_val;
            }
            result[i*n+j] = sum;
        }
    }
}

结语

通过选择合适的压缩存储方案，可以显著降低特殊矩阵的存储开销。实际应用中需权衡： 1. 访问时间复杂度（压缩后可能增加计算量） 2. 实现的复杂性 3. 特定场景的存储需求

掌握这些压缩技术对处理大规模数值计算、图形学等领域的矩阵运算至关重要。 “`

注：实际使用时请根据具体需求调整代码中的N/M等常量，并添加必要的边界检查。文章包含的数学公式和代码示例可根据读者水平适当增减细节。