武汉理工大学

您所在的位置:网站首页 利用三元组实现矩阵转置运算的条件 武汉理工大学

武汉理工大学

2024-07-11 07:40| 来源: 网络整理| 查看: 265

文章目录 实验目标存储结构稀疏矩阵转置方法1:直接暴力法—— 时间复杂度:O(M.row_num * M.column_num * M.elem_num)方法2:遍历找列法—— 时间复杂度:O(M.column_num * M.elem_num)方法3:快速转置法—— 时间复杂度:O(M.column_num + M.elem_num) 稀疏矩阵相乘方法1:直接暴力法—— 时间复杂度:O(Q.row_num * Q.column_num * N.row_num)方法2:遍历找行法—— 时间复杂度:O(M.elem_num * N.column_num) 稀疏矩阵相加方法:逐个比较法—— 时间复杂度:O(max{A.elem_num,B.elem_num}) 源代码整合写在最后

实验目标

编写程序,采用合适的数据结构存储稀疏矩阵,实现其转置、相乘、相加的算法; 对于每一种操作,尽可能使用时间复杂度较小的算法。

存储结构

本文采用 三元组结构 对稀疏矩阵进行压缩存储。 对于矩阵中的每一个非零元素,使用以下结构体存储其 数据、行下标、列下标:

//矩阵的非零元素(三元组存储) typedef struct { int row; //元素行下标(由0开始) int column; //元素列下标(由0开始) int value; //元素的值 }Triple;

将所有非零元素的结构体 以行序为主序 排列为 结构体数组,即成为稀疏矩阵的存储结构:

//稀疏矩阵 typedef struct { Triple data[MAXSIZE + 1]; //元素组成的数据存储数组(data[0]不使用) int row_number; //矩阵行数(由1开始) int column_number; //矩阵列数(由1开始) int elem_number; //矩阵非零元个数 int EachRow_Number[MAXNUM]; //矩阵每一行非零元数量 int EachRow_Index[MAXNUM]; //矩阵每一行非零元在数组的位置 int EachColumn_Number[MAXNUM]; //矩阵每一列非零元数量 int EachColumn_Index[MAXNUM]; //矩阵每一列非零元在数组的位置 }SMatrix;

同时使用向量 EachRow_Number / EachColumn_Number 保存每一行/列的非零元素数量, 例如 EachRow_Number [1] = 2 表示第 1 行有 2 个非零元素;

向量 EachRow_Index / EachColumn_Index 保存的是指向某一行/列的某一个元素的 “指针”, 例如 EachRow_Index [1] = 2 表示“指向”了矩阵第 1 行的 data [2] 元素;

这两个向量的引入是为了缩短后续矩阵操作的时间复杂度。

稀疏矩阵转置

稀疏矩阵转置总结 3 种方法,记待转置矩阵为 M,转置后矩阵为 T。

方法1:直接暴力法 —— 时间复杂度:O(M.row_num * M.column_num * M.elem_num) /* 矩阵转置(方法1) 直接暴力法 时间复杂度: O(M.row_number * M.column_number * M.elem_number) */ bool TransposeSMatrix_ByViolence(SMatrix M, SMatrix &T) //利用引用来返值 { //属性赋予 T.elem_number = M.elem_number; T.row_number = M.column_number; T.column_number = M.row_number; if (T.elem_number > 0) { int index_T = 1; //T数组下标 for (int i = 0; i


【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3