稀疏矩阵与压缩存储

一、稀疏矩阵的定义

　　矩阵中非零元素的个数远远小于矩阵元素的总数，并且非零元素的分布没有规律，通常认为矩阵中非零元素的总数比上矩阵所有元素总数的值小于等于0.05时，则称该矩阵为稀疏矩阵(sparse matrix)，该比值称为这个矩阵的稠密度；与之相区别的是，如果非零元素的分布存在规律（如上三角矩阵、下三角矩阵、对角矩阵），则称该矩阵为特殊矩阵。
　　优点：稀疏矩阵的计算速度更快,因为MATLAB只对非零元素进行操作,这是稀疏矩阵的一个突出的优点。

二、稀疏矩阵的压缩存储

    参考博客：http://blog.csdn.net/zhongjiekangping/article/details/5585933

　　由于稀疏矩阵中非零元素较少，零元素较多，因此可以采用只存储非零元素的方法来进行压缩存储。
　　由于非零元素分布没有任何规律，所以在进行压缩存储的时侯需要存储非零元素值的同时还要存储非零元素在矩阵中的位置，即非零元素所在的行号和列号，也就是在存储某个元素比如aij的值的同时，还需要存储该元素所在的行号i和它的列号j，这样就构成了一个三元组(i,j,aij)的线性表。
　　三元组可以采用顺序表示方法，也可以采用链式表示方法，这样就产生了对稀疏矩阵的不同压缩存储方式。

a 稀疏矩阵的顺序实现
　　若把稀疏矩阵的三元组线性表按顺序存储结构存储，则称为稀疏矩阵的三元组顺序表。
　　顺序表中除了存储三元组外，还应该存储矩阵行数、列数和总的非零元素数目，这样才能唯一的确定一个矩阵。

　　　　

　　顺序存储结构存储三元组线性表的C#代码如下：

 struct tupletype<T>
    {
        public int i;//行号
        public int j;//列号
        public T v; //元素值
        public tupletype(int i, int j, T v)
        {
            this.i = i;
            this.j = j;
            this.v = v;
        }
    }
    class spmatrix<T>
    {
        int MAXNUM;//非零元素的最大个数
        int md;//行数值
        int nd;//列数值
        int td;//非零元素的实际个数
        tupletype<T>[] data;//存储非零元素的值及一个表示矩阵行数、列数和总的非零元素数目的特殊三元组
    }

b 稀疏矩阵的十字链表实现
　　十字链表结点分为三类 :
　　表结点，它由五个域组成，其中i和j存储的是结点所在的行和列，right和down存储的是指向十字链表中该结点所有行和列的下一个结点的指针，v用于存放元素值。
　　行头和列头结点，这类结点也有域组成，其中行和列的值均为零，没有实际意义，right和down的域用于在行方向和列方向上指向表结点，next用于指向下一个行或列的表头结点。
　　总表头结点，这类结点与表头结点的结构和形式一样，只是它的i和j存放的是矩阵的行和列数。

　　十字链表可以看作是由各个行链表和列链表共同搭建起来的一个综合链表，每个结点aij既是处在第i行链表的一个结点，同时也是处在第j列链表上的一个结点，就你是处在十字交叉路口上的一个结点一样，这就是十字链表的由来。
　　十字链表中的每一行和每一列链表都是一个循环链表，都有一个表头结点。