矩阵压缩存储

矩阵压缩存储

• 特殊矩阵和稀疏矩阵

1. 特殊矩阵:矩阵中很多值相同的元素并且分布具有一定规律。

2. 稀疏矩阵:矩阵中有很多零元素。

3. 压缩矩阵的基本思想：

   (1)为多个值相同的元素只分配一个存储空间；

   (2)对零元素不分配存储空间。

一.特殊矩阵的压缩存储

1. 对称矩阵

   通过正对角线分为两个对称区域的矩阵。

对于这种对称矩阵的压缩存储，我们的主要方法就是将二维下三角矩阵转化为一维数组，所以我们要确定某一元素在一位数组中的位置。

通过公式计算出来的k值便是所找元素在一维数组中所处的位置。

对于下三角中的元素a_ij(i>=j)，在数组中下标k与i、j的关系为：k=i*(i-1)/2+j-1。

对于上三角中的元素a_ij(i<=j)，因为a_ij=a_ji，则访问和他对应的元素a_ij即可，即：k=j*(j-1)/2+i-1。

通过这个方法，我们就可以将对称的矩阵进行压缩，能节省将近一半的存储空间。

2. 三角矩阵

   上三角或下三角区域为某一常数的矩阵。

   

对于这种三角矩阵的存储，和对称矩阵的存储类似，只需要存储下三角所有元素和某一个元素。

下三角矩阵中某一元素**a_ij**在数组中的下标k与i、j的对应关系：

​ 当i>=j：k=i*(i-1)/2+j-i 当i<=j：n*(n+1)/2

3. 三对角矩阵

   所有非零元素都集中在以主对角线为中心的带状区域中，除了主对角线和它的上下方若干条对角线的元素外，所有其他元素都为零。

   

   对于三对角矩阵，除了对角线有值的元素需要存储，剩下的0可以省略

   

   首先我们要认识到,矩阵下标是从1开始的,而数组下标是从0开始的.该矩阵中，除第一行只有两个元素外，其余的i-2行都有三个元素，所以前i-1行非0元素的个数为：3（i-1）-1；第i行的三个元素下标可以通过j-i确定，可以得出第i行中非0元素的个数为j-i+1。

   所以：k=3（i-1）-1+j-i+1 = 2i+j-3

   4. 稀疏矩阵

   矩阵中非零元素的个数过低（有的说是低于5%，有的说是低于30%）称为稀疏矩阵。

   

4.3.1 三元组

​ 将稀疏矩阵的非零元素对应的三元组所构成的集合，按行优先的顺序排列成一个线性表。

​ 将上图排列为一个三元组表：((1,1,15),(2,2,11),(3,4,6),(5,1,9)).即：（i，j，a_ij）.

row为行,col为列,item为该行该列的元素值.

const int MAX = 100;

struct Triple {
    int row, col; //行号,列号
    int item; //非零元素值.
};

struct sparseMatrix {
    struct Triple data[MAX]; //存储非零元素
    int mu, nu, num; //行数,列数,非零元素个数
};

4.2 十字链表

​ 通过链表,将矩阵的每一行用一个带头结点的链表表示,每一列也用一个带头结点的链表表示.每个元素结点有五个量,分别为: 行数,列数,值,指向下方结点的指针,指向右方结点的指针.

typedef struct Node {
    int i,j;//非零元素的行标和列表
    int data;
    struct Node* right;
    struct Node* down;//指向右方和下方结点的指针
}Node;
typedef struct hNode {
    struct hNode *rhead;
    struct hNode *chode;//指向两头结点数组的指针
    int r,c,k;//矩阵的行数,列数,及非零元素的个数
}hNOde;

图源来自: 懒猫