【计算机考研（408）- 数据结构】数组和特殊矩阵

数组和特殊矩阵

数组

数组的定义

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

数组是[[线性表]]的推广，一维数组可视为一个线性表，二维数组可视为其元素是定长数组的线性表。

数组的存储结构

各数组元素大小相同，且物理上连续存放。

我们用一个 Markdown 表格模拟数组的地址存储结构（ElemType a[7]）：

其他 a[0] a[1] a[2] a[3] a[4] a[5] a[6] 其他 LOC LOC+1 … … … … … …

$$数组元素a[i]的存放地址=LOC+i\ast sizeof(ElemType)$$

每个单元格表示数组元素在内存中的连续存储位置，数组元素之间没有间隔，便于通过下标快速访问。

接下来假设有一个二维数组() ElemType b[2][4]，我们可以用一个 Markdown 表格模拟其地址存储结构和逻辑结构：

逻辑结构：

b[0][0] b[0][1] b[0][2] b[0][3] b[1][0] b[1][1] b[1][2] b[1][3]

但是在内存中，数组是连续的，那么也就有了行优先和列优先的存储方式。

列优先存储结构：

其他 b[0][0] b[1][0] b[0][1] b[1][1] b[0][2] b[1][2] b[0][3] b[1][3] 其他 … LOC+0 LOC+1 LOC+2 LOC+3 LOC+4 LOC+5 LOC+6 LOC+7 …

M行N列的二维数组b[M][N]中，若按列优先存储，则：

$$b[i][j]的存放地址=LOC+(j\ast M+i)\ast sizeof(ElemType)$$

行优先存储结构：

其他 b[0][0] b[0][1] b[0][2] b[0][3] b[1][0] b[1][1] b[1][2] b[1][3] 其他 … LOC+0 LOC+1 LOC+2 LOC+3 LOC+4 LOC+5 LOC+6 LOC+7 …

M行N列的二维数组b[M][N]中，若按行优先存储，则：

$$b[i][j]的存放地址=LOC+(i\ast N+j)\ast sizeof(ElemType)$$

矩阵的存储和特殊矩阵的压缩存储

压缩存储是指为多个值相同的元素只分配一个存储空间，对零元素不分配空间。
特殊矩阵就是指分布有一定规律的矩阵。
压缩存储方法：找出分布规律，把那些呈现规律性分布的、值相同的元素放在同一个存储空间中。

对称矩阵

a1,1a_{1,1}a1,1​ a1,2a_{1,2}a1,2​ $\cdots$ a1,na_{1,n}a1,n​ a2,1a_{2,1}a2,1​ a2,2a_{2,2}a2,2​ $\cdots$ a2,na_{2,n}a2,n​ $⋮$ $⋮$ $\ddots$ $⋮$ an,1a_{n,1}an,1​ an,2a_{n,2}an,2​ $\cdots$ an,na_{n,n}an,n​

如上所示的矩阵是一个n阶矩阵，若对于任意的$i,j$，都有ai,j=aj,ia_{i,j}=a_{j,i}ai,j​=aj,i​，则称之为对称矩阵。其中的元素也可以根据i,j的大小分为三个部门:$i=j$主对角线，$i>j$ 下三角区，$i<j$ 上三角区。

普通存储：n*n二维数组，因为上下两个三角区数值相同，所以可以压缩存储。

压缩存储策略：只存储主对角线+下三角区（或主对角线+上三角区）

同时我们需要按照行/列优先的原则存入到一个一维数组中，并建立i,j（矩阵下标）与数组下标的映射关系。

以下以行优先为例：

对于i>=j的下标来说，第一个存储的是 i=1,j=1，第二个存储的是 i=2,j=1，接着 2,2、3,1、3,2、3,3。分别映射到了0,1,2,3上面。

根据不难看出，对于i是累加的，比如第一行起始是0，第二行起始是1，到了第三行起始就变为了3。那么其实他就是一个等差数列。

根据等差数列求和公式：n(a1+an)2\\frac{n(a_1 + a_n)}{2}2n(a1​+an​)​