数据结构课件PPT110章全 第五章 数组和广义表.ppt 50页

'第五章数组和广义表5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.3.1特殊矩阵5.3.2稀疏矩阵5.4广义表的定义5.5广义表的存储结构 数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数所元素本身也是一种线性表。5.1数组的定义数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组：a11a12…a1na21a22…a2n…………am1am2…amnAmn= 可以看成是由个n行向量组成的向量，也可以看成是个m列向量组成的向量。在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说，typedefelemtypearray2[m][n];等价于：typedefelemtypearray1[n];typedefarray1array2[m];同理，一个n维数组类型可以定义为其数据元素为n-1维数组类型的一维序组类型。数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。 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,……,an1,an2,…,anm在FORTRAN语言中，数组就是按列优先顺序存储的。 以上规则可以推广到多维数组的情况：行优先顺序可规定为先排最右的下标，从右到左，最后排最左下标：列优先顺序与此相反，先排最左下标，从左向右，最后排最右下标。按上述两种方式顺序存储的序组，只要知道开始结点的存放地址（即基地址），维数和每维的上、下界，以及每个数组元素所占用的单元数，就可以将数组元素的存放地址表示为其下标的线性函数。因此，数组中的任一元素可以在相同的时间内存取，即顺序存储的数组是一个随机存取结构。 例如，二维数组Amn按“行优先顺序”存储在内存中，假设每个元素占用L个存储单元。元素aij的存储地址应是数组的基地址加上排在aij前面的元素所占用的单元数。因为aij位于第i行、第j列，前面i-1行一共有(i-1)×b2个元素，第i行上aij前面又有j-1个元素，故它前面一共有(i-1)×b2+j-1个元素，因此，aij的地址计算函数为：LOC(aij)=LOC(a11)+[(i-1)*b2+j-1]*L同样，三维数组Aijk按“行优先顺序”存储，其地址计算函数为：LOC(aijk)=LOC(a111)+[(i-1)*b2*b3+(j-1)*b3+(k-1)]*L 上述讨论均是假设数组各维的下界是1，更一般的二维数组是A[c1..b1,c2..b2]，这里c1,c2不一定是1。aij前一共有i-c1行，二维数组一共有b2-c2+1列，故这i-c1行共有(i-c1)*(b2-c2+1)个元素，第i行上aij前一共有j-c2个元素，因此，aij的地址计算函数为：LOC(aij)=LOC(ac1c2)+[(i-c1)*(b2-c2+1)+j-c2)]*L例如，在C语言中，数组各维下标的下界是0，b长度的数组下标为0..b-1。因此在C语言中，二维数组a[b1][b2]的地址计算公式为：LOC(aij)=LOC(a00)+(i*b2+j)*L 更一般地，可以得到n维数组存储位置的计算公式，如书P93映像函数。P93，数组的顺序表示和实现 5.3矩阵的压缩存储在科学与工程计算问题中，矩阵是一种常用的数学对象，在高级语言编制程序时，简单而又自然的方法，就是将一个矩阵描述为一个二维数组。矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费，为了节省存储空间，我们可以对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。 5.3.1特殊矩阵所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。1、对称矩阵在一个n阶方阵A中，若元素满足下述性质：aij=aji1≦i,j≦n则称A为对称矩阵。对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先 顺序”存储主对角线（包括对角线）以下的元素，其存储形式如图所示：15137a1150800a21a2218926a31a32a3330251………………..70613an1an2an3…ann图5.1对称矩阵在这个下三角矩阵中，第i行恰有i个元素，元素总数为：1+2+…+n=n(n+1)/2因此，我们可以按图中箭头所指的次序将这些元素存放在一个向量sa[0..n(n+1)/2-1]中。为了便于访问对称矩阵A中的元素，我们必须在aij和sa[k] 之间找一个对应关系。若i≧j，则aij在下三角形中。aij之前的i-1行（从第1行到第i-1行）一共有1+2+…+i-1=i(i-1)/2个元素，在第i行上，aij之前恰有j-1个元素（即ai1,ai2,…,aij-1），因此有：k=i*(i-1)/2+j-10≦k=0个元素a1,a2,a3,…,an的有限序列。线性表的元素仅限于原子项，原子是作为结构上不可分割的成分，它可以是一个数或一个结构，若放松对表元素的这种限制，容许它们具有其自身结构，这样就产生了广义表的概念。广义表是n(n>=0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表。通常记作LS=（a1,a2,a3,…,an)。LS是广义表的名字，n为它的长度，当n=0时为空表。若ai是广义表，则称它为LS的子表。广义表的深度指的是广义表中括弧的重数。 通常用圆括号将广义表括起来，用逗号分隔其中的元素。为了区别原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。若广义表LS（n>=1)非空，则a1是LS的表头，其余元素组成的表(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，三个元素A,B,C都是广义表。显然，将子表的值代入后，则有D=((),(e),(a,(b,c,d)))。 (5)E=（a,E）——这是一个递归的表，它的长度为2，E相当于一个无限的广义表E=(a,(a,(a,(a,…)))).从上述重要结论：定义和例子可推出广义表的三个广义表的元素可以是子表，而子表的元素还可以是子表。由此，广义表是一个多层次的结构，可以用图形象地表示。P108广义表可为其它表所共享。例如在上述例（4）中，广义表A，B，C为D的子表，则在D中可以不必列出子表的值，而是通过子表的名称来引用。广义表可以是一个递归的表，如例（5）。 由表头、表尾的定义可知：任何一个非空广义表其表头可能是广义表，也可能是广义表，而其表尾必定是广义表。对于B=(e)GetHead(B)=e,GetTail(B)=()对于D＝(A,B,C)GetHead(D)=A,GetTail(D)=(B,C)由于(B,C)为非空广义表，则可继续分解得到：GetHead(B,C)=BGetTail(B,C)=(C)注意广义表（）和(())不同。前者是长度为0的空表，对其不能做求表头的和表尾的运算；而后者是长度为1的非空表（只不过该表中唯一的一个元素是空表）。对其可进行分解，得到表头和表尾均为空表（）。 5.5广义表的存储结构由于广义表(a1,a2,a3,…an)中的数据元素可以具有不同的结构（或是原子，或是广义表），因此，难以用顺序存储结构表示，通常采用链式存储结构，每个数据元素可用一个结点表示。由于广义表中有两种数据元素，原子或广义表，因此，需要两种结构的结点：一种是表结点，一种是原子结点。下面介绍两种广义表的链式存储结构。1、表结点由三个域组成：标志域、指示表头的指针域和指示表尾的指针域；而原子域只需两个域：标志域和值域。表结点原子结点tag=1hptptag=0atom 广义表的头尾链表存储表示typedefenum{ATOM,LIST}ElemTag;//ATOM==0表示原子，LIST＝＝1表示子表typedefstructGLNode{ElemTagtag;union{AtomTypeatom;struct{structGLNode*hp,*tp;}ptr;//ptr是表结点的指针域，ptr.hp和ptr.tp分别指示表头和表尾。};}*GList; tag=1hptptag=0atomtp2广义表的扩展线性链表存储表示，如下图:表结点原子结点 广义表的扩展线性链表存储表示：typedefenum{ATOM,LIST}ElemTag;typedefstructGLNode{ElemTagtag;union{AtomTypeatom;structGLNode*hp;};structGLNode*tp;}*GList; 习题5.7,5.18,5.195.10(5)(7),5.11(4)(6),5.12(1),5.13(1),5.23,5.30'