考研数据结构与算法（五）数组

一、数组的定义

数组是由 $n(n>=1)$ 个相同类型的数据元素构成的有限序列，每个数据元素称为一个数组元素，每个元素在 $n$ 个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界

数组和线性表的关系：数组是 线性表的推广 。一维数组可视为一个线性表；二维数组可视为其元素也是定长线性表的线性表，以此类推。数组一旦被定义，其维数和维界就不再改变。因此，除结构的初始化和销毁外，数组只会有存取元素和修改元素的操作。

二、二维数组的存储方式

对于数组而言占用的内存是一个连续的空间，那么在二维数组或者是多维数组的情况，对于地址映射的方式大题分为两种：

2.1 按行优先

顾名思义，我们元素地址是一行一行的填充，那么假设当前的二维数组是一个 $N\times N$ 的结构（下标从0开始），每一个元素占用 $L$ 的空间，那么假设我们要求 $a[i][j]$ 的地址的话：

$Lo{c}_{a[i][j]}=Lo{c}_{a[0][0]}+[i\times n+j]\times L$

2.2 按列优先

这样的话我们是一列一列的填充，那么和上面的假设一样的话，要想求 $a[i][j]$ 的地址，则需要小小的变化：

$Lo{c}_{a[i][j]}=Lo{c}_{a[0][0]}+[j\times n+i]\times L$

三、特殊矩阵和压缩矩阵

3.1 特殊矩阵

一个二维矩阵可以根据主对角线分为上三角区和下三角区：

3.1.1 对称矩阵

如果对于一个二维矩阵而言，其中所有单位元素满足：$a[i][j]=a[j][i](1<=i,j<=n)$ 那么就称其为对称矩阵，顾名思义就是沿着对角线对称，如下图所示

由于存在这样的结构，那么我们可以发现空间是重复了，为了提高空间利用率，我们将这个二维数组压缩到一个一维数组里面，那么我们其实可以发现我们只需要保存上三角区或者下三角区的数据就能完整的恢复整个矩阵的数据，这样的话我们就节约了近一半的空间，于是我们将元素 $a[i][j]$ 存放到一位数组 $b[k]$ 的位置，那么 $k$ 和 $i、j$ 的关系为（这里的 $i、j$ 从 $1$ 开始，而 $k$ 从 0开始）：
k = { i ( i − 1 ) 2 + j − 1 , i>=j，下三角区 j ( j − 1 ) 2 + i − 1 , i

{i(i−1)2+j−1,i>=j，下三角区j(j−1)2+i−1,i<j，上三角区" role="presentation">{i(i−1)2+j−1,j(j−1)2+i−1,i>=j，下三角区i，上三角区