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

数据结构课程本章内容5.1 数组的定义5.2 数组的顺序表示和实现5.3 矩阵的压缩存储5.4 广义表的定义5.5 广义表的存储结构中国科大数据结构5-3 数组和广义表简单描述中国科大数据结构5-4 数组是我们最熟悉的数据类型，在早期的高级语言中，数组是数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组：二维数组：5.1 数组的定义Amn=a11 a12 a1na21 a22 a2n am1 am2 amn中国科大数据结构5-5 5.1 数组的定义p二维数组二维数组n二维数组可以看成是由若干个行向量组成的向量，也可以看成是若干二维数组可以看成是由若干个行向量组成的向量，也可以看成是若干个列向量组成的向量。个列向量组成的向量。n在在C C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说，的一维数组类型，也就是说，typedef elemtype array2mn;等价于：等价于：typedef elemtype array1n;typedef array1 array2m;p多维数组：多维数组：用一维顺序结构线性表实现多维数组用一维顺序结构线性表实现多维数组struct Array ElemType*buffer;/数据区数据区 int dims;/维数维数 int*L;/各维长度各维长度;中国科大数据结构5-6 5.2 数组的顺序表示和实现p设一设一3 3维数组维数组A423A423，存贮，存贮在一个顺序线性表在一个顺序线性表S S中，结构如中，结构如下所示：下所示：A312A311A310A302A301A300A212A211A210A202A201A200A112A111A110A102A101A100A012A011A010A002A001A000A312A311A310A302A301A300A212A211A210A202A201A200A112A111A110A102A101A100A012A011A010A002A001A0000A0001A0012A0023A0104A0115A0126A1007A101.22A31123A312中国科大数据结构5-7 5.2 数组的顺序表示和实现p两种顺序存储方式：两种顺序存储方式：n行优先顺序行优先顺序将数组元素按行排列，第将数组元素按行排列，第i+1i+1个行向量紧接在第个行向量紧接在第i i个行向量后面。以二维数组为例，按行优先顺序存储的线性序个行向量后面。以二维数组为例，按行优先顺序存储的线性序列为：列为：a11,a12,a1n,a21,a22,a2n,am1,am2,amn。在。在PASCAL、C语言中，数组就是按行优先顺序存储的。语言中，数组就是按行优先顺序存储的。行优先顺行优先顺序推广到多维数组，可规定为先排最右的下标。序推广到多维数组，可规定为先排最右的下标。n列优先顺序列优先顺序将数组元素按列向量排列，第将数组元素按列向量排列，第j+1j+1个列向量紧接个列向量紧接在第在第j j个列向量之后，个列向量之后，A A的的m m*n n个元素按列优先顺序存储的线性序个元素按列优先顺序存储的线性序列为：列为：a11,a21,am1,a12,a22,am2,an1,an2,anm 。在。在FORTRAN语言中，数组就是按列优先顺序存储的。语言中，数组就是按列优先顺序存储的。列优先顺列优先顺序推广到多维数组，可规定为先排最左的下标。序推广到多维数组，可规定为先排最左的下标。中国科大数据结构5-8 5.2 数组的顺序表示和实现p二维数组元素的存取二维数组元素的存取n二维数组二维数组A Amnmn按按“行优先顺序行优先顺序”存储在内存中，假设每个元素占存储在内存中，假设每个元素占用用L L个存储单元。个存储单元。n元素元素a aijij的存储地址应是数组的基地址加上排在的存储地址应是数组的基地址加上排在a aijij前面的元素所前面的元素所占用的单元数。因为占用的单元数。因为a aijij位于第位于第i i行、第行、第j j列，前面列，前面 i-1 行一共有行一共有(i-1)n 个元素，第个元素，第i i行上行上a aijij前面又有前面又有j-1j-1个元素，故它前面一个元素，故它前面一共有共有(i-1)n+j-1个元素，因此，个元素，因此，aij的地址计算函数为：的地址计算函数为：LOC(aij)=LOC(a11)+(i-1)*n+j-1*L中国科大数据结构5-9 5.2 数组的顺序表示和实现p例：二维数组例：二维数组AcAc1 1.d.d1 1,c,c2 2.d.d2 2 的存取的存取n分析：分析：a aijij前一共有前一共有i-ci-c1 1行，二维数组一共有行，二维数组一共有d d2 2-c-c2 2+1+1列，故这列，故这i-i-c c1 1行共有行共有(i-c(i-c1 1)*(d(d2 2-c-c2 2+1)+1)个元素，第个元素，第i i行上行上a aijij前一共有前一共有j-cj-c2 2个个元素，因此，元素，因此，a aijij的地址计算函数为：的地址计算函数为：LOC(aij)=LOC(ac1c2)+(i-c1)*(d2-c2+1)+j-c2)*Ln在在C C语言中，数组各维下标的下界是语言中，数组各维下标的下界是0 0，因此二维数组，因此二维数组A Am m n n的地址的地址计算公式为：计算公式为：LOC(aij)=LOC(a00)+(i*n+j)*L中国科大数据结构5-10 5.3 矩阵的压缩存储p在高级语言编制程序时，将一个矩阵描述为一个二维数组。在高级语言编制程序时，将一个矩阵描述为一个二维数组。p矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为运算也非常简单，并且存储的密度为1 1。但是在矩阵中非零元素呈。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为密度仍为1 1，但实际上占用了许多单元去存储重复的非零元素或零，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费元素，这对高阶矩阵会造成极大的浪费.p为了节省存储空间，为了节省存储空间，对这类矩阵进行压缩存储：即为多个相同的对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。非零元素只分配一个存储空间；对零元素不分配空间。中国科大数据结构5-11 5.3 矩阵的压缩存储5.3.1 特殊矩阵特殊矩阵所谓所谓是指非零元素或零元素的分布有一定规律的矩阵，是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。下面我们讨论几种特殊矩阵的压缩存储。1 1、对称矩阵、对称矩阵 2 2、对角矩阵、对角矩阵中国科大数据结构5-12 5.3 矩阵的压缩存储p对称矩阵对称矩阵在一个在一个n n阶方阵阶方阵A A中，若元素满足下述性质：中，若元素满足下述性质：aij=aji 0i,jn-1 则称则称A A为为对称矩阵对称矩阵。如下图是一个。如下图是一个5 5阶对称矩阵。阶对称矩阵。对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按样，能节约近一半的存储空间。不失一般性，我们按“行优先顺序行优先顺序”存储主对角线（包括对角线）以下的元素，其存储形式如上图示。存储主对角线（包括对角线）以下的元素，其存储形式如上图示。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-13 5.3 矩阵的压缩存储p对称矩阵的存储表示对称矩阵的存储表示n在这个下三角矩阵中，第在这个下三角矩阵中，第i i行恰有行恰有i+1i+1个元素，元素总数为：个元素，元素总数为：(i+1)=n(n+1)/2n因此，我们可以按行优先的次序将这些元素存放在一个向量因此，我们可以按行优先的次序将这些元素存放在一个向量sa0.n(n+1)/2-1sa0.n(n+1)/2-1中。中。pa aijij和和sak sak 之间对应关系之间对应关系n若若ijij，则，则a ai ji j在下三角形中。在下三角形中。a ai ji j之前的之前的i i行（从第行（从第0 0行到第行到第i-i-1 1行）一共有行）一共有 1+2+i=i(i+1)/2 个元素，在第个元素，在第i i行上，行上，a ai ji j之前之前恰有恰有j j个元素（即个元素（即 ai0,ai1,ai2,aij-1），因此有：），因此有：k=i*(i+1)/2+j 0kn(n+1)/2n若若ijij，则，则a aijij是在上三角矩阵中。因为是在上三角矩阵中。因为a aijij=a=ajiji，所以只要交换上，所以只要交换上述对应关系式中的述对应关系式中的i i和和j j即可得到：即可得到：k=j*(j+1)/2+i 0 k1i-j1时，元素时，元素a aijij=0=0。n由此可知，一个由此可知，一个k k对角矩阵对角矩阵(k(k为奇数为奇数)A)A是满足下述条件的矩阵：是满足下述条件的矩阵：若若i-j(k-1)/2 i-j(k-1)/2，则元素，则元素 a aijij=0=0。n对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。个向量中，并且也能找到每个非零元素和向量下标的对应关系。中国科大数据结构5-18 5.3 矩阵的压缩存储在三对角矩阵里附满足条件在三对角矩阵里附满足条件i=0i=0，j=0j=0、1 1，或，或i=n-1j=n-2i=n-1j=n-2、n-1n-1或或1in-1,j=i-11in-1,j=i-1、i i、i+1i+1的元素的元素a aijij外，其余元素都是零。外，其余元素都是零。对这种矩阵，我们也可按行优序为主序来存储。除第对这种矩阵，我们也可按行优序为主序来存储。除第0 0行和第行和第n-n-1 1行是行是2 2个元素外，每行的非零元素都是个元素外，每行的非零元素都是3 3个，因此，需存储的元素个个，因此，需存储的元素个数为数为3n-23n-2。数组数组sasa中的元素中的元素saksak与三对角带状矩阵中的元素与三对角带状矩阵中的元素a aijij存在一一存在一一对应关系，在对应关系，在a aijij之前有之前有i i行行,共有共有3 3*i-1i-1个非零元素，在第个非零元素，在第i i行，有行，有j-j-i+1i+1个非零元素个非零元素.a n-1 n-1a n-1 n-2a21 a12a11a10a01 a00K=0 1 2 3 4 5 3n-2 3n-1中国科大数据结构5-19 5.3 矩阵的压缩存储5.3.2 稀疏矩阵稀疏矩阵p定义：设矩阵定义：设矩阵A A中有中有s s个非零元素，若个非零元素，若s s远远小于矩阵元素的总数远远小于矩阵元素的总数（即（即smsm)m=n;/不是子表不加深度不是子表不加深度 temp=temptp;/temp指向下一个元素指向下一个元素 return m+1;中国科大数据结构5-40 习题p本章习题参见教师网页：本章习题参见教师网页：http:/