数组

数组的定义

在数据结构中，数组是一个由n（n大于等于1）个相同数据类型数据元素组成的有限序列，本质上是一种受限的线性表，数组在定义的时候，大小就被确定了，所以数组除了初始化和销毁，就只有修改和存取操作

数组的存储结构

数组在内存上是一段连续的存储空间

在存储方式上又可以划分为按行优先和按列优先

比如用二维数组来存储一个2*2的矩阵

0 1

2 3

按行优先

0 1 2 3

按列优先

0 2 1 3

矩阵的压缩存储

压缩存储：目的为了节省空间，多个相同值只分配一个存储空间，零不分配空间

特殊矩阵：有许多相同元素的矩阵，比如对称矩阵，上（下）三角矩阵，对角矩阵

对称矩阵

对称矩阵的上三角和下三角存储数据是一样的，如果用二维数组存放，就会浪费部分空间，所以可以考虑只存储一部分数据（上三角，或下三角）

以三阶矩阵为例

用二维数组表示的存储情况

[[a(1,1),a(1,2),a(1,3)],[a(2,1),a(2,2),a(2,3)],[a(3,1),a(3,2),a(3,3)]]

除了主对角线以外，a(i,j)与a(j,i)存储的数据是相同的，就没有必要再存一次

用一维数组表示的存储情况（下三角）

[a(1,1),a(2,1),a(2,2),a(3,1),a(3,2),a(3,3)]

那么如何确定数组下标k和三阶矩阵的对应关系呢

1.先判断存储的是上下三角区域还是下三角，

2.把数组还原成矩阵时候，判断还原矩阵元素位置，如果i<j则在上三角地区，到矩阵对应的下三角去找

3.确定数组下标k和i，j对应关系

k=i(i-1)/2+j-i i大于等于j (下三角和主对角线)

k=j(j-1)/2+i-i i小于j (上三角)

三角矩阵

还是以下三角矩阵为例，下三角区域需要存储，上三角为同一常量，就可以把这一常量存储在数组最后

k=i(i-1)/2+j-i i大于等于j (下三角和主对角线)

k=n(n+1)/2 i小于j (上三角)n为矩阵行数

上三角类推

k=(i-1)(2n-i+2)/2+j-i i小于等于j (上三角和主对角线)

k=n(n+1)/2 i大于j (下三角)n为矩阵行数

稀疏矩阵

矩阵中非0的个数相对于0的个数比较少的叫稀疏矩阵，这个时候就可以直接记录非零元素的i，j值，用三元组来存储

比如有一个如下矩阵

就可以用三元组（行标，列表，值）表示

i	j	v
0	0	0
1	1	1
2	2	2

稀疏矩阵经过压缩后就失去了随机存储的特性