# 数组习题

## 三对角矩阵

**例题** 有一个$100$阶的三对角矩阵$M$，其元素$m_{i,j}$（$1\leqslant i,j\leqslant100$）按行优先依次压缩存入下标从$0$开始的一维数组$N$中。元素$m_{30,30}$在$N$中的下标是()。

$A.86$

$B.87$

$C.88$

$D.89$

解：$B$。根据公式$k=2i+j-3$。但是这种公式很难记忆，所以直接找规律。观察三对角矩阵不难发现，第一行有两个元素，剩下的在元素$m_{30,30}$所在行之前的$28$行中，每行都有$3$个元素，而$m_{30,30}$之前仅有一个元素$m_{30,29}$，不难发现元素$m_{30,30}$在数组$N$中的下标是$2+28\times3+2-1=87$。

**例题** 若将$n$阶上三角矩阵$A$按列优先级压缩存放在一维数组$B[1\cdots n(n+1)/2+1]$中，则存放到$B[k]$中的非零元素$a_{i,j}（$1\leqslant i,j\leqslant n$）的下标$i$、$j$与$k$的对应关系是()。

$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$

解：$C$。按列优先存储，故元素$a$，前面有$j-1$列，共有$1+2+3+\cdots+j-1=j(j-1)/2$个元素，元素$a_{i,j}$在第$j$列上是第$i$个元素，数组$B$的下标是从$1$开始，因此$k=j(j-1)/2+i$。

**例题** 若将$n$阶下三角矩阵$A$按列优先顺序压缩存放在一维数组$B[1\cdots n(n+1)/2+1]$中，则存放到$B[k]$中的非零元素$a_{i,j}$（$1\leqslant i,j\leqslant n$）的下标$i,j$与$k$的对应关系是()。

$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$

解：$B$。按列优先存储，故元素$a_{i,j}$之前有$j-1$列，共有$n+(n-1)+\cdots+(n-j+2)=(j-1)(2n-j+2)/2$个元素，元素$a_{i,j}$是第$j$列上第$i-j+1$个元素，数组$B$下标从$1$开始，$k=(j-1)(2n-j+2)/2+i-j+1$。

**例题** 设有一个$12\times12$的对称矩阵$M$，将其上三角部分的元素$m_{i,j}$（$1\leqslant i\leqslant j\leqslant12$）按行优先存入$C$语言的一维数组$N$中，元素$m_{7,2}$在$N$中的下标是()。

$A.50$

$B.51$

$C.55$

$D.66$

解：$A$。在$C$语言中，数组$N$的下标从$0$开始。第一个元素$m_{1,1}$对应存入$n_0$，矩阵$M$的第一行有$12$个元素，第二行有$11$个，第三行有$10$个，第四行有$9$个，第五行有$8$个，所以$m_{6,6}$。是第$12+11+10+9+8+1=51$个元素，下标应为$50$。