数据结构第五章C剖析.ppt

第五章多维数组和广义表,第五章多维数组和广义表,5.1多维数组5.2矩阵的压缩存储5.2.1特殊矩阵5.2.2稀疏矩阵5.3广义表的概念5.4广义表的存储,本章主题：多维数组、特殊矩阵和广义表教学目的：掌握数组和广义表的定义、运算教学难点：矩阵的压缩存储,对许多应用程序来说，使用简单的线性表和数组完成任务就足够了，但是有一些应用程序不能使用简单线性表来有效地实现。人们可以对线性表进行扩展，实现一些功能更强大、具有更多操作的高级线性结构。前几章讨论的线性结构中的数据元素都是非结构的原子类型，元素的值是不再分解的。本章讨论的两种数据结构-数组和广义表可以看成是线性表在下述含义上的扩展：表中的数据元素本身也是一个数据结构。,多维数组和广义表的逻辑特征是：一个数据元素可能有多个直接前趋和多个直接后继。5.1多维数组数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的结构类型。数组（Array）是由n(n1)个相同类型数据元素a0，al，ai，an-1构成的有限序列。n是数组的长度。其中数组中的数据元素ai是一个数据结构，即ai可以是线性表中的一个元素，本身也可以是一个线性表，而线性子表中的每一个数据元素还可以再分解。根据数组元素ai的组织形式不同，数组可以分为一维数组、二维数组以及多维（n维）数组。,可以看成是由m个行向量组成的向量，也可以看成是n个列向量组成的向量。二维数组中的每个元素aij均属于两个向量：第i行的行向量和第j列的列向量，即除边界外，每个元素aij都恰好有两个直接前趋和两个直接后继结点。二维数组仅有一个开始点a11，它没有前趋；仅有一个终端结点amn，它没有后继。边界上的结点（开始结点和终端结点除外）只有一个直接前趋或者只有一个直接后继。三维数组中的每个元素aijk都属于三个向量：每个元素最多可以有三个直接前趋和三个直接后继。依次类推，m维数组的每个元素都属于m个向量，最多可以有m个直接前趋和m个直接后继。,由于计算机的内存结构是一维的，因此用一维内存来表示多维数组，就必须按某种次序将数组元素排成一个线性序列，然后将这个线性序列存放在存储器中。又由于对数组一般不做插入和删除操作，也就是说，数组一旦建立，结构中的元素个数和元素间的关系就不再发生变化。因此，一般都是采用顺序存储的方法来表示数组。通常有两种顺序存储方式：行优先顺序将数组元素按行排列，第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语言中，数组就是按列优先顺序存储的。,a11a12.a1n,a21a22.a2n,am1am2.amn,.,loc(aij)=loc(a11)+(i-1)n+(j-1)S,按行优先顺序存放,a11a12.a1n,a21a22.a2n,am1am2.amn,.,loc(aij)=loc(a11)+(j-1)m+(i-1)S,按列优先顺序存放,假设有一个342的三维数组A，共有24个元素，其逻辑结构如图所示。三维数组的标号由三个数字表示，即行、列、纵三个方向。a142表示第1行，第4列，第2纵的元素。如果对A342（下标从1开始）采用以行优先的方法存放，即行下标变化最慢，纵下标变化最快，则顺序为：a111,a112,a121,a122,a331,a332,a341,a342,采用以纵优先的方法存放，即纵下标变化最慢，行下标变化最快，则顺序为：a111,a211,a311,a121,a221,a321,a132,a232,a332,a142,a242,a342,以上规则可以推广到多维数组的情况：优先顺序可规定为先排最右的下标，从右到左，最后排最左下标：列优先顺序与此相反，先排最左下标，从左向右，最后排最右下标。按上述两种方式顺序存储的数组，只要知道开始结点的存放地址（即基地址），维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。,总结：任何多维数组都可以看作一个线性表，这时线性表中的每个数据元素也是一个线性表。例如一个二维数组可以看作是每个数据元素都是相同类型的一维数组。多维数组是特殊的线性表，是线性表的推广。数组的性质：(1)数组中的数据元素数目固定。一旦定义了一个数组，其数据元素数目不再有增减变化。它属于静态分配存储空间的数据结构。(2)数组中的数据元素必须具有相同的数据类型。(3)数组中的每个数据元素都有一组唯一的下标值。(4)数组是一种随机存储结构。可随机存取数组中的任意数据元素。,例如，二维数组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同样，三维数组Amnp可以看成是m个np的二维数组，按“行优先顺序”存储，其地址计算函数为：LOC(aijk)=LOC(a111)+(i-1)*n*p+(j-1)*p+(k-1)*d,上述讨论均是假设数组各维的下界是1，更一般的二维数组是Ac1.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(ac1c2)+(i-c1)*(d2-c2+1)+j-c2)*d例如，在C语言中，数组各维下标的下界是0，因此在C语言中，二维数组的地址计算公式为：LOC(aij)=LOC(a00)+(i*(d2+1)+j)*d,【例】对于给定的二维数组floata34，计算：(1)数组a中的数组元素数目；(2)若数组a的起始地址为1000，且每个数组元素长度为32位(即4个字节)，数组元素a23的内存地址。【解】(1)由于C语言中数组的行、列下标值的下界均为0，该数组行上界为3-1=2，列上界为4-1=3，所以该数组的元素数目共有3*4=12个。(2)由于C语言采用行序为主序的存储方式，有：LOC(a23)=LOC(a00)+(i*（d2+1)+j)*d=1000+(2*4+3)*4=1044,5.2矩阵的压缩存储在科学与工程计算问题中，矩阵是一种常用的数学对象，在用高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。,5.2.1特殊矩阵所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面讨论几种特殊矩阵的压缩存储。1、对称矩阵在一个n阶方阵A中，若元素满足下述性质：aij=aji0i,jn-1则称A为对称矩阵。下图便是一个5阶对称矩阵。对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先顺序”存储主对角线（包括对角线）以下的元素，其存储形式如图所示：,若ij，则aij在下三角形中。aij之前的i行（从第0行到第i-1行）一共有1+2+i=i(i+1)/2个元素，在第i行上，aij之前恰有j个元素（即ai0,ai1,ai2,aij-1），因此有：k=i*(i+1)/2+j0kn(n+1)/2若ij，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到：k=j*(j+1)/2+i0kn(n+1)/2令I=max(i,j)，J=min(i,j)，则k和i,j的对应关系可统一为：k=I*(I+1)/2+J0k(k-1)/2，则元素aij=0。对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。上述的各种特殊矩阵，其非零元素的分布都是有规律的，因此总能找到一种方法将它们压缩存储到一个向量中，并且一般都能找到矩阵中的元素与该向量的对应关系，通过这个关系，仍能对矩阵的元素进行随机存取。,5.2.2稀疏矩阵什么是稀疏矩阵？简单说，设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即smn），则称A为稀疏矩阵。假设在矩阵A中，有s个非零元素。令e=s/(m*n)，称e为矩阵的稀疏因子。通常认为e0.05时称之为稀疏矩阵。在存储稀疏矩阵时，为了节省存储单元，很自然地想到使用压缩存储方法。但由于非零元素的分布一般是没有规律的，因此在存储非零元素的同时，还必须同时记下它所在的行和列的位置（i,j)。于是，一个三元组(i,j,aij)唯一确定了矩阵A的一个非零元素。因此，稀疏矩阵可由表示非零元素的三元组及其行列数唯一确定。,例如，下列三元组表(1,2,12)(1,3,9),(3,1,-3),(3,6,14),(4,3,24),(5,2,18),(6,1,15),(6,4,-7)加上(6,7)这一对行、列值便可作为下列矩阵M的另一种描述。而由上述三元组表的不同表示方法可引出稀疏矩阵不同的压缩存储方法。0129000000-30015000000012000180-3000014090024000024000000000701800000001400015007000000000000000稀疏矩阵M和T,M=,T=,1、三元组表假设以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方法三元顺序表。#definemaxsize16typedefintdatatype;typedefstructinti,j;datatypev;node;typedefstructnodedatamaxsize;intm,n,t;spmatrix;,ijv011202920-3251432244118501553-7,012900000000000-30000140002400000180000015007000,设A为spmatrix型的结构变量，如图所示的稀疏矩阵的三元组的表示如下：,下面以矩阵的转置为例，说明在这种压缩存储结构上如何实现矩阵的运算。一个mn的矩阵A，它的转置B是一个nm的矩阵，且aij=bji，0im，0jn，即A的行是B的列，A的列是B的行。将A转置为B，就是将A的三元组表a.data置换为表B的三元组表b.data，如果只是简单地交换a.data中i和j的内容，那么得到的b.data将是一个按列优先顺序存储的稀疏矩阵B，要得到按行优先顺序存储的b.data，就必须重新排列三元组的顺序。由于A的列是B的行，因此，按a.data的列序转置，所得到的转置矩阵B的三元组表b.data必定是按行优先存放的。,21,5,3,-1,3,2,-4,1,1,15,4,0,700-2,0-400,15000,0000,00-10,00021,顺序存储结构稀疏矩阵的转置运算,按这种方法设计的算法，其基本思想是：对A中的每一列col(0coln-1)，通过从头至尾扫描三元表a.data，找出所有列号等于col的那些三元组，将它们的行号和列号互换后依次放入b.data中，即可得到B的按行优先的压缩存储表示。,ijv02-3051510121418209232435-75214,ijv011202920-3251432244118501553-7,Voidtransmatrix(tripletablea,tripletableb)intpqcol;b.m=a.n;b.n=a.m;b.t=a.t;if(b.t=0)printf(“A=0n”);q=0;for(col=1;col=a.n;col+)for(p=0;p=a.t;p+)if(a.datap.j=col)b.dataq.i=a.datap.j;b.dataq.j=a.datap.i;b.dataq.v=a.datap.v;q+;,分析这个算法，主要的工作是在p和col的两个循环中完成的，故算法的时间复杂度为O(n*t)，即矩阵的列数和非零元素的个数的乘积成正比。而一般传统矩阵的转置算法为：for(col=0;col=n-1;+col)for(row=0;row=m;+row)tcolrow=mrowcol;其时间复杂度为O(n*m)。当非零元素的个数t和m*n同数量级时，算法transmatrix的时间复杂度为O(n*n2)。三元组顺序表虽然节省了存储空间，但时间复杂度比一般矩阵转置的算法还要复杂，同时还有可能增加算法的难度。因此，此算法仅适用于t=0)个元素a1,a2,a3,an的有限序列，其中ai或者是原子项，或者是一个广义表。通常记作LS=（a1,a2,a3,an)。LS是广义表的名字，n为它的长度。若ai是广义表，则称它为LS的子表。,广义表LS=(1,2,n)的结构特点:1)广义表中的数据元素有相对次序；2)广义表的长度定义为最外层包含元素个数；3)广义表的深度定义为所含括弧的重数；注意：“原子”的深度为0“空表”的深度为1通常用圆括号将广义表括起来，用逗号分隔其中的元素。为了区别原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。若广义表LS（n=1)非空，则a0是LS的表头，其余元素组成的表(a1,a2,an)称为LS的表尾。,显然广义表是递归定义的，这是因为在定义广义表时又用到了广义表的概念。广义表的例子如下：（1）A=（）A是一个空表，其长度为零。（2）B=（e）表B只有一个原子e，B的长度为1。（3）C=（a,(b,c,d)表C的长度为2，两个元素分别为原子a和子表(b,c,d)。（4）D=（A，B，C）表D的长度为3，三个元素都是广义表。显然，将子表的值代入后，则有D=(),(e),(a,(b,c,d)。（5）E=（a，E）这是一个递归的表，它的长度为2，E相当于一个无限的广义表E=(a,(a,(a,(a,).,从上述定义和例子可推出广义表的三个重要结论：（1）广义表的元素可以是子表，而子表的元素还可以是子表。由此，广义表是一个多层次的结构，可以用图形象地表示。（2）广义表可为其它表所共享。例如在上述例（4）中，广义表A，B，C为D的子表，则在D中可以不必列出子表的值，而是通过子表的名称来引用。（3）广义表的递归性。递归表的深度是无穷值，长度是有限值。,广义表的分类：（1）线性表：元素全部是原子的广义表。（2）纯表：与树对应的广义表，见下图。（3）再入表：与图对应的广义表(允许结点共享)，（4）递归表：允许有递归关系的广义表，例如E=(a,E)。这四种表的关系满足：递归表再入表