数据结构中数组下标计算和矩阵压缩存储下标计算


因涉及到公式排版,建议使用电脑浏览,手机浏览可长按公式,选择 Math Settings -> Zoom Trigger -> Double-Click,然后双击即可左右滑动查看完整公式。

数据结构复习到数组和矩阵压缩存储这个地方,下标计算是考研常考的问题,对于下标计算公式感觉辅导书上不是特别全,在网上没有找到我满意的总结文章,这里归纳一下,其他考研需求的小伙伴也可以看一下,部分公式是我自己归纳总结的,如果存在错误还请评论告知。

公式太多,一天的复习计划之后实在太累,懒得letex排版了,先占个坑,后续补上。

2021-7-21:更新了一部分,未更新完。部分公式渲染异常,太累了,有空再修复。。。
2021-7-31:更新完成。

数组地址计算 (有点小问题,还未修改)

$$ LOC(j_1, j_2, ..., j_n)=LOC(L_1, L_2, ..., L_n) + (\begin{equation*} \sum_{i=1}^nj_i \end{equation*} \prod_{k=i+1}^n D_k) * SIZE $$

其中$ D_k $为第$k$维度的长度,$D_k= H_k-L_k+1$,$H_k$为第$k$维度右边界,$L_k$为第$k$维度左边界,$SIZE$为一个元素所占存储单元

来个例题(一个题集里的题目,这里有点小问题,发邮件和题集作者讨论了一下,还未修改):

按行优先存储的四维数组$A=array[1...10, 1...5, 1...7, 1..8]$,设每个数据元素占用2个存储单元,基地址为10,则$A[3,4,5,6]$的存储位置为(B

A. 2110 B.2230 C.2120 D.2220

解答:
$$LOC(3,4,5,6)= \\ LOC(1,1,1,1)+[3*(5-1+1)*(7-1+1)*(8-1+1) + 4*(7-1+1)*(8-1+1) + 5*(8-1+1) + 6]*2 \\ =10+(840+224+40+6)*2 \\ =2230 $$

按列存储:

$$ LOC(j_1, j_2, ..., j_n)=LOC(L_1, L_2, ..., L_n)+ (\begin{equation*} \sum_{i=0}^{n-1}j_{n-i} \end{equation*} \prod_{k=i+1}^{n-1}D_{n-k}) * SIZE $$

对称矩阵压缩存储

形如:

元素关于红线对称。

存储$n$阶矩阵需要空间为:$\frac{n(n-1)}{2}$

按行存储:

上三角(只看上半部分):

第一行有$n$个元素

第$i-1$行有$n-(i-1)+1$个元素

故前$i-1$行共 有$n-(i-1)+1+n-(i-2)+1+\cdot\cdot\cdot+n=\frac{(i-1)[n-(i-1)+1+n]}{2}$个

第$i$行第$j$个元素,在第$i$行是第$(j-i+1)$个元素

所以$a_{ij}$是第$\frac{(i-1)[n-(i-1)+1+n]}{2}+j-i+1$个

因为对称矩阵的对称性,$a_{ij} = a_{ji}$

所以数组下标$$k= \left \{ \begin{matrix}
\quad \quad 下标从1开始: \left \{ \begin{matrix}
\frac{(i-1)[n-(i-1)+1+n]}{2}+j-i+1 & i ≤ j \\
\frac{(j-1)[n-(j-1)+1+n]}{2}+i-j+1 & i>j
\end{matrix} \right.& \\
下标从0开始: \left\{\begin{matrix}
\frac{(i-1)[n-(i-1)+1+n]}{2}+j-i & i ≤ j \\
\frac{(j-1)[n-(j-1)+1+n]}{2}+i-j & i>j
\end{matrix} \right.&
\end{matrix} \right.$$

下三角(只看下半部分):

第一行有$1$个元素

第二行有$2$个元素

第$i-1$行有$i-1$个元素

故前$(i-1)$行共有$\frac{(i-1)(1+i-1)}{2}= \frac{i(i-1)}{2}$个元素

$a_{ij}$是第$i$行第$j$个元素

所以$a_{ij}$是第$\frac{i(i-1)}{2} + j$个

故下标$$ k= \left \{ \begin{matrix}
下标从1开始: \left \{ \begin{matrix}
\frac{i(i-1)}{2}+j & i ≥ j \\
\frac{j(j-1)}{2}+i & i<j
\end{matrix}\right.& \\
\quad \quad下标从0开始: \left \{ \begin{matrix}
\frac{i(i-1)}{2}+j-1 & i ≥ j \\
\frac{j(j-1)}{2}+i-1 & i
\end{matrix} \right.&
\end{matrix} \right. $$

按列存储(和按行存储的计算公式类比记忆——对应关系:行上-列下,行下-列上)

上三角

前$(j-1)$列共$\frac{j(j-1)}{2}$个(等差数列求和可得)

第$j$列第$i$个元素为本列第$i$个

$\Rightarrow a_{ij}是第\frac{j(j-1)}{2}+i$个

故下标$$k= \left \{ \begin{matrix}
下标从1开始: \left\{ \begin{matrix}
\frac{j(j-1)}{2}+i & i ≤ j \\
\frac{i(i-1)}{2}+j & i>j
\end{matrix}\right.& \\
\quad\quad 下标从0开始: \left \{ \begin{matrix}
\frac{j(j-1)}{2}+i-1 & i ≤ j \\
\frac{i(i-1)}{2}+j-1 & i>j
\end{matrix}\right.&
\end{matrix}\right.$$

下三角

前$j-1$列共 有$n-(j-1)+1+n-(j-2)+1+ \cdot \cdot \cdot +n= \frac{(j-1)[n-(j-1)+1+n]}{2}$个

第$j$列第$i$个元素是本列第$i-j+1$个元素

$\Rightarrow a_{ij}$是第$\frac{(j-1)[n-(j-1)+1+n]}{2}+i-j+1$个

所以数组下标$$k=\left\{\begin{matrix}
\quad \quad下标从1开始: \left\{\begin{matrix}
\frac{(j-1)[n-(j-1)+1+n]}{2}+i-j+1 & i ≥ j \\
\frac{(i-1)[n-(i-1)+1+n]}{2}+j-i+1 & i<j
\end{matrix} \right.& \\
下标从0开始: \left\{\begin{matrix}
\frac{(j-1)[n-(j-1)+1+n]}{2}+i-j & i ≥ j \\
\frac{(i-1)[n-(i-1)+1+n]}{2}+j-i & i<j
\end{matrix}\right.&
\end{matrix}\right.$$

三角矩阵(与对称矩阵类似,半角+一个常数)

形如:

$$ \begin{bmatrix}
a_{11} &a_{12} &a_{13} \\
c& a_{22} & a_{23} \\
c& c & a_{33} \\
\end{bmatrix} $$

一半有不同元素,另一半都是$c$。

压缩存储三角矩阵所需空间为:

$$\frac{n(n+1)}{2}+1$$

按行存储

上三角矩阵

$$k= \left \{ \begin{matrix}
\quad \quad下标从1开始: \left \{ \begin{matrix}
\frac{(i-1)[n-(i-1)+1+n]}{2}+j-i+1 & i ≤ j \\
\frac{n(n+1)}{2}+1 & i>j
\end{matrix}\right.& \\
下标从0开始: \left \{ \begin{matrix}
\frac{(i-1)[n-(i-1)+1+n]}{2}+j-i & i ≤ j \\
\frac{n(n+1)}{2} & i>j
\end{matrix} \right.&
\end{matrix} \right.$$

下三角矩阵

$$k= \left \{ \begin{matrix}
下标从1开始: \left \{ \begin{matrix}
\frac{n(n+1)}{2}+1 & i < j \\
\frac{i(i-1)}{2}+j & i≥j
\end{matrix}\right.& \\
\quad下标从0开始: \left \{ \begin{matrix}
\frac{n(n+1)}{2} & i<j \\
\frac{i(i-1)}{2}+j-1 & i≥j
\end{matrix} \right.&
\end{matrix} \right.$$

按列存储

上三角矩阵

$$k= \left \{ \begin{matrix}
下标从1开始: \left \{ \begin{matrix}
\frac{n(n+1)}{2}+1 & i > j \\
\frac{j(j-1)}{2}+i & i≤j
\end{matrix}\right.& \\
\quad下标从0开始: \left \{ \begin{matrix}
\frac{n(n+1)}{2} & i > j \\
\frac{j(j-1)}{2}+i-1 & i≤j
\end{matrix} \right.&
\end{matrix} \right.$$

下三角矩阵

$$ k= \left \{ \begin{matrix}
\quad \quad下标从1开始: \left \{ \begin{matrix}
\frac{(j-1)[n-(j-1)+1+n]}{2}+i-j+1 & i ≥ j \\
\frac{n(n+1)}{2}+1 & i<j
\end{matrix} \right.& \\
下标从0开始: \left \{ \begin{matrix}
\frac{(j-1)[n-(j-1)+1+n]}{2}+i-j & i ≥ j \\
\frac{n(n+1)}{2} & i<j
\end{matrix} \right.&
\end{matrix} \right. $$

$m$阶$n$对角矩阵

形如:

上图所示为$4$阶三对角矩阵。

压缩存储$n$对角矩阵需要空间:$n(m-2) + 2(n-1)$,公式理解:第一行和最后一行有$n-1$个元素,其余$m-2$行每行有$n$个元素。

非零元素角标$i,j$得关系:$j=k+i, 1≤k≤ \left \lfloor \frac{n}{2} \right \rfloor$,$k为整数,不满足此关系得$$a_{ij}$均为$0$。

按行存储

第一行$n-1$个,第$2至i-1$行每行$n$个

$\Rightarrow 前i-1行共n(i-2)+n-1个$

第$i$行第$j$个是本行第$j-i+\left \lceil \frac{n}{2} \right \rceil$个

$\Rightarrow a_{ij}是本第n(i-2)+n-1+j-i+\left \lceil \frac{n}{2} \right \rceil$个

故$k = \left \{ \begin{matrix}
下标从1开始:(n-1)i+j+\left \lceil \frac{n}{2} \right \rceil-n-1& \\
下标从0开始:(n-1)i+j+\left \lceil \frac{n}{2} \right \rceil-n-2&
\end{matrix} \right.$

声明:楓の街|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - 数据结构中数组下标计算和矩阵压缩存储下标计算


Just For Fun...