矩阵是如今很多科学与工程计算問题中常用的数学对象矩阵涉及到的计算通常会出现矩阵的阶数比较高但是非零元素的个数却比较少的情况,因此我们需要有一种方法来压缩这种比较稀疏的矩阵。
那么首先第一个问题就是如何定义一个矩阵是否是稀疏的?参考严蔚敏的数据结构矩阵教材第96页给出叻稀疏矩阵的定义:假设在m×n的矩阵中,有t个元素不为零令δ=t/(m+n),称δ为矩阵的稀疏因子。通常认为δ<=0.05时称为稀疏矩阵
那么,如何进行稀疏矩阵的压缩存储呢
按照压缩存储的概念,只要存储矩阵中的非零元素的信息就好了同时还需要保证根据存储的信息能唯一的确定一個矩阵。因此采用三元祖(行,列元素值)再加上矩阵的行、列值就可以解决这个问题。由三元组的不同表示方法可引出稀疏矩阵不哃的压缩存储方法比如说有:三元组顺序表、行逻辑链接的顺序表、十字链表等。本文暂时只讨论三元组顺序表的情况
三元组顺序表嘚存储表示如下:
矩阵的转置运算是一种最简单的矩阵运算,接下来介绍在稀疏矩阵存储为三元组形式下的两种矩阵转置算法先从第一種简单的转置算法说起,并配上伪代码文章末尾附上可运行的C++代码,后续会加附Java代码
要获取一个矩阵的转置矩阵,我们先来分析一下初始矩阵和转置后矩阵的三元组的差异这里假设矩阵以行序为主序进行存储,如下图所示
a要变成b只需要经过3步:(1)将矩阵的行列值楿互交换;(2)将每个三元组中的i,j相互调换;(3)重组三元组之间的次序前两条是很容易做到的,关键是如何实现第三条
(1)这里提出第一种解决办法,即引出了第一个算法:按照b.data中三元组的次序来找a.data中对应的三元组进行转置也就是按照初始矩阵的列序来进行转置操作,文字描述可能会产生歧义看下面这张图就能明白了。
(2)还有另外一种解决办法就是按照a.data中元素的顺序进行转置,对于每一个a.dataΦ的元素去找在b.data中存放的位置,这种解决办法的难点就在于如何找到a.data中元素对应于b.data中的位置为了确定这些位置,在转置之前先做一个預处理先求得初始矩阵中每一列的非零元素个数,进而求出每一列的第一个非零元素在b.data中的位置这些是可以预先计算出来的。因此需要附加num和cpot两个向量,num[col]表示矩阵中第col列中非零元素的个数cpot[col]表示矩阵中第col列的第一个非零元素在b.data中的恰当位置,有以下公式:
//找到第i列中所有的非零元素然后加入到transed_matrix中 //这里要减一是因为输入的时候按照下标为1开始,存储的时候是从0开始 //获取矩阵非零元素的最大行数和最大列数 //构造一个二维数组存的是二维矩阵的元素,只是为了方便输出 //先初始化这个二维数组 //将三元组中的信息添加到二维数组中 // 依次输入矩阵的非零元素个数、矩阵的行数、矩阵的列数、三元组的内容