0数组的版序存猪结构 第五章数组和广义表 同样,对于n维数组也有上述两种不同的顺序存储方式:以 一左下标为主序的存储方式和以右下标为主序的存储方式。 把n维数组的元素按上述方式顺序存放在存储单元中,则每 个元素的存储地址可以用一个公式计算出来,这个公式称为“地 一址公式 计算存储地址:对于A[1.m,1.n],设每个数组元素占个存 储单元。 LOC[1,1] 不同程序设计语言中 数组的起始下标不完全相 11412 同,C语言起始下标为0,A=212 Pascal为1,某些4GL则允 许定义起始下标 注.以左下标为主序,指主序变化最慢(实现时为最外层循环) 第11页
第五章 数组和广义表 第11页 同样，对于n维数组也有上述两种不同的顺序存储方式：以 左下标为主序的存储方式和以右下标为主序的存储方式。 把n维数组的元素按上述方式顺序存放在存储单元中，则每 个元素的存储地址可以用一个公式计算出来，这个公式称为“地 址公式”。 计算存储地址：对于A[1..m, 1..n]，设每个数组元素占L个存 储单元。 = m m mn n n a a a a a a a a a A 1 2 2 1 2 2 2 1 1 1 2 1 i→ j ↓ aij LOC[1,1] ↓ 注. 以左下标为主序，指主序变化最慢（实现时为最外层循环） ⚫ 数组的顺序存储结构 不同程序设计语言中 数组的起始下标不完全相 同，C语言起始下标为0， Pascal为1，某些4GL则允 许定义起始下标
0数组的版序存猪结构 第五章数组和广义表 一以二维数组为例,先讨论简化情况(C1=1,d=m,C2=1, d2=n),再讨论一般情况(下标分别为c1,d1,C2,d2 记a1的存储地rA1空且 二维数组A的起始 C语言起始下标从0开始,则 首地址),L为元素o[1i1=001+(n*2+3)x五 记a1m,1m)的LOC[, 则 LOC[ j]LOC[1, 1]+[n*(i-1)+(j-1)]L. LOC[1,1] 11012 般地,对于A[c1,d1,C2,d2],则有 21122 aen LocL,j= Loc[C, C2]+ [(d2-C2+1)(i-c1)+(j-C2)L mlm 其中LOCc1,C2]是二维数组A的基地址 第12页
第五章 数组和广义表 第12页 记a11的存储地址为LOC[1,1]，它即是 二维数组A的起始存储位置，或称基地址（ 首地址）,L为元素所占的单元数。 记aij(1≤i≤m, 1≤j≤n)的存储地址为LOC[i,j]， 则 LOC[i,j]=LOC[1,1]+ [n*(i-1)+(j-1)]*L. 以二维数组为例，先讨论简化情况（c1=1，d1=m， c2=1， d2=n），再讨论一般情况（下标分别为c1，d1， c2，d2）. ⚫ 数组的顺序存储结构 一般地，对于A[c1 ..d1，c2 ..d2 ]，则有 Loc[i,j] = Loc[c1 ,c2 ] + [(d2 -c2+1)(i- c1 )+(j- c2 )]*L 其中LOC[c1 ,c2 ]是二维数组A的基地址。 C语言起始下标从0开始，则 Loc[i,j] = Loc[0,0] + ( n*i + j ) * L = m m mn n n a a a a a a a a a A 1 2 2 1 2 2 2 1 1 1 2 1 i→ j ↓ aij LOC[1,1] ↓
0数组的版序存猪结构 第五章数组和广义表 对于三维数组A[c1d1,C2d2,c3,d3],设基地址为LOC[c1,c2,C3], 则 LOC[1l2]=Locc1,C2C3]+(d2-C2+1)(d3-C3+1)j1-cn)+(d3C3+1)(2c2)+(3C3 LOCLCI, C2,C3]+ ∑( C;)元 k k+1)+(j )]·Z k=i+1 LOCIC1, C2,C31+>a, (ii-C) 其中 x(dk-ck+1),1si≤3 k=i+1 当i=3时,令,x(dk-ck+1)=1 k=i+1 第13页
第五章 数组和广义表 第13页 LOC[j1 ,j2 , j3 ]=LOC[c1 ,c2 , c3 ]+[(d2 -c2+1) (d3 -c3+1)(j1 -c1 )+(d3 -c3+1) (j2 -c2 )+ (j3 -c3 )]*L 对于三维数组A[c1 ..d1， c2 ..d2， c3 ..d3 ]，设基地址为LOC[c1 ,c2 , c3 ], 则 3 , ( 1) 1 . ( 1),1 3 [ , , ] ( ) [ ( ) ( 1) ( )] [ , , ] 3 1 3 1 3 1 1 2 3 3 3 2 1 3 1 1 2 3 = − + = = − + = + − − − + + − = + = + = + = = = + k k k i k k k i i i i i i k k i k i i i i d c l d c i LOC c c c j c j c d c j c l LOC c c c 当 时 令 其中 ⚫ 数组的顺序存储结构
第五章数组和广义表 上已推导出,对于三维数组Acd1,C2.d2,c3dal, 设基地址为LOCc1,C2,c3],则 LOCL1J22131=LOCICI c3」+ ∑a( 其中 k 1),1≤≤3 (“=23(4-+1)=) 推广至n维数组4c1d12C 1,有 LOCT,2,n= LOCICi, C2,CnI+ ∑∝1(j-c;) (5-5) 其中 k+1)21≤z i=n时,x(dk-ck+1)=1 =i+1 第14页
第五章 数组和广义表 第14页 上已推导出，对于三维数组A[c1 ..d1， c2 ..d2， c3 ..d3 ]， 设基地址为LOC[c1 ,c2 , c3 ]，则 , ( 1) 1 . ( 1),1 ( ), (5 5) [ , , ] [ , , ] [ .. , .. , .. ], 3 , ( 1) 1 . ( 1),1 3 ( ) [ , , ] [ , , ] 1 1 1 1 2 1 2 1 1 2 2 3 1 3 1 3 1 1 2 3 1 2 3 = − + = = − + − − = + = − + = = − + − = + = + = + = = + = + = k k n k i k k n k i i n i i i i n n n n k k k i k k k i i i i i i i n d c l d c i n j c LOC j j j LOC c c c n A c d c d c d i d c l d c i j c LOC j j j LOC c c c 时 其中 推广至 维数组 有 当 时 其中
●矩阵压缩存储的概念 第五章数组和广义表 矩阵:在科学研究和工程计算中经常用到的一种数学工 具,是研究的主要数学对象之一。 矩阵的存:一般情况下,可用二维数组实现。 三二维数组,通常也就称为矩阵,是数学上的一种 重要数据结构。 11c412 2122 2n m×n mlm 第15页
第五章 数组和广义表 第15页 = m m m n n n a a a a a a a a a A 1 2 2 1 2 2 2 1 1 1 2 1 矩阵：在科学研究和工程计算中经常用到的一种数学工 具，是研究的主要数学对象之一。 矩阵的存储：一般情况下，可用二维数组实现。 二维数组，通常也就称为矩阵，是数学上的一种 重要数据结构。 m×n ⚫矩阵压缩存储的概念