考研笔记

速查：特殊矩阵压缩存储的下标公式

速查表：公式集中在这里。不套公式的「数前面有几个元素」手算法与 6 道真题见 3.4 数组和特殊矩阵。 这一页的公式必须一字不差——每一个都直接对应过真题（2016、2018、2020、2021、2023）。

数组的存储（3.4.2）

一维数组 A[0…n-1]：

其中 是每个数组元素所占的存储单元。

二维数组（行下标与列下标范围分别为 与 ）：

映射方法存储结构关系式
按行优先
按列优先

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

注意行数是 、列数是 ——下标范围是 ，个数要加 1。

对称矩阵（3.4.3）

阶矩阵 中任意元素 都有 （）。存放在一维数组 B[n(n+1)/2] 中，只存下三角部分（含主对角线）。数组下标从 0 开始时：

下三角区和主对角线元素上三角区元素

所需一维数组长度：。

教材注意框：二维数组 A[n][n] 和 A[0…n-1][0…n-1] 的写法是等价的。若数组写成 A[1…n][1…n]，则表示指定了下标是从 1 开始的。二维数组元素写为 a[i][j]，注意数组元素下标 和 通常是从 0 开始的。矩阵元素通常写为 ，行号 和列号 通常是从 1 开始的。

「矩阵下标从 1、数组下标从 0」是这一节所有公式里 的来源。

三角矩阵

下三角矩阵：上三角区的所有元素均为同一常量。存储完下三角区和主对角线上的元素之后，紧接着存储对角线上方的常量一次，所以压缩存储在 B[n(n+1)/2+1] 中。

下三角区和主对角线元素上三角区元素，即那一个常量

上三角矩阵：下三角区的所有元素均为同一常量。只需存储主对角线、上三角区上的元素和下三角区的常量一次，压缩存储在 B[n(n+1)/2+1] 中。

在数组 B 中，位于元素 （）前面的元素个数为：第 1 行 个、第 2 行 个、……、第 行 个、第 行 个。因此

上三角区和主对角线元素下三角区元素

「以上推导均假设数组的下标从 0 开始，若题设有具体要求，则应该灵活应对。」

三对角矩阵（带状矩阵）

对 阶矩阵 中的任意一个元素 ，当 时若有 （），则称为三对角矩阵。所有非零元素都集中在以主对角线为中心的 3 条对角线的区域，其他区域的元素都为零。

将 3 条对角线上的元素按行优先方式存放在一维数组 B 中，且 存放于 B[0] 中：

反之，若已知某元素 存放在一维数组 B 的第 个位置：

教材的三个验算例：

元素
0
2
4

存储形式：，共 个元素。

稀疏矩阵（3.4.4）

矩阵中非零元素的个数 ，相对矩阵元素的个数 来说非常少，即 的矩阵称为稀疏矩阵。

  • 仅存储非零元素。但通常非零元素的分布没有规律，所以仅存储非零元素的值是不够的，还要存储它所在的行和列。
  • 因此将非零元素及其相应的行和列构成一个三元组（行标 ，列标 ，值 ），然后按照某种规律存储这些三元组线性表。
  • 稀疏矩阵压缩存储后便失去了随机存取特性。
  • 三元组表既可以采用数组存储，又可以采用十字链表存储。
  • 当存储稀疏矩阵时，不仅要保存三元组表，而且要保存稀疏矩阵的行数、列数和非零元素的个数。

一张表汇总

矩阵数组长度下标公式（数组下标从 0，矩阵下标从 1）
对称矩阵：；：
下三角矩阵：；：
上三角矩阵：；：
三对角矩阵
稀疏矩阵（三元组）无公式，失去随机存取特性

高频边界

说法判断说明
「对称矩阵需要 个单元」❌是
「三角矩阵与对称矩阵的数组长度相同」❌三角矩阵要多 1 个存那个常量
「三对角矩阵需要 个单元」❌（首尾两行各少一个）
「压缩存储的目的是表达简单」❌是减少不必要的存储空间
「稀疏矩阵压缩后仍可随机存取」❌失去随机存取特性
「存稀疏矩阵只要存三元组表」❌还要存行数、列数、非零元素个数
「矩阵下标和数组下标都从 0 开始」❌矩阵下标通常从 1，数组下标通常从 0
「按列优先时 用 」❌按列优先用 （行数）

链接

反向链接