【数据结构】数组和字符串（二）：特殊矩阵的压缩存储：对角矩阵——一维数组

2024-07-30 09:32:47 浏览数 (1)

4.2.1 矩阵的数组表示

【数据结构】数组和字符串（一）：矩阵的数组表示

4.2.2 特殊矩阵的压缩存储

  矩阵是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵，如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等, 如果用这种方式存储，会出现大量存储空间存放重复信息或零元素的情况，这样会造成很大的空间浪费。为节约存储空间和算法（程序）运行时间，通常会采用压缩存储的方法。

  • 对角矩阵：指除了主对角线以外的元素都为零的矩阵，即对 任意 i ≠ j (1≤ i , j ≤n)，都有M(i, j)=0。由于只有主对角线上有非零元素，只需存储主对角线上的元素即可。
  • 三角矩阵：指上三角或下三角的元素都为零的矩阵。同样地，只需存储其中一部分非零元素，可以节省存储空间。
  • 对称矩阵：指矩阵中的元素关于主对角线对称的矩阵。由于对称矩阵的非零元素有一定的规律，可以只存储其中一部分元素，从而减少存储空间。
  • 稀疏矩阵：指大部分元素为零的矩阵。传统的按行优先次序存储方法会浪费大量空间来存储零元素，因此采用压缩存储的方法更为合适。常见的压缩存储方法有：压缩稠密行（CSR）、压缩稠密列（CSC）、坐标列表（COO）等。

a. 对角矩阵的压缩存储

  对于一个n×n维的对角矩阵M，由于非主对角线上的元素都为零，只需存储其n个对角元素的值即可。可以使用一维数组d[n]来压缩存储对角矩阵，其中d[i-1] (1≤ i ≤ n)存储M(i, i)的值。这种压缩存储方式可以显著减少存储空间的使用量，尤其在矩阵规模较大时效果更为明显。同时，在对角矩阵的运算中，由于非主对角线上的元素都为零，可以通过直接访问压缩后的数据来提高算法的效率。

结构体
代码语言：javascript复制
typedef struct {
    int size;       // 矩阵的维度
    int diagonal[MAX_SIZE];  // 存储对角元素的数组
} DiagonalMatrix;

DiagonalMatrix 结构体定义了对角矩阵的结构，包括矩阵的维度 size 和存储对角元素的数组 diagonal。

初始化
代码语言：javascript复制
void initialize(DiagonalMatrix *matrix, int size) {
    matrix->size = size;

    // 初始化对角元素数组
    for (int i = 0; i < size; i  ) {
        matrix->diagonal[i] = 0;
    }
}

initialize 函数用于初始化对角矩阵，接受一个指向 DiagonalMatrix 结构体的指针和矩阵的维度作为参数，在函数内部将矩阵的维度存储到 size 成员变量中，并将对角元素数组的所有元素初始化为0。

元素设置
代码语言：javascript复制
void setElement(DiagonalMatrix *matrix, int row, int col, int value) {
    if (row != col) {
        printf("Error: Only diagonal elements can be set.n");
    } else if (row < 0 || row >= matrix->size || col < 0 || col >= matrix->size) {
        printf("Error: Invalid row or column index.n");
    } else {
        matrix->diagonal[row] = value;
    }
}

setElement 函数用于设置对角矩阵中指定位置的元素值，接受一个指向 DiagonalMatrix 结构体的指针、行索引、列索引和要设置的值作为参数。

  • 函数首先检查行索引和列索引是否相等，因为只有对角线上的元素可以被设置。
  • 检查行索引和列索引是否有效，即在矩阵范围内。
  • 如果通过了检查，将指定位置的对角元素设置为给定的值。
元素获取
代码语言：javascript复制
int getElement(DiagonalMatrix *matrix, int row, int col) {
    if (row < 0 || row >= matrix->size || col < 0 || col >= matrix->size) {
        printf("Error: Invalid row or column index.n");
        return 0;
    } else if (row != col) {
        return 0;
    } else {
        return matrix->diagonal[row];
    }
}

getElement 函数用于获取对角矩阵中指定位置的元素值，接受一个指向 DiagonalMatrix 结构体的指针、行索引和列索引作为参数。

  • 函数首先检查行索引和列索引是否有效，如果无效则打印错误信息并返回0。、
  • 然后再次检查行索引和列索引是否相等，如果不相等则表示该位置不是对角元素，返回0。
  • 如果通过了检查，返回指定位置的对角元素的值。
打印矩阵
代码语言：javascript复制
void printMatrix(DiagonalMatrix *matrix) {
    for (int i = 0; i < matrix->size; i  ) {
        for (int j = 0; j < matrix->size; j  ) {
            printf("%d ", getElement(matrix,i,j));
        }
        printf("n");
    }
}

printMatrix 函数用于打印对角矩阵，接受一个指向 DiagonalMatrix 结构体的指针作为参数。函数通过两层循环遍历矩阵的每个位置，调用getElement 函数获取并打印元素的值。

主函数
代码语言：javascript复制
int main() {
    DiagonalMatrix matrix;
    int size = 6;

    initialize(&matrix, size);
    // 读入数据并设置对角矩阵的元素
    for (int i = 0; i < size; i  ) {
        int value;
        printf("nEnter the value for element [%d][%d]: ", i, i);
        scanf("%d", &value);
        setElement(&matrix, i, i, value);
    }

    printf("Diagonal Matrix:n");
    printMatrix(&matrix);
    return 0;
}

  在 main 函数中，首先定义了一个 DiagonalMatrix 类型的变量 matrix 和一个整数变量 size。然后调用 initialize 函数初始化矩阵，将矩阵的维度设置为4，并将对角元素分别设置为1、2、3和4。最后使用 printMatrix 函数打印矩阵。

输出结果
代码整合
代码语言：javascript复制
#include <stdio.h>

#define MAX_SIZE 100

// 定义对角矩阵结构体
typedef struct {
    int size;       // 矩阵的维度
    int diagonal[MAX_SIZE];  // 存储对角元素的数组
} DiagonalMatrix;

// 初始化对角矩阵
void initialize(DiagonalMatrix *matrix, int size) {
    matrix->size = size;

    // 初始化对角元素数组
    for (int i = 0; i < size; i  ) {
        matrix->diagonal[i] = 0;
    }
}

// 设置对角矩阵中指定位置的元素值
void setElement(DiagonalMatrix *matrix, int row, int col, int value) {
    if (row != col) {
        printf("Error: Only diagonal elements can be set.n");
    } else if (row < 0 || row >= matrix->size || col < 0 || col >= matrix->size) {
        printf("Error: Invalid row or column index.n");
    } else {
        matrix->diagonal[row] = value;
    }
}

// 获取对角矩阵中指定位置的元素值
int getElement(DiagonalMatrix *matrix, int row, int col) {
    if (row < 0 || row >= matrix->size || col < 0 || col >= matrix->size) {
        printf("Error: Invalid row or column index.n");
        return 0;
    } else if (row != col) {
        return 0;
    } else {
        return matrix->diagonal[row];
    }
}

// 打印对角矩阵
void printMatrix(DiagonalMatrix *matrix) {
    for (int i = 0; i < matrix->size; i  ) {
        for (int j = 0; j < matrix->size; j  ) {
            printf("%d ", getElement(matrix,i,j));
        }
        printf("n");
    }
}

int main() {
    DiagonalMatrix matrix;
    int size = 6;

    initialize(&matrix, size);
    // 读入数据并设置对角矩阵的元素
    for (int i = 0; i < size; i  ) {
        int value;
        printf("nEnter the value for element [%d][%d]: ", i, i);
        scanf("%d", &value);
        setElement(&matrix, i, i, value);
    }

    printf("Diagonal Matrix:n");
    printMatrix(&matrix);
    return 0;
}
存储 数据结构 数组 压缩 字符串

0 人点赞