徐州高端网站建设,无锡找做网站,顺德购物网站建设,企业建设网站的目标文章目录 4.2.1 矩阵的数组表示4.2.2 特殊矩阵的压缩存储a. 对角矩阵的压缩存储b~c. 三角、对称矩阵的压缩存储d. 稀疏矩阵的压缩存储——三元组表4.2.3三元组表的转置、加法、乘法、操作转置加法乘法算法测试实验结果代码整合 4.2.1 矩阵的数组表示
【数据结构】数组和字符串… 文章目录 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. 稀疏矩阵的压缩存储——三元组表 对于稀疏矩阵的压缩存储由于非零元素的个数远小于零元素的个数并且非零元素的分布没有规律无法简单地利用一维数组和映射公式来实现压缩存储。针对稀疏矩阵通常采用特定的数据结构来进行压缩存储以减少存储空间的占用。 一种常见的稀疏矩阵压缩存储方法是使用三元组表示法也称为COOCoordinate格式只存储非零元素的值以及它们的行列坐标。通过使用三元组Triplet来表示非零元素的位置和值每个三元组包含三个信息非零元素的行索引、非零元素的列索引以及非零元素的值。
【数据结构】数组和字符串四特殊矩阵的压缩存储稀疏矩阵——三元组表
4.2.3三元组表的转置、加法、乘法、操作
转置 假设稀疏矩阵存储在一个三元组表a中且A的非零元素个数为count算法Transpose求A的转置矩阵并将其保存在三元组表b中。
算法的主要思想是针对每个列号kk0, 2,… , n-1对a进行扫描考察a中是否有列号为k的结点注意列号为k的结点可能不止一个若有记为a[u]假定a[u]在a中的行号为i 将a[u]依次保存在b的b[w] 中则row(b[w])kcol(b[w])ivalue(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 table-cols; k) {for (int i 0; i table-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 table1-length j table2-length) {Triple* element1 (table1-data[i]);Triple* element2 (table2-data[j]);if (element1-row element2-row || (element1-row element2-row element1-col element2-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 table1-length) {Triple* element1 (table1-data[i]);insertElement(result, element1-row, element1-col, element1-value);i;}while (j table2-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 table1-rows; i) {for (int j 0; j table2-cols; j) {matrix[i][j] 0;}}for (int i 0; i table1-length; i) {Triple* element1 (table1-data[i]);for (int j 0; j table2-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 table1-rows; i) {for (int j 0; j table2-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 AinsertElement(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 BinsertElement(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;
}实验结果 代码整合
#include stdio.h
#include stdlib.h
#include string.h
#define MAX_SIZE 10typedef struct {int row;int col;int value;
} Triple;typedef struct {Triple data[MAX_SIZE];int rows;int cols;int length;
} TripletTable;void initTable(TripletTable* table, int rows, int cols) {table-rows rows;table-cols cols;table-length 0;memset(table-data, 0, sizeof(Triple) * MAX_SIZE); // 新添加
}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;
}void displayMatrix(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);}
}
TripletTable matrixAddition(TripletTable* table1, TripletTable* table2) {TripletTable result;initTable(result, table1-rows, table1-cols);int i 0, j 0;while (i table1-length j table2-length) {Triple* element1 (table1-data[i]);Triple* element2 (table2-data[j]);if (element1-row element2-row || (element1-row element2-row element1-col element2-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 table1-length) {Triple* element1 (table1-data[i]);insertElement(result, element1-row, element1-col, element1-value);i;}while (j table2-length) {Triple* element2 (table2-data[j]);insertElement(result, element2-row, element2-col, element2-value);j;}return 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 table1-rows; i) {for (int j 0; j table2-cols; j) {matrix[i][j] 0;}}for (int i 0; i table1-length; i) {Triple* element1 (table1-data[i]);for (int j 0; j table2-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 table1-rows; i) {for (int j 0; j table2-cols; j) {if (matrix[i][j] ! 0) {insertElement(result, i, j, matrix[i][j]);}}}return result;
}TripletTable matrixTranspose(TripletTable* table) {TripletTable result;initTable(result, table-cols, table-rows); // 转置后的矩阵行列互换int j 0;for (int k 0; k table-cols; k) {for (int i 0; i table-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;
}int main() {TripletTable matrixA, matrixB;initTable(matrixA, 3, 3);initTable(matrixB, 3, 3);// Insert elements into matrix AinsertElement(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 BinsertElement(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;
}
