数据结构第6问：什么是数组？

数组

数组（Array） 是由 一组类型相同的元素 按 连续的存储空间 排列组成的数据结构，通过数组名和下标（索引）来访问其中的元素。

具体来说：

• 数组中的元素类型必须相同，比如都是整数、都是字符或者都是浮点数。
• 数组的元素在内存中连续存储，这保证了通过索引能够快速访问任意元素。
• 数组大小在定义时通常是固定的（静态数组），确定了元素个数。
• 访问数组元素时，通过数组名加索引来访问，例如：a[0] 表示数组的第一个元素（一般数组下标从0开始）。

一维数组的存储结构

$$LOC(a_i)=LOC(a_0)+i\times L,(0\le i＜n)$$

• LOC(a_i) ：表示数组中第 i 个元素 a_i 的内存地址。
• LOC(a_0) ：表示数组中第0个元素（即第一个元素） a_0 的内存地址。
• i ：表示元素的下标（索引），从0开始。
• L ：表示数组中每个元素所占的内存大小（单位字节数），例如 int 类型一般占4字节。

二维数组的存储结构

行优先

行优先存储即先存储行号较小的元素，行号相等的则按照列号顺序存储。

// 举例：
int A[2][3];
// 按矩阵排列为：
A[0][0], A[0][1], A[0][2]
A[1][0], A[1][1], A[1][2]
// 行优先存储顺序为：
A[0][0], A[0][1], A[0][2]，A[1][0], A[1][1], A[1][2]

假设一个二维数组的行下标范围为[0, h₁]，列下标范围为[0, h₂]。

则对于行优先的存储结构关系式为：（L是指数组中每个元素所占的内存大小）
$$LOC(a_{i,j})=LOC(a_{0,0})+[i\ast (h_2+1)+j]\times L$$

列优先

列优先存储即先存储列号较小的元素，列号相等的则按照行号顺序存储。

// 举例：
int A[2][3];
// 按矩阵排列为：
A[0][0], A[0][1], A[0][2]
A[1][0], A[1][1], A[1][2]
// 列优先存储顺序为：
A[0][0], A[1][0], A[0][1]，A[1][1], A[0][2], A[1][2]

假设一个二维数组的行下标范围为[0, h₁]，列下标范围为[0, h₂]。

则对于行优先的存储结构关系式为：（L是指数组中每个元素所占的内存大小）
$$LOC(a_{i,j})=LOC(a_{0,0})+[j\ast (h_1+1)+i]\times L$$

特殊矩阵的压缩存储

压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配空间。

特殊矩阵：指在矩阵中具有很多相同的矩阵元素或者有很多的零元素，并且它们在分布上有一定的规律的一种矩阵。

对特殊矩阵的压缩存储方法：找规律，把呈现规律性分布且值相同的矩阵元素压缩存储到同一个存储空间中。

对称矩阵

$$\begin{gathered} 设有一个n\times n的矩阵A=[a_{ij}],如果对任意的i,j(行列索引)都有: \\ {a}_{i,j}=a_{j,i} \\ 那么A就是一个对称矩阵 \end{gathered}$$

1. 主对角线（Main diagonal）

• 位于矩阵从左上角到右下角的对角线，元素下标满足 i=j，即矩阵中所有 aᵢᵢ 元素组成的线。
• 例如，对于一个 n×n矩阵 A=[aᵢᵢ]，主对角线元素是： a₁₁, a₂₂, …, aₙₙ

2. 上三角区（Upper triangular part）

• 指主对角线以上（包括主对角线）所有元素组成的区域，满足下标条件 j≥i，即列号大于等于行号的元素。
• 这些元素包括：主对角线元素和其上方的元素。

3. 下三角区（Lower triangular part）

• 指主对角线以下（包括主对角线）所有元素组成的区域，满足下标条件 i≥j ，即行号大于等于列号的元素。
• 这些元素包括：主对角线元素和其下方的元素。

由于上三角区的所有元素和下三角区的对应元素是相同的，那么在存储的时候，就可以用数组 Bₖ 仅存储上三角区或下三角区域的元素。这样存储后，对称矩阵的元素个数由 n² 减少为 n(n+2)/2 。因为主对角线和三角区域共有这么多元素。

举例说明：

假设存储下三角区，元素顺序可以按行或按列依次存储：

• 按行存储下三角区元素示意（n=3） ：
  • B = [a₁₁, a₂₁, a₂₂, a₃₁, a₃₂, a₃₃]
• 使用时：访问 aᵢⱼ 时，如果 i≤j，直接从 B 中对应位置取值；如果 i>j，则用对称性取 aⱼᵢ

公式推导：

矩阵元素 aᵢⱼ 中满足 i≥j 的元素按行依次存入一维数组 B

• 第1行存1个元素：a₁₁
• 第2行存2个元素：a₂₁, a₂₂
• 第3行存3个元素：a₃₁, a₃₂, a₃₃
• …
• 第 i 行存 i 个元素： aᵢ₁, aᵢ₂, aᵢ₃, … , aᵢᵢ

定位元素 aᵢⱼ 在一维数组 B 中的下标 k

• k 表示aᵢⱼ 在 B 数组中的位置，数组下标从0开始。

• 若 i≥j（即属于下三角区或主对角线），则：k = 第 i 行之前元素数 + 第 i 行 j 列前面的元素数。

• 第1行之前元素数：
  $$1+2+\cdots +(i-1)=(i-1)i/2$$

• 第 i 行中第 j 个元素前面有 j−1个元素，因此：
  $$k=i(i-1)/2+(j-1)$$

对于上三角区的元素

• 如果 i<j，那么元素 aᵢⱼ 就是上三角区的元素

• 通过对称性，aᵢⱼ = aⱼᵢ，而 j>i 意味着 aⱼᵢ 是下三角区的元素

• 所以，我们先将行列互换，定位到下三角区元素aⱼᵢ
  $$k=j(j-1)/2+(i-1)$$
  这个就是上三角区元素的 k 值计算公式了。

综合 k 计算公式如下：
$$k=\{\begin{array}{ll}\frac{i(i-1)}{2}+(j-1),& i\ge j(\text{元素在下三角区或主对角线})\\ \frac{j(j-1)}{2}+(i-1),& i<j(\text{元素在上三角区，利用对称性变换})\end{array}$$

三角矩阵

三角矩阵是指矩阵中元素在主对角线的一侧（不含另一侧）均为零的矩阵。

注意：由于这里研究的是三角矩阵压缩存储在一个数组中的问题，所以三角矩阵对角一侧可以为一个常数，这并不影响三角矩阵在数组中的存储结构。

需要存储的元素个数 = 一侧三角矩阵的个数 + 1个用于存储常数的元素，即：
$$\begin{gathered} 存储元素总个数=n(n+1)/2+1 \\ 注意：常数项存放位置在数组中的下标为:n(n+1)/2 \end{gathered}$$

下三角矩阵

矩阵中位于主对角线上方（即行号小于列号的位置） 的元素全部等于零。
$$k=\{\begin{array}{ll}\frac{i(i-1)}{2}+(j-1),& i\ge j(\text{下三角区元素和主对角线元素})\\ \frac{n(n+1)}{2},& i<j(\text{上三角区元素})\end{array}$$
该公式推导过程和对称矩阵的推导过程基本一致，唯一有区别的是：由于上三角区元素都是相同的常数，所以再给一个存储单元来存储这个常数。

上三角矩阵

矩阵中位于主对角线下方（即行号大于列号的位置） 的元素全部等于零。

公式推导：

①元素个数及分布

上三角包含对角线的元素共有：n(n+1)/2 个元素（包括所有满足 i≤j 的位置）。

②按行存储的思想：

​ 在数组 BB 中按行顺序存储每一行的上三角元素：

• 第 1 行有元素 n 个：a[1,1], a[1,2], … , a[1,n]
• 第 2 行有元素 n−1 个：a[2,2], a[2,3], … , a[2,n]
• 第 i 行有元素 n−i+1 个：a[i,i], a[i,i+1], … , a[i,n]
• …
• 第 n 行有元素 1 个：a[n,n]

③下标 k 的推导：

设所有元素的下标从 0 开始计数，到第 i 行元素前面，一共有多少元素？

第 1 行元素数： n
第 2 行元素数： n−1
第 3 行元素数： n−2
…
第 i−1 行元素数： n−(i−1)+1=n−i+2

那么，到第 i 行开始前的元素总数为：

n+(n−1)+⋯+(n−i+2)n+(n−1)+⋯+(n−i+2)

这是一个等差数列求和，首项 a[1]=n，末项为 a[i−1]=n−i+2，项数为 i−1，和为：
$$S=\frac{(a_1+a_{i-1})\times (i-1)}{2}=\frac{(n+(n-i+2))\times (i-1)}{2}=\frac{(2n-i+2)(i-1)}{2}$$
④行内元素偏移：

第 i 行对应元素 a[i,j] 在这一行中，因为这一行子序列从 a[i,i] 开始的，所有位置偏移为：j−i

⑤结合得对应一维数组下标 k：

将行前元素数和行内偏移相加（若下标从0开始）：
$$k=\{\begin{array}{ll}\frac{(2n-i+2)(i-1)}{2}+(j-i),& i\le j(\text{上三角区元素和主对角线元素})\\ \frac{n(n+1)}{2},& i>j(\text{下三角区元素})\end{array}$$

三对角矩阵

定义：对于n阶矩阵A中的任意一个元素aᵢⱼ，当 |i-j|>1 时，若有aᵢⱼ = 0，（i≥1，j≤n），则称为三对角矩阵。在三对角矩阵中，所有非零元素都集中在以主对角线为中心的3条对角线的区域，其它区域的元素都为零。非零元素个数为 3n−2。

三对角矩阵的压缩存储方式为：将3条对角线上的元素按行优先方式存放在一个一维数组中。

举例说明：
$$A=\left[\begin{array}{cccccc}{a}_{1,1}& a_{1,2}& 0& \cdots & 0& 0\\ a_{2,1}& b_{2,2}& c_{2,3}& \ddots & & ⋮\\ 0& a_{3,2}& a_{3,3}& a_{3,4}& \ddots & 0\\ ⋮& \ddots & \ddots & \ddots & \ddots & 0\\ 0& & \ddots & a_{n-1,n-2}& a_{n-1,n-1}& a_{n-1,n}\\ 0& 0& \cdots & 0& a_{n,n-1}& a_{n,n}\end{array}\right]$$
压缩存储形式为：

三对角矩阵的3条对角线上的元素 aᵢⱼ 在数组中存放的下标为 k = 2i + j - 3。其中 i，j 是矩阵元素的行列索引，且满足 1≤i，j≤n，且 ∣i−j∣≤1。

公式推导

①三对角矩阵 A=[aᵢⱼ] 满足：∣i−j∣≤1

即非零元素仅存在于：

• 主对角线：j=i
• 下邻对角线：j=i−1
• 上邻对角线：j=i+1

其他元素为零，不需要存储。

②第 i 行存储的元素个数

• 第1行： 主对角线和上邻对角线 → 2个元素（a[1,1]，a[1,2]）
• 第 i 行（2 ≤ i ≤ n−1）：3个元素（a[i,i−1]， a[i,i]， a[i,i+1]）
• 第n行：主对角线和下邻对角线 → 2个元素（a[n,n−1]，a[n,n]）

③计算第 i 行前面所有元素数

先计算第 i 行之前存了多少个元素。

• 第1行：2个元素
• 行2至第 i−1 行，每行3个元素（假设 i≥2）

那么第 i 行之前共存储元素数为：
$$S_i=2+3\times (i-2)=3i-4$$
④计算元素下标 k

在第 ii 行，元素顺序是：
$$a_{i,i-1}{a}_{i,i}{a}_{i,i+1}$$
这三个元素在数组中连续，占用下标：
$$S_i{S}_{i+1}{S}_{i+2}$$
已知 Si=3i−4，令 p 表示该元素在该行中的位置编号：

• 若 j=i−1，则 p=0，（注意：这里可以得到：p = j - i + 1）
• 若 j=i，则 p=1
• 若 j=i+1，则 p=2

那么
$$k=S_i+p=3i-4+p$$
将 p 用 i,j 表达得到：
$$k=3i-4+j-i+1=2i+j-3$$

数组下标反推元素在矩阵中的位置

$$\begin{gathered} i=\lfloor (k+1)/2\rfloor +1 \\ j=k-2i+3 \\ \lfloor \rfloor :下取整符号，表示将数字x向下取整到不大于x的最大整数 \end{gathered}$$

稀疏矩阵

稀疏矩阵（Sparse Matrix）是指在矩阵中绝大多数元素为零的矩阵。换句话说，矩阵中非零元素的数量远远小于总元素数。

特点

• 大量零元素：零元素占据矩阵很大比例，通常超过 50% 以上，有些甚至达到 90% 以上。
• 存储优化：为了节省存储空间和加快计算速度，稀疏矩阵通常不以普通二维数组存储，而采用专门的数据结构（如压缩稀疏行CSR、压缩稀疏列CSC、三元组格式、十字链表等）只存储非零元素及其位置信息。

三元组举例

$$矩阵M=\left[\begin{array}{cccc}4& 0& 0& 0\\ 0& 0& 0& 6\\ 0& 0& 9& 0\\ 0& 23& 0& 0\end{array}\right]$$

三元组（行标i，列标j，值a[i,j]）：

注意：

1. 稀疏矩阵压缩存储后便失去了随机存取的特性。
2. 存储稀疏矩阵时，不仅要保存三元组表，还要保存稀疏矩阵的行数、列数和非零元素的个数。