第一部分：矩阵
矩阵在线性代数中已经有过详细了解，在考研中矩阵部分常常考察数组下标 k 与 矩阵行 i 和列 j 的关系。
需要注意的是矩阵下标 i、j 通常是：
1
到
n
1到n
1到n，而数组下标 k 通常是：
0
到
n
2
−
1
0到n^2-1
0到n2−1。
- k 与 i、j 的关系就是： k = n ∗ ( i − 1 ) + j − 1 k=n*(i-1)+j-1 k=n∗(i−1)+j−1
第一部分习题
- 数组A中，每个元素的长度为3个字节，行下标 i 从1到8，列下标 j 从1到10，从首地址SA开始连续存放的存储器内，该数组按行存放，元素 A[8][5] 的起始地址为（C）。
A.SA+141
B.SA+144
C.SA+222（用公式可以求出 A 85 A_{85} A85前面有74个元素，所以它的起始地址就是： S A + 74 ∗ 3 SA+74*3 SA+74∗3）
D.SA+225 - 设二维数组 A[1…m,1…n] 按行存储在数组B中，则二维数组元素 A[i,j] 在一维数组B中的下标为（A）。
A.n*(i-1)+j（题目中没有强调数组B的下标从0开始，再结合其他选项只能选A）
B.n*(i-1)-j-1（迷惑性选项，“- j”必然是错的）
C.i*(j-1)
D.i*m+i-1
第二部分：对称矩阵
对称矩阵就是主对角线两侧的数据相同的方阵，对于这类矩阵我们通常可以节约空间，只存储上三角部分的数据或下三角部分的数据。
- 此时数组下标 k 与 矩阵行 i 和列 j 的关系通常满足（上三角转置后就是下三角了）： k 下三角 = S i − 1 + j − 1 k 上三角 = S j − 1 + i − 1 k_{下三角}=S_{i-1}+j-1\\k_{上三角}=S_{j-1}+i-1 k下三角=Si−1+j−1k上三角=Sj−1+i−1
- 在之前数组存储普通矩阵的表达式中 S x = x ∗ n S_x=x*n Sx=x∗n，n为矩阵的总列数；而这里因为存储的是上/下三角矩阵，所以结合等差数列求和公式有： S x = x ∗ ( x + 1 ) 2 S_{x}=\frac{x*(x+1)}{2} Sx=2x∗(x+1)
需要注意的是，为了达到转置的效果，上三角矩阵需要按列存储到数组当中（转置时列会变为行）。结合上面的两个式子可以得出以下关系：
第二部分习题
- 设有一个对称矩阵A，采用压缩存储方式，以行序为主序存储A11为第一个元素其存储地址为1，每个元素占一个地址空间，则A85地址为（B） 。
A.23
B.33 （前面的元素个数：k=8*(8-1)/2+5-1=32，地址为：1+k*1=33）
C.18
D.40
第三部分：三角矩阵
三角矩阵分为下三角矩阵和上三角矩阵，需要和对称矩阵的上下三角矩阵区分。
- 下三角矩阵：下三角为权值，上三角全相同（例如全为0或1）
- 上三角矩阵：上三角为权值，下三角全相同（例如全为0或1）
此时数组除了需要存储上/下三角区域当中的权值，还需要增加一个位置，记录余下的相同数据（保存一份即可）。
- 下三角矩阵中元素对应的数组下标： { k 权值区域 = i ∗ ( i − 1 ) 2 + j − 1 （ i ≥ j ） k 相同区域 = n ∗ ( n + 1 ) 2 （ i < j ） \begin{cases}k_{权值区域}=\frac{i*(i-1)}{2}+j-1&（i \geq j）\\\\k_{相同区域}=\frac{n*(n+1)}{2}&（i < j）\end{cases} ⎩ ⎨ ⎧k权值区域=2i∗(i−1)+j−1k相同区域=2n∗(n+1)（i≥j）（i<j）
- 上三角矩阵中元素对应的数组下标： { k 权值区域 = j ∗ ( j − 1 ) 2 + i − 1 （ i ≤ j ） k 相同区域 = n ∗ ( n + 1 ) 2 （ i > j ） \begin{cases}k_{权值区域}=\frac{j*(j-1)}{2}+i-1&（i \leq j）\\\\k_{相同区域}=\frac{n*(n+1)}{2}&（i > j）\end{cases} ⎩ ⎨ ⎧k权值区域=2j∗(j−1)+i−1k相同区域=2n∗(n+1)（i≤j）（i>j）
其中权值区域的最大下标为： k n n = n ∗ ( n − 1 ) 2 + n − 1 = n ∗ ( n + 1 ) 2 − 1 （ i = j = n ） k_{nn}=\frac{n*(n-1)}{2}+n-1=\frac{n*(n+1)}{2}-1 \quad（i=j=n） knn=2n∗(n−1)+n−1=2n∗(n+1)−1（i=j=n）
第三部分习题
- 若将 n 阶下三角矩阵 A 按列优先顺序压缩存放在一维数组 B[1…n(n+1)/2+1] 中,则存放到 B[k] 中的非零元素 aij（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（题目中说了数组B下标从1开始，所以不需要减1）
C.(j-1)(2n-j+2)/2+i-j
D.(j-1)(2n-j+ 1)/2+i-j-1
【分析】下三角按列优先顺序压缩与上三角按行优先顺序压缩一样，需要进行等差数列的反向求和，具体过程见下图：（图中为本题的下三角按列压缩，要求上三角按行压缩只需要进行转置——互换 i 和 j 位置）
第四部分：三对角矩阵
三对角矩阵也可称为“爪型”矩阵、带状矩阵，它的特点就是当
∣
i
−
j
∣
>
1
|i-j|>1
∣i−j∣>1时
A
i
j
=
0
A_{ij}=0
Aij=0。
第四部分习题
- 有一个100阶的三对角矩阵
M
M
M，其元素
m
i
j
m_{ij}
mij（1<= i，j<=100）按行优先依次压缩存入下标从0开始的一维数组
N
N
N中。元素
m
30
,
30
m_{30,30}
m30,30在N中的下标是（B）。
A.86
B.87（套公式：2*30+30-3=87）
C.88
D.89
第五部分：稀疏矩阵
当矩阵中非零元素的个数远少于矩阵元素个数时，我们就将其称为稀疏矩阵。
稀疏矩阵—般的压缩存储方式有两种：三元组和十字链表。以下主要介绍三元组，十字链表在图的部分会介绍。
三元组看似是多此一举的把一个矩阵变成了另一个矩阵，但是当原矩阵维数非常大，但却是一个稀疏矩阵时，三元组可以非常有效的压缩数据，并且三元组本身也可以进一步压缩成一元数组。
需要注意的是，稀疏矩阵在压缩存储后便失去了随机存取的特性。
第五部分习题
-
稀疏矩阵—般的压缩存储方式有两种，即（C）。
A.二维数组和三维数组
B.三元组和散列
C.三元组和十字链表
D.散列和十字链表 -
有一个100×90的稀疏矩阵，非0元素有10个，设每个整型数占2个字节，将稀疏矩阵压缩到三元组表data中时，我们用 data[0].i，data[0].j，data[0].v 分别存放矩阵行数、列数和非零元个数，总共需要的字节数是（B）。
A.20
B.66（题目的描述存在陷阱，数组下标为0的地方存储了总行数、总列数、总非零元个数，一共消耗了6字节）
C.18000
D.33文章来源：https://www.toymoban.com/news/detail-724645.html
小结
矩阵部分主要包含了四类矩阵，考察点就是矩阵数据压缩到数组里时，不同矩阵元素对应的数组下标，分值占比不高。
文章来源地址https://www.toymoban.com/news/detail-724645.html
到了这里，关于数据结构复盘——第四章：数组和矩阵的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
