第五章数组和广义表 51数组的定义 52数组的顺序表示和实现 53矩阵的压缩存储 5.3.1特殊矩阵 532稀疏矩阵 54广义表的定义 55广义表的存储结构
第五章 数组和广义表 ⚫ 5.1 数组的定义 ⚫ 5.2 数组的顺序表示和实现 ⚫ 5.3 矩阵的压缩存储 5.3.1 特殊矩阵 5.3.2 稀疏矩阵 5.4 广义表的定义 5.5 广义表的存储结构
数组和广义表可看成是一种特殊的线性表, 其特殊在于,表中的数所元素本身也是一种线 性表。 5.1数组的定义 数组是我们最熟悉的数据类型,在早期的 高级语言中,数组是唯一可供使用的数据类型。 由于数组中各元素具有统一的类型,并且数组 元素的下标一般具有固定的上界和下界,因此, 数组的处理比其它复杂的结构更为简单。多维 数组是向量的推广。例如,二维数组: a11a12 In a21a22 a2n mn ●●●● aml am2 ●●● mit
数组和广义表可看成是一种特殊的线性表， 其特殊在于，表中的数所元素本身也是一种线 性表。 5.1 数组的定义 数组是我们最熟悉的数据类型，在早期的 高级语言中，数组是唯一可供使用的数据类型。 由于数组中各元素具有统一的类型，并且数组 元素的下标一般具有固定的上界和下界，因此， 数组的处理比其它复杂的结构更为简单。多维 数组是向量的推广。例如，二维数组： a11 a12 … a1n a21 a22 … a2n … … … … am1 am2 … amn Amn =
可以看成是由个行向量组成的向量,也可以看成是 个列向量组成的向量。 在C语言中,一个二维数组类型可以定义为其分 量类型为一维数组类型的一维数组类型,也就是说, typedef elemtype array2[m][n] 等价于: typedef elemtype array l[n] typedef array array2 [ m] 同理,一个维数组类型可以定义为其数据元素为维 数组类型的一维序组类型。 数组一旦被定义,它的维数和维界就不再改变。 因此,除了结构的初始化和销毁之外,数组只有存 取元素和修改元素值的操作
可以看成是由个行向量组成的向量，也可以看成是 个列向量组成的向量。 在C语言中，一个二维数组类型可以定义为其分 量类型为一维数组类型的一维数组类型，也就是说， typedef elemtype array2[m][n]; 等价于： typedef elemtype array1[n]; typedef array1 array2[m]; 同理，一个维数组类型可以定义为其数据元素为维 数组类型的一维序组类型。 数组一旦被定义，它的维数和维界就不再改变。 因此，除了结构的初始化和销毁之外，数组只有存 取元素和修改元素值的操作
5.2数组的顺序表示和实现 由于计算机的内存结构是一维的,因此用 维内存来表示多维数组,就必须按某种 次序将数组元素排成一列序列,然后将这 个线性序列存放在存储器中。 又由于对数组一般不做插入和删除操作, 也就是说,数组一旦建立,结构中的元素 个数和元素间的关系就不再发生变化。因 此,一般都是采用顺序存储的方法来表示 数组
5.2 数组的顺序表示和实现 由于计算机的内存结构是一维的，因此用 一维内存来表示多维数组，就必须按某种 次序将数组元素排成一列序列，然后将这 个线性序列存放在存储器中。 又由于对数组一般不做插入和删除操作， 也就是说，数组一旦建立，结构中的元素 个数和元素间的关系就不再发生变化。因 此，一般都是采用顺序存储的方法来表示 数组
通常有两种顺序存储方式: (1)行优先顺序—将数组元素按行排列,第i+1个行 向量紧接在第i个行向量后面。以二维数组为例, 按行优先顺序存储的线性序列为 a11a12,…a1n,a21,a22a2n∴;am1am2,…amn 在 PASCAL、C语言中,数组就是按行优先顺序 存储的 (2)列优先顺序将数组元素按列向量排列,第j+1 个列向量紧接在第j个列向量之后,A的m*n个元素 按列优先顺序存储的线性序列为 a11,a21,aml,a12,a22∴am2,…,an1,an2,…;anm 在 FORTRAN语言中,数组就是按列优先顺序存储的
通常有两种顺序存储方式： ⑴行优先顺序——将数组元素按行排列，第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,……,an1,an2,…,anm 在FORTRAN语言中，数组就是按列优先顺序存储的
以上规则可以推广到多维数组的情况:优先 顺序可规定为先排最右的下标,从右到左,最 后排最左下标:列优先顺序与此相反,先排最 左下标,从左向右,最后排最右下标。 按上述两种方式顺序存储的序组,只要 知道开始结点的存放地址(即基地址),维数 和每维的上、下界,以及每个数组元素所占用 的单元数,就可以将数组元素的存放地址表示 为其下标的线性函数。因此,数组中的任一元 素可以在相同的时间内存取,即顺序存储的数 组是一个随机存取结构
以上规则可以推广到多维数组的情况：优先 顺序可规定为先排最右的下标，从右到左，最 后排最左下标：列优先顺序与此相反，先排最 左下标，从左向右，最后排最右下标。 按上述两种方式顺序存储的序组，只要 知道开始结点的存放地址（即基地址），维数 和每维的上、下界，以及每个数组元素所占用 的单元数，就可以将数组元素的存放地址表示 为其下标的线性函数。因此，数组中的任一元 素可以在相同的时间内存取，即顺序存储的数 组是一个随机存取结构
例如:假设数组各维的下界是不是1,二维数组Am按“行 优先顺序”存储在内存中,假设每个元素占用d个存 储单元。元素a1;的存储地址应是数组的基地址加上排 在a1前面的元素所占用的单元数。因为a位于第行 第j列,前面i-1行一共有(i-1)×n个元素,第i行上 a1j前面又有-1个元素,故它前面一共有 (i-1)×n+j-1个元素,因此, a1的地址计算函数为: L0C(a1)=L0C(a1)+[(i-1)*n+-1]*d 同样,三维数组A按“行优先顺序”存储,其地址 计算函数为: L0C(a1)=L0C(a1)+[(i-1)*n*p+(j-1)*p+(k-1)d
例如:假设数组各维的下界是不是1,二维数组Amn按“行 优先顺序”存储在内存中，假设每个元素占用d个存 储单元。元素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
上述讨论均是假设数组各维的下界是1,更 般的二维数组是A[.d,C2.d2],这里,c2不 定是1。a1前一共有i-c1行,二维数组一共有 d2-c2+1列,故这i-c1行共有(i-c1)米(d2-c2+1)个 元素,第i行上a;前一共有j-c2个元素,因此, a1的地址计算函数为 L0C(a1)=L0C(a1c)+[(ic1)*(d2-c2+1)+j-cd 例如,在C语言中,数组各维下标的下界是0, 因此在C语言中,二维数组的地址计算公式为: L0C(a1)=L0C(a0)+(i*(d2+1)+j)*d
上述讨论均是假设数组各维的下界是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的地址计算函数为： LOC(aij)=LOC(ac1 c2 )+[(i-c1)*(d2-c2+1)+j-c2)]*d 例如，在C语言中，数组各维下标的下界是0， 因此在C语言中，二维数组的地址计算公式为： LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d
5.3矩阵的压缩存储 在科学与工程计算问题中,矩阵是一种常用的 数学对象,在高级语言编制程序时,简单而又自然 的方法,就是将一个矩阵描述为一个二维数组。矩 阵在这种存储表示之下,可以对其元素进行随机存 取,各种矩阵运算也非常简单,并且存储的密度为 1。但是在矩阵中非零元素呈某种规律分布或者矩 阵中出现大量的零元素的情况下,看起来存储密度 仍为1,但实际上占用了许多单元去存储重复的非 零元素或零元素,这对高阶矩阵会造成极大的浪费, 为了节省存储空间,我们可以对这类矩阵进行压 缩存储:即为多个相同的非零元素只分配一个存储 空间;对零元素不分配空间
5.3 矩阵的压缩存储 在科学与工程计算问题中，矩阵是一种常用的 数学对象，在高级语言编制程序时，简单而又自然 的方法，就是将一个矩阵描述为一个二维数组。矩 阵在这种存储表示之下，可以对其元素进行随机存 取，各种矩阵运算也非常简单，并且存储的密度为 1。但是在矩阵中非零元素呈某种规律分布或者矩 阵中出现大量的零元素的情况下，看起来存储密度 仍为1，但实际上占用了许多单元去存储重复的非 零元素或零元素，这对高阶矩阵会造成极大的浪费， 为了节省存储空间， 我们可以对这类矩阵进行压 缩存储：即为多个相同的非零元素只分配一个存储 空间；对零元素不分配空间
5.3.1特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一定 规律的矩阵,下面我们讨论几种特殊矩阵的压缩存 储。 1、对称矩阵 在一个n阶方阵A中,若元素满足下述性质: aij8aj0三i,jn-1 则称A为对称矩阵。如图5.1便是一个5阶对称矩阵 对称矩阵中的元素关于主对角线对称,故只要 存储矩阵中上三角或下三角中的元素,让每两个对 称的元素共享一个存储空间,这样,能节约近一半 的存储空间。不失一般性,我们按“行优先顺序 存储主对角线(包括对角线)以下的元素,其存储 形
5.3.1特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一定 规律的矩阵，下面我们讨论几种特殊矩阵的压缩存 储。 1、对称矩阵 在一个n阶方阵A中，若元素满足下述性质： aij=aji 0≦i,j≦n-1 则称A为对称矩阵。如图5.1便是一个5阶对称矩阵。 对称矩阵中的元素关于主对角线对称，故只要 存储矩阵中上三角或下三角中的元素，让每两个对 称的元素共享一个存储空间，这样，能节约近一半 的存储空间。不失一般性，我们按“行优先顺序” 存储主对角线（包括对角线）以下的元素，其存储 形