特殊矩阵的压缩存储

矩阵在计算机图形学、工程计算中占有举足轻重的地位。在数据结构中考虑的是如何用最小的内存空间来存储同样的一组数据。所以，我们不研究矩阵及其运算等，而把精力放在如何将矩阵更有效地存储在内存中，并能方便地提取矩阵中的元素。

数组的定义

数组是由 #card=math&code=n%5C%20%28n%5Cge%201%29&id=HthJ8) 个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在 个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。

数组与线性表的关系：数组是线性表的推广。一维数组可视为一个线性表；二维数组可视为其元素也是定长线性表的线性表，以此类推。数组一旦被定义，其维数和维界就不再改变。因此，除结构的初始化和销毁外，数组只会有存取元素和修改元素的操作。

数组的存储结构

大多数计算机语言都提供了数组数据类型，逻辑意义上的数组可采用计算机语言中的数组数据类型进行存储，一个数组的所有元素在内存中占用一段连续的存储空间。

以一维数组 A[0...n-1] 为例，其存储结构关系式为：， 其中， 是内存地址， 是每个数组元素所占的存储单元。

对于多维数组，有两种映射方法：按行优先（一行一行存，一行存完存下一行）和按列优先（一列一列存，一列存完存下一列）。以二维数组为例，按行优先存储的基本思想是：先行后列，先存储行号较小的元素，行号相等先存储列号较小的元素。设二维数组的行下标与列下标的范围分别为 与 ，则存储结构关系式为：

当以列优先方式存储时， 得出存储结构关系式为：

矩阵的压缩存储

普通矩阵可用二维数组存储，特殊矩阵可以压缩存储空间。

• 压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。其目的是为了节省存储空间。
• 特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。常见的特殊矩阵有对称矩阵、上（下）三角矩阵、对角矩阵等。

特殊矩阵的压缩存储方法：找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的、值相同的多个矩阵元素压缩存储到一个存储空间中。

对称矩阵

若对一个 阶方阵 中的任意一个元素 都有 #card=math&code=a%7Bi%2Cj%7D%3Da%7Bj%2Ci%7D%5C%20%28a%20%5Cle%20i%2Cj%20%5Cle%20n%29&id=TOclW) ，称为对称矩阵。

对于一个 阶方阵，其中的元素可以划分为3个部分，即上三角区（）、主对角线（）和下三角区（）。

对于 阶对称矩阵，上三角区的所有元素和下三角区的对应元素相同，若仍采用二维数组存放，则会浪费几乎一半的空间，为此将对称矩阵 存放在一维数组 %7D%7B2%7D%20%5D#card=math&code=B%5B%5Cfrac%7Bn%28n%2B1%29%7D%7B2%7D%20%5D&id=KYTs0) 中，即元素 存放在 中。只按行优先原则将各元素存入一维数组中，存放下三角部分（含主对角）的元素。

在数组 中，位于元素 #card=math&code=a_%7Bi%2Cj%7D%20%5C%20%28i%20%5Cge%20j%29&id=fuTy4) 前面的元素个数为：

• 第 1 行：1 个元素 #card=math&code=%28a_%7B1%2C1%7D%29&id=Ut3Zi)
• 第 2 行：2 个元素 #card=math&code=%28a%7B2%2C1%7D%2Ca%7B2%2C2%7D%29&id=gJNGv)
• ……
• 第 行： 个元素 #card=math&code=%28a%7Bi-1%2C1%7D%2Ca%7Bi-1%2C2%7D%2C%5Cdots%20%2Ca_%7Bi-1%2Ci-1%7D%29&id=XE6Db)
• 第 行： 个元素 #card=math&code=%28a%7Bi%2C1%7D%2Ca%7Bi%2C2%7D%2C%5Cdots%20a_%7Bi%2Cj-1%7D%29&id=ETGjn)

因此，元素 在数组 中的下标 %20%2B%20j-%201%20%3D%20%5Cfrac%7Bi(i-1)%7D%7B2%7D%2Bj-1#card=math&code=k%3D1%20%2B2%2B%20%5Cdots%20%2B%28i%20-%201%29%20%2B%20j-%201%20%3D%20%5Cfrac%7Bi%28i-1%29%7D%7B2%7D%2Bj-1&id=Azeo0) （数组下标从0开始）。因此，元素下标之间的对应关系如下：

%7D%7B2%7D%2Bj-1%2C%20%26%20i%20%5Cge%20j%20%5C%5C%5C%5C%20%20%0A%20%20%5Cfrac%7Bj(j-1)%7D%7B2%7D%2Bi-1%2C%20%26%20i%20%3C%20j%0A%5Cend%7Bcases%7D#card=math&code=k%20%3D%20%5Cbegin%7Bcases%7D%20%0A%20%20%5Cfrac%7Bi%28i-1%29%7D%7B2%7D%2Bj-1%2C%20%26%20i%20%5Cge%20j%20%5C%5C%5C%5C%20%20%0A%20%20%5Cfrac%7Bj%28j-1%29%7D%7B2%7D%2Bi-1%2C%20%26%20i%20%3C%20j%0A%5Cend%7Bcases%7D&id=Dn7gb)

TODO 对称矩阵压缩代码实现

三角矩阵

下三角矩阵中，上三角区的所有元素均为同一常量。其存储思想与对称矩阵类似，不同之处在于存储完下三角区和主对角线上的元素之后，紧接着存储对角线上方的常量一次，故可以将下三角矩阵 压缩存储在 %7D%7B2%7D%2B1%5D#card=math&code=B%5B%5Cfrac%7Bn%28n%2B1%29%7D%7B2%7D%2B1%5D&id=GoFmX) 中。元素下标之间的对应关系为：

%7D%7B2%7D%2Bj-1%2C%20%26%20i%20%5Cge%20j%20%5C%5C%5C%5C%20%5Cfrac%7Bn(n%2B1)%7D%7B2%7D%2C%20%26%20i%20%3C%20j%20%5Cend%7Bcases%7D%0A#card=math&code=k%20%3D%20%5Cbegin%7Bcases%7D%20%5Cfrac%7Bi%28i-1%29%7D%7B2%7D%2Bj-1%2C%20%26%20i%20%5Cge%20j%20%5C%5C%5C%5C%20%5Cfrac%7Bn%28n%2B1%29%7D%7B2%7D%2C%20%26%20i%20%3C%20j%20%5Cend%7Bcases%7D%0A&id=csd9K)

上三角矩阵中，下三角区的所有元素均为同一常量。只需存储主对角线、上三角区上的元素和下三角区的常量一次，可将其压缩存储在 %7D%7B2%7D%2B1%5D#card=math&code=B%5B%5Cfrac%7Bn%28n%2B1%29%7D%7B2%7D%2B1%5D&id=oyRSW) 中，元素下标之间的对应关系如下：

(2n-i%2B2)%7D%7B2%7D%2B(j-i)%2C%20%26%20i%20%5Cge%20j%20%5C%5C%5C%5C%20%20%0A%20%20%5Cfrac%7Bn(n%2B1)%7D%7B2%7D%2C%20%26%20i%20%3C%20j%0A%5Cend%7Bcases%7D%20#card=math&code=%20k%20%3D%20%5Cbegin%7Bcases%7D%20%0A%20%20%5Cfrac%7B%28i-1%29%282n-i%2B2%29%7D%7B2%7D%2B%28j-i%29%2C%20%26%20i%20%5Cge%20j%20%5C%5C%5C%5C%20%20%0A%20%20%5Cfrac%7Bn%28n%2B1%29%7D%7B2%7D%2C%20%26%20i%20%3C%20j%0A%5Cend%7Bcases%7D%20&id=g1jAD)

TODO 三角矩阵压缩代码实现

三对角矩阵

对角矩阵也称带状矩阵。对于 阶方阵 中任一元素 ，当 时，有 #card=math&code=a_%7Bi%2Cj%7D%3D0%20%5C%20%281%5Cle%20i%2Cj%20%5Cle%20n%29&id=J87MG) ，则称为三对角矩阵。

在三对角矩阵中，所有非零元素都集中在以主对角线为中心的3条对角线区域，其他区域的元素都为 0。

三对角矩阵 也可以采用压缩存储，将 3 条对角线上的元素按行优先方式存放在一维数组 中，且 存放于 中。

三对角矩阵 3 对角线上的元素 #card=math&code=a_%7Bi%2Cj%7D%20%5C%20%281%20%5Cle%20i%2Cj%20%5Cle%20n%2C%5C%20%7Ci-j%7C%20%5Cle%201%29&id=NVA9H) 在一维数组 中存放的下标为

反之，若己知三对角线矩阵中某元素 ， 存放于一维数组 的第 个位置，则可得 ，

TODO 三对角矩阵压缩实现

稀疏矩阵

矩阵中非零元素的个数 ，相对矩阵元素的个数 来说非常少，即 的矩阵称为稀疏矩阵。例如，一个矩阵的阶为100×100，该矩阵中只有少于 100 个非零元素。

若采用常规的方法存储稀疏矩阵，则相当浪费存储空间，因此仅存储非零元素。但通常零元素的分布没有规律，所以仅存储非零元素的值是不够的，还要存储它所在的行和列。因此，将非零元素及其相应的行和列构成一个三元组（行标，列标，值）。然后再按照某种规律存储这些三元组。稀疏矩阵压缩存储后便失去了随机存取特性。

稀疏矩阵的三元组既可以采用数组存储，也可以采用十字链表法存储。

TODO 稀疏矩阵两种方法的 C++ 语言实现