数组元素存储地址的计算
- 格式：doc
- 大小：284.00 KB
- 文档页数：8
数组元素存储地址的计算 一维数组设一维数组A[n]存放在n 个连续的存储单元中，每个数组元素占一个存储单元（不妨设为C 个连续字节）. 如果数组元素A[0]的首地址是L ，则A[1]的首地址是L+C ，A[2]的首地址是L+2C ，… …，依次类推，对于01≤≤-in 有：C i A Loc i A Loc *])0[(])[(+=二维数组二维数组的每个元素含两个下标，如果将二维数组的第一个下标理解为行号，第二个下标理解为列号，然后按行列次序排列个元素，则二维数组呈阵列形状。
例如mnm m nn a a a a a a a a a A ΛΛΛΛ212222111211=它是一个行号为1~m ，列号为1~n 的二维数组元素阵列。
如何保存二维数组？ 首先要确定一个顺序222120121110020100a a a a a a a a a B = 222120121110020100a a a a a a a a a B = 222120121110020100a a a a a a a a a B = 222120121110020100a a a a a a a a a第0行 第1行 第2行222120121110020100a a a a a a a a a B = 222120121110020100aa aaa a aa a B =222120121110020100a a a a a a a a a B =221202211101201000a a a a a a a a a第0列 第1列 第2列222120121110020100a a a a a a a a a B = 221202a a a a a B = B =B B 021*******00211020a a a a a a a a a设count 为数组B 中元素的个数，则count=9 按行优先存储按列优先存储地址如何计算？所谓按行优先顺序，就是将数组元素按行向量的顺序存储，第1i个行向量存储在第i个行向量之后。
下面我们计算二维数组A m n[][]中任一元素A[i][j]的存储地址，设每个数组元素所占空间为C个连续字节。
显然，A[i][j]是第i个行向量B[i]中的第j个元素。
在A[i][j]之前的元素个数为u，分别是A[0][0]，A[0][1]，A[0][2]，…，A[0][n]，A[1][0]，A[1][1]，A[1][2]，…，A[1][n]，…，A[i-1][0]，A[i-1][1]，A[i-1][2]，…，A[i-1][n]，A[i][0]，A[i][1]，A[i][2]，…，A[i][j-1]设每个数组元素所占空间为C个连续字节。
则Loc（A[i][j]）=Loc（A[0][0]）+u*Cu=?前i行（第0行到第i-1行）（每行n个元素）的元素个数+第i 行的元素个数（A[i][0]到A[i][j-1]）因此，u=i*n+j故Loc（A[i][j]）=Loc（A[0][0]）+u*C=Loc（A[0][0]）+（i*n+j）*C按列优先存储地址如何计算？在A[i][j]之前的元素个数为v，分别是A[0][0]，A[1][0]，A[2][0]，…，A[m][0]，A[0][1]，A[1][1]，A[2][1]，…，A[m][1]，…，A[0][j-1]，A[1][j-1]，A[2][j-1]，…，A[m][j-1]，A[0][j]，A[1][j]，A[2][j]，…，A[i-1][j]设每个数组元素所占空间为C个连续字节。
则Loc（A[i][j]）=Loc（A[0][0]）+v*Cv=?前j列（第0列到第j-1列）（每列m个元素）的元素个数+第j 列的元素个数（A[0][j]到A[i-1][j]）因此，v=j*m+i故Loc （A[i][j]）=Loc （A[0][0]）+v*C=Loc （A[0][0]）+（j*m+i ）*C高维数组按行优先：“左”下标优先，即第一（最左）下标的下标值较小的元素较先存储，第一个下标值相同者，按第二下标优先存储，对任意的k>1，对第1~（k-1）维相同者，先存储第k 维中下标值较小者。
按列优先：“右”下标优先（最后一维下标为最右），先存储第n 维下标值较小者，第n 维下标值相同者，先存储第n-1维下标值较小者。
三维数组D[3][3][4]的顺序存储次序是元素表示为D[i][j][k] 其中，0≤i ≤2，0≤j ≤2，0≤k ≤3，可以把它看作一维数组B 1[3] = { D[0][3][4]，D[1][3][4]，D[2][3][4] }D[0][0][0]，D[0][0][1]，D[0][0][2]，D[0][0][3] D[0][1][0]，D[0][1][1]，D[0][1][2]，D[0][1][3] D[0][2][0]，D[0][2][1]，D[0][2][2]，D[0][2][3]D[1][0][0]，D[1][0][1]，D[1][0][2]，D[1][0][3] D[1][1][0]，D[1][1][1]，D[1][1][2]，D[1][1][3] D[1][2][0]，D[1][2][1]，D[1][2][2]，D[1][2][3]D[2][0][0]，D[2][0][1]，D[2][0][2]，D[2][0][3] D[2][1][0]，D[2][1][1]，D[2][1][2]，D[2][1][3] D[2][2][0]，D[2][2][1]，D[2][2][2]，D[2][2][3]D[0][3][4]i=0D[1][3][4]i=1D[2][3][4]i=2For x=0 to 2 do For y=0 to 2 do For z=0 to 3 do D[i][j][k]的地址：Loc （D[i][j][k]）=Loc （D[0][0][0]）+w*C 第一个下标的变化：0到i-1，共i*3*4个元素第一个下标为i 时，第二个下标的变化：0到j-1，共j*4个元素 第一个下标为i ，第二个下标为j 时，第三个下标的变化：0到k-1，共k 个元素 w= i*3*4+j*4+kLoc （D[i][j][k]）=Loc （D[0][0][0]）+w*C=Loc （D[0][0][0]）+（i*3*4+j*4+k ）*CFor z=0 to 3 do For y=0 to 2 do For x=0 to 2 do221202211101201000a a a a a a a a aD[0][0][0]，D[1][0][0]，D[2][0][0] D[0][1][0]，D[1][1][0]，D[2][1][0] D[0][2][0]，D[1][2][0]，D[2][2][0]D[0][0][1]，D[1][0][1]，D[2][0][1] D[0][1][1]，D[1][1][1]，D[2][1][1] D[0][2][1]，D[1][2][1]，D[2][2][1]D[0][0][2]，D[1][0][2]，D[2][0][2] D[0][1][2]，D[1][1][2]，D[2][1][2] D[0][2][2]，D[1][2][2]，D[2][2][2]D[0][0][3]，D[1][0][3]，D[2][0][3] D[0][1][3]，D[1][1][3]，D[2][1][3] D[0][2][3]，D[1][2][3]，D[2][2][3]For z=0 to 3 do For y=0 to 2 do For x=0 to 2 do D[i][j][k]的地址：Loc （D[i][j][k]）=Loc （D[0][0][0]）+w*C 第三个下标的变化：0到k-1，共k*3*3个元素第三个下标为k 时，第二个下标的变化：0到j-1，共j*3个元素 第三个下标为k ，第二个下标为j 时，第一个下标的变化：0到i-1，共i 个元素 w= k*3*3+j*3+iLoc （D[i][j][k]）=Loc （D[0][0][0]）+w*C=Loc （D[0][0][0]）+（k*3*3+j*3+i ）*CD[3][3][0] k=0D[3][3][1] k=1D[3][3][2] k=2D[3][3][3] k=3j=0 j=1 j=2 j=0 j=1 j=2 j=0 j=1 j=2 j=0 j=1 j=2n 维数组][]][[21n m m m a K For 1l =0 to 11-m do For 2l =0 to 12-m do… … … …For n l =0 to 1-n m doC s Loc i i i Loc n *)0,,0,0(),,,(21+=ΛΛs = ?1l 的变化：0~1i -1，共1i *2m *3m *…*n m =1i *∏=np p m 2个元素1l 等于1i 时，2l 的变化：0~2i -1，共2i *3m *…*n m =2i *∏=np p m 3个元素1l 等于1i 时，2l 等于2i 时，3l 的变化：0~3i -1，共3i *4m *…*n m =3i *∏=np pm 4个元素… … … …1l 等于1i 时，2l 等于2i 时，…，1-n l 等于1-n i 时，n l 的变化：0~n i -1，共n i 个元素 故s=1i *∏=np p m 2+2i *∏=np p m 3+3i *∏=np p m 4+…+1-n i *n m +n in n k nk p p k i m i +=∑∏-=+=)* (111C s Loc i i i Loc n *)0,,0,0(),,,(21+=ΛΛC i m i Loc n n k nk p p k *})* ({)0,,0(111++=∑∏-=+=Λ。
