特殊矩阵的压缩存储

1 数组的存储结构

1.1 一维数组

• 各数组元素大小相同，且物理上连续存放。
• 第i个元素的地址位置是：a[i] = LOC + i*sizeof(ElemType) (LOC为起始地址)

1.2 二维数组

对于多维数组有行优先、列优先的存储方法

1. 行优先：先行后列，先存储行号小的对于一个M行N列的二维数组来说：LOC(ai,j) = LOC + (i*N+j)*sizeof(ElemType)
2. 列优先：先列后行
   LOC(ai,j) = LOC + （j*M + i）*sizeof(ElemType)

2 特殊矩阵

2.1 对称矩阵

1. 只存储主对角线以及下三角区
   按照行优先原则将各元素存入一维数组中。
   问题1：该一维数组的大小是多少？
   （1+n）n/2
   问题2：如何将一维数组下标与矩阵下标对应上?
   
   aij是第几个元素？i(1+i)/2 + j
   则k======>i(1+i)/2 + j-1
   2.列存储
   

2.2 三角矩阵

2.3 三对角矩阵

2.4 稀疏矩阵

(1) 存储策略1：顺序存储

(2) 存储策略2：链式存储–十字链表法