前言

本文內(nèi)容源于對《數(shù)據(jù)結(jié)構(gòu)（C語言版）》（第2版）、王道講解學(xué)習(xí)所得心得、筆記整理和總結(jié)。

本文主要以舉例子的方式講解考研選擇題型中的特殊矩陣的壓縮存儲知識點(diǎn)，配以圖文（含408真題）。

可搭配以下鏈接進(jìn)行學(xué)習(xí)：

【2023考研】數(shù)據(jù)結(jié)構(gòu)?？紤?yīng)用典型例題（含真題）_住在陽光的心里的博客-CSDN博客

目錄

前言

一、數(shù)組的存儲結(jié)構(gòu)

二、矩陣的壓縮存儲

（一）基本概念

（二）三對角矩陣

（三）對稱矩陣和三角矩陣

三、稀疏矩陣

一、數(shù)組的存儲結(jié)構(gòu)

1、以一維數(shù)組 A[0...n-1] 為例， 其存儲結(jié)構(gòu)關(guān)系式為

其中，L 是每個數(shù)組元素所占的存儲單元。

2、對于多維數(shù)組，有兩種映射方法：按行優(yōu)先和按列優(yōu)先。

以二維數(shù)組為例，按行優(yōu)先存儲的基本思想是：先行后列，先存儲行號較小的元素，行號相等先存儲列號較小的元素。

設(shè)二維數(shù)組的行下標(biāo)與列下標(biāo)的范圍分別為??與 ，則存儲結(jié)構(gòu)關(guān)系式為:

按列優(yōu)先方式存儲時，得出存儲結(jié)構(gòu)關(guān)系式為:

舉例：

二、矩陣的壓縮存儲

（一）基本概念

1、壓縮存儲：指為多個值相同的元素只分配一個存儲空間，對零元素不分配存儲空間。其目的是節(jié)省存儲空間。

2、特殊矩陣：指具有許多相同矩陣元素或零元素，并且這些相同矩陣元素或零元素的分布有一定規(guī)律性的矩陣。常見的特殊矩陣有對稱矩陣、上(下)三角矩陣、對角矩陣等。

3、特殊矩陣的壓縮存儲方法：找出特殊矩陣中值相同的矩陣元素的分布規(guī)律，把那些呈現(xiàn)規(guī)律性分布的、值相同的多個矩陣元素壓縮存儲到一個存儲空間中。

（二）三對角矩陣

1、【2016統(tǒng)考真題】有一個 100 階的三對角矩陣 M，其元素?（1 ≤ i, j ≤ 100）按行優(yōu)先依次壓縮存入標(biāo)從 0 開始的一維數(shù)組中 N。元素? 在 N 中的下標(biāo)是（? ? B? ?）

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

解：三對角矩陣 A 如下所示：

（在三對角矩陣中，所有非零元素都集中在以主對角線為中心的 3 條對角線的區(qū)域，其他區(qū)域的元素都為零。）

采用壓縮存儲，將 3 條對角線上的元素，按行優(yōu)先方式存放在一維數(shù)組 B 中，且??存放于 B[0]中，其存儲形式如下所示：

可以計(jì)算矩陣 A 中 3 條對角線上的元素 （1 ≤ i, j ≤ 100, |i - j| <= 1）在一維數(shù)組 B 中存放的下標(biāo)為 k = 2i + j - 3。（下標(biāo)從 0 開始）

解法一：針對該題，僅需將數(shù)字逐一代入公式: k = 2 x 30 + 30 - 3 = 87，結(jié)果為87。

解法二：觀察上圖的三對角矩陣不難發(fā)現(xiàn)，第一行有兩個元素，剩下的在元素? 所在行之
前的 28 行（注意下標(biāo) 1 ≤ i，j ≤ 100）中，每行都有 3 個元素，而 ?之前僅有一個元素 ，?不難發(fā)現(xiàn)元素 ?在數(shù)組 N 中的下標(biāo)是 2 + 28x3 + 2 - 1 = 87。

（解法二中，減一是因?yàn)橐痪S數(shù)組 B 的下標(biāo)是從 0 開始。）

【注意】

解法一中的一維數(shù)組 B[k] 的下標(biāo)是從 0 開始。若是從 1 開始，則公式應(yīng)為?k = 2i + j - 2。

反過來，求 i , j ，有表如下：(三對角矩陣 A?從 1 開始)

一維數(shù)組 B下標(biāo)	從 0 開始	從 1 開始
i
j	k - 2i + 3	k - 2i + 2
k	2i + j - 3	2i + j - 2

?2、將三對角矩陣 A[1..100] 按行優(yōu)先存入一維數(shù)組 B[1..298] 中，A 中元素 A[66][65] 在數(shù)組B 中的位置 k 為(? ? ? B? ? ?)
A. 198? ? ? ? ? ? ? ? ? ? ? ? ?B. 195? ? ? ? ? ? ? ? ? ? ? ? ? C.197? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? D.196?

?解：一維數(shù)組 B[k] 的下標(biāo)是從 1 開始。由公式?k = 2i + j - 2，得 k = 2*66 + 65 - 2 = 195。

【另】反過來推導(dǎo)：已知 k 為 195 , 求?i , j：

（三）對稱矩陣和三角矩陣

1、若將 n 階上三角矩陣 A 按列優(yōu)先級壓縮存放在一維數(shù)組 B[1...n(n+1)/2+1] 中， 則存放到B[k] 中的非零元素 ?(1 ≤ i, j ≤ n) 的下標(biāo) i, j 與 k 的對應(yīng)關(guān)系是(? ? 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

解：按列優(yōu)先存儲，故元素 ?前面有 j - 1 列，

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

數(shù)組 B 的下標(biāo)是從 1 開始，因此 k = j ( j - 1 ) / 2 + i。

2、若將 n 階下三角矩陣 A 按列優(yōu)先順序壓縮存放在一維數(shù)組 B[1...n(n+1)/2+1] 中，則存放到 B[k] 中的非零元素??(1 ≤ i, j ≤ n) 的下標(biāo) i, j 與 k 的對應(yīng)關(guān)系是(? ? ?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

解：按列優(yōu)先存儲，故元素? 之前有 j - 1 列，

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

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

數(shù)組 B 下標(biāo)從 1 開始，k = (j - 1) (2n -?j + 2) / 2 + i - j + 1。

3、【2018統(tǒng)考真題】設(shè)有一個 12*12?對稱矩陣 M 的上三角部分的元素??(1 ≤ i ≤ j ≤ 10) 按行優(yōu)先存入 C 語言的一維數(shù)組 N 中， 元素 ?在 N 中的下標(biāo)是(? ? ?A? ? ?)。
A. 50? ? ? ? ? ? ? ? ? ? ? ? ? ? B. 51? ? ? ? ? ? ? ? ? ? ? ? C. 55? ? ? ? ? ? ? ? ? ? ? ? ? ? D. 66

解：?在 C 語言中，數(shù)組 N 的下標(biāo)從 0 開始。

第一個元素? 對應(yīng)存入 ，矩陣 M 的第一行有 12 元素，第二行有 11 個，第三行有 10 個，第四行有 9 個，第五行有 8 個，所以? 是第 12 + 11 + 10 + 9 + 8 + 1 = 51 個元素。

下標(biāo)應(yīng)為 50。
?

4、【2020統(tǒng)考真題】將一個10*10 對稱矩陣 M 的上三角部分的元素??(1 ≤ i ≤ j ≤ 12) 按列優(yōu)先存入 C 語言的一維數(shù)組 N 中， 元素 ?在 N 中的下標(biāo)是(? ? ?C? ? ?)。
A. 15? ??? ? ? ? ? ? ? ? ? ? ? ? B. 16? ? ? ? ? ? ? ? ? ? ? ? C. 22? ? ? ? ? ? ? ? ? ? ? ? ? ? D. 23

解： 因?yàn)槭菍ΨQ矩陣，要求元素 ?在 N 中的下標(biāo)，即求元素 ?在 N 中的下標(biāo)。

?在 C 語言中，數(shù)組 N 的下標(biāo)從 0 開始。

上三角矩陣按列優(yōu)先存儲，先存儲只有 1 個元素的第一列， 再存儲有 2 個元素的第二列，以此類推。在??之前存有
第 1 列: 1

第 2 列: 2

....

第 6 列: 6

第 7 列: 1

前面共存儲有 1 + 2 + 3 + 4 + 5 + 6 + 1 = 22 個元素 ( 數(shù)組下標(biāo)范圍為0 ~ 21 )，注意數(shù)組下標(biāo)從 0 開始，故 ?在數(shù)組N中的下標(biāo)為 22，即 ?在數(shù)組 N 中的下標(biāo)為 22。

三、稀疏矩陣

1、【2017統(tǒng)考真題】適用于壓縮存儲稀疏矩陣的兩種存儲結(jié)構(gòu)是(? ? ?A? ? ?)。
A. 三元組表和十字鏈表? ? ? ? ? ? ? ? ? ? ? ? ?B. 三元組表和鄰接矩陣
C. 十字鏈表和二叉鏈表? ? ? ? ? ? ? ? ? ? ? ? ?D. 鄰接矩陣和十字鏈表

解：稀疏矩陣：矩陣中非零元素的個數(shù) t，相對矩陣元素的個數(shù) s 來說非常少，即 s >> t 的矩陣。

（1）非零元素及其相應(yīng)的行和列構(gòu)成個三元組(行標(biāo)，列標(biāo)，值)，即三元組表的結(jié)點(diǎn)存儲了行 row、列 col、值 value 三種信息，是主要用來存儲稀疏矩陣的一種數(shù)據(jù)結(jié)構(gòu)。

（2）十字鏈表將行單鏈表和列單鏈表結(jié)合起來存儲稀疏矩陣。鄰接矩陣空間復(fù)雜度達(dá) ，不適合于存儲稀疏矩陣。

（3）二叉鏈表又名左孩子右兄弟表示法，可用于表示樹或森林。

所以，A正確。文章來源地址http://www.zghlxwxcb.cn/news/detail-778402.html

到了這里，關(guān)于【考研】數(shù)據(jù)結(jié)構(gòu)——特殊矩陣的壓縮存儲（含真題）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！