三元组稀疏矩阵快速转置Ｃ语言算法
徐光联
摘要：三元组稀疏矩阵的快速转置算法在《数据结构》课程中是一个难点，这里给出三元组稀疏矩阵的转置算法详细讲解，并给出Ｃ语言算法的源程序。
关键词：三元组；稀疏矩阵；快速转置
｛ｉｎｔ ｍ，ｎ，ｔ； ／＊ ｍ 表示行数， ｎ 表示列数，ｔ 表示非零元素个数 ＊／
Ｍａｔ ｄａｔａ［ＭＡＸＳＩＺＥ］； ／＊ 所存储元素的最大个数 ＊／)Ｓｐｍａｔｒｉｘ；
Ｓｐｍａｔｒｉｘ ａ，ｂ；
要假定结构中ｄａｔａ域表示非零元素的三元组是以行为主顺序排列的。(算式１)表示了稀疏矩阵Ｍ和Ｎ中ｄａｔａ域的排列情况。这种表示方法，在矩阵足够稀疏的情况下，对存储空间的需求量比通常的方法少得多。
一、前 言
三元组稀疏矩阵的快速转置算法在《数据结构》课程中是一个难点，处理这个知识点很费时间，在教学过程中，往往受课时限制，采取略过不讲的办法，有的教材就干脆把它省去不提。日常生产和科研过程中，数字计算中大量使用了矩阵，为了减少运算量，提高运算效率，这个算法很有用处。这里给出三元组稀疏矩阵的快速转置算法详细过程，并给出Ｃ语言描述的实例。
矩阵转置定义为： ｍ行ｎ列矩阵Ｍ(ｍ，ｎ) 转换为ｎ行ｍ列Ｎ
矩阵，即行列互换。例如：(ｎ，ｍ)
如Ｍ(３，４)转置为Ｎ(４，３)。如图－１矩阵转置。
二、数组的三元组表示与稀疏矩阵
在实际应用中，往往会遇到一种大多数元素的值为零的矩阵，只有少部分为非零元素，这些非零元素在矩阵中的分布又没有一定的规律，我们把它记作“零元素个数＞＞非零元素个数”，即零元素个数远远大于非零元素个数。这种矩阵称为稀疏矩阵(ｓｐａｒｓｅ ｍａｔｒｉｘ)。例如，下面所示的矩阵Ｍ和它的转置矩阵Ｎ，在３０个元素中只有８个非零元素，显然是个稀疏矩阵。如图－２，稀疏矩阵Ｍ转置成Ｎ的示意图。
为了节省空间，可以
进行压缩存储，只需存储稀疏矩阵的非零元素。但是，为了实现矩阵的各种运算，除了存储非零元素的值外，还必须同时记下它所在的行和列。可以用一个三元组(ｉ， ｊ， ａｉｊ)唯一地确定矩阵中的一个非零元素，其中ｉ， ｊ分别表示非零元素的行号和列号，ａｉｊ表示非零元素的值。
下面就是(算式１)式中矩阵Ｍ的(５行６列共有)８个非零元素的三元组表示：
｛ (１，１， ８)， (１，３， ９) ， (２，２，２) ， (３，４，３) ， (３，６，７)， (４，１，６) ， (４，３，４) ， (５，４，５)｝
若以某种方式(以行为主或以列为主的顺序)将８个三元组排列起来，再加上一个表示矩阵Ｍ的行数，列数及非零元素的个数的特殊的三元组(５，６，８)，则所形成的表就能唯一地确定稀疏矩阵。
三元组表： 假设以顺序存储结构来表示三元组表(ｔｒｉｐｌｅｔａｂｌｅ)，则得到稀疏矩阵的一种压缩存储方式，即三元组顺序表，简称三元组表。其结构描述如下：
ｔｙｐｅｄｅｆ ｓｔｒｕｃｔ｛ｉｎｔ Ｉ，ｊ；
ＥｌｅｍＴｙｐｅ ｖ；｝Ｍａｔ；
ｔｙｐｅｄｅｆ ｓｔｒｕｃｔ2008.No5９２
例如， 我们所说的５×６的矩阵Ｍ，若用三元组表来表示，在每个元素占一个存储单元的情况下，则只需要２７个存储单元(包括特殊三元组所占的３个单元，可以使用数组［０］单元)；若直接用二维数组，按通常办法表示，则需３０个单元。矩阵越大，越稀疏，其优越性越明显。
三、稀疏矩阵的转置算法。
矩阵的转置运算是变换元素的位置，把位于(ｉ， ｊ)的元素换到(ｊ， ｉ)位置上。也就是说，把元素的行和列对换。所以一个ｍ×ｎ的矩阵Ｍ，它的转置矩阵是一个ｎ×ｍ的矩阵，且Ｎ［ｉ，ｊ］＝Ｍ［ｊ，ｉ］，其中，１≤ｉ≤ｎ，１≤ｊ≤ｍ。例如， (算式１)中的矩阵Ｎ就是矩阵Ｍ的转置矩阵，矩阵Ｎ也是一个稀疏矩阵，其非零元素的排列情况如表－１(ｂ)所示。求矩阵Ｍ的转置矩阵Ｎ，实际上就是由表－１(ａ)求表－１(ｂ)。
从表－１可以看出，对每个非零元素而言，从Ｍ转置到Ｎ，分两步，第一步，把ａ．ｄａｔａ的第一列数和第二列数对换，得到的ｂ＇．ｄａｔａ。因为ｂ’．ｄａｔａ是按非零元素在Ｎ中的列序排列的，又因为我们已约定，ｂ．ｄａｔａ中的非零元素应按照在矩阵Ｎ中的行序排列。第二步，将ｂ’．ｄａｔａ转换成按非零元素在矩阵Ｎ中的行序排列的ｂ．ｄａｔａ。转换方法如下：
普通算法分析：按ｂ．ｄａｔａ中三元组的次序进行转置。也就是说，按照矩阵Ｍ的列序进行转置。显然，为了找到Ｍ中的每一列的所有的非零元素，需要对ａ．ｄａｔａ从第１行起整个扫描一遍。由于ａ．ｄａｔａ是以Ｍ的行序来存放每一个非零元素的，因此，这样得到的顺序恰好是ｂ．ｄａｔａ应有的顺序。其具体算法描述如下：
＃ｄｅｆｉｎｅ ＭａｘＳｉｚｅ １００＃ｄｅｆｉｎｅ ＥｌｅｍＴｙｐｅ ｉｎｔｔｙｐｅｄｅｆ ｓｔｒｕｃｔ｛ｉｎｔ ｉ，ｊ；ＥｌｅｍＴｙｐｅ ｖ；｝Ｍａｔ；
ｔｙｐｅｄｅｆ ｓｔｒｕｃｔ