注意
# 注意
二维数组 $\mathrm{A}[n][n]$ 与 $\mathrm{A}[0\dots n - 1][0\dots n - 1]$ 写法等价，表示下标从0开始。若写作 $A[1\dots n][1\dots n]$ ，则表示下标从1开始。矩阵元素通常记为 $a_{i,j}$ ，其行号 $i$ 和列号 $j$ 通常从1开始。
# 2. 三角矩阵
在下三角矩阵[见图3.22(a)]中，上三角区的所有元素均为同一常量。其存储思想与对称矩阵的类似，但是需要额外存储该常量一次。因此，可以将 $n$ 阶下三角矩阵 $A$ 压缩存储在 $\mathrm{B}[n(n + 1) / 2 + 1]$ 中。
对于元素 $a_{i,j}$ $(i\geq j)$ ，其在数组B中的下标为
$$
k = \left\{ \begin{array}{l l} \frac {i (i - 1)}{2} + j - 1, & i \geq j \text {(下三角区和主对角线元素)} \\ \frac {n (n + 1)}{2}, & i < j \text {(上三角区元素)} \end{array} \right.
$$
下三角矩阵的压缩存储形式如图3.21所示。
| 0 | 1 | 2 | 3 | 4 | 5 | ... | ... | n(n+1)/2 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| a1,1 | a2,1 | a2,2 | a3,1 | a3,2 | a3,3 | ... | a_n,1 | a_n,2 |
| 第1行 | 第2行 | 第3行 | | | | 第n行 | 常数项 | |
图3.21 下三角矩阵的压缩存储
考点点评 上三角矩阵采用行优先存储的应用（2011）
在上三角矩阵 [见图3.22(b)]中，下三角区所有元素均为同一常量。只需存储主对角线、上三角区上元素及该常量一次，同样将其压缩存储在 $\mathrm{B}[n(n + 1) / 2 + 1]$ 中。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(a) 下三角矩阵
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
(b) 上三角矩阵
图3.22 三角矩阵
<!-- page: 115 -->
第3章 栈、队列和数组
103
对于元素 $a_{i,j}$ （ $i \leqslant j$ ），其在数组B中前方的元素个数为
第1行：$n$ 个元素
第2行：$n - 1$ 个元素
……
第 $i - 1$ 行：$n - i + 2$ 个元素
第 $i$ 行：$j - i$ 个元素
故元素 $a_{i,j}$ 在数组 B 中的下标 $k = n + (n - 1) + \dots + (n - i + 2) + (j - i + 1) - 1 = (i - 1)(2n - i + 2)/2 + (j - i)$ 。元素下标之间的对应关系如下：
$$
k = \left\{ \begin{array}{l l} \frac {(i - 1) (2 n - i + 2)}{2} + (j - i), & i \leqslant j \text{（上三角区和主对角线元素）} \\ \frac {n (n + 1)}{2}, & i > j \text{（下三角区元素）} \end{array} \right.
$$
上三角矩阵的压缩存储形式如图3.23所示。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图3.23 上三角矩阵的压缩存储
以上推导均假设数组下标从0开始。若下标指定从1开始，则要相应地调整映射关系。
## 3. 三对角矩阵
若 $n$ 阶矩阵 $A$ 中的任意元素 $a_{i,j}$ ，当 $|i - j| > 1$ 时均有 $a_{i,j} = 0$ （ $1 \leqslant i, j \leqslant n$ ），则称为三对角矩阵，如图3.24所示。非零元素仅集中在以主对角线为中心的3条对角线的区域。
原转写引用的配图未随 Markdown 保存，请回到原 PDF 核验。
图3.24 三对角矩阵 $A$
可将三对角上的元素按行优先顺序存入一维数组B，且 $a_{1,1}$ 存于B[0]，如图3.25所示。
| a1,1 | a1,2 | a2,1 | a2,2 | a2,3 | ... | a_{n-1,n} | a_{n,n-1} | a_{n,n} |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
图3.25 三对角矩阵的压缩存储
**参阅图表** $\triangleright$ 三对角矩阵压缩存储的下标对应关系（2016）
三对角上的元素 $a_{i,j}$ （ $1 \leqslant i, j \leqslant n, |i - j| \leqslant 1$ ）在一维数组B中的下标 $k = 2i + j - 3$ 。
反之，已知元素存于 $\mathrm{B}[k]$ 中时， $i = \lfloor (k + 1) / 3 \rfloor + 1, j = k - 2i + 3$ 。例如，当 $k = 0$ 时， $i = \lfloor (0 + 1) / 3 + 1 \rfloor = 1, j = 0 - 2 \times 1 + 3 = 1$ ，存放的是 $a_{1,1}$ ；当 $k = 2$ 时， $i = \lfloor (2 + 1) / 3 + 1 \rfloor = 2, j = 2 - 2 \times 2 + 3 = 1$ ，存放的是 $a_{2,1}$ ；当 $k = 4$ 时， $i = \lfloor (4 + 1) / 3 + 1 \rfloor = 2, j = 4 - 2 \times 2 + 3 = 3$ ，存放的是 $a_{2,3}$ 。
## 3.4.4 稀疏矩阵
若矩阵中非零元素的个数 $t$ 相对于总元素个数 $s$ 来说非常少，即 $t \ll s$ ，则称该矩阵为稀疏矩
<!-- page: 116 -->
2027年数据结构考研复习指导
陈。例如，一个 $100 \times 100$ 的矩阵中只有不到 100 个非零元素。
考点信息 存储稀疏矩阵需要保存的信息（2023）
为避免空间浪费，稀疏矩阵通常仅存储非零元素。然而，由于非零元素的分布通常是无规律的，仅存储其值是不够的，还需记录它们所在的行和列。为此，将每个非零元素及其对应的行列位置组合成一个三元组（行标 $i$，列标 $j$，值 $a_{i,j}$），如图 3.26 所示。这些三元组可以按某种顺序排列成线性表进行存储。稀疏矩阵压缩存储后便失去了随机存取特性。
$$
M = \left[ \begin{array}{cccc} 4 & 0 & 0 & 0 \\ 0 & 0 & 6 & 0 \\ 0 & 9 & 0 & 0 \\ 0 & 23 & 0 & 0 \end{array} \right] \text{ 对应的三元组}
$$
| i | j | a_{i,j} |
| --- | --- | --- |
| 0 | 0 | 4 |
| 1 | 2 | 6 |
| 2 | 1 | 9 |
| 3 | 1 | 23 |
图 3.26 稀疏矩阵及其对应的三元组
考点信息 稀疏矩阵压缩存储的方式（2017）
稀疏矩阵的三元组表可通过多种方式存储，常见的有：数组存储将所有三元组按某种顺序存储在一维数组中，这种方式简单直接，但插入和删除操作的效率较低；十字链表存储（见 6.2 节）通过链表的方式组织三元组，适用于频繁插入和删除操作的场景。无论采用哪种方式，都需要额外保存稀疏矩阵的行数、列数和非零元素的个数，以便支持后续的各种操作。
## 3.4.5 本节试题精选
### 单项选择题
01. 对特殊矩阵采用压缩存储的主要目的是（）。
A. 表达变得简单
B. 对矩阵元素的存取变得简单
C. 去掉矩阵中的多余元素
D. 减少不必要的存储空间
02. 对 $n$ 阶对称矩阵压缩存储时，需要表长为（ ）的顺序表。
A. $n/2$
B. $n \times n/2$
C. $n(n + 1)/2$
D. $n(n - 1)/2$
03. 有一个 $n \times n$ 的对称矩阵 $A$，将其下三角部分按行存放在一维数组 $B$ 中，而 $A[0][0]$ 存放于 $B[0]$ 中，则元素 $A[i][i]$ 存放于 $B$ 中的（ ）处。
A. $(i + 3)i/2$
B. $(i + 1)i/2$
C. $(2n - i + 1)i/2$
D. $(2n - i - 1)i/2$
04. 在二维数组 A 中，假设每个数组元素的长度为 3 个存储单元，行下标 $i$ 为 $0 \sim 8$，列下标 $j$ 为 $0 \sim 9$，从首地址 SA 开始连续存放。在这种情况下，元素 $A[8][5]$ 的起始地址为（）。
A. SA + 141
B. SA + 144
C. SA + 222
D. SA + 255
05. 二维数组 A 按行优先存储，其中每个元素占 1 个存储单元。若 $A[1][1]$ 的存储地址为 420，$A[3][3]$ 的存储地址为 446，则 $A[5][5]$ 的存储地址为（）。
A. 472
B. 471
C. 458
D. 457
06. 将三对角矩阵即数组 $A[1 \dots 100][1 \dots 100]$ 按行优先存入一维数组 $B[1 \dots 298]$ 中，数组 A 中元素 $A[66][65]$ 在数组 B 中的位置 $k$ 为（）。
A. 198
B. 195
C. 197
D. 196
07. 若将 $n$ 阶上三角矩阵 $A$ 按列优先级压缩存放在一维数组 $B[1 \dots n(n + 1)/2 + 1]$ 中，则存放到 $B[k]$ 中的非零元素 $a_{i,j}$（$1 \leqslant i, j \leqslant n$）的下标 $i, j$ 与 $k$ 的对应关系是（）。
A. $i(i + 1)/2 + j$
B. $i(i - 1)/2 + j - 1$
C. $j(j - 1)/2 + i$
D. $j(j - 1)/2 + i - 1$
<!-- page: 117 -->
第3章 栈、队列和数组
105
08. 若将 $n$ 阶下三角矩阵 $A$ 按列优先顺序压缩存放在一维数组 $\mathrm{B}[1\dots n(n + 1) / 2 + 1]$ 中，则存放到 $\mathrm{B}[k]$ 中的非零元素 $a_{ij}$ （$1 \leqslant i,j \leqslant 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 + 2) / 2 + i - j$
D. $(j - 1)(2n - j + 1) / 2 + i - j - 1$
09. 稀疏矩阵采用压缩存储后的缺点主要是（）。
A. 无法判断矩阵的行列数
B. 丧失随机存取的特性
C. 无法由行、列值查找某个矩阵元素
D. 使矩阵元素之间的逻辑关系更复杂
10. 下列关于矩阵的说法中，正确的是（）。
I. 在 $n (n > 3)$ 阶三对角矩阵中，每行都有 3 个非零元素
II. 稀疏矩阵的特点是矩阵中的元素较少
A. 仅 I
B. 仅 II
C. I 和 II
D. 无正确项
11.【2016 统考真题】有一个 100 阶的三对角矩阵 $M$，其元素 $m_{i,j}$ （$1 \leqslant i,j \leqslant 100$）按行优先依次压缩存入下标从 0 开始的一维数组 N 中。元素 $m_{30,30}$ 在 N 中的下标是（）。
A. 86
B. 87
C. 88
D. 89
12.【2017 统考真题】适用于压缩存储稀疏矩阵的两种存储结构是（）。
A. 三元组表和十字链表
B. 三元组表和邻接矩阵
C. 十字链表和二叉链表
D. 邻接矩阵和十字链表
13.【2018 统考真题】设有一个 $12 \times 12$ 阶对称矩阵 $M$，将其上三角部分的元素 $m_{i,j}$ （$1 \leqslant i \leqslant j \leqslant 12$）按行优先存入 C 语言的一维数组 N 中，元素 $m_{6,6}$ 在 N 中的下标是（）。
A. 50
B. 51
C. 55
D. 66
14.【2020 统考真题】将一个 $10 \times 10$ 阶对称矩阵 $M$ 的上三角部分的元素 $m_{i,j}$ （$1 \leqslant i \leqslant j \leqslant 10$）按列优先存入 C 语言的一维数组 N 中，元素 $m_{7,2}$ 在 N 中的下标是（）。
A. 15
B. 16
C. 22
D. 23
15.【2021 统考真题】二维数组 A 按行优先方式存储，每个元素占用 1 个存储单元。若元素 A[0][0]的存储地址是 100，A[3][3]的存储地址是 220，则元素 A[5][5]的存储地址是（）。
A. 295
B. 300
C. 301
D. 306
16.【2023 统考真题】若采用三元组表存储结构存储稀疏矩阵 $M$，则除三元组表外，下列数据中还需要保存的是（）。
I. $M$ 的行数
II. $M$ 中包含非零元素的行数
III. $M$ 的列数
IV. $M$ 中包含非零元素的列数
A. 仅 I、III
B. 仅 I、IV
C. 仅 II、IV
D. I、II、III、IV
## 3.4.6 答案与解析
### 单项选择题
01. D
特殊矩阵中含有很多相同元素或零元素，所以可采用压缩存储，以节省存储空间。
02. C
只需存储其上三角或下三角部分（含对角线），元素个数为 $n + (n - 1) + \dots + 1 = n(n + 1)/2$。
03. A
此题要注意 3 个细节：矩阵的最小下标为 0；数组下标也是从 0 开始的；矩阵按行优先存在
<!-- page: 118 -->
2027年数据结构考研复习指导
数组中。注意到此三点，答案不难得到为选项 A。此外，本类题建议采用特殊值代入法求解，例如，A[1][1]对应的下标应为 2，代入后只有选项 A 满足条件。
## 技巧
对于特殊三角矩阵压缩存储的题，心中应有“平移”搬动的思想，并结合草图，这样会比较形象，在计算时再注意矩阵和数组的起始下标，就不容易出错。
## 04. D
二维数组计算地址（按行优先顺序）的公式为
$$
\operatorname {L O C} (i, j) = \operatorname {L O C} (0, 0) + (i m + j) L
$$
其中， $\mathrm{LOC}(0,0) = \mathrm{SA}$ ，是数组存放的首地址； $L = 3$ 是每个数组元素的长度； $m = 9 - 0 + 1 = 10$ 是数组的列数。因此有 $\mathrm{LOC}(8,5) = \mathrm{SA} + (8\times 10 + 5)\times 3 = \mathrm{SA} + 255$ ，所以选择选项D。
## 05. A
本题未直接给出数组A的行数和列数，因此需要根据题目中的信息来推理。因为该二维数组按行优先存储，且A[3][3]的存储地址为446，所以A[3][1]的存储地址为444，又A[1][1]的存储地址为420，显然A[1][1]和A[3][1]正好相差2行，所以该矩阵的列数为12。而A[5][3]和A[3][3]正好相差2行，A[5][5]和A[5][3]又相差2个元素，所以A[5][5]的存储地址是 $446 + 24 + 2 = 472$
## 06. B
对于三对角矩阵，将 $\mathrm{A}[1\dots n][1\dots n]$ 压缩至 $\mathrm{B}[1\dots 3n - 2]$ 时， $a_{i,j}$ 与 $b_{k}$ 的对应关系为 $k = 2i + j - 2$ 。则A中的元素A[66][65]在数组B中的位置 $k$ 为 $2\times 66 + 65 - 2 = 195$
## 07. C
按列优先存储，所以元素 $a_{i,j}$ 前面有 $j - 1$ 列，共有 $1 + 2 + 3 + \dots + j - 1 = j(j - 1)/2$ 个元素，元素 $a_{i,j}$ 在第 $j$ 列上是第 $i$ 个元素，数组B的下标是从1开始，因此 $k = j(j - 1)/2 + i$ 。
## 08. B
按列优先存储，故元素 $a_{ij}$ 前有 $j - 1$ 列，共有 $n + (n - 1) + \dots + (n - j + 2) = (j - 1)(2n - j + 2)/2$ 个元素，元素 $a_{i,j}$ 是第 $j$ 列上第 $i - j + 1$ 个元素，数组B的下标从1开始， $k = (j - 1)(2n - j + 2)/2 + i - j + 1$ 。
## 09. B
稀疏矩阵通常采用三元组来压缩存储，存储矩阵元素的行列下标和相应的值，因此不能根据矩阵元素的行列下标快速定位矩阵元素，失去了随机存取的特性。
## 10. D
在三对角矩阵中，第1行和最后1行只有2个非零元，其余各行均有3个非零元。稀疏矩阵的特点是矩阵中非零元的个数较少。
## 11. B
三对角矩阵如下所示。
$$
\left[ \begin{array}{c c c c c c} a _ {1, 1} & a _ {1, 2} & & & & \\ a _ {2, 1} & a _ {2, 2} & a _ {2, 3} & & 0 & \\ & a _ {3, 2} & a _ {3, 3} & a _ {3, 4} & & \\ & & \ddots & \ddots & \ddots & \\ & 0 & & a _ {n - 1, n - 2} & a _ {n - 1, n - 1} & a _ {n - 1, n} \\ & & & & a _ {n, n - 1} & a _ {n, n} \end{array} \right]
$$
采用压缩存储，将3条对角线上的元素按行优先方式存放在一维数组B中，且 $a_{1,1}$ 存放于B[0]中，其存储形式如下所示：
<!-- page: 119 -->
第3章 栈、队列和数组
107
| a1,1 | a1,2 | a2,1 | a2,2 | a2,3 | ... | a_{n-1,n} | a_{n,n-1} | a_{n,n} |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
可以计算矩阵 $A$ 中 3 条对角线上的元素 $a_{i,j}$ $(1 \leqslant i,j \leqslant n, |i - j| \leqslant 1)$ 在一维数组 B 中存放的下标为 $k = 2i + j - 3$，公式很难记忆，我们通常采用解法 2。
解法1：针对该题，仅需将数字逐一代入公式：$k = 2 \times 30 + 30 - 3 = 87$，结果为87。
解法2：观察上图的三对角矩阵不难发现，第一行有两个元素，剩下的在元素 $m_{30,30}$ 所在行之前的28行（注意下标 $1 \leqslant i,j \leqslant 100$）中，每行都有3个元素，而 $m_{30,30}$ 之前仅有一个元素 $m_{30,29}$，不难发现元素 $m_{30,30}$ 在数组N中的下标是 $2 + 28 \times 3 + 2 - 1 = 87$。
## 注意
矩阵和数组的下标从0或1开始（如矩阵可能从 $a_{0,0}$ 或 $a_{1,1}$ 开始，数组可能从B[0]或B[1]开始），这时就需要适时调整计算方法（方法无非是多计算1或少计算1的问题）。
## 12. A
三元组表的结点存储了行（row）、列（col）、值（value）三种信息，是主要用来存储稀疏矩阵的一种数据结构。十字链表将行单链表和列单链表结合起来存储稀疏矩阵。邻接矩阵空间复杂度达 $O(n^{2})$，不适合存储稀疏矩阵。二叉链表又名左孩子右兄弟表示法，可用于表示树或森林。