第五章数组和广义表 ●51数组的定义 ●52数组的顺序表示和实现 ●53矩阵的压缩存储 ●5.3.1特殊矩阵 ●5.32稀疏矩阵 °54广义表的定义 55广义表的存储结构 北京邮电大学自动化学院
北京邮电大学自动化学院 1 第五章 数组和广义表 ⚫ 5.1 数组的定义 ⚫ 5.2 数组的顺序表示和实现 ⚫ 5.3 矩阵的压缩存储 ⚫ 5.3.1 特殊矩阵 ⚫ 5.3.2 稀疏矩阵 ⚫ 5.4 广义表的定义 ⚫ 5.5 广义表的存储结构
51数组的定义 数组和广义表可看成是一种特殊的线性表,其特殊在于,表 中的所有元素本身也是一种线性表。 数组是我们最熟悉的数据类型,在早期的高级语言中,数组 是唯一可供使用的数据类型。由于数组中各元素具有统一的 类型,并且数组元素的下标一般具有固定的上界和下界,因 此,数组的处理比其它复杂的结构更为简单。多维数组是向 量的推广。例如,二维数组: 2 2 2n mxn 2 mn 北京邮电大学自动化学院
北京邮电大学自动化学院 2 ⚫ 数组和广义表可看成是一种特殊的线性表，其特殊在于，表 中的所有元素本身也是一种线性表。 = m m m n n n m n a a a a a a a a a A 1 2 2 1 2 2 2 1 1 1 2 1 ⚫ 数组是我们最熟悉的数据类型，在早期的高级语言中，数组 是唯一可供使用的数据类型。由于数组中各元素具有统一的 类型，并且数组元素的下标一般具有固定的上界和下界，因 此，数组的处理比其它复杂的结构更为简单。多维数组是向 量的推广。例如，二维数组： 5.1 数组的定义
51数组的定义 二维数组可以看成是由行向量组成的向量,也可以看成是 列向量组成的向量 ●同样,可把三维数组看成是一个线性表,表中每一个数组 元素为一个二维数组。依次类推,可把n维数组看成是一个 线性表,表中每一个数据元素是一个n-1维数组。 数组的运算:数组一旦被定义,它的维数和维界就不再改 变。因此,除了结构的初始化和销毁之外,数组只有存取 元素和修改元素值的操作。 即给定一组下标,存取或修改相应的数组元素。 北京邮电大学自动化学院
北京邮电大学自动化学院 3 ⚫ 二维数组可以看成是由行向量组成的向量，也可以看成是 列向量组成的向量。 ⚫ 同样，可把三维数组看成是一个线性表，表中每一个数组 元素为一个二维数组。依次类推，可把n维数组看成是一个 线性表，表中每一个数据元素是一个n-1维数组。 ⚫ 数组的运算：数组一旦被定义，它的维数和维界就不再改 变。因此，除了结构的初始化和销毁之外，数组只有存取 元素和修改元素值的操作。 ⚫ 即给定一组下标，存取或修改相应的数组元素。 5.1 数组的定义
52数组的顺序表示和实现 ●1、顺序存储结构 顺序存储结构:用一组地址连续的存储单元依次存放数据元 素,称为数组的顺序存储结构。 ●由于计算机的内存结构是一维的,因此用一维内存来表示多 维数组,就必须按某种次序将数组元素排成一列序列,然后 将这个线性序列存放在存储器中。 由于对数组一般不做插入和删除操作,也就是说,数组一旦 建立,结构中的元素个数和元素间的关系就不再发生变化。 因此,一般都是采用顺序存储的方法来表示数组。 北京邮电大学自动化学院 4
北京邮电大学自动化学院 4 ⚫ 1、顺序存储结构 5.2 数组的顺序表示和实现 ⚫ 顺序存储结构：用一组地址连续的存储单元依次存放数据元 素，称为数组的顺序存储结构。 ⚫ 由于计算机的内存结构是一维的，因此用一维内存来表示多 维数组，就必须按某种次序将数组元素排成一列序列，然后 将这个线性序列存放在存储器中。 ⚫ 由于对数组一般不做插入和删除操作，也就是说，数组一旦 建立，结构中的元素个数和元素间的关系就不再发生变化。 因此，一般都是采用顺序存储的方法来表示数组
2、顺序存储方式 通常有两种顺序存储方式: (1)行优先顺序—将数组元素按行排列,第|+1个行向量紧接在 第个行向量后面。以二维数组为例,按行优先顺序存储的线性 序列为:a1,a12…,a1mna21a222n…,amn1,amn2,,lamn ●在 PASCAL、C语言中,数组就是按行优先顺序存储的。 (2)列优先顺序—将数组元素按列向量排列,第j+1个列向量紧 接在第个列向量之后,A的mn个元素按列优先顺序存储的线 性序列为: a1a21…ama12a22yam2yana2ny…,amn ●在 FORTRAN语言中,数组就是按列优先顺序存储的。 北京邮电大学自动化学院
北京邮电大学自动化学院 5 ⚫ 通常有两种顺序存储方式： 2、顺序存储方式 ⚫ ⑴行优先顺序——将数组元素按行排列，第i+1个行向量紧接在 第i个行向量后面。以二维数组为例，按行优先顺序存储的线性 序列为： a11,a12,…,a1n,a21,a22,…a2n,……,am1,am2,…,amn ⚫ 在PASCAL、C语言中，数组就是按行优先顺序存储的。 ⚫ ⑵列优先顺序——将数组元素按列向量排列，第j+1个列向量紧 接在第j个列向量之后，A的m*n个元素按列优先顺序存储的线 性序列为： ⚫ a11,a21,…,am1,a12,a22,…am2,……,a1n,a2n,…,amn ⚫ 在FORTRAN语言中，数组就是按列优先顺序存储的
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 矩阵的压缩存储 ⚫ 压缩存储：为多个相同的非零元素只分配一个存储空间；对 零元素不分配空间。 ⚫ 假若值相同的元素或零元素在矩阵中的分布有一定规律，则 我们称此类矩阵为特殊矩阵；反之，称为稀疏矩阵