特殊矩阵的压缩存储

• 数组与线性表的关系
• 数组的存储结构
• • 一维数组**A[0……n-1]**
  • 二维数组
  • • 按行优先：先行后列
    • 按列优先：先列后行
• 矩阵的压缩存储
• • 对称矩阵、
  • • 策略一
  • 三角矩阵
  • • 下三角矩阵
    • • 上三角矩阵
  • 三对角矩阵

数组与线性表的关系

数组是线性表的推广。一维数组可以视为一个线性表；二维数组也可以视为其元素定长的线性表。
数组一旦定义，其维数和维界(下标取值范围)就不可再改变。

数组的存储结构

一维数组A[0……n-1]

LOC(a_i)=LOC(a₀)+i*L (0 ≤ i＜n)→<下标默认从0开始>

LOC(a_i)=LOC(a₁)+(i-1)*L (1 ≤ i ≤ n)→<下标从1开始>

二维数组

按行优先：先行后列

行下标：[0,h₁]，列下标：[0,h₂]
LOC(a_i,_j)=LOC(a₀,₀)+[i*(h₂+1)+j]*L

i*(h₂+1)+j→前面有i行，每列h₂个元素，共i*h₂个元素。再加上第i+1行前面的j个元素。

按列优先：先列后行

行下标：[0,h₁]，列下标：[0,h₂]
LOC(a_i,_j)=LOC(a₀,₀)+[j*(h₁+1)+i]*L

i*(h₂+1)+j→前面有i行，每列h₂个元素，共i*h₂个元素。再加上第i+1行前面的j个元素。

矩阵的压缩存储

描述矩阵时行、列号通常从1开始

对称矩阵、

压缩策略：

1. 只存主对角线+下三角区
2. 只存主对角线+上三角区

策略一

1. 只存储主对角线+下三角区
2. 按行优先原则将各元素存入一维数组

一维数组大小：n/2+n*n/2 = (1+n)*n/2


key：
a_ij在一维数组中的映射

1. 当i>=j时,元素处于下三角区
   第 1+2+3+…+(i-1)+j = (i-1)*i/2+j 个元素
   一维数组下标k = (i-1)*i/2+j -1
2. 当i<j时,元素处于上三角区
   一维数组下标k = (j-1)*j/2+i -1

三角矩阵

下三角矩阵

压缩策略：
按行优先原则将橙色区元素存入一维数组中。并在最后一个位置存储常量c

key:

1. 一维数组长长度：n*(n+1)/2+1
2. 当i>=j时，元素处于下三角区：
   一维数组中的第 1+2+…+(i-1)+j = (i-1)*i/2个
   一维数组下标：(i-1)*i/2+j-1
3. 当i<j时，位于上三角区：
   一维数组下标：n(n-1)/2

上三角矩阵

a_ij

1. 当i<=j,上三角区域：
   一维数组下标：n+(n-1)+…+(n-(i-1-1))+(j-i) = n+(n-1)+…+(n-i+2)+(j-i) =(2n-i-2)(i-1)+(j-i)
2. 当i>j，下三角区域：
   一维数组下标：n(n+1)/2

三对角矩阵

三对角矩阵，又叫带状矩阵

1. 当|i-j|>1时，有a_ij=0
2. 压缩策略：
   按行优先(或列有限)只存取带状部分
3. 数组长度：3n-2
   

key:
1、**a_ij**是第几个元素？

前 (i-1) 行一共 3*(i-1)-1个元素
**a_ij是第i行第j-i+2个元素
→a_ij*是3(i-1)-1+(j-i+2)=2i+j-2个元素
数组下标：2i+j-3