数据结构之数组

第五章数组

第一节数组的概念

1.数据概念

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

2.数组的实现

​ 以一维数组A[0…n-1]为例，其存储结构关系式为
$$
LOC(a_i) = LOC(a_0)+i*L\quad\quad (0≤i<n)
$$
​ 其中，L时每个数组元素所占的存储单元

第二节特殊矩阵和稀疏矩阵的压缩存储

1.特殊矩阵的压缩存储

（1）对称矩阵（1，0）

$$
k=
\begin{cases}
i(i-1)/2+j-1,\quad\quad i≥j（下三角区和主对角线元素）\\
j(j-1)/2+i-1,\quad\quad i<j（上三角区元素a_{ij} = a_{ji}）
\end{cases}
$$

（2）三角矩阵（1，0）

下三角矩阵
$$
k=
\begin{cases}
i(i-1)/2+j-1,\quad\quad i≥j（下三角区和主对角线元素）\\
n(n+1)/2,\quad\quad~~~~~~~~~~~ i<j（上三角区元素）
\end{cases}
$$
上三角矩阵
$$
k=
\begin{cases}
(i-1)(2n-i+2)/2+(j-i),\quad\quad i≤j（上三角区和主对角线元素）\\
n(n+1)/2,\quad\quad~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ i>j（下三角区元素）
\end{cases}
$$

（3）三对角矩阵（1，0）

$$
k = 2i+j-3
$$

2.稀疏矩阵的压缩存储

稀疏矩阵压缩存储后便失去了随机存取特性
$$
M=\left[
\matrix{
4 & 0 & 0 & 0\
0 & 0 & 6 & 0\
0 & 9 & 0 & 0\
0 & 23 & 0 & 0\
}
\right]
$$
对应三元组

i	j	v
0	0	4
1	2	6
2	1	9
3	1	23