数据结构之多维数组及特殊矩阵的压缩存储

发表于 | 分类于

基本知识

多维数组可以认为是线性表的一种推广，其元素本身可以是具有某种结构的数据，但必须是同种元素。数组在实际存储时采取的顺序存储，因此数组可以以$O(1)$的时间复杂度进行访问。对于一维数组，其元素内存地址可通过起始地址+偏移地址的方式直接计算得到；而对于多维数组，根据存储方式的不同，计算元素地址的方式也有细微的差别。目前存储方式主要有：

  • 行优先存储：即每行存放完后再存放下一行
  • 列优先存储：即一列一列地分配

假设有一$m*n$二维数组定义为$A_{m,n}$，每个元素的大小为$d$个字节，数组任意元素$A_{i,j}$的地址为（下标从$1$开始）：

  • 按行优先存储：$LOC(A_{i,j}) = LOC(A_{1,1})+((i-1)*n+j-1)*d$
  • 按列优先存储：$LOC(A_{i,j}) = LOC(A_{1,1}) + ((j-1)*m + i-1)*d$

特殊矩阵

由于矩阵本身结构就是二维的，因此采用二维数组存储矩阵是非常合理的，但是有一类矩阵其有效元素数量占整个矩阵元素数量比重不大，因此从节约空间的角度，希望通过压缩存储无效元素（一般为$0$）的方式来存储该矩阵。先简要介绍几种特殊矩阵以及其压缩方法。

对称矩阵

对称矩阵是指元素值关于对角线对称，即$A^T=A$，由于有一半左右的元素是相同，因此可采用只保存上半部分或者下半部分元素的方式将对称矩阵存入特别设计的一维数组，同时给出元素访问映射公式。

注：详细对称矩阵定义见：对称矩阵

以存储对称矩阵的下半部分且以行优先存储方式为例分析映射公式。（矩阵为n阶方阵，数组下标从0开始，矩阵下标从1开始）

在第一行需要存储的元素个数为$1$，第二行为$2$，依次类推总共需要存储$1+2+3….+n=(n+1)*n/2$个元素，因此数组元素的大小可定义为$(n+1)*n/2$。而对于位置为$A_{i,j}$的元素，我们分两种情况分析：

  • 第一种情况：$i>=j$，此时元素在下半部分，在该元素前面的元素个数有$Before=1+2+….+(i-1)+j-1$个，因此该元素的位置为第$Before+1=(i-1)*i/2+j$个，考虑到下标从$0$开始，则$A_{i,j}$在数组中的下标为$k=(i-1)*i/2+j-1$
  • 第二种情况：$i<j$，此时元素在上半部分，其值和$A_{i,j}$相等，根据上一步分析有数组下标$k=(j-1)*j/2+i-1$

合并上述两种情况即可得出统一的下标计算公式

$k=(max(i,j)-1)*max(i,j)/2+min(i,j)-1$

注：$max(i,j)$表示$i、j$中较大的一个，$min(i,j)$表示$i、j$中较小的一个。

三角矩阵

三角矩阵分为上三角矩阵以及下三角矩阵，其存储模式思想和对称矩阵类似，不过有大约一半（不算对角线）元素值相等，因此可以使用比对称矩阵存储个数$+1$的数组来存放整个矩阵。

注：详细三角矩阵定义见：三角矩阵

对于的一个元素用来存放相同的那个元素。下三角矩阵的分析过程和对称矩阵相似，以下为结论：

注：矩阵为n阶方阵，数组下标从$0$开始，矩阵下标从$1$开始，行优先存储

对于$i>=j$，下标$k=k=(i-1)*i/2+j-1；i<j$，下标$k=(n+1)*n/2$

对于上三角矩阵，分为两种情况讨论，

  • 第一种情况：$i<=j$，此时元素在上半部分，在该元素前面共有$Before=n+n-1+….+(n-(i-1)+1)+j-i$个元素，因此该元素的位置为第$Before+1=(2n-i+1)*(i-1)/2+j-i+1$个，考虑到下标从$0$开始，则$A_{i,j}$在数组中的下标为$k=(n+i-1)*(i-1)/2+j-i$。
  • 第二种情况：$i>j$，此时元素在下半部分，元素值相同，全部存到数组最后一个元素中，因此下标$k=(n+1)*n/2$

对角矩阵

对角矩阵也称为带状矩阵，其对角带（以对角线为中心的带状区域内）元素非零，其余元素全部为零。对于$k$（$k$为奇数）对角矩阵，当$|i-j|<=k/2$时，元素为带内元素，否则元素值为$0$。由此可根据每行元素数量求取元素位置。比如三对角矩阵，只有第一行和最后一行非零元素个数为$2$，其余非零元素为$3$。我们可以使用部分冗余，使得每一行数量均为$3$个，这样可以极大减少计算复杂度。以下推导三对角矩阵的压缩存储。

由于第一行第前面和最后一行后面分别补一个零凑足$3$个元素，因此对于每一行其前面一共存储$3*(i-1)$个元素。而每行的第一个元素下标为$A_{i,i-1}$，因此对于第$A_{i,j}$元素在一维数组中的下标为$k=3*(i-1)+j-(i-1)=2*i+j-2$。其中第一个元素为$0$。

注：详细对角矩阵定义见：对角矩阵

稀疏矩阵

稀疏矩阵是元素大部分为零的矩阵，其有效元素的个数非常稀少，因此如果重复存储零元素是非常不合理的，目前常用来存储稀疏矩阵的数据结构为三元组和十字链表，三元组基本定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#define MAXSIZE 1000

//以下为三元组的定义
template <typename DataType>
struct TripleNode
{
	int i; //行下标
	int j; //列下标
	DataType element; //实际元素值
};

//以下为稀疏矩阵存储结构定义
template <typename DataType>
struct SparseMatrix
{
	int mu; //矩阵行数
	int nu; //矩阵列数
	int tu; //矩阵非零个数
	TripleNode<DataType> matrix[MAXSIZE]; //TripleNode数组
};

稀疏矩阵在按行优先存储时遵循一下规则

  • 同一行内非零元素依次放置
  • 一行元素放完再放第二行元素

注：详细稀疏矩阵定义见：稀疏矩阵