【考研】数据结构——特殊矩阵的压缩存储（含真题）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【考研】数据结构——特殊矩阵的压缩存储（含真题）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

本文内容源于对《数据结构（C语言版）》（第2版）、王道讲解学习所得心得、笔记整理和总结。

本文主要以举例子的方式讲解考研选择题型中的特殊矩阵的压缩存储知识点，配以图文（含408真题）。

可搭配以下链接进行学习：

【2023考研】数据结构常考应用典型例题（含真题）_住在阳光的心里的博客-CSDN博客

一、数组的存储结构

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

$特殊矩阵的压缩存储,数据结构,考研,数据结构,学习,矩阵$

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

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

以二维数组为例，按行优先存储的基本思想是：先行后列，先存储行号较小的元素，行号相等先存储列号较小的元素。

设二维数组的行下标与列下标的范围分别为与，则存储结构关系式为:

$特殊矩阵的压缩存储,数据结构,考研,数据结构,学习,矩阵$

按列优先方式存储时，得出存储结构关系式为:

$特殊矩阵的压缩存储,数据结构,考研,数据结构,学习,矩阵$

举例：

特殊矩阵的压缩存储,数据结构,考研,数据结构,学习,矩阵

二、矩阵的压缩存储

（一）基本概念

1、压缩存储：指为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。其目的是节省存储空间。

2、特殊矩阵：指具有许多相同矩阵元素或零元素，并且这些相同矩阵元素或零元素的分布有一定规律性的矩阵。常见的特殊矩阵有对称矩阵、上(下)三角矩阵、对角矩阵等。

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

（二）三对角矩阵

1、【2016统考真题】有一个 100 阶的三对角矩阵 M，其元素（1 ≤ i, j ≤ 100）按行优先依次压缩存入标从 0 开始的一维数组中 N。元素在 N 中的下标是（ B ）

A. 86 B. 87 C. 88 D. 89

解：三对角矩阵 A 如下所示：

（在三对角矩阵中，所有非零元素都集中在以主对角线为中心的 3 条对角线的区域，其他区域的元素都为零。）

特殊矩阵的压缩存储,数据结构,考研,数据结构,学习,矩阵

采用压缩存储，将 3 条对角线上的元素，按行优先方式存放在一维数组 B 中，且存放于 B[0]中，其存储形式如下所示：

特殊矩阵的压缩存储,数据结构,考研,数据结构,学习,矩阵

可以计算矩阵 A 中 3 条对角线上的元素（1 ≤ i, j ≤ 100, |i - j| <= 1）在一维数组 B 中存放的下标为 k = 2i + j - 3。（下标从 0 开始）

解法一：针对该题，仅需将数字逐一代入公式: k = 2 x 30 + 30 - 3 = 87，结果为87。

解法二：观察上图的三对角矩阵不难发现，第一行有两个元素，剩下的在元素所在行之
前的 28 行（注意下标 1 ≤ i，j ≤ 100）中，每行都有 3 个元素，而之前仅有一个元素，不难发现元素在数组 N 中的下标是 2 + 28x3 + 2 - 1 = 87。

（解法二中，减一是因为一维数组 B 的下标是从 0 开始。）

【注意】

解法一中的一维数组 B[k] 的下标是从 0 开始。若是从 1 开始，则公式应为 k = 2i + j - 2。

反过来，求 i , j ，有表如下：(三对角矩阵 A 从 1 开始)

一维数组 B下标	从 0 开始	从 1 开始
i	$特殊矩阵的压缩存储,数据结构,考研,数据结构,学习,矩阵$	$特殊矩阵的压缩存储,数据结构,考研,数据结构,学习,矩阵$
j	k - 2i + 3	k - 2i + 2
k	2i + j - 3	2i + j - 2

2、将三对角矩阵 A[1..100] 按行优先存入一维数组 B[1..298] 中，A 中元素 A[66][65] 在数组B 中的位置 k 为( B )
A. 198 B. 195 C.197 D.196

解：一维数组 B[k] 的下标是从 1 开始。由公式 k = 2i + j - 2，得 k = 2*66 + 65 - 2 = 195。

【另】反过来推导：已知 k 为 195 , 求 i , j：

$特殊矩阵的压缩存储,数据结构,考研,数据结构,学习,矩阵$

（三）对称矩阵和三角矩阵

1、若将 n 阶上三角矩阵 A 按列优先级压缩存放在一维数组 B[1...n(n+1)/2+1] 中，则存放到B[k] 中的非零元素 (1 ≤ i, j ≤ n) 的下标 i, j 与 k 的对应关系是( C )。
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

解：按列优先存储，故元素前面有 j - 1 列，

共有 1 + 2 + 3 + ... +j -1 = j ( j - 1 ) / 2 个元素，元素在第 j 列上是第 i 个元素，

数组 B 的下标是从 1 开始，因此 k = j ( j - 1 ) / 2 + i。

2、若将 n 阶下三角矩阵 A 按列优先顺序压缩存放在一维数组 B[1...n(n+1)/2+1] 中，则存放到 B[k] 中的非零元素 (1 ≤ i, j ≤ n) 的下标 i, j 与 k 的对应关系是( B )。
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

解：按列优先存储，故元素之前有 j - 1 列，

共有 n + (n - 1) + ... + (n - j + 2) = (j-1)(2n - j + 2) / 2 个元素，

元素是第 j 列上第 i - j + 1 个元素，

数组 B 下标从 1 开始，k = (j - 1) (2n - j + 2) / 2 + i - j + 1。