一维/二维数组和普通/对称/三角/三对角/稀疏矩阵的存储

文章目录

• ​​1 数组​​

• ​​1.1 一维数组​​
• ​​1.2 二维数组​​

• ​​2 矩阵​​

• ​​2.1 普通矩阵​​
• ​​2.2 特殊矩阵​​

• ​​2.2.1 对称矩阵​​

• ​​2.2.1.1 策略1​​
• ​​2.2.1.2 策略2​​

• ​​2.2.2 三角矩阵​​

• ​​2.2.2.1 上三角矩阵​​
• ​​2.2.2.2 下三角矩阵​​

• ​​2.2.3 三对角矩阵​​
• ​​2.2.4 稀疏矩阵​​

1 数组

1.1 一维数组

ElemType a[10]; //C语言中的一维数组，数据类型是ElemType

数组中的每个元素大小都相同，且存储时是连续存放的。数组元素a[i]的存放地址=Loc+i*sizeof(ElemType)，其中0≤i<10。

1.2 二维数组

ElemType b[2][4]; //C语言中2行4列的二维数组，数据类型是ElemType

上面数组的逻辑视角为：

二维数组有两种存储方式，分别是行优先存储和列优先存储，如下：

对于M行N列的二维数组​​b[M][N]​​，设二维数组b的初始地址为Loc，则：

（1）若按行优先存储，则​​b[i][j]​​的存储地址=Loc+(i*N+j)*sizeof(ElemType)。

（2）若按列优先存储，则​​b[i][j]​​的存储地址=Loc+(j*M+i)*sizeof(ElemType)。

2 矩阵

2.1 普通矩阵

下图为一个抽象的m×n阶矩阵：

可按【2.2 二维数组】一节中的二维数组存储——行优先存储和列优先存储。需要注意的是：描述矩阵元素时，行、列号通常从1开始；而描述数组时通常下标从0开始。

2.2 特殊矩阵

注意，本节及以下部分讨论的都是方阵。

2.2.1 对称矩阵

若n阶方阵中任意一个元素a_ij都有a_ij=a_ji，则该矩阵为对称矩阵。按普通的存储方式即二维数组存储就浪费存储空间了。

对称矩阵的压缩存储策略：只存储主对角线和下三角区或者主对角线和上三角区。

上图中上三角区为①，i<j；主对角线为②，i=j；下三角区为③，i>j。

2.2.1.1 策略1

存储策略：只存储主对角线+下三角区的元素，并且按行优先原则将各元素存入一维数组中，因此需要存储(1+n)*n/2个元素。存储是为了使用，因此存储方式要使得访问矩阵中的某个元素时能很快找到它。可以实现一个映射函数——将矩阵元素​​a[i][j]​​​的下标映射为一维数组b[k]的下标，其中i、j从1开始到n，k从0到(1+n)*n/2-1。因此矩阵的​​a[i][j]​​​元素对应于一维数组的：① i≥j时是​​b[i(i-1)/2+j-1]​​​；② i<j时是​​b[j(j-1)/2+i-1]​​。

2.2.1.2 策略2

存储策略：只存储主对角线+下三角区的元素，并且按列优先原则将各元素存入一维数组中，因此需要存储(1+n)*n/2个元素。存储是为了使用，因此存储方式要使得访问矩阵中的某个元素时能很快找到它。可以实现一个映射函数——将矩阵元素​​a[i][j]​​​的下标映射为一维数组b[k]的下标，其中i、j从1开始到n，k从0到(1+n)*n/2-1。因此矩阵的​​a[i][j]​​​元素对应于一维数组的：① i≥j时是​​b[(2n-j+2)(j-1)/2+i-j]​​​；② i<j时是​​b[(2n-i+2)(i-1)/2+j-i]​​。

2.2.2 三角矩阵

2.2.2.1 上三角矩阵

上三角矩阵：除了主对角线和上三角区，其余的元素都相同，如下：

存储策略：按行优先原则将两个阴影部分合成的三角形区域的元素存入一维数组中，并在最后一个位置存储常量c，因此需要存储(1+n)*n/2+1个元素。可以实现一个映射函数——将矩阵元素​​a[i][j]​​​的下标映射为一维数组b[k]的下标，其中i、j从1开始到n，k从0到(1+n)*n/2。因此矩阵的​​a[i][j]​​​元素对应于一维数组的：① i≤j时是​​b[(2n-i+2)(i-1)/2+j-i]​​​；② i<j时是​​b[(1+n)*n/2]​​。

2.2.2.2 下三角矩阵

下三角矩阵：除了主对角线和下三角区，其余的元素都相同，如下：

存储策略：按行优先原则将两个阴影部分合成的三角形区域的元素存入一维数组中，并在最后一个位置存储常量c，因此需要存储(1+n)*n/2+1个元素。可以实现一个映射函数——将矩阵元素​​a[i][j]​​​的下标映射为一维数组b[k]的下标，其中i、j从1开始到n，k从0到(1+n)*n/2。因此矩阵的​​a[i][j]​​​元素对应于一维数组的：① i≥j时是​​b[i(i-1)/2+j-1]​​​；② i<j时是​​b[(1+n)*n/2]​​。

2.2.3 三对角矩阵

三对角矩阵又称带状矩阵：当|i-j|>1时，有​​a[i][j]=0​​，其中1≤i,j≤n。

存储策略：按行优先原则，只存储带状部分，因此需要存储3n-2个元素。可以实现一个映射函数——将矩阵元素​​a[i][j]​​​的下标映射为一维数组b[k]的下标，其中i、j从1开始到n，k从0到3n-3。因此矩阵的​​a[i][j]​​​元素对应于：① |i-j|>1时是0；② |i-j|≤1时是一维数组的​​b[2i+j-3]​​。

有一个问题，若已知数组下标k，如何得到矩阵的j,j？b[k]是数组中第k+1个元素，对应于矩阵的第​​i=⌈(k+2)/3⌉​​​行第​​j=k-2i+3​​列的元素，⌈m⌉是对m向上取整。

2.2.4 稀疏矩阵

稀疏矩阵是非零元素远远少于矩阵元素的个数的矩阵，总之就是0特别多，下面是一个示例：

存储策略1：使用顺序存储三元组<行，列，值>，如下：

存储策略2：使用链式存储三元组<行，列，值>，即十字链表法，其中非零数据的结点如下：

全部结点如下：

上图中：绿色为向右域right，指向第i行的第一个元素，红色为向下域down，指向第j列的第一个元素。

END