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


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

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

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

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

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

所以数组下标从$1$开始时,下标

$$ k=\begin{cases} \frac{(i-1)[n-(i-1)+1+n]}{2}+j-i+1& \text{i ≤ j} \\ \frac{(j-1)[n-(j-1)+1+n]}{2}+i-j+1& \text{i>j} \end{cases} $$

从0开始时,$$ k= \begin{cases} \frac{(i-1)[n-(i-1)+1+n]}{2}+j-i& \text{i ≤ j} \\ \frac{(j-1)[n-(j-1)+1+n]}{2}+i-j& \text{i>j} \end{cases} $$

下三角:

第一行有$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$

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

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


Just For Fun...