三元组结构实现稀疏矩阵转置算法的分析
文章简要叙述了稀疏矩阵压缩存储的三元组表示法及其基于此种结构的矩阵的转置运算。探讨了基于三元组结构的矩阵转置算法的具体实现方法及其时空复杂度的问题。
  【关键词】稀疏矩阵 压缩存储 三元组 转置算法
  在一些特殊矩阵中，如对称矩阵和上下三角矩阵，非零元素一般都有明显的规律，从而都可以压缩到一维数组里面，然而，实际应用中经常会遇到这样一些矩阵，它们非零元素少，且分布不均匀，且没有明显的规律，称之为稀疏矩阵。按照压缩存储的思想，只需存储矩阵中的非零元素。为了便于存取和检索，一般在存储的时候必须带有合适的辅助信息，即同时记录下它所在的行列的位置等等。在实际应用中，一般我们采取的是用三元组和十字链表两种表示方法来实现稀疏矩阵的存储及其运算。稀疏矩阵在数值计算、电力系统的潮流计算、天气预报、工程分析计算等方面都有着大量的应用，不少实际问题都可以转化为对稀疏矩阵的计算问题。了解稀疏矩阵的各种操作变得尤为重要。
  1 基本概念
  设矩阵中有t个非零元素，若t远远小于矩阵元素的总数，则称该矩阵为稀疏矩阵。通常，在m×n 的矩阵中，存在t个非零元素。设δ= t/（m*n），则称δ为矩阵的稀疏因子，一般认为当δ≤0.05时为稀疏矩阵。在存储稀疏矩阵时，为了节约存储单元，很自然的压缩方法就是只存储非零元素，但由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储相应的辅助信息，才能准确迅速确定一个非零元素是矩阵中的哪一个元素。最简单的办法就是将非零元素的值和它所在的行列号作为一个结点存放到一起，于是矩阵中的每一个非零元素就由一个三元组（i，j，aij）唯一确定。显然，稀疏矩阵的压缩存储方法会让其失去随机存取功能。
  2 三元组表示稀疏矩阵转置算法的实现
  用三元组来表示非零元素时稀疏矩阵的压缩存储方法的具体数据类型说明如下：
  三元组表示的稀疏矩阵，如何实现转置算法呢？矩阵的转置是基本的矩阵运算，对于一个m×n 的矩阵M，它的转置N是一个n×m 的矩阵，且有N（i，j）=M（j，i）。设M和N互为转置矩阵，显然一个稀疏矩阵的转置亦是稀疏矩阵，假定a和b是此Stp类型的变量，分别表示矩阵M和N，接下来的问题就是如何实现由a到b。由于我们所用的存储方式一般都是按行存
储，三元组表示的稀疏矩阵实现转置时具体做法是将每个三元组中的行列号互换，并按照新的行号排列三元组。实现转置操作主要有两步：第一步，在三元组表中，对i和j的值进行交换。第二步，重新排列三元组之间的次序从而得到矩阵的转置。第一步实现起来很容易，第二步的实质就是如何实现使b.data三元组以矩阵N的行，也就是M的列为主序列来存储。按照M矩阵的列序进行转置操作，对M中的每一列col，通过从头到尾扫描三元组表a.data，到所有列序号等于col的那些三元组，将它们的行号和列号交换后顺序依次放入b.data中，即可以得到N的按行优先的压缩存储表示。具体代码实现过程比较简单，读者可自行完成，过程中需要注意的是参数之间利用地址传递比利用值传递容易实现很多。基于三元组的存储方式对稀疏矩阵的压缩存储，在对稀疏矩阵进行转置运算时，还有一种改进的的快速转置的算法，它的时间复杂度只有O（n+t），这种快速转置的算法还需引入两个数组作为辅助数据结构，其中一个表示矩阵M中某列的非零元素的个数；另一个数组初始值表示矩阵M中某列的第一个非零元素在N中的位置。它们之间具有一定的递归关系。利用附加的这种关系结构能够更精巧的完成稀疏矩阵基于三元组的转置运算，这里就不再敖述。
  3 算法时空复杂度的分析
  一般情况下，算法的时间效率和空间效率是一对矛盾体。有时算法的时间效率的提高是以使用了更多的存储空间为代价的，反之亦然。基于三元组的基本的矩阵转置算法的时间主要耗费在了此算法的二重循环上，若M的列数为n，非零元素的个数为t，则执行时间为O（n*t），即与矩阵的列数和非零元素个数的乘积成正比例。通常我们用二维数组表示矩阵时，其转置算法的执行时间是O（m*n），它和行数和列数的乘积成正比。虽然稀疏矩阵的三元组存储方式可以为系统节约很多的存储空间，但由于矩阵中非零元素的个数一般远远大于行数，所以基于此种结构的稀疏矩阵的转置算法的时间，一般会大于非压缩存储的矩阵转置算法的时间。在稀疏矩阵的实际应用中，我们应该根据具体领域应用的不同，设计更合理的压缩存储结构，基于结构设计出更适合实际需要的算法。
  参考文献
  [1] 严蔚敏，吴伟民.数据结构（C语言版）[M]. 北京：清华大学出版，2008.
  [2]杨开城.数据结构（C语言版）[M].北京：电子工业出版社，2008.
  [3]郝春梅.数据结构（C语言版）[M].北京：清华大学出版社，2010.
c语言二维数组转置
  作者单位
  河北科技大学唐山分院 河北省唐山市 063000