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

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

一、数组的定义

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

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

二、二维数组的存储方式

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

2.1 按行优先

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

L o c a [ i ] [ j ] = L o c a [ 0 ] [ 0 ] + [ i × n + j ] × L Loc_{a[i][j]} = Loc_{a[0][0]} + [i\times n + j] \times L Loca[i][j]​=Loca[0][0]​+[i×n+j]×L

2.2 按列优先

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

L o c a [ i ] [ j ] = L o c a [ 0 ] [ 0 ] + [ j × n + i ] × L Loc_{a[i][j]} = Loc_{a[0][0]} + [j\times n + i] \times L Loca[i][j]​=Loca[0][0]​+[j×n+i]×L

三、特殊矩阵和压缩矩阵 3.1 特殊矩阵

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

3.1.1 对称矩阵

如果对于一个二维矩阵而言，其中所有单位元素满足： a [ i ] [ j ] = a [ j ] [ i ] ( 1 < = i , j < = n ) a[i][j] = a[j][i] (1{a,b,c}}