数据结构第五章数组与广义表ppt课件

1、 数据结构课程本章内容5.1 数组的定义5.2 数组的顺序表示和实现5.3 矩阵的紧缩存储5.4 广义表的定义5.5 广义表的存储构造中国科大数据结构数组和广义表简单描画中国科大数据结构 数组是我们最熟习的数据类型，在早期的高级言语数组是我们最熟习的数据类型，在早期的高级言语中，数组是独一可供运用的数据类型。由于数组中各中，数组是独一可供运用的数据类型。由于数组中各元素具有一致的类型，并且数组元素的下标普通具有元素具有一致的类型，并且数组元素的下标普通具有固定的上界和下界，因此，数组的处置比其它复杂的固定的上界和下界，因此，数组的处置比其它复杂的构造更为简单。多维数组是向量的推行。例如，二维构

2、造更为简单。多维数组是向量的推行。例如，二维数组：数组： 5.1 数组的定义Amn=a11 a12 a1na21 a22 a2n am1 am2 amn中国科大数据结构5.1 数组的定义p二维数组二维数组p二维数组可以看成是由假设干个行向量组成的向量，也可以看成是假设干二维数组可以看成是由假设干个行向量组成的向量，也可以看成是假设干个列向量组成的向量。个列向量组成的向量。p在在C C言语中，一个二维数组类型可以定义为其分量类型为一维数组类型的一言语中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说，维数组类型，也就是说，typedef elemtype array2

3、mn; typedef elemtype array2mn; 等价于：等价于：p typedef elemtype array1n; typedef elemtype array1n;p typedef array1 array2m; typedef array1 array2m;p多维数组：用一维顺序构造线性表实现多维数组多维数组：用一维顺序构造线性表实现多维数组pstruct Arraystruct Arrayp ElemType ElemType * *buffer;buffer;/ / 数据区数据区p int dims; int dims;/ / 维数维数p int int * *L;

4、L;/ / 各维长度各维长度p;中国科大数据结构5.2 数组的顺序表示和实现p设一3维数组A423，存贮在一个顺序线性表S中，构造如下所示：A312A311A310A302A301A300A212A211A210A202A201A200A112A111A110A102A101A100A012A011A010A002A001A000A312A311A310A302A301A300A212A211A210A202A201A200A112A111A110A102A101A100A012A011A010A002A001A00001234567.2223A000A001A002A010A011A012A

5、100A101.A311A312中国科大数据结构5.2 数组的顺序表示和实现p两种顺序存储方式：两种顺序存储方式：p行优先顺序行优先顺序将数组元素按行陈列，第将数组元素按行陈列，第i+1i+1个行向量紧接在第个行向量紧接在第i i个个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为：行向量后面。以二维数组为例，按行优先顺序存储的线性序列为：a11,a12,a1n,a21,a22,a2n,am1,am2,amna11,a12,a1n,a21,a22,a2n,am1,am2,amn。在。在PASCALPASCAL、C C言语中，数组就是按行优先顺序存储的。行优先顺序推行到多维言语中，数组就

6、是按行优先顺序存储的。行优先顺序推行到多维数组，可规定为先排最右的下标。数组，可规定为先排最右的下标。 p列优先顺序列优先顺序将数组元素按列向量陈列，第将数组元素按列向量陈列，第j+1j+1个列向量紧接在个列向量紧接在第第j j个列向量之后，个列向量之后，A A的的m m* *n n个元素按列优先顺序存储的线性序列为：个元素按列优先顺序存储的线性序列为：a11,a21,am1,a12,a22,am2,an1,an2,anm a11,a21,am1,a12,a22,am2,an1,an2,anm 。在。在FORTRANFORTRAN言语中，数组就是按列优先顺序存储的。列优先顺序推行言语中，数组就

7、是按列优先顺序存储的。列优先顺序推行到多维数组，可规定为先排最左的下标。到多维数组，可规定为先排最左的下标。 中国科大数据结构5.2 数组的顺序表示和实现p二维数组元素的存取二维数组元素的存取p二维数组二维数组AmnAmn按按“行优先顺序存储在内存中，假设每个元素占用行优先顺序存储在内存中，假设每个元素占用L L个存储单元。个存储单元。p元素元素aijaij的存储地址应是数组的基地址加上排在的存储地址应是数组的基地址加上排在aijaij前面的元素所占前面的元素所占用的单元数。由于用的单元数。由于aijaij位于第位于第i i行、第行、第j j列，前面列，前面 i-1 i-1 行一共有行一共有(

8、i-1) (i-1) n n 个元素，第个元素，第i i行上行上aijaij前面又有前面又有j-1j-1个元素，故它前面一共有个元素，故它前面一共有(i-(i-1) 1) n+j-1n+j-1个元素，因此，个元素，因此，aijaij的地址计算函数为：的地址计算函数为：p LOC(aij) = LOC(a11)+(i-1) LOC(aij) = LOC(a11)+(i-1)* *n+j-1n+j-1* *L L中国科大数据结构5.2 数组的顺序表示和实现p例：二维数组例：二维数组Ac1.d1,c2.d2Ac1.d1,c2.d2的存取的存取p分析：分析：aijaij前一共有前一共有i-c1i-c1

9、行，二维数组一共有行，二维数组一共有d2-c2+1d2-c2+1列，故这列，故这i-c1i-c1行共有行共有(i-c1)(i-c1)* *(d2-c2+1)(d2-c2+1)个元素，第个元素，第i i行上行上aijaij前一共有前一共有j-c2j-c2个元素，个元素，因此，因此，aijaij的地址计算函数为：的地址计算函数为：p LOC(aij) = LOC(ac1c2)+(i-c1) LOC(aij) = LOC(ac1c2)+(i-c1)* *(d2-c2+1)+j-c2)(d2-c2+1)+j-c2)* *L Lp在在C C言语中，数组各维下标的下界是言语中，数组各维下标的下界是0 0，

10、因此二维数组，因此二维数组AmAmn n的地址的地址计算公式为：计算公式为：p LOC(aij) = LOC(a00)+(i LOC(aij) = LOC(a00)+(i* *n+j)n+j)* *L L中国科大数据结构5.3 矩阵的紧缩存储p在高级言语编制程序时，将一个矩阵描画为一个二维数组。在高级言语编制程序时，将一个矩阵描画为一个二维数组。p矩阵在这种存储表示之下，可以对其元素进展随机存取，各种矩阵矩阵在这种存储表示之下，可以对其元素进展随机存取，各种矩阵运算也非常简单，并且存储的密度为运算也非常简单，并且存储的密度为1 1。但是在矩阵中非零元素呈。但是在矩阵中非零元素呈某种规律分布或者

11、矩阵中出现大量的零元素的情况下，看起来存储某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为密度仍为1 1，但实践上占用了许多单元去存储反复的非零元素或零，但实践上占用了许多单元去存储反复的非零元素或零元素，这对高阶矩阵会呵斥极大的浪费元素，这对高阶矩阵会呵斥极大的浪费. .p为了节省存储空间，为了节省存储空间， 对这类矩阵进展紧缩存储：即为多个一样的对这类矩阵进展紧缩存储：即为多个一样的非零元素只分配一个存储空间；对零元素不分配空间。非零元素只分配一个存储空间；对零元素不分配空间。中国科大数据结构5.3 矩阵的紧缩存储5.3.1 特殊矩阵特殊矩阵所谓特殊矩阵是指非零元素或零元

12、素的分布有一定规律的矩阵，所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的紧缩存储。下面我们讨论几种特殊矩阵的紧缩存储。 1、对称矩阵、对称矩阵 2、对角矩阵、对角矩阵中国科大数据结构5.3 矩阵的紧缩存储p对称矩阵对称矩阵p在一个在一个n n阶方阵阶方阵A A中，假设元素满足下述性质：中，假设元素满足下述性质：aij=aji aij=aji 0i,jn-10i,jn-1p 那么称那么称A A为对称矩阵。如以下图是一个为对称矩阵。如以下图是一个5 5阶对称矩阵。阶对称矩阵。p对称矩阵中的元素关于主对角线对称，故只需存储矩对称矩阵中的元素关于主对角线对称，故只需

13、存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失普通性，我们按空间，这样，能节约近一半的存储空间。不失普通性，我们按“行行优先顺序存储主对角线包括对角线以下的元素，其存储方式优先顺序存储主对角线包括对角线以下的元素，其存储方式如上图示。如上图示。1 5 1 3 7 a005 0 8 0 0 a10 a 111 8 9 2 6 a20 a21 a233 0 2 5 1 .7 0 6 1 3 an-1 0 a n-1 1 a n-1 2 a n-1 n-1中国科大数据结构5.3 矩阵的

14、紧缩存储p对称矩阵的存储表示对称矩阵的存储表示p在这个下三角矩阵中，第在这个下三角矩阵中，第i i行恰有行恰有i+1i+1个元素，元素总数为：个元素，元素总数为：p (i+1) = n(n+1)/2 (i+1) = n(n+1)/2p因此，我们可以按行优先的次序将这些元素存放在一个向量因此，我们可以按行优先的次序将这些元素存放在一个向量sa0.n(n+1)/2-1sa0.n(n+1)/2-1中。中。paijaij和和sak sak 之间对应关系之间对应关系p假设假设ijij，那么，那么ai jai j在下三角形中。在下三角形中。 ai j ai j之前的之前的i i行从第行从第0 0行到行到第

15、第i-1i-1行一共有行一共有 1+2+i=i(i+1)/2 1+2+i=i(i+1)/2 个元素，在第个元素，在第i i行上，行上， ai j ai j之前恰有之前恰有j j个元素即个元素即 ai0,ai1,ai2,aij-1 ai0,ai1,ai2,aij-1，因此有：，因此有：pk=ik=i* *(i+1)/2+j 0kn(n+1)/2(i+1)/2+j 0kn(n+1)/2p假设假设ijij，那么，那么aijaij是在上三角矩阵中。由于是在上三角矩阵中。由于aij=ajiaij=aji，所以只需交，所以只需交换上述对应关系式中的换上述对应关系式中的i i和和j j即可得到：即可得到：p

16、k=jk=j* *(j+1)/2+i 0 kn(n+1)/2(j+1)/2+i 0 k1i-j1时，元素时，元素aij=0aij=0。p由此可知，一个由此可知，一个k k对角矩阵对角矩阵(k(k为奇数为奇数)A)A是满足下述条件的矩阵：假是满足下述条件的矩阵：假设设i-j(k-1)/2 i-j(k-1)/2 ，那么元素，那么元素 aij=0 aij=0。p对角矩阵可按行优先顺序或对角线的顺序，将其紧缩存储到一个向对角矩阵可按行优先顺序或对角线的顺序，将其紧缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。量中，并且也能找到每个非零元素和向量下标的对应关系。中国科大数据结构5.3 矩阵的紧缩存储在三对角矩阵里附满足条件i=0，j=0、1，或i=n-1j=n-2、n-1或1in-1,j=i-1、i、i+1的元素aij外，其他元素都是零。对这种矩阵，我们也可按行优序为主序来存储。除第0行和第n-1行是2个元素外，每行的非零元素都是3个，因此，需存储的元素个数为3n-2。数组sa中的元素sak与三对角带状矩阵中的元素aij存在一一对应关系，在aij之前有i行,共有3*i-1个非零元素，在第i行，有j-i+1个非零元素.a n-1 n-1a n-1 n-2