（二十六）数据结构-数组

一、数组

数组是由n（>=1）个相同类型的数据元素构成的有限序列

1.1一维数组的存储结构

1.2二维数组的存储结构

使用行优先存储：用行号乘，在加上列号

使用列优先存储

二、特殊矩阵的压缩存储

方法：找出特殊矩阵中值相同的矩阵元素分布的规律，把那些呈现规律性分布的、值相同的多个矩阵元素压缩到一个存储空间中

2.1对称矩阵

思路：由于对称矩阵的性质是上三角区和下三角区域所有元素都相同，那么我们可以只存放上三角或者下三角

1. 例如，我们想要知道aij前面元素的个数的求法：
2. 采用行存储，我们可以知道i前面有1、2、…i-1行元素，通过通项公式：i(i-1)/2
3. 还需算出列j，想象一下a23，对应的3是列，代表a23在第二行是第3个元素
4. 则aij，直接+j
5. 由于aij=aji，那么直接把ij互换即可
   

2.2三角矩阵

下三角存储

我们只需要存储下半部分在加上0即可

i>=j为下三角，i

上三角存储

2.3三对角矩阵