广州建站网络推广公司,滁州网站开发公司电话,百度一下你就知道主页,宁波seo品牌推广排名文章目录 4.2.1 矩阵的数组表示4.2.2 特殊矩阵的压缩存储a. 对角矩阵的压缩存储b~c. 三角、对称矩阵的压缩存储d. 稀疏矩阵的压缩存储——三元组表e. 压缩稀疏行#xff08;Compressed Sparse Row#xff0c;CSR#xff09;矩阵结构体创建CSR矩阵元素设置初始化打印矩阵销毁… 文章目录 4.2.1 矩阵的数组表示4.2.2 特殊矩阵的压缩存储a. 对角矩阵的压缩存储b~c. 三角、对称矩阵的压缩存储d. 稀疏矩阵的压缩存储——三元组表e. 压缩稀疏行Compressed Sparse RowCSR矩阵结构体创建CSR矩阵元素设置初始化打印矩阵销毁CSR矩阵主函数代码整合 4.2.1 矩阵的数组表示
【数据结构】数组和字符串一矩阵的数组表示
4.2.2 特殊矩阵的压缩存储 矩阵是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等, 如果用这种方式存储会出现大量存储空间存放重复信息或零元素的情况这样会造成很大的空间浪费。为节约存储空间和算法程序运行时间通常会采用压缩存储的方法。
对角矩阵指除了主对角线以外的元素都为零的矩阵即对 任意 i ≠ j (1≤ i , j ≤n)都有M(i, j)0。由于只有主对角线上有非零元素只需存储主对角线上的元素即可。三角矩阵指上三角或下三角的元素都为零的矩阵。同样地只需存储其中一部分非零元素可以节省存储空间。对称矩阵指矩阵中的元素关于主对角线对称的矩阵。由于对称矩阵的非零元素有一定的规律可以只存储其中一部分元素从而减少存储空间。稀疏矩阵指大部分元素为零的矩阵。传统的按行优先次序存储方法会浪费大量空间来存储零元素因此采用压缩存储的方法更为合适。常见的压缩存储方法有压缩稠密行CSR、压缩稠密列CSC、坐标列表COO等。
a. 对角矩阵的压缩存储
【数据结构】数组和字符串二特殊矩阵的压缩存储对角矩阵——一维数组
b~c. 三角、对称矩阵的压缩存储
【数据结构】数组和字符串三特殊矩阵的压缩存储三角矩阵、对称矩阵——一维数组
d. 稀疏矩阵的压缩存储——三元组表
【数据结构】数组和字符串四特殊矩阵的压缩存储稀疏矩阵——三元组表
e. 压缩稀疏行Compressed Sparse RowCSR矩阵 压缩稀疏行Compressed Sparse RowCSR是一种常用的稀疏矩阵存储格式。CSR存储格式通过压缩非零元素的行指针和列索引以及存储非零元素的值来有效地表示稀疏矩阵。它包含以下几个关键组成部分
row_ptr行指针数组它是一个长度为rows 1的数组用于存储每一行在col_indices和elements数组中的起始索引位置。row_ptr[i]表示第i行的元素在col_indices和elements数组中的起始位置而row_ptr[i1] - row_ptr[i]表示第i行的非零元素个数。col_indices列索引数组它是一个长度为num_elements的数组用于存储每个非零元素对应的列索引。col_indices[i]表示第i个非零元素所在的列索引。elements元素数组它是一个长度为num_elements的数组用于存储每个非零元素的值。elements[i]表示第i个非零元素的值。 CSR存储格式的主要优点是有效地压缩了稀疏矩阵的存储空间只存储非零元素及其对应的行和列信息。此外CSR格式还支持高效的稀疏矩阵向量乘法和稀疏矩阵乘法等操作。
结构体
typedef struct {int row;int col;int value;
} Element;typedef struct {int rows;int cols;int num_elements;Element* elements;int* row_ptr;int* col_indices;
} CSRMatrix;Element 结构体表示矩阵中的一个元素包含三个成员变量row行索引、col列索引和 value元素值。 CSRMatrix 结构体表示一个CSR矩阵包含了矩阵的行数 rows、列数 cols、非零元素的个数 num_elements以及三个指针成员变量 elements、row_ptr 和 col_indices。
创建CSR矩阵
CSRMatrix createCSRMatrix(int rows, int cols, int num_elements) {CSRMatrix matrix;matrix.rows rows;matrix.cols cols;matrix.num_elements num_elements;matrix.elements (Element*)malloc(num_elements * sizeof(Element));matrix.row_ptr (int*)malloc((rows 1) * sizeof(int));matrix.col_indices (int*)malloc(num_elements * sizeof(int));return matrix;
}createCSRMatrix 函数用于创建一个CSR矩阵。接受矩阵的行数、列数和非零元素的个数作为参数并返回创建的CSR矩阵。在函数内部通过动态内存分配分别为 elements、row_ptr 和 col_indices 分配内存空间并将 row_ptr 数组的所有元素初始化为0最后返回创建的矩阵。
元素设置
void setElement(CSRMatrix* matrix, int row, int col, int value) {if (row 0 || row matrix-rows) {printf(Invalid row index.\n);return;}int index matrix-row_ptr[row];matrix-elements[index].row row;matrix-elements[index].col col;matrix-elements[index].value value;matrix-col_indices[index] col;matrix-row_ptr[row]; // 递增索引值
}setElement 函数可用于设置修改CSR矩阵中某个位置的元素值。
接受一个指向CSR矩阵的指针 matrix以及要设置的元素的行索引、列索引和值作为参数。在函数内部首先检查行索引是否有效如果无效则打印错误信息并返回。然后根据行索引找到对应行的起始位置将元素的行索引、列索引和值分别赋给对应的矩阵元素并更新 col_indices 数组和 row_ptr 数组中的值。
初始化
void initializeCSRMatrix(CSRMatrix* matrix, int* values, int* row_indices, int* col_indices, int num_elements) {for (int i 0; i num_elements; i) {matrix-elements[i].value values[i];matrix-elements[i].row row_indices[i];matrix-elements[i].col col_indices[i];matrix-col_indices[i] col_indices[i];matrix-row_ptr[row_indices[i]];}int sum 0;for (int i 0; i matrix-rows; i) {int temp matrix-row_ptr[i];matrix-row_ptr[i] sum;sum temp;}
}initializeCSRMatrix 函数用于初始化CSR矩阵的数据。
接受一个指向CSR矩阵的指针 matrix以及包含非零元素的值、行索引和列索引的数组以及非零元素的个数作为参数。通过遍历非零元素数组将值、行索引和列索引分别赋给对应的矩阵元素并更新 col_indices 数组和 row_ptr 数组中的值。row_ptr 数组的每个元素表示对应行的非零元素在 elements 数组中的起始位置通过累加非零元素的个数来计算每行的结束位置。
打印矩阵
void printCSRMatrix(CSRMatrix matrix) {printf(CSR Matrix:\n);printf(Rows: %d, Cols: %d, Num Elements: %d\n, matrix.rows, matrix.cols, matrix.num_elements);printf(Values: );for (int i 0; i matrix.num_elements; i) {printf(%d , matrix.elements[i].value);}printf(\n);printf(Row Pointer: );for (int i 0; i matrix.rows; i) {printf(%d , matrix.row_ptr[i]);}printf(\n);printf(Column Indices: );for (int i 0; i matrix.num_elements; i) {printf(%d , matrix.col_indices[i]);}printf(\n);
}
void printMatrixForm(CSRMatrix matrix) {printf(Matrix Form:\n);for (int i 0; i matrix.rows; i) {for (int j 0; j matrix.cols; j) {int value 0;for (int k matrix.row_ptr[i]; k matrix.row_ptr[i 1]; k) {if (matrix.elements[k].col j) {value matrix.elements[k].value;break;}}printf(%d , value);}printf(\n);}
}
printCSRMatrix 函数用于打印CSR矩阵的信息它接受一个CSR矩阵作为参数并打印矩阵的行数、列数、非零元素的个数以及 elements、row_ptr 和 col_indices 数组的内容。printMatrixForm 函数用于以矩阵形式打印CSR矩阵。它接受一个CSR矩阵作为参数并按矩阵的行数和列数遍历矩阵元素通过遍历 row_ptr 数组和 col_indices 数组来获取每个位置的元素值并打印出矩阵的形式。
销毁CSR矩阵
void destroyCSRMatrix(CSRMatrix* matrix) {free(matrix-elements);free(matrix-row_ptr);free(matrix-col_indices);matrix-elements NULL;matrix-row_ptr NULL;matrix-col_indices NULL;
}主函数
int main() {int rows 9;int cols 3;int num_elements 5;CSRMatrix matrix createCSRMatrix(rows, cols, num_elements);int col_indices[] {0, 0, 0, 0, 1};int row_indices[] {3, 5, 7, 8, 7};int values[] {2, 1, 3, 1, 4};initializeCSRMatrix(matrix, values, row_indices, col_indices, num_elements);printCSRMatrix(matrix);printMatrixForm(matrix);destroyCSRMatrix(matrix);return 0;
} 代码整合
#include stdio.h
#include stdlib.h
#include string.htypedef struct {int row;int col;int value;
} Element;typedef struct {int rows;int cols;int num_elements;Element* elements;int* row_ptr;int* col_indices;
} CSRMatrix;CSRMatrix createCSRMatrix(int rows, int cols, int num_elements) {CSRMatrix matrix;matrix.rows rows;matrix.cols cols;matrix.num_elements num_elements;matrix.elements (Element*)malloc(num_elements * sizeof(Element));matrix.row_ptr (int*)malloc((rows 1) * sizeof(int));matrix.col_indices (int*)malloc(num_elements * sizeof(int));memset(matrix.row_ptr, 0, (rows 1) * sizeof(int));return matrix;
}
void initializeCSRMatrix(CSRMatrix* matrix, int* values, int* row_indices, int* col_indices, int num_elements) {for (int i 0; i num_elements; i) {matrix-elements[i].value values[i];matrix-elements[i].row row_indices[i];matrix-elements[i].col col_indices[i];matrix-col_indices[i] col_indices[i];matrix-row_ptr[row_indices[i]];}int sum 0;for (int i 0; i matrix-rows; i) {int temp matrix-row_ptr[i];matrix-row_ptr[i] sum;sum temp;}
}void setElement(CSRMatrix* matrix, int row, int col, int value) {if (row 0 || row matrix-rows) {printf(Invalid row index.\n);return;}int index matrix-row_ptr[row];matrix-elements[index].row row;matrix-elements[index].col col;matrix-elements[index].value value;matrix-col_indices[index] col;matrix-row_ptr[row]; // 递增索引值
}void printCSRMatrix(CSRMatrix matrix) {printf(CSR Matrix:\n);printf(Rows: %d, Cols: %d, Num Elements: %d\n, matrix.rows, matrix.cols, matrix.num_elements);printf(Values: );for (int i 0; i matrix.num_elements; i) {printf(%d , matrix.elements[i].value);}printf(\n);printf(Row Pointer: );for (int i 0; i matrix.rows; i) {printf(%d , matrix.row_ptr[i]);}printf(\n);printf(Column Indices: );for (int i 0; i matrix.num_elements; i) {printf(%d , matrix.col_indices[i]);}printf(\n);
}
void printMatrixForm(CSRMatrix matrix) {printf(Matrix Form:\n);for (int i 0; i matrix.rows; i) {for (int j 0; j matrix.cols; j) {int value 0;for (int k matrix.row_ptr[i]; k matrix.row_ptr[i 1]; k) {if (matrix.elements[k].col j) {value matrix.elements[k].value;break;}}printf(%d , value);}printf(\n);}
}void destroyCSRMatrix(CSRMatrix* matrix) {free(matrix-elements);free(matrix-row_ptr);free(matrix-col_indices);matrix-elements NULL;matrix-row_ptr NULL;matrix-col_indices NULL;
}int main() {int rows 9;int cols 3;int num_elements 5;CSRMatrix matrix createCSRMatrix(rows, cols, num_elements);int col_indices[] {0, 0, 0, 0, 1};int row_indices[] {3, 5, 7, 8, 7};int values[] {2, 1, 3, 1, 4};initializeCSRMatrix(matrix, values, row_indices, col_indices, num_elements);printCSRMatrix(matrix);printMatrixForm(matrix);destroyCSRMatrix(matrix);return 0;
}
