特殊矩阵压缩存储时的下标变换公式,对角矩阵压缩到一维数组中
墨初 知识笔记 96阅读
文章目录 4.2.1 矩阵的数组表示4.2.2 特殊矩阵的压缩存储a. 对角矩阵的压缩存储结构体初始化元素设置元素获取打印矩阵主函数输出结果代码整合
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)的值。这种压缩存储方式可以显著减少存储空间的使用量尤其在矩阵规模较大时效果更为明显。同时在对角矩阵的运算中由于非主对角线上的元素都为零可以通过直接访问压缩后的数据来提高算法的效率。
结构体typedef struct { int size; // 矩阵的维度 int diagonal[MAX_SIZE]; // 存储对角元素的数组} DiagonalMatrix; DiagonalMatrix 结构体定义了对角矩阵的结构包括矩阵的维度 size 和存储对角元素的数组 diagonal。
void initialize(DiagonalMatrix *matrix, int size) { matrix->size size; // 初始化对角元素数组 for (int i 0; i < size; i) { matrix->diagonal[i] 0; }} initialize 函数用于初始化对角矩阵接受一个指向 DiagonalMatrix 结构体的指针和矩阵的维度作为参数在函数内部将矩阵的维度存储到 size 成员变量中并将对角元素数组的所有元素初始化为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; }} setElement 函数用于设置对角矩阵中指定位置的元素值接受一个指向 DiagonalMatrix 结构体的指针、行索引、列索引和要设置的值作为参数。
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 结构体的指针、行索引和列索引作为参数。
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 函数获取并打印元素的值。
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 函数打印矩阵。
#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;}