考研笔记

数组和特殊矩阵

六道统考真题（2016、2017、2018、2020、2021、2023）全在这一节，而且每道题换一套下标约定。 教材【技巧】框：「对于特殊三角矩阵压缩存储的题，心中应有『平移』搬动的思想，并结合草图，这样会比较形象，在计算时再注意矩阵和数组的起始下标，就不容易出错。」各类矩阵的现成公式收在 速查：特殊矩阵压缩存储的下标公式，本页只讲不套公式的数法。

机制

3.4.1 数组的定义

数组是由 个相同类型的数据元素构成的有限序列。每个元素在 个线性关系中的序号称为该元素的下标，下标的取值范围称为数组的维界。

数组是线性表的推广：一维数组可视为一个线性表；二维数组可视为其元素是定长数组的线性表。数组一旦被定义，维数和维界就不再改变，所以除结构的初始化和销毁外，数组只会有存取元素和修改元素的操作。

3.4.2 数组的存储结构

一个数组的所有元素在内存中占用一段连续的存储空间。一维数组 A[0…n-1]：多维数组有两种映射方法（2021 命题追踪）。行、列下标范围分别为 、：

按行优先：按列优先：

按行优先：先行后列，先存储行号较小的元素，行号相等先存储列号较小的元素。 方括号里的量就是「 前面有几个元素」。

3.4.3 特殊矩阵的压缩存储

  • 压缩存储：为多个值相同的元素只分配一个存储空间，对零元素不分配空间。
  • 特殊矩阵：具有许多相同矩阵元素或零元素，并且这些元素的分布有一定规律性的矩阵，如对称矩阵、上（下）三角矩阵、对角矩阵。
矩阵存什么一维数组长度
对称矩阵 下三角区和主对角线（或上三角区和主对角线）
下三角矩阵下三角区和主对角线，再存上三角区的常量一次
上三角矩阵上三角区和主对角线，再存下三角区的常量一次
三对角矩阵（带状矩阵）： 时 3 条对角线上的元素按行优先存放

三对角矩阵以 存放于 B[0] 为准，；反之 ，（2016 命题追踪）。

口径差异：矩阵下标从 1，数组下标从 0

教材注意框：「二维数组 A[n][n] 和 A[0…n-1][0…n-1] 的写法是等价的。若数组写成 A[1…n][1…n]，则表示指定了下标是从 1 开始的。二维数组元素写为 a[i][j]，注意数组元素下标 和 通常是从 0 开始的。矩阵元素通常写为 ，行号 和列号 通常是从 1 开始的。」 教材的所有推导「均假设数组的下标从 0 开始，若题设有具体要求，则应该灵活应对」。题目里的「C 语言的一维数组」就是在说数组下标从 0 开始。

3.4.4 稀疏矩阵

非零元素的个数 相对矩阵元素的个数 来说非常少，即 的矩阵。

  • 非零元素的分布没有规律，仅存储非零元素的值不够，还要存储它所在的行和列，构成三元组（行标 ，列标 ，值 ）。
  • 压缩存储后便失去了随机存取特性。
  • 三元组表既可以采用数组存储，又可以采用十字链表存储（2017 命题追踪）。
  • 存储稀疏矩阵时，不仅要保存三元组表，还要保存稀疏矩阵的行数、列数和非零元素的个数（2023 命题追踪）。

手算模板

不背公式，数「目标元素前面有几个元素」。

  1. 画草图，标出要存的区域（下三角 / 上三角 / 三条对角线）和存储顺序（行优先 / 列优先）。
  2. 目标元素在存储区域外就先翻过去：对称矩阵存上三角时， 要换成 。
  3. 数前面的完整行（或列）：每一行（列）在存储区域内有几个元素，逐行相加。
  4. 加上本行（列）内排在它前面的元素。
  5. 按数组起始下标收尾：数组从 0 开始，下标 = 前面的元素个数；从 1 开始，再加 1。
年份题设数法答案
2016100 阶三对角矩阵，按行优先存入下标从 0 开始的 N，求 第 1 行 2 个，第 2~29 行各 3 个；第 30 行在它前面有 一个。87
201812 阶对称矩阵，上三角部分按行优先存入 C 语言数组，求 第 1~5 行在上三角里分别有 个，共 50 个； 是本行第一个50
202010 阶对称矩阵，上三角部分按列优先存入 C 语言数组，求 先翻成 。上三角按列存，第 列有 个：第 1~6 列共 21 个；第 7 列里 在它前面，再加 122
2021二维数组按行优先，每元素 1 单元，A[0][0] 地址 100，A[3][3] 地址 220，求 A[5][5]设每行 个：，。A[5][5] 前面有 个300

2016 也可以直接代公式 ，王道称之为「解法 1」；「解法 2」就是上面的数法，公式记混时仍然能做。

边界

说法判断说明
「数组可以做插入和删除」❌维数和维界定义后不再改变，只有存取和修改元素
「对特殊矩阵压缩存储是为了表达简单」❌是为了减少不必要的存储空间
「对称矩阵需要 个单元」❌，含主对角线
「三角矩阵的数组长度与对称矩阵相同」❌要多 1 个单元存那个常量
「三对角矩阵每行都有 3 个非零元素」❌首行和末行只有 2 个，共 个
「稀疏矩阵就是元素较少的矩阵」❌是非零元素较少
「稀疏矩阵压缩存储的缺点是无法判断行列数」❌另外保存了行列数。缺点是丧失随机存取特性
「用三元组表存稀疏矩阵，只需保存三元组」❌还要保存行数、列数（和非零元素个数）。否则两个大小不同的矩阵可能三元组表完全相同
「邻接矩阵、二叉链表适合存储稀疏矩阵」❌适合的是三元组表和十字链表（2017）
「A[0…n] 有 个元素」❌有 个
「按列优先的地址公式里乘 」❌按列优先乘行数

错题复盘：2020 为什么要先翻到上三角

题目给的是 （，在下三角），却说「上三角部分按列优先存入」。下三角的元素根本没有存，要利用对称性换成 再数。 直接对 数下三角会得到别的下标。王道解析第一句就是「 位于左下角，对应右上角的元素为 」。

错题复盘：2023 三元组表之外还要存什么

选项是 M 的行数、含非零元素的行数、M 的列数、含非零元素的列数，答案 A：仅 I、III。 三元组表只记录了非零元素的位置，无法知道矩阵有多大。王道解析举的例子是一个 矩阵和一个 矩阵，二者的三元组表相同。「含非零元素的行数、列数」从三元组表本身就能数出来，不需要另存。

错题复盘：三对角矩阵存进 B[1…298]（3.4.5 第 6 题）

三对角矩阵 A[1…100][1…100] 按行优先存入 B[1…298]，求 A[66][65] 的位置。答案 195。 数组从 1 开始，所以公式变成 ：。用数法：前 65 行有 个，A[66][65] 是第 66 行第一个，排第 195。 这个公式只在 B 从 0 开始时成立。

考点

  • 行优先 / 列优先的地址公式；2021 由两个地址反推每行元素个数。
  • 特殊矩阵的数组长度：、、。
  • 下标计算用数法：2016、2018、2020 三道。
  • 矩阵下标从 1、数组下标从 0，以及题目指定 B[1…] 时整体加 1。
  • 稀疏矩阵：三元组、失去随机存取、要另存行列数（2023）、存储结构是三元组表或十字链表（2017）。

链接

反向链接