a 按列序为主序存放 a2 21 an a 2 a11a12 a a22 a21a22 ●●●●。 2n a amI am2 nn a n Loc(aij=Loc(a11+G-1)m+(i-D)* m*n-1 a
北京邮电大学自动化学院 6 a11 a12 …….. a1n a21 a22 …….. a2n am1 am2 …….. amn …………………. Loc( aij)=Loc(a11)+[(i-1)n+(j-1)]*l 按行序为主序存放 amn …….. am2 am1 ………. a2n …….. a22 a21 a1n ……. a12 a11 0 1 n-1 m*n-1 n 按列序为主序存放 0 1 m-1 m*n-1 m amn …….. a2n a1n ………. am2 …….. a22 a12 am1 ……. a21 a11 a11 a12 …….. a1n a21 a22 …….. a2n am1 am2 …….. amn …………………. Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l
3、n维数组 以上规则推广到多维数组的情况:行优先顺序可规定为先排 最右的下标,从右到左,最后排最左下标; ●列优先顺序与此相反,先排最左下标,从左向右,最后排最 右下标。 ●按上述两种方式顺序存储的数组,只要知道开始结点的存放 地址(即基地址)、维数和每维的上、下界,以及每个数组 元素所占用的单元数,就可以将数组元素的存放地址表示为 其下标的线性函数。因此,数组中的任一元素可以在相同的 时间内存取,即顺序存储的数组是一个随机存取结构 北京邮电大学自动化学院
北京邮电大学自动化学院 7 ⚫ 以上规则推广到多维数组的情况：行优先顺序可规定为先排 最右的下标，从右到左，最后排最左下标； 3、n维数组 ⚫ 按上述两种方式顺序存储的数组，只要知道开始结点的存放 地址（即基地址）、维数和每维的上、下界，以及每个数组 元素所占用的单元数，就可以将数组元素的存放地址表示为 其下标的线性函数。因此，数组中的任一元素可以在相同的 时间内存取，即顺序存储的数组是一个随机存取结构。 ⚫ 列优先顺序与此相反，先排最左下标，从左向右，最后排最 右下标
4、地址公式 例如,二维数组Am按“行优先顺序”存储在内存中,假设 每个元素占用d个存储单元。 元素a的存储地址应是数组的基地址加上排在a前面的元素所 占用的单元数。因为a位于第行、第列,前面1行一共有 1)×n个元素,第行上a前面又有j1个元素,故它前面一共有 (i-1)×n+1个元素,因此,a的地址计算函数为: LOC(ai=LOC(al)+[(i-1)*n+j-1]*d 同样,三维数组A按“行优先顺序”存储,其地址计算函数 为: Loc(ak)=Loc(a1)+[(1-1)*n*p+(-1)p+(k1]d 北京邮电大学自动化学院
北京邮电大学自动化学院 8 ⚫ 例如，二维数组Amn按“行优先顺序”存储在内存中，假设 每个元素占用d个存储单元。 4、地址公式 ⚫ 元素aij的存储地址应是数组的基地址加上排在aij前面的元素所 占用的单元数。因为aij位于第i行、第j列，前面i-1行一共有(i- 1) ×n个元素，第i行上aij前面又有j-1个元素，故它前面一共有 (i-1) ×n+j-1个元素，因此，aij的地址计算函数为： ⚫ LOC(aij)=LOC(a11)+[(i-1)*n+j-1]*d ⚫ 同样，三维数组Aijk按“行优先顺序”存储，其地址计算函数 为： ⚫ LOC(aijk)=LOC(a111)+[(i-1)*n*p+(j-1)*p +(k-1)]*d
4、地址公式 上述讨论均是假设数组各维的下界是1,更一般的二维数组 是A[c1d1,C2d2】,这里c1C2不一定是1。a前一共有ic1 行,二维数组一共有d2C2+1列,故这ⅰ-c1行共有(i-c1)(d2 C2+1)个元素,第行上a前一共有j-c2个元素,因此,a的地 址计算函数为 Loc(a=LOC(ac1c2+li-C,*(d2-C2+1)+j-C2]d 例如,在C语言中,数组各维下标的下界是0,因此在C语言 中,二维数组的地址计算公式为: Loca)=Loc(a00)t(°(d2+1)+j)’d 北京邮电大学自动化学院
北京邮电大学自动化学院 9 ⚫ 上述讨论均是假设数组各维的下界是1，更一般的二维数组 是A[c1 ..d1 ,c2 ..d2 ]，这里c1 ,c2不一定是1。aij前一共有i-c1 行，二维数组一共有d2 -c2+1列，故这i-c1行共有(i-c1 )*(d2 - c2+1)个元素，第i行上aij前一共有j-c2个元素，因此，aij的地 址计算函数为： 4、地址公式 ⚫ LOC(aij)=LOC(ac1c2)+[(i-c1 )*(d2 -c2+1)+j-c2 )]*d ⚫ 例如，在C语言中，数组各维下标的下界是0，因此在C语言 中，二维数组的地址计算公式为： ⚫ LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d
53矩阵的压缩存储 在科学与工程计算问题中,矩阵是一种常用的数学对象,在 高级语言编制程序时,简单而又自然的方法,就是将一个矩 阵描述为一个二维数组。但是在矩阵中非零元素呈某种规律 分布或者矩阵中出现大量的零元素的情况下,看起来存储密 度仍为1,但实际上占用了许多单元去存储重复的非零元素 或零元素,这对高阶矩阵会造成极大的浪费,为了节省存储 空间,我们可以对这类矩阵进行压缩存储。 ●压缩存储:为多个相同的非零元素只分配一个存储空间;对 零元素不分配空间 假若值相同的元素或零元素在矩阵中的分布有一定规律,则 我们称此类矩阵为特殊矩阵;反之,称为稀疏矩阵, 北京邮电大学自动化学院 10
北京邮电大学自动化学院 10 ⚫ 在科学与工程计算问题中，矩阵是一种常用的数学对象，在 高级语言编制程序时，简单而又自然的方法，就是将一个矩 阵描述为一个二维数组。但是在矩阵中非零元素呈某种规律 分布或者矩阵中出现大量的零元素的情况下，看起来存储密 度仍为1，但实际上占用了许多单元去存储重复的非零元素 或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储 空间， 我们可以对这类矩阵进行压缩存储。 5.3 矩阵的压缩存储 ⚫ 压缩存储：为多个相同的非零元素只分配一个存储空间；对 零元素不分配空间。 ⚫ 假若值相同的元素或零元素在矩阵中的分布有一定规律，则 我们称此类矩阵为特殊矩阵；反之，称为稀疏矩阵