矩阵的存储

1. 前言

    矩阵是许多科学与工程计算中经常遇到的问题，在高级语言中，通常使用二维数组来存储矩阵。然而，在矩阵的算法中，往往会出现阶数很高的矩阵中存在许多相同的元素或值为零的元素。为了节约存储空间，需要将这些矩阵进行压缩存储。如果矩阵中的元素存在一定的规律，则称这种矩阵为特殊矩阵。如果矩阵中的元素有许多的零元素且不具有规律性，则称这种矩阵为稀疏矩阵。

2. 特殊矩阵的压缩存储

（1）对称矩阵的压缩存储

    在一个n阶方阵A中，若元素满足下述性质： 

    a_ij=a_ji 0≤i，j≤n-1

    则称A为对称矩阵。

    例如下图便是一个5阶对称矩阵：

图 对称矩阵示例

    对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间。这样，能节约近一半的存储空间。按"行优先顺序"存储主对角线(包括对角线)以下的元素：

图 对称矩阵的行优先存放

     即按a₀₀,a₁₀,a₁₁,……，a_n-1,0,a_n-1,1…，a_n-1,n-1次序存放在一个向量sa[0．．n(n+1)／2-1]中（下三角矩阵中，元素总数为n(n+1)／2）。

图 对称矩阵的压缩存储

 

（2）三角矩阵的压缩存储

     以主对角线划分，三角矩阵有上三角矩阵和下三角矩阵两种。
    ①上三角矩阵
    　如下图(a)所示，它的下三角(不包括主角线)中的元素均为常数c。
    ②下三角矩阵
    　与上三角矩阵相反，它的主对角线上方均为常数c，如下图(b)所示。
     注意：
　        在多数情况下，三角矩阵的常数c为零。

图 三角矩阵示意图

    三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n×(n+1)／2个，因此，三角矩阵可压缩存储到向量sa[0．．n(n+1)／2]中，其中c存放在向量的最后一个分量中。

   

（3）对角矩阵的压缩存储

    所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零的矩阵为对角矩阵。

图 对角矩阵示意图

    对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。

3. 稀疏矩阵的压缩存储

    设矩阵A_mn中有s个非零元素，若s远远小于矩阵元素的总数(即s<<m×n)，则称A为稀疏矩阵。稀疏因子=(s)/(m+n)，若s<=0.05，则称矩阵为稀疏矩阵。

    为了节省存储单元，可只存储非零元素。由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须存储非零元素所在的行号、列号，才能迅速确定一个非零元素是矩阵中的哪一个元素。稀疏矩阵的压缩存储会失去随机存取功能。
    其中每一个非零元素所在的行号、列号和值组成一个三元组(i，j，aij)，并由此三元组惟一确定。
    稀疏矩阵进行压缩存储通常有两类方法：顺序存储和链式存储。

    将表示稀疏矩阵的非零元素的三元组按行优先(或列优先)的顺序排列(跳过零元素)，并依次存放在向量中，这种稀疏矩阵的顺序存储结构称为三元组表。

图 稀疏矩阵和它的三元组表

    为了运算方便，将矩阵的总行数、总列数及非零元素的总数均作为三元组表的属性进行描述。其类型描述为：

#define MaxSize 10000 //由用户定义
typedef int DataType； //由用户定义
typedef struct { //三元组
    int i，j；//非零元的行、列号
    DataType v； //非零元的值
}TriTupleNode；

typedef struct{ //三元组表
    TriTupleNode data[MaxSize]； //三元组表空间
    int m,n，t； //矩阵的行数、列数及非零元个数
}TriTupleTable； 

 

矩阵的转置：

    方法一:简单地交换a->data中i和j中的内容，得到按列优先顺序存储倒b->data;再将b->data重排成按行优先顺序的三元组表。
    方法二:由于A的列是B的行，因此，按a->data的列序转置，所得到的转置矩阵B的三元组表b->data必定是按行优先存放的。
    按这种方法设计的算法，其基本思想是：对A中的每一列col(0≤col≤a->n-1)，通过从头至尾扫描三元组表a->data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放人b->data中，即可得到B的按行优先的压缩存贮表示。具体实现参见【动画演示】

 

稀疏矩阵的十字链表示：

    稀疏矩阵的链式存储，就是利用链表来表示矩阵，链表中的每个结点存储稀疏矩阵中的每个非零元素。每个结点包含5个域：其中3个数据域是i、j和e，分别表示非0元素的行号、列号和元素值；两个指针域是right域和down域，right指向同一行中的下一个非零元素，down指向同一列的非零元素。

    同一行的非零元素由right链接构成一个线性链表，同一列的非零元素由down链接构成一个线性链表。每个非零元素既是某一行链表的一个元素，又是某一列链表的一个元素，整个链表构成一个十字交叉的形状，这样的链表称为十字链表。

    十字链表的类型描述如下:

typedef struct OLNode
{
        int i,j;
        DataType e;
        struct OLNode *right, *down;
}OLNode,*OLink;
typedef struct
{
        OLink *rowhead, *colhead;
        int m, n, len;
}CrossList;

    其中，i和j分表表示稀疏矩阵中非零元素的行号和列号，e表示非零元素值，right指向同一行的下一个非零元素，down指向同一列的下一个非零元素。rowhead和colhead分别存放指向行链表和列链表的指针，m和n分别表示稀疏矩阵的行数和列数，len表示稀疏矩阵中非零元素的个数。