矩阵压缩存储

矩阵压缩存储 特殊矩阵和稀疏矩阵

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

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

压缩矩阵的基本思想：

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

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

一.特殊矩阵的压缩存储 对称矩阵

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

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

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

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

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

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

三角矩阵

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

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

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

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

三对角矩阵

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

对于三对角矩阵，除了对角线有值的元素需要存储，剩下的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

稀疏矩阵

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

4.3.1 三元组

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

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

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;

图源来自: 懒猫