昆山网站建设哪家便宜,网站建设盒子模型浮动,展示型网站设计案例,宿迁北京网站建设文章目录 4.2.1 矩阵的数组表示4.2.2 特殊矩阵的压缩存储a. 对角矩阵的压缩存储b~c. 三角、对称矩阵的压缩存储d. 稀疏矩阵的压缩存储——三元组表结构体初始化元素设置打印矩阵主函数输出结果代码整合 4.2.1 矩阵的数组表示
【数据结构】数组和字符串#xff08;一#xff… 文章目录 4.2.1 矩阵的数组表示4.2.2 特殊矩阵的压缩存储a. 对角矩阵的压缩存储b~c. 三角、对称矩阵的压缩存储d. 稀疏矩阵的压缩存储——三元组表结构体初始化元素设置打印矩阵主函数输出结果代码整合 4.2.1 矩阵的数组表示
【数据结构】数组和字符串一矩阵的数组表示
4.2.2 特殊矩阵的压缩存储 矩阵是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等, 如果用这种方式存储会出现大量存储空间存放重复信息或零元素的情况这样会造成很大的空间浪费。为节约存储空间和算法程序运行时间通常会采用压缩存储的方法。
对角矩阵指除了主对角线以外的元素都为零的矩阵即对 任意 i ≠ j (1≤ i , j ≤n)都有M(i, j)0。由于只有主对角线上有非零元素只需存储主对角线上的元素即可。三角矩阵指上三角或下三角的元素都为零的矩阵。同样地只需存储其中一部分非零元素可以节省存储空间。对称矩阵指矩阵中的元素关于主对角线对称的矩阵。由于对称矩阵的非零元素有一定的规律可以只存储其中一部分元素从而减少存储空间。稀疏矩阵指大部分元素为零的矩阵。传统的按行优先次序存储方法会浪费大量空间来存储零元素因此采用压缩存储的方法更为合适。常见的压缩存储方法有压缩稠密行CSR、压缩稠密列CSC、坐标列表COO等。
a. 对角矩阵的压缩存储
【数据结构】数组和字符串二特殊矩阵的压缩存储对角矩阵——一维数组
b~c. 三角、对称矩阵的压缩存储
【数据结构】数组和字符串三特殊矩阵的压缩存储三角矩阵、对称矩阵——一维数组
d. 稀疏矩阵的压缩存储——三元组表 对于稀疏矩阵的压缩存储由于非零元素的个数远小于零元素的个数并且非零元素的分布没有规律无法简单地利用一维数组和映射公式来实现压缩存储。针对稀疏矩阵通常采用特定的数据结构来进行压缩存储以减少存储空间的占用。 一种常见的稀疏矩阵压缩存储方法是使用三元组表示法也称为COOCoordinate格式只存储非零元素的值以及它们的行列坐标。通过使用三元组Triplet来表示非零元素的位置和值每个三元组包含三个信息非零元素的行索引、非零元素的列索引以及非零元素的值。
结构体
typedef struct {int row;int col;int value;
} Triple;typedef struct {Triple data[MAX_SIZE];int rows;int cols;int length;
} TripletTable;定义了两个结构体Triple 和 TripletTable。
Triple 结构体表示稀疏矩阵的非零元素包含三个字段row 表示行号col 表示列号value 表示元素的值。TripletTable 结构体用于存储稀疏矩阵的数据包含一个 data 数组用于存储非零元素的 Triple 结构体以及 rows、cols 和 length 字段分别表示矩阵的行数、列数和非零元素的数量。
初始化
void initTable(TripletTable* table, int rows, int cols) {table-rows rows;table-cols cols;table-length 0;
}initTable 函数用于初始化 TripletTable 结构体指定矩阵的行数和列数并将 length 字段置为 0。
元素设置
void insertElement(TripletTable* table, int row, int col, int value) {if (table-length MAX_SIZE) {printf(Table is full. Cannot insert more elements.\n);return;}Triple* element (table-data[table-length]);element-row row;element-col col;element-value value;table-length;
}insertElement 函数用于向稀疏矩阵中插入一个元素传入参数为行号、列号和元素的值。
函数首先检查当前非零元素的数量是否已达到上限 MAX_SIZE 如果达到上限则输出错误信息并返回。否则将新元素插入到 data 数组的末尾并更新 length 字段。
打印矩阵
void displayTable(TripletTable* table) {int matrix[table-rows][table-cols];for (int i 0; i table-rows; i) {for (int j 0; j table-cols; j) {matrix[i][j] 0;}}printf(Row\tColumn\tValue\n);for (int i 0; i table-length; i) {Triple* element (table-data[i]);printf(%d\t%d\t%d\n, element-row, element-col, element-value);matrix[element-row][element-col] element-value;}printf(Matrix:\n);for (int i 0; i table-rows; i) {for (int j 0; j table-cols; j) {printf(%d\t, matrix[i][j]);}printf(\n);}
}displayTable 函数用于显示稀疏矩阵的内容
创建一个与稀疏矩阵相同大小的二维数组 matrix并将其所有元素初始化为 0遍历 data 数组中的非零元素输出每个元素的行号、列号和值并将相应位置的 matrix 数组元素更新为对应的值输出整个矩阵的内容。
主函数
int main() {TripletTable table;initTable(table, 3, 3);insertElement(table, 0, 0, 1);insertElement(table, 0, 1, 2);insertElement(table, 1, 1, 3);insertElement(table, 2, 2, 4);displayTable(table);return 0;
}创建一个 TripletTable 结构体 table并使用 initTable 函数初始化它指定矩阵的行数和列数为3。调用 insertElement 函数向 table 中插入四个非零元素分别位于 (0, 0)、(0, 1)、(1, 1) 和 (2, 2) 位置。通过调用 displayTable 函数打印出稀疏矩阵的内容和对应的完整矩阵表示。
输出结果 代码整合
#include stdio stdio.h
#include stdlib#include stdlib.htypedef struct {int row;int col;int value;
} Element;typedef struct {int rows;int cols;int numElements;Element* elements;
} SparseMatrix;SparseMatrix* createSparseMatrix(int rows, int cols, int numElements) {SparseMatrix* matrix (SparseMatrix*)malloc(sizeof(SparseMatrix));matrix-rows rows;matrix-cols cols;matrix-numElements numElements;matrix-elements (Element*)malloc(numElements * sizeof(Element));return matrix;
}void destroySparseMatrix(SparseMatrix* matrix) {free(matrix-elements);free(matrix);
}void setElement(SparseMatrix* matrix, int row, int col, int value) {if (row matrix-rows || col matrix-cols) {printf(Error: Invalid row or column index.\n);return;}int index row * matrix-cols col;matrix-elements[index].row row;matrix-elements[index].col col;matrix-elements[index].value value;
}int getElement(SparseMatrix* matrix, int row, int col) {if (row matrix-rows || col matrix-cols) {printf(Error: Invalid row or column index.\n);return 0;}int index row * matrix-cols col;return matrix-elements[index].value;
}int main() {int rows 3;int cols 3;int numElements 4;SparseMatrix* matrix createSparseMatrix(rows, cols, numElements);setElement(matrix, 0, 0, 1);setElement(matrix, 0, 2, 2);setElement(matrix, 1, 1, 3);setElement(matrix, 2, 2, 4);printf(Matrix:\n);for (int i 0; i rows; i) {for (int j 0; j cols; j) {int value getElement(matrix, i, j);printf(%d , value);}printf(\n);}destroySparseMatrix(matrix);return 0;
}
