【数据结构】数组和字符串（七）：特殊矩阵的压缩存储：三元组表的转置、加法、乘法操作 |
您所在的位置：网站首页 › 稀疏矩阵的三元组存储方法字节计算 › 【数据结构】数组和字符串（七）：特殊矩阵的压缩存储：三元组表的转置、加法、乘法操作 |
【数据结构】数组和字符串（七）：特殊矩阵的压缩存储：三元组表的转置、加法、乘法操作
|
文章目录
4.2.1 矩阵的数组表示4.2.2 特殊矩阵的压缩存储a. 对角矩阵的压缩存储b~c. 三角、对称矩阵的压缩存储d. 稀疏矩阵的压缩存储——三元组表4.2.3三元组表的转置、加法、乘法、操作转置加法乘法算法测试实验结果代码整合
4.2.1 矩阵的数组表示
【数据结构】数组和字符串（一）：矩阵的数组表示 4.2.2 特殊矩阵的压缩存储矩阵是以按行优先次序将所有矩阵元素存放在一个一维数组中。但是对于特殊矩阵，如对称矩阵、三角矩阵、对角矩阵和稀疏矩阵等, 如果用这种方式存储，会出现大量存储空间存放重复信息或零元素的情况，这样会造成很大的空间浪费。为节约存储空间和算法（程序）运行时间，通常会采用压缩存储的方法。 对角矩阵：指除了主对角线以外的元素都为零的矩阵，即对 任意 i ≠ j (1≤ i , j ≤n)，都有M(i, j)=0。由于只有主对角线上有非零元素，只需存储主对角线上的元素即可。三角矩阵：指上三角或下三角的元素都为零的矩阵。同样地，只需存储其中一部分非零元素，可以节省存储空间。对称矩阵：指矩阵中的元素关于主对角线对称的矩阵。由于对称矩阵的非零元素有一定的规律，可以只存储其中一部分元素，从而减少存储空间。稀疏矩阵：指大部分元素为零的矩阵。传统的按行优先次序存储方法会浪费大量空间来存储零元素，因此采用压缩存储的方法更为合适。常见的压缩存储方法有：压缩稠密行（CSR）、压缩稠密列（CSC）、坐标列表（COO）等。 a. 对角矩阵的压缩存储【数据结构】数组和字符串（二）：特殊矩阵的压缩存储：对角矩阵——一维数组 b~c. 三角、对称矩阵的压缩存储【数据结构】数组和字符串（三）：特殊矩阵的压缩存储：三角矩阵、对称矩阵——一维数组 d. 稀疏矩阵的压缩存储——三元组表对于稀疏矩阵的压缩存储，由于非零元素的个数远小于零元素的个数，并且非零元素的分布没有规律，无法简单地利用一维数组和映射公式来实现压缩存储。针对稀疏矩阵，通常采用特定的数据结构来进行压缩存储，以减少存储空间的占用。 一种常见的稀疏矩阵压缩存储方法是使用"三元组"表示法，也称为COO（Coordinate）格式，只存储非零元素的值以及它们的行列坐标。通过使用三元组（Triplet）来表示非零元素的位置和值，每个三元组包含三个信息：非零元素的行索引、非零元素的列索引以及非零元素的值。 【数据结构】数组和字符串（四）：特殊矩阵的压缩存储：稀疏矩阵——三元组表 4.2.3三元组表的转置、加法、乘法、操作 转置假设稀疏矩阵存储在一个三元组表a中，且A的非零元素个数为count，算法Transpose求A的转置矩阵并将其保存在三元组表b中。 算法的主要思想是针对每个列号k（k=0, 2,… , n-1）对a进行扫描，考察a中是否有列号为k的结点（注意：列号为k的结点可能不止一个），若有，记为a[u]（假定a[u]在a中的行号为i ），将a[u]依次保存在b的b[w] 中，则row(b[w])=k，col(b[w])=i，value(b[w]) =value(a[u]).
TripletTable matrixTranspose(TripletTable* table) {
TripletTable result;
initTable(&result, table->cols, table->rows); // 转置后的矩阵行列互换
int j = 0;
for (int k = 0; k cols; k++) {
for (int i = 0; i length; i++) {
Triple* element = &(table->data[i]);
if (element->col == k) {
insertElement(&result, k, element->row, element->value);
// result.data[j].row = k; // 该元素在result中的行号应为k
// result.data[j].col = element->row; // 该元素在result中的列号应为其在table中的行号
// result.data[j].value = element->value;
j++; // 考察result中的下一个结点
result.length = j; // 更新result的长度
}
}
// printf("\n");
// displayMatrix(&result);
}
return result;
}
matrixTranspose函数实现稀疏矩阵的转置操作： 首先，创建一个新的TripletTable变量result，用于存储输入矩阵的转置。使用initTable函数初始化result，将其行数设置为输入矩阵的列数，列数设置为输入矩阵的行数。使用一个循环遍历输入矩阵的所有元素： 对于每个元素，将其行号作为转置后矩阵中的列号，列号作为转置后矩阵中的行号，并将值保持不变。将转置后的元素插入到result中。 返回result作为输入矩阵的转置。 加法 TripletTable matrixAddition(TripletTable* table1, TripletTable* table2) { TripletTable result; initTable(&result, table1->rows, table1->cols); int i = 0, j = 0; while (i length && j length) { Triple* element1 = &(table1->data[i]); Triple* element2 = &(table2->data[j]); if (element1->row row || (element1->row == element2->row && element1->col col)) { insertElement(&result, element1->row, element1->col, element1->value); i++; } else if (element1->row > element2->row || (element1->row == element2->row && element1->col > element2->col)) { insertElement(&result, element2->row, element2->col, element2->value); j++; } else { int sum = element1->value + element2->value; if (sum != 0) { insertElement(&result, element1->row, element1->col, sum); } i++; j++; } } while (i length) { Triple* element1 = &(table1->data[i]); insertElement(&result, element1->row, element1->col, element1->value); i++; } while (j length) { Triple* element2 = &(table2->data[j]); insertElement(&result, element2->row, element2->col, element2->value); j++; } return result; }matrixAddition函数实现稀疏矩阵的加法操作： 创建一个新的TripletTable变量result，用于存储两个输入矩阵的和。使用initTable函数初始化result，将其行数和列数设置为与输入矩阵相同。使用两个指针i和j分别指向两个输入矩阵的元素。通过比较当前元素的行号和列号，以及使用循环遍历的方式，将两个输入矩阵的元素逐个比较并进行相应的操作： 如果第一个矩阵的元素在行号和列号上小于第二个矩阵的元素，将第一个矩阵的元素插入到result中，并增加指向第一个矩阵元素的指针i。如果第一个矩阵的元素在行号和列号上大于第二个矩阵的元素，将第二个矩阵的元素插入到result中，并增加指向第二个矩阵元素的指针j。如果两个矩阵的元素在行号和列号上相等，将它们的值相加，并将结果插入到result中。然后，增加指向两个矩阵元素的指针i和j。 处理完所有元素后，将剩余的未处理元素插入到result中。返回result作为两个输入矩阵的和。 乘法 TripletTable matrixMultiplication(TripletTable* table1, TripletTable* table2) { TripletTable result; initTable(&result, table1->rows, table2->cols); int matrix[table1->rows][table2->cols]; for (int i = 0; i rows; i++) { for (int j = 0; j cols; j++) { matrix[i][j] = 0; } } for (int i = 0; i length; i++) { Triple* element1 = &(table1->data[i]); for (int j = 0; j length; j++) { Triple* element2 = &(table2->data[j]); if (element1->col == element2->row) { matrix[element1->row][element2->col] += element1->value * element2->value; } } } for (int i = 0; i rows; i++) { for (int j = 0; j cols; j++) { if (matrix[i][j] != 0) { insertElement(&result, i, j, matrix[i][j]); } } } return result; }matrixMultiplication函数实现稀疏矩阵的乘法操作： 创建一个新的TripletTable变量result，用于存储两个输入矩阵的乘积。使用initTable函数初始化result，将其行数设置为第一个输入矩阵的行数，列数设置为第二个输入矩阵的列数。创建一个临时的二维数组matrix，用于存储两个输入矩阵相乘的结果。将matrix中的所有元素初始化为0。使用两个嵌套的循环遍历第一个输入矩阵的所有元素： 对于每个元素，使用另一个嵌套的循环遍历第二个输入矩阵的所有元素。如果第一个矩阵的元素的列号等于第二个矩阵的元素的行号，将它们的值相乘，并将结果累加到matrix中对应位置的元素上。 遍历matrix中的所有元素，将非零元素插入到result中。返回result作为两个输入矩阵的乘积。 算法测试 int main() { TripletTable matrixA, matrixB; initTable(&matrixA, 3, 3); initTable(&matrixB, 3, 3); // Insert elements into matrix A insertElement(&matrixA, 0, 0, 1); insertElement(&matrixA, 0, 2, 2); insertElement(&matrixA, 1, 1, 3); insertElement(&matrixA, 2, 0, 4); insertElement(&matrixA, 2, 2, 5); // Insert elements into matrix B insertElement(&matrixB, 0, 1, 6); insertElement(&matrixB, 1, 0, 7); insertElement(&matrixB, 1, 2, 8); insertElement(&matrixB, 2, 1, 9); printf("Matrix A:\n"); displayMatrix(&matrixA); printf("\nMatrix B:\n"); displayMatrix(&matrixB); TripletTable matrixC = matrixAddition(&matrixA, &matrixB); printf("\nMatrix A + B:\n"); displayMatrix(&matrixC); TripletTable matrixD = matrixTranspose(&matrixA); printf("\nTranspose of Matrix A:\n"); displayMatrix(&matrixD); TripletTable matrixE = matrixMultiplication(&matrixA, &matrixB); printf("\nMatrix A * B:\n"); displayMatrix(&matrixE); return 0; } 实验结果
|
【本文地址】
今日新闻 |
推荐新闻 |