数据结构

1.如果矩阵中有很多数值相同的数据元素，在存储时，可以考虑对其进行适当的压缩存储。 有必要压缩存储的矩阵大致分为两大类：

2.两类矩阵压缩存储的方法：

3.对称矩阵

如果n阶矩阵中的元素满足： aij = aji ( i 为行标， j 为列标)，就称这个矩阵为对称矩阵。

图 为 3 阶对称矩阵，图中的虚线为矩阵的 “主对角线” ，主对角线上方区域称为 “上三角” ；主对角线下方称为 “下三角” ，沿主对角线对称的数据元素一一相等，所以对于此矩阵来说，只需要存储 6 个元素即可。 若将对称矩阵压缩存储在一维数组 S[k] 中，矩阵中数据元素在数组中存储的位置和所在的行标（用 i 表示）和列标（用 j 表示）有关。 对称矩阵沿主对角线对称的数据元素相等，任选一边的数据元素进行存储即可： 存储下三角区域的数据元素：

存储上三角区域的数据元素：

4.上下三角矩阵

上下三角矩阵，和对称矩阵类似，不同在于，上三角矩阵是指主对角线下方的元素（不包括主对角线上的）都是常数C（包括数值 0 ）；同理，下三角矩阵是指主对角线上方的元素都是常数C。 例如：

存储时，上（下）三角存储上（下）三角的数据元素，除此之外，额外存储一个下（上）三角含有的常数C（图 2 中，C==0）

5.稀疏矩阵

稀疏矩阵，简单的说，就是矩阵中只含有少量的非 0 元素，相比于使用普通方式将矩阵中的所有数据元素一一存储，不如只存储非 0 元素更节省内存空间。

例如：

6.矩阵压缩存储的方式

矩阵压缩存储的方式有 3 种，分别为：三元组顺序表、行逻辑链接的顺序表和十字链表。

7.三元组顺序表

在存储稀疏矩阵时，除了要存储非 0 元素的值之外，还需要存储元素所在矩阵中的行标 i 和列标 j ，三个元素构成三元组（行标，列标，元素值）。 所以，表示三元组结构需要使用结构体进行自定义：

8.每个稀疏矩阵的表示，需要存储矩阵中所有非 0 元素的三元组，并且还需要记录矩阵的行数和列数，这样才能唯一确定一个稀疏矩阵。所以，表示矩阵的结构也需要使用结构体实现：

例如，对于图 3 的稀疏矩阵来说，即将（2，2，3）、（2，3，4）、（3，2，5）存储进 data 数组，并且存储稀疏矩阵的行数 3 和列数 3 ，该稀疏矩阵中非 0 元素有 3 个。

9.行逻辑链接的顺序表

使用三元组顺序表存储矩阵后，当需要提取矩阵某一行的非 0 元素时，需要遍历整个顺序表。 为了提高查找的效率，在三元组顺序表的基础上，增加一个数组用于记录每一行第一个非 0 元素的存储位置，这样的存储结构，称为：行逻辑链接的顺序表。 结构代码：

10.十字链表

以上两种存储稀疏矩阵的方法，说到底，还是操作数组，在进行矩阵运算过程中，如果有插入非 0 元素或者删除某一个元素的操作，可能需要大量的移动数组中的三元组。这时，就要考虑使用链表的存储结构。 例如在进行“将矩阵 B 加到矩阵 A 上”的操作时，矩阵 A 中的数据元素会发生很大的变化，之前的 0 元素可能变成非 0 元素，非 0 元素也可能变成 0 （正负数相加为 0）。在这种情况下，就需要使用链表的存储结构来存储矩阵，这种存储方式称为：十字链表法。 例如，将下列矩阵以十字链表的方式存储起来：

总结：