若将n阶下三角矩阵A按列优先顺序压缩存放在一维数组B[0..n(n+1)/2-1]中,A中第一个非0元素A[1][1]存于数组B[0]中,则应存放到B[k]中的非0元素A[i]j的下标i,j与k的对应关系是
时间: 2023-08-31 11:36:22 浏览: 305
用一维数组表现的顺序存储结构
### 回答1:
对于下三角矩阵,只有当 $i \geq j$ 时,$A_{i,j}$ 才可能是非零元素。因此,我们可以按照列优先顺序将下三角矩阵压缩成一个一维数组 $B$,存储非零元素 $A_{i,j}$ 的下标 $i,j$ 与 $B$ 中的下标 $k$ 的对应关系如下:
$$
k = \frac{i(i-1)}{2} + j - 1
$$
其中,$i$ 和 $j$ 是非零元素 $A_{i,j}$ 的行列下标,$k$ 是 $A_{i,j}$ 在一维数组 $B$ 中的下标。因为第 $i$ 行前面有 $i-1$ 行,每行元素个数分别为 $1,2,\cdots,i-1,i$,所以前 $i-1$ 行的元素个数之和为 $\frac{i(i-1)}{2}$,再加上 $j-1$ 即为 $A_{i,j}$ 在一维数组 $B$ 中的下标 $k$。
### 回答2:
对于下三角矩阵A,元素A[i][j](1≤i≤n,1≤j≤n)满足i≥j,即只有当i大于等于j时,A[i][j]才可能是非零元素。
由于下三角矩阵A按列优先顺序压缩存放在一维数组B中,每一列中的元素按照从上到下的顺序依次存放。
设非零元素A[i][j]存放到数组B中的下标为k,则我们可以分析k与i,j之间的关系。
首先,对于第j列的元素,它的上面有j-1列,每一列的元素个数分别为1, 2, ... , j-1。因此,前j-1列元素的总数量为1+2+...+(j-1)=(j-1) * j / 2。
而第j列中的第i个元素A[i][j]的上方有i-1个非零元素,因此,我们可以得到第j列中的第i个元素在数组B中的下标为k = (j-1) * j / 2 + i - 1。
综上所述,非零元素A[i][j]在数组B中的下标k与i,j之间的对应关系是k = (j-1) * j / 2 + i - 1。
### 回答3:
若将n阶下三角矩阵A按列优先顺序压缩存放在一维数组B[0..n(n 1)/2-1]中,A中第一个非0元素A[1][1]存于数组B[0]中,则应存放到B[k]中的非0元素A[i][j]的下标i,j与k的对应关系是:
设矩阵A的行数为n,下标i,j为矩阵A中某一个元素的下标,下标k为数组B中某一个元素的下标。
矩阵A是下三角矩阵,即只有对角线上方的元素为0,所以当i > j 时,A[i][j]一定为0。而对角线及对角线以下的元素不为0。
对于B数组,按列优先存放矩阵A的元素,即先存放第一列的所有元素,再存放第二列的所有元素,以此类推。因此,对于B中的第k个元素,它与矩阵A中的第i行第j列的元素是对应的。
那么如何确定i和j的值呢?
我们可以根据k的值反推出i和j的值。首先,根据k的值可以确定i的值,因为B中的元素是按列优先存放的,所以当k为0时,对应的元素肯定是矩阵A中的第一个非0元素,也就是A[1][1]。当k为1时,对应的元素是矩阵A中第二列的第一个非0元素,也就是A[2][1],以此类推,当k为2时,对应的元素是矩阵A中第三列的第一个非0元素,也就是A[3][1]。
可以发现,k的值和i的值是存在对应关系的,即i = k + 1。
然后,再根据k的值可以确定j的值,因为矩阵A是下三角矩阵,所以对于每一列来说,元素A[k+1][j]都是矩阵A中第k+1行的第一个非0元素,即j = k + 1。
综上所述,若将n阶下三角矩阵A按列优先顺序压缩存放在一维数组B[0..n(n 1)/2-1]中,A中第一个非0元素A[1][1]存于数组B[0]中时,应存放到B[k]中的非0元素A[i][j]的下标i,j与k的对应关系为i = k + 1,j = k + 1。
阅读全文