【数据结构】数组的顺序存储(1、2、3、n维数组的元素地址计算) |
您所在的位置:网站首页 › 二维数组按什么存储结构形式 › 【数据结构】数组的顺序存储(1、2、3、n维数组的元素地址计算) |
数组是一种特殊的的数据结构,在存储结构是顺序存储(一个连着一个),所有只要给定数组的维度,和各维度的长度,数组中元素个数就是确定的。且给出首元素的地址,例如根据A[i][j][k],的i、j、k就可以计算出该元素的地址(或与首元素的地址之差) 在计算机中,内存储器的结构是一维的。 对于一维数组,可以直接按照顺序直接存储对于常见的二维数组,通常采用两种方式实现物理结构上的一维顺序存储 行优先:一行一行的存储,存完一行,再在这一行尾元素后面接着存储下一行列优先、 三维数组:三维数组元素的下标号由三个数字组成:即行、列、纵 3个方向 下面的图片是以行为主序的方法存放![]() 🥕总之,知道了多维数组的维度、每维度的上下限,就可以把多维数组的元素按照一维的顺序存储,存储在计算机中。 同样,根据数组的下标,可以计算出其在计算机中的位置(地址),这是重点和难点。 下面我将分别从 一维数组的地址计算二维数组的地址计算三维数组的地址计算3个方面来详细讲解 🍊二、一维数组的地址计算一维数组的本质其实就是线性表,它的存储非常简单 假设一维数组的元素为:(我们假设A数组下标从1开始) A = a 1 , a 2 , a 3 , a 4... a i A = a1,a2,a3,a4 ... ai A=a1,a2,a3,a4...ai 假设每个元素占用size个字节(存储单元),那么ai的存储地址为:首元素地址 + (该元素和首元素相差元素个数)× size 图形结合来理解(黄色的箭头就是地址(指针 🥕 ai的存储地址计算公式 L o c ( A [ i ] ) = L o c ( A [ 1 ] ) + ( i − 1 ) × s i z e Loc(A[i]) = Loc(A[1]) + (i-1)×size Loc(A[i])=Loc(A[1])+(i−1)×size 🍊三、二维数组的地址计算二维数组分行优先和列优先,原理都是一样的。这里我们按照行优先,A数组下标从(1,1)开始 假设每个元素占用size个字节(存储单元),那么A[i][j]的存储地址为:首元素地址 + (该元素和首元素相差元素个数)× size 这个i-1和j-1的减去这个1,代表的起使分别是起使元素下标A[1][1]中的两个1 i - 1表示相差的行数,× 一行元素个数,表示i这一行之前所差的所有元素个数j-1表示的是只考虑i这一行,A[i][j]所相差元素个数理解了这个,当A数组首元素下标从(0,0)开始,可以很轻松的写出相应的公式了! 🥕 A[i][j]的存储地址计算公式(行优先) L o c ( A [ i ] [ j ] ) = L o c ( A [ 1 ] [ 1 ] ) + ( n ( i − 1 ) + j − 1 ) × s i z e Loc(A[i][j]) = Loc(A[1][1]) + (n(i-1) + j -1)×size Loc(A[i][j])=Loc(A[1][1])+(n(i−1)+j−1)×size 🍊四、三维数组的地址计算关于三维数组的理解方式,我是这样理解的:
A [ 1.. r ] [ 1.. m ] [ 1.. n ] A[1..r][1..m][1..n] A[1..r][1..m][1..n] 假定每个元素占size个存储单位,并且按照行优先(就是我假设的那个把三维数组看成一个二维数组的那个行,体现在三维数组中,起使就是m*n的平面,每次r+1其实就跳过了m*n这个平面中这么多元素!) 🥕理解&推导(行优先) 首元素的地址为Loc(A[1][1][1]) 对于A[i][1][1]的地址,因为该元素前面有i-1个m*n的平面的元素,所以 L o c ( A [ i ] [ 1 ] [ 1 ] ) = L o c ( A [ 1 ] [ 1 ] [ 1 ] ) + ( ( i − 1 ) × m × n ) × s i z e Loc(A[i][1][1]) = Loc(A[1][1][1]) + ( (i-1)×m×n)×size Loc(A[i][1][1])=Loc(A[1][1][1])+((i−1)×m×n)×size对于A[i][j][1]的地址,则在上面元素个数((i-1)×m×n)基础上,再加j-1个“元素”,上面我说道,三维数组看作二维数组,一个元素,可以看作是长度为纵维度长度,即n的一个一维数组;所以需要加上(j-1)×n所以A[i][j][k]就在上面两个答案累加的基础上加上该元素所在纵维度的没有算的k-1个元素即可🥕 A[i][j][k]的存储地址计算公式(行优先) L o c ( A [ i ] [ j ] [ k ] ) = L o c ( A [ 1 ] [ 1 ] [ 1 ] ) + ( ( i − 1 ) × m × n + ( j − 1 ) × n + k − 1 ) × s i z e Loc(A[i][j][k]) = Loc(A[1][1][1]) + ( (i-1)×m×n+(j-1)×n + k-1)×size Loc(A[i][j][k])=Loc(A[1][1][1])+((i−1)×m×n+(j−1)×n+k−1)×size 🍊五、n维数组的地址计算对于n维度数组 A [ c 1.. d 1 , c 2.. d 2 , c 3.. d 3 , . . . , c n . . d n ] A[c1..d1,c2..d2,c3..d3,...,cn..dn] A[c1..d1,c2..d2,c3..d3,...,cn..dn] 🥕 A[j1][j2]...[jn]的存储地址计算公式(行优先) L o c ( A [ j 1 ] [ j 2 ] . . . [ j n ] ) = L o c ( A [ c 1 ] [ c 2 ] . . . [ c n ] ) + ∑ i = 1 n a i × ( j i − c i ) Loc(A[j1][j2]...[jn]) = Loc(A[c1][c2]...[cn]) +\sum\limits_{i=1}^{n}ai×(ji-ci) Loc(A[j1][j2]...[jn])=Loc(A[c1][c2]...[cn])+i=1∑nai×(ji−ci) 其中: a i = s i z e × ∏ k = i + 1 n ( d k − c k + 1 ) , 1 < = i < = n ai = size×\prod\limits_{k=i+1}^{n}(dk-ck+1),1 |
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |