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

数据结构 第五章 数组与广义表,本章内容 5.1 数组的定义 5.2 数组的顺序表示和实现 5.3 矩阵的压缩存储 5.4 广义表的定义 5.5 广义表的存储结构,5-3,数组和广义表可看成是一种特殊的线性表。表中的元素本身也是一种数据结构。 数组的的数据元素是数组；广义表的数据元素可以是原子类型，也可以是广义表，分别称为广义表的原子项和子表,数组和广义表简单描述,5-4,数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更为简单。多维数组是向量的推广。例如，二维数组：,5.1 数组的定义,5-5,5.1 数组的定义,二维数组 二维数组可以看成是由若干个行向量组成的向量，也可以看成是若干个列向量组成的向量。 在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说，typedef elemtype array2mn; 等价于： typedef elemtype array1n; typedef array1 array2m; 多维数组：用一维顺序结构线性表实现多维数组 struct Array ElemType *buffer; / 数据区 int dims; / 维数 int *L; / 各维长度 ;,5-6,5.2 数组的顺序表示和实现,设一3维数组A423，存贮在一个顺序线性表S中，结构如下所示：,5-7,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语言中，数组就是按列优先顺序存储的。列优先顺序推广到多维数组，可规定为先排最左的下标。,5-8,5.2 数组的顺序表示和实现,二维数组元素的存取 二维数组Amn按“行优先顺序”存储在内存中，假设每个元素占用L个存储单元。 元素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*L,5-9,5.2 数组的顺序表示和实现,例：二维数组Ac1d1,c2d2的存取 分析：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)*L 在C语言中，数组各维下标的下界是0，因此二维数组Amn的地址计算公式为： LOC(aij) = LOC(a00)+(i*n+j)*L,5-10,5.3 矩阵的压缩存储,在高级语言编制程序时，将一个矩阵描述为一个二维数组。 矩阵在这种存储表示之下，可以对其元素进行随机存取，各种矩阵运算也非常简单，并且存储的密度为1。但是在矩阵中非零元素呈某种规律分布或者矩阵中出现大量的零元素的情况下，看起来存储密度仍为1，但实际上占用了许多单元去存储重复的非零元素或零元素，这对高阶矩阵会造成极大的浪费. 为了节省存储空间， 对这类矩阵进行压缩存储：即为多个相同的非零元素只分配一个存储空间；对零元素不分配空间。,5-11,5.3 矩阵的压缩存储,5.3.1 特殊矩阵 所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵，下面我们讨论几种特殊矩阵的压缩存储。 1、对称矩阵 2、对角矩阵,5-12,5.3 矩阵的压缩存储,对称矩阵 在一个n阶方阵A中，若元素满足下述性质：aij=aji 0i,jn-1 则称A为对称矩阵。如下图是一个5阶对称矩阵。 对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间，这样，能节约近一半的存储空间。不失一般性，我们按“行优先顺序”存储主对角线（包括对角线）以下的元素，其存储形式如上图示。,5-13,5.3 矩阵的压缩存储,对称矩阵的存储表示 在这个下三角矩阵中，第i行恰有i+1个元素，元素总数为： (i+1) = n(n+1)/2 因此，我们可以按行优先的次序将这些元素存放在一个向量sa0n(n+1)/2-1中。 aij和sak 之间对应关系 若ij，则ai j在下三角形中。 ai j之前的i行（从第0行到第i-1行）一共有 1+2+i=i(i+1)/2 个元素，在第i行上， ai j之前恰有j个元素（即 ai0,ai1,ai2,aij-1），因此有： k=i*(i+1)/2+j 0kn(n+1)/2 若ij，则aij是在上三角矩阵中。因为aij=aji，所以只要交换上述对应关系式中的i和j即可得到： k=j*(j+1)/2+i 0 kn(n+1)/2,5-14,5.3 矩阵的压缩存储,aij的地址可用下列式子计算： LOC(aij ) = LOC(sak) =LOC(sa0)+k*L = LOC(sa0）+I*(I+1)/2+J*L 有了上述的下标交换关系，对于任意给定一组下标(i，j)，均可在sak中找到矩阵元素aij，反之，对所有的k=0,1,2,，n(n-1)/2-1，都能确定sak中的元素在矩阵中的位置(i,j)。,5-15,5.3 矩阵的压缩存储,称san(n+1)/2为对称矩阵A的压缩存储，见下图： 例如a21和a12均存储在 sa4中，这是因为 k=I*(I+1)/2+J=2*(2+1)/2+1=4,5-16,5.3 矩阵的压缩存储,对角矩阵 对角矩阵中，所有的非零元素集中在以主对角线为了中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零。下图给出了一个三对角矩阵。,5-17,5.3 矩阵的压缩存储,对角矩阵的存储表示 非零元素仅出现在主对角(aii,0in-1上，紧邻主对角线上面的那条对角线上(aii+1,0in-2)和紧邻主对角线下面的那条对角线上(ai+1 i,0in-2)。显然，当i-j1时，元素aij=0。 由此可知，一个k对角矩阵(k为奇数)A是满足下述条件的矩阵：若i-j(k-1)/2 ，则元素 aij=0。 对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。,5-18,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个非零元素.,5-19,5.3 矩阵的压缩存储,5.3.2 稀疏矩阵 定义：设矩阵A中有s个非零元素，若s远远小于矩阵元素的总数（即smn），则称A为稀疏矩阵。 设在的矩阵A中，有s个非零元素。令 e=s/(m*n)，称e为矩阵的稀疏因子。通常认为e0.05时称之为稀疏矩阵。 稀疏矩阵的存储 存储非零元素的同时，还必须记下所属行和列的位置（i,j)。 一个三元组(i,j,aij)唯一确定了矩阵A的一个非零元。 稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。 这样的存储方法大大节约了存储空间，但矩阵的运算变得复杂。,5-20,5.3 矩阵的压缩存储,三元组法存储,5-21,5.3 矩阵的压缩存储,带行向量的三元组法 注意：第三行在三元表中不存在，所以行向量以上一行的位置代替,5-22,5.3 矩阵的压缩存储,三元组法表示的矩阵转置 方法1：先行栏对调地复制，再排序 方法2：对目标矩阵逐行扫描,5-23,5.3 矩阵的压缩存储,5-24,5.3 矩阵的压缩存储,带行向量的三元组法的矩阵乘法,5-26,5.3 矩阵的压缩存储,十字链表法：为稀疏矩阵中的链接存储中的一种较好的存储方法,5-27,5.3 矩阵的压缩存储,十字链表结点定义：每一个非零元用一个结点表示，结点包括五个域：除了表示非零元所在的行、列和值的三元组（i, j, v）外，还需增加两个链域：行指针域（right），用来指向本行中下一个非零元素；列指针域（down），用来指向本列中下一个非零元素。,5-28,5.3 矩阵的压缩存储,十字链表类型定义 稀疏矩阵中同一行的非零元通过向右的right指针链接成一个带表头结点的线性链表。同一列的非零元也通过down指针链接成一个带表头结点的线性链表。因此，每个非零元既是第i行循环链表中的一个结点，又是第j列循环链表中的一个结点，相当于处在一个十字交叉路口，故称链表为十字链表。可用两个分别存储行链表的头指针和列链表的头指针的一维数组表示之。,5-29,5.3 矩阵的压缩存储,稀疏矩阵的十字链表存储表示,typedef struct CLNode int i, j ; DataType v; struct CLNode * right, *down; CLNode; typedef struct CLNode *rheadMaxRow; /行链表头指针，MaxRow在前定义 CLNode *cheadMaxCol; /列链表头指针，MaxRow在前定义 int n, m, t; CrossList; CrossList A;,5-30,5.4 广义表,广义表的概念 n ( 0 )个表元素组成的有限序列，记作 LS = ( a1, a1, a2, , an ) LS是表名，ai 是表元素，它可以是表(称为子表)，可以是数据元素(称为原子)。 n为表的长度。n = 0 的广义表为空表。 n 0 时，表的第一个表元素称为广义表的表头(head)，除此之外，其它表元素组成的表称为广义表的表尾(tail)。 广义表举例 A=（） / 空表，长度n = 0，d = 1 B=（a, b） / n=2, d=1. (线性表) C=（a, (b, c, d) ) / n=2, d=2. a1为原子，a2为子表 D=（A，B，C） / n=3, d=2. a1，a2 ,a3为子表 E= (a , E） / n=2, d=,5-31,5.4 广义表,任意一个非空广义表，均可分解为表头和表尾。 对于一个非空广义表，其表头可能是原子，也可能是子表；而表尾一定是子表。,5-32,5.4 广义表,性质 广义表是一个多层次结构; 广义表的深度 d 定义为所含括弧的重数; “原子”的深度为0 ; “空表”的深度为1 广义表可以共享;也可以是一个递归的表;,子表结点用圈表示， 原子结点用方框表示,5-33,5.5 广义表的存储结构,由于广义表的元素类型不同，难以用顺序结构表示，常用链接存储方法存储广义表，并称之为广义链表。 广义表中有两种数据元素，原子或子表，需要两种结构的结点：一种是表结点，一种是原子结点。 扩展的线性链表表示法 表结点由三个域组成：标志域、表头指针域和下一个元素的指针域； 原子结点的三个域为：标志域、值域和下一个元素的指针域。,5-34,5.5 广义表的存储结构,typedef enumatom,listelemtag; typedef struct GLnode Elemtag tag; union AtomType atom; struct GLnode *hp; /表结点的表头指针 ; struct GLnode *tp; / 指向下一个元素结点 *GList;,5-35,5.5 广义表的存储结构,广义表的运算 创建空的广义表: initGList(,5-36,5.5 广义表的存储结构,广义表作为ADT,ADT Glist 数据对象: D=ei |i=1,2, n; n0, ei AtomSet 或ei Glist 数据关系: R=(ei-1 , ei ) | ei D 基本操作: initGList(,5-37,5.5 广义表的存储结构,求广义表的深度 设：LS = (a1, a2, , an)， 例如，对于广义表 E ( B (a, b), D ( B (a, b), C (u, (x, y, z), A ( ) ) ) 按递归算法分析： Depth (E) = 1+Max Depth (B), Depth (D) Depth (B) = 1+Max Depth (a), Depth (b) = 1 Depth (D) = 1+Max Depth (B), Depth (C), Depth (A),5-38,5.5 广义表的存储结构,Depth (C) = 1+Max Depth (u), Depth (x, y, z) Dept