数组结构之数组和特殊矩阵

数组的存储结构

数组是一种重要的数据结构，几乎所有计算机语言都提供了数组数据类型。逻辑上的数组可以通过计算机语言中的数组类型来存储。在内存中，数组的所有元素占用一段连续的存储空间。

一维数组的存储

以一维数组 $ A[0..n-1] $ 为例，其存储结构关系式为：

$ (A[i]) = (A[0]) + i L (0 i < n) $

其中：

$ (A[i]) $ 表示数组元素 $ A[i] $ 在内存中的地址。
$ L $ 表示每个数组元素所占的存储单元。

多维数组的存储

对于多维数组，通常有两种映射方法：按行优先和按列优先。

按行优先存储

基本思想：先存储行，后存储列，行号较小的元素先存储，行号相等时列号较小的元素先存储。

设二维数组的行下标与列下标的范围分别为 $[0, h]$ 和 $[0, k]$，则存储结构关系式为：

$ (A[i][j]) = (A[0][0]) + (i (k + 1) + j) L $

例如，对于一个 $ 2 $ 的二维数组 $ A $，按行优先方式在内存中的存储形式如图 3.18 所示：

1 2	第1行: a[0][0], a[0][1], a[0][2] 第2行: a[1][0], a[1][1], a[1][2]

按列优先存储

基本思想：先存储列，后存储行，列号较小的元素先存储，列号相等时行号较小的元素先存储。

对于同样的二维数组，其存储结构关系式为：

$ (A[i][j]) = (A[0][0]) + (j (h + 1) + i) L $

例如，对于数组 $ A $ 按列优先方式在内存中的存储形式如图 3.19 所示：

1
2
3

第1列: a[0][0], a[1][0]
第2列: a[0][1], a[1][1]
第3列: a[0][2], a[1][2]

对称矩阵

定义：若对于一个 $ n $ 阶方阵 $ A[1..n][1..n] $ 中的任意一个元素 $ a_{ij} $ 都有 $ a_{ij} = a_{ji} $ (即 $ 1 i, j n $)，则称其为对称矩阵。

矩阵的划分

对于一个 $ n $ 阶对称矩阵，可以将其元素划分为三个部分：

上三角区：$ i < j $ 的元素。
主对角线：$ i = j $ 的元素。
下三角区：$ i > j $ 的元素。

如图 3.20 所示：

第1行: a[1][1]
第2行: a[2][1], a[2][2]
第3行: a[3][1], a[3][2], a[3][3]
...
第n行: a[n][1], a[n][2], ..., a[n][n]

存储方式

由于对称矩阵的性质，上三角区的所有元素与下三角区的对应元素相同，因此如果仍采用二维数组存放，会浪费几乎一半的空间。因此，通常采用一维数组 $ B $ 来存放对称矩阵的元素。

存储结构

将对称矩阵 $ A[1..n][1..n] $ 存放在一维数组 $ B $ 中，数组的大小为 $ $。该一维数组只存放下三角部分（包含主对角线）的元素。

元素存储关系

在数组 $ B $ 中，元素 $ a_{ij} $ 的位置可以通过以下公式计算得到：

下三角区和主对角线元素（$ i j $）：

$ k = + j (0 j i) $
上三角区元素（$ i < j $）：

$ a_{ij} = a_{ji} $

下标计算

对于下三角区元素 $ a_{ij} $（含主对角线）：
- 位置计算： $ k = + j $
- 这里，$ i $ 是行索引，$ j $ 是列索引。
对于上三角区元素：
- 可以通过 $ a_{ij} = a_{ji} $ 访问其对应的下三角区元素。

例子

假设我们有一个 $ 3 $ 的对称矩阵 $ A $ 如下：

$ A = \[\begin{bmatrix} a_{11} & a_{12} & a_{13} \\ a_{12} & a_{22} & a_{23} \\ a_{13} & a_{23} & a_{33} \end{bmatrix}\]

在一维数组 $ B $ 中，元素的存放顺序为：

$ B[0] = a_{11} $
$ B[1] = a_{12} $
$ B[2] = a_{22} $
$ B[3] = a_{13} $
$ B[4] = a_{23} $
$ B[5] = a_{33} $

对应的存储关系为：

$ a_{12} $ 对应于 $ B[1] $
$ a_{13} $ 对应于 $ B[3] $
$ a_{23} $ 对应于 $ B[4] $

通过这种方式，我们可以有效地存储和访问对称矩阵，而不会浪费内存。

三角矩阵

三角矩阵分为下三角矩阵和上三角矩阵。它们的特点和存储方法如下：

1. 下三角矩阵

定义：下三角矩阵是指一个 $ n $ 阶矩阵 $ A[1..n][1..n] $，其上三角区的所有元素均为同一常量。

存储思想：与对称矩阵类似，存储下三角区和主对角线上的元素后，紧接着存储对角线上方的常量一次。

存储结构

存储数组：使用一维数组 $ B $，大小为 $ n(n+1)/2 + 1 $，其中：
- 下三角区和主对角线上的元素存储在前面。
- 常量项存储在最后。

元素下标关系

下三角区和主对角线元素（$ i j $）：$ k = + j $ 这里 $ i $ 是行索引，$ j $ 是列索引。
上三角区元素（$ i < j $）：$ k = n(n+1)/2 + 1 () $

存储形式

下三角矩阵在内存中的压缩存储形式如图 3.21 所示。

第1行: a[11]
第2行: a[21], a[22]
第3行: a[31], a[32], a[33]
...
第n行: a[n1], a[n2], ..., a[nn]
常量项

2. 上三角矩阵

定义：上三角矩阵是指一个 $ n $ 阶矩阵 $ A[1..n][1..n] $，其下三角区的所有元素均为同一常量。

存储思想：只需存储主对角线、上三角区的元素和下三角区的常量一次。

存储结构

存储数组：同样使用一维数组 $ B $，大小为 $ n(n+1)/2 + 1 $，其中：
- 主对角线和上三角区的元素存储在前面。
- 常量项存储在最后。

元素下标关系

上三角区和主对角线元素（$ i j $）：$ k = + (j - n) $
下三角区元素（$ i > j $）：$ k = n(n+1)/2 + 1 () $

存储形式

上三角矩阵在内存中的压缩存储形式如图 3.23 所示。

第1行: a[11], a[12], a[13], ...
第2行: a[22], a[23], ...
第3行: a[33], ...
...
常量项

三对角矩阵

定义：三对角矩阵（又称带状矩阵）是一个 $ n $ 阶方阵 $ A $，其满足以下条件：对于任一元素 $ a_{ij} $，当 $ |i-j| > 1 $ 时，$ a_{ij} = 0 $（即矩阵中只有主对角线及其上下第一条对角线的元素非零），如图 3.24 所示。

特点

三对角矩阵的非零元素集中在以主对角线为中心的三条对角线的区域。
其余区域的元素均为零。

存储结构

为减少内存使用，可以采用压缩存储方法，将三条对角线上的元素按行优先的方式存放在一维数组 $ B $ 中。

存储数组：大小为 $ B[n] $，其中：
- $ B[0] $ 存放 $ a_{11} $（主对角线元素）。
- 紧接着存放主对角线和上下对角线的元素。

存储形式示意图

   0   1   2   3   4   ...
| 0 | a11 | a12 | 0 | 0 | ...
| 1 | a21 | a22 | a23 | 0 | ...
| 2 | 0 | a32 | a33 | a34 | ...
| 3 | 0 | 0 | a43 | a44 | ...
| 4 | 0 | 0 | 0 | a54 | ...

（图 3.25 三对角矩阵的压缩存储）

存储下标关系

矩阵中的元素：
- 对于三条对角线上的元素 $ a_{ij} $，可以通过以下公式计算在一维数组 $ B $ 中的下标 $ k $：$ k = 2i + (i - 3) $ 其中 $ i $ 表示行索引，$ j $ 表示列索引，且 $ |i-j| $。
已知元素在数组中的位置：
- 若已知三对角线矩阵中某元素 $ a_{ij} $ 存放于一维数组 $ B $ 的第 $ k $ 个位置，可以通过以下公式反推 $ i $ 和 $ j $：$ i = + 1 $ $ j = k - 2i + 3 $ 例如：
- 当 $ k = 0 $ 时： $ i = + 1 = 1, j = 0 - 2 + 3 = 1 $ 存放的是 $ a_{11} $。
- 当 $ k = 2 $ 时： $ i = + 1 = 2, j = 2 - 2 + 3 = 1 $ 存放的是 $ a_{21} $。
- 当 $ k = 4 $ 时： $ i = + 1 = 2, j = 4 - 2 + 3 = 3 $ 存放的是 $ a_{23} $。

稀疏矩阵

定义：稀疏矩阵是指矩阵中非零元素的个数 $ t $ 相对于矩阵总元素个数 $ s $（$ s = n m $，其中 $ n $ 和 $ m $ 分别是矩阵的行数和列数）非常少的矩阵。通常情况下，稀疏矩阵满足条件 $ s t $，即非零元素远远小于总元素。例如，一个 $ 100 $ 的矩阵，如果只有少于 $ 100 $ 个非零元素，那么这个矩阵就是稀疏矩阵。

存储问题

存储空间浪费：若采用常规的二维数组存储稀疏矩阵，尽管绝大多数元素都是零，但这些零元素仍然占用存储空间，造成资源浪费。

稀疏矩阵的压缩存储

为了解决存储空间的浪费问题，稀疏矩阵的压缩存储方法主要包括以下步骤：

只存储非零元素：只记录非零元素的值，而忽略零元素的存储。
存储元素位置：
- 除了存储非零元素的值，还需存储其所在的行和列，以便在后续的操作中能够准确地访问这些元素。
- 采用三元组表示法，记录每个非零元素的行标、列标和对应的值。每个三元组的格式为： $ (行标, 列标, 值) $

三元组示例：如图 3.26 所示，假设有一个稀疏矩阵如下：

| 0  0  0  6  0 |
| 0  0  2  0  0 |
| 0  0  0  0  9 |
| 0  3  0  0  0 |
| 0  0  0  0  0 |

对应的三元组为：

(0, 3, 6)
(1, 2, 2)
(2, 4, 9)
(3, 1, 3)

存储规律：三元组可以按照行优先或列优先的顺序进行存储，这取决于具体应用的需要。通常会将三元组按行标升序排列。

随机存取特性

由于稀疏矩阵经过压缩存储后只保留了非零元素和它们的位置，传统的随机存取特性可能会丧失。需要进行查找操作来找到特定位置的元素。

选择题

01. 对特殊矩阵采用压缩存储的主要目的是()。

A. 表达变得简单
B. 对矩阵元素的存取变得简单
C. 去掉矩阵中的多余元素
D. 减少不必要的存储空间

解析：特殊矩阵中含有许多相同元素或零元素，因此采用压缩存储可以节省存储空间。

02. 对 $ n $ 阶对称矩阵压缩存储时，需要表长为()的顺序表。

A. $ n/2 $
B. $ n n/2 $
C. $ n(n+1)/2 $
D. $ n(n-1)/2 $

解析：只需存储其上三角或下三角部分（含对角线），元素个数为 $ n + (n - 1) + (n - 2) + + 1 = n(n + 1)/2 $。

03. 有一个 $ n n $ 的对称矩阵 $ A $，将其下三角部分按行存放在一维数组 $ B $ 中，而 $ A[0][0] $ 存放于 $ B[0] $ 中，则第 $ i+1 $ 行的对角元素 $ A[i][i] $ 存放于 $ B $ 中的()处。

A. $ (i+1)i/2 $
B. $ (i + 3)i/2 $
C. $ (2n-i+1)i/2 $
D. $ (2n-i-1)i/2 $

解析：注意矩阵的最小下标为0，数组下标也是从0开始的，并且矩阵按行优先存放在数组中。计算可得第 $ i $ 行的对角元素在 $ B $ 中的位置为 $ (i+1)i/2 $。

04. 在一个二维数组 $ A $ 中，假设每个数组元素的长度为3个存储单元，行下标 $ i $ 为0~8，列下标 $ j $ 为0~9，从首地址 $ S_A $ 开始连续存放。在这种情况下，元素 $ A[8][5] $ 的起始地址为( )。

A. $ S_A + 141 $
B. $ S_A + 144 $
C. $ S_A + 222 $
D. $ S_A + 255 $

解析：二维数组计算地址（按行优先顺序）的公式为 $ LOC(i,j) = LOC(0,0) + (i m + j) L $ 其中，$ LOC(0,0) = S_A $，$ L = 3 $ 是每个数组元素的长度，$ m = 10 $ 是数组的列数。因此有： $ LOC(8,5) = S_A + (8 + 5) = S_A + 255 $

05. 将三对角矩阵 $ A[1..100][1..100] $ 按行优先存入一维数组 $ B[1..298] $ 中，$ A $ 中元素 $ A[66][65] $ 在数组 $ B $ 中的位置 $ k $ 为()。

A. 198
B. 195
C. 197
D. 196

解析：对于三对角矩阵，将 $ A[1..n][1..n] $ 压缩至 $ B[1..3n-2] $ 时，$ a_{ij} $ 与 $ k $ 的对应关系为 $ k = 2i + j - 2 $。因此：$ k = 2 + 65 - 2 = 195 $

06. 若将 $ n $ 阶上三角矩阵 $ A $ 按列优先级压缩存放在一维数组 $ B[1..n(n+1)/2+1] $ 中，则存放到 $ B[k] $ 中的非零元素 $ a_{ij} (1 i,j n) $ 的下标 $ i,j $ 与 $ k $ 的对应关系是( )。

A. $ i(i+1)/2 + i $
B. $ i(i-1)/2 + j - 1 $
C. $ j(j-1)/2 + i $
D. $ j(j-1)/2 + i - 1 $

解析：按列优先存储，因此元素 $ a_{ij} $ 前面有 $ j-1 $ 列，共有 $ 1 + 2 + 3 + + (j-1) = j(j-1)/2 $ 个元素，元素 $ a_{ij} $ 在第 $ j $ 列上是第 $ i $ 个元素，数组 $ B $ 的下标是从1开始，因此 $ k = j(j-1)/2 + i $。

07. 若将 $ n $ 阶下三角矩阵 A 按列优先顺序压缩存放在一维数组 $ B[1..n(n+1)/2+1] $ 中，则存放到 $ B[k] $ 中的非零元素 $ a_{ij}(1≤i,j≤n) $ 的下标 $ i,j $ 与 $ k $ 的对应关系是( )。
A. $(j-1)(2n-j+1)/2 + i - j$
B. $(j-1)(2n-j+2)/2 + i - j+1$
C. $(j-1)(2n-j+1)/2 + i - j - 1$
答案： B
解析： 按列优先存储，故元素$a_{i,j}$之前有$j-1$列，共有$n+(n-1)+…+(n-j+2)=(j-1)(2n-j+ 2)/2$个元素，元素av是第j列上第i-j+1个元素，数组B下标从1开始，$k=(j-1)(2n-j+2)/2+i-j+1$。

08. 有一个 100 阶的三对角矩阵 M，其元素 $ m_{ij}(1≤i,j≤100) $ 按行优先依次压缩存入下标从 0 开始的一维数组 $ N $ 中。元素 $ m_{30,30} $ 在 $ N $ 中的下标是( )。
答案： D. 87

解析： 在三对角矩阵中，行优先存储时，第 $ i $ 行有 $ i+1 $ 个元素，因此元素 $ m_{30,30} $ 对应的下标为 $ 3 - 3 = 87 $。

09. 适用于压缩存储稀疏矩阵的两种存储结构是( )
A. 三元组表和十字链表
B. 三元组表和邻接矩阵
C. 十字链表和二叉链表
答案： A
解析： 三元组表存储行、列和值，十字链表结合行单链表和列单链表来存储稀疏矩阵。

10. 设有一个 $ 12 $ 的对称矩阵 M, 将其上三角部分的元素 $ m_{ij}(1≤i≤j≤12) $ 按行优先存入 C 语言的一维数组 N 中，元素 $ m_{6,6} $ 在 N 中的下标是( )。
A. 50
B. 51
C. 55
D. 66
答案： A
解析： 在C语言中，数组N的下标从0开始。第一个元素m,对应存入n，矩阵M的第一行有12个元素，第二行有11个，第三行有 10个，第四行有9个，第五行有8个，所以$m_{6,6}$是第 12+11+10+9+8+1=51个元素，下标应为50。

11. 将一个 $ 10 $ 对称矩阵 M 的上三角部分的元素 $ m_{ij}(1≤i≤j≤10) $ 按列优先存入 C 语言的一维数组 N 中，元素 $ m_{7,2} $ 在 N 中的下标是( )。
A. 15
B. 16
C. 22
D. 23
答案： C
解析： 对于 $ 10 $ 的上三角矩阵，按列优先存储，元素 $ m_{12} $ 需要计算所有前面的元素，最终确定下标。

12. 二维数组 $ A $ 按行优先方式存储，每个元素占用 1 个存储单元。若元素 $ A[0][0] $ 的存储地址是 100，$ A[3][3] $ 的存储地址是 220，则元素 $ A[5][5] $ 的存储地址是( )。
A. 295
B. 300
C. 301
D. 306

答案： B

解析：

行优先存储的地址计算：在行优先存储中，元素的地址可以通过以下公式计算： $ (A[i][j]) = + (n i + j) $ 其中，$ n $ 是每行的元素数量，$ i $ 和 $ j $ 是元素的行索引和列索引。
确定数组的行数和列数：给定 $ A[0][0] $ 的地址为 100，意味着这是数组的起始地址。
给定 $ A[3][3] $ 的地址为 220。根据公式，$ A[3][3] $ 的地址计算如下： $ (A[3][3]) = 100 + (n + 3) $ 这等于 220： $ 100 + (3n + 3) = 220 $ $ 3n + 3 = 120 $ $ 3n = 117 n = 39 $
计算元素 $ A[5][5] $ 的地址：使用上面的公式计算 $ A[5][5] $ 的地址： $ (A[5][5]) = 100 + (39 + 5) = 100 + (195 + 5) = 100 + 200 = 300 $