数据结构经典课件.ppt

第5章 数组和广义表,1教学目的：掌握数组和广义表的定义、特点及典型算法。2教学要求：掌握数组在以行为主的存储结构中的地址计算方法。掌握矩阵实现压缩存储时的下标变换。理解稀疏矩阵的两种存储方式的特点和适用范围，领会以三元组表示稀疏矩阵时进行运算采用的处理方法。掌握广义表的定义及其存储结构，学会将广义表分解为表头，表尾的方法。3教学重点：掌握特殊矩阵的压缩存储。掌握稀疏矩阵采用三元组存储时典型算法的实现。广义表的定义、运算。4教学难点：数组的十字链表存储结构。,图5.1 Amn的二维数组,5.1 数组,5.1.1 数组的逻辑结构 是线性表的推广 数组特点：元素本身可以是具有某种结构的数据，但属于同一数据类型。比如：一维数组可以看作一个线性表，二维数组可以看作“数据元素是一维数组”的一维数组，依此类推。图5.1是一个m行n列的二维数组。,图5.2 矩阵Amn看成n个列向量的线性表,图5.3 矩阵Amn看成m个行向量的线性表,推广：n维数组每个数据元素受n个关系的约束，任一单个关系，仍是线性关系。,通过以上分析可总结出数组具有以下性质：数组中数据元素数目固定。数组中数据元素具有相同的数据类型。数组中每一个数据元素由唯一的一组下标来标识。数组是随机存取的存储结构。在数组上不能做插入、删除数据元素的操作。通常在各种高级语言中数组一旦被定义，每一维的大小及上下界都不能改变。两种操作：取值操作：给定一组下标，读其对应的数据元素。赋值操作：给定一组下标，存储或修改其相对应的数据元素。,二维数组形式化表示为：,数组的顺序存储结构有两种：2Array（D,R）D=aij|i=c1,c1+1,d1,j=c2,c2+1,d2,aijD0 R=Row,Col Row|c1 i d1,c2 j d2-1,aij,ai(j+1)D0 Col|c1 i d1-1,c2 j d2,aij,a(i+1)j D0,5.1.2 数组的存储结构,数组的顺序存储结构有两种：1.按行序存储。如：BASIC、COBOL和PASCAL语言。2.按列序存储。如：FORTRAN语言。二维数组Amn以行为主的存储序列为：a11,a12,，a1n,a21,a22,a2n,am1,am2,amn 而以列为主的存储序列为：a11,a21,，am1，a12,a22,am2,a1n,a2n,amn,设有二维数组Amn，按元素的下标求其地址的计算：以“以行为主序”的分配为例：设数组的基址为LOC(a11)，每个数组元素占据l个地址单元，那么aij的物理地址计算为：LOC(aij)=LOC(a11)+(i-1)*n+j-1)*l,在C语言中，数组中每一维的下界定义为0，则：LOC(aij)=LOC(a00)+(i*n+j)*l 推广到一般二维数组：Ac1.d1c2.d2，aij地址计算函数为：LOC(aij)=LOC(a c1 c2)+(i-c1)*(d2-c2+1)+(j-c2)*l 同理对于三维数组Amnp，即mnp数组，aijk其物理地址为：LOC(aijk)=LOC(a111)+(i-1)*n*p+(j-1)*p+k-1)*l 推广到一般的三维数组：Ac1.d1c2.d2c3.d3，则aijk物理地址为：LOC(i,j,k)=LOC(a c1 c2 c3)+(i-c1)*(d2-c2+1)*(d3-c3+1)+(j-c2)*(d3-c3+1)+(k-c3)*l,容易看出，数组元素的存储位置是其下标的线性函数，一旦数组下标的界偶确定之后，数组中的元素可随机存取。我们称具有这一特点的存储结构为随机存储结构。,对于维数组A(c1.d1,c2.d2，,cn.dn)，元素aj1j2jn的存储地址的计算公式:,例5.1 若矩阵Amn 中存在某个元素aij满足：aij是第i行中最小值且是第j列中的最大值，则称该元素为矩阵A的一个鞍点。试编写一个算法，找出A中的所有鞍点。基本思想：在矩阵A中求出每一行的最小值元素，然后判断该元素是不是它所在列中的最大值，是则打印输出，接着处理下一行。矩阵A用一个二维数组表示。,void saddle(int A,int m,int n)int i,j,min;for(i=0;i=m)printf(%d,%d,%dn,i,k,min);/*if*/*for i*/,算法的时间性能为O(m*(n+m*n)。,5.2 特殊矩阵的压缩存储特殊矩阵：1.非零元素非常少；2.矩阵元素的分布有一定规律所谓压缩存储是指：为多个值相同的元素只分配一个存储空间，值为零的元素不分配空间。,5.2.1 对称矩阵 特点：在一个n阶方阵中，有aij=aji，其中1i,jn，如图5.3所示是一个5阶对称矩阵。,对于元素aij，特点是：ij且1in，下标k与i、j的关系为：k=i*(i-1)/2+j-1(kn*(n+1)/2)若ij，则aij是上三角中的元素，因为aij=aji，这样，访问上三角中的元素aij时则去访问和它对应的下三角中的aji即可，因此将上式中的行列下标交换就是上三角中的元素在SA中的对应关系：k=j*(j-1)/2+i-1(kn*(n+1)/2)对于对称矩阵中的任意元素aij，若令I=max(i,j)，J=min(i,j)，则将上面两个式子综合起来得到：k=I*(I-1)/2+J-1。,对于对称矩阵，因其元素满足aij=aji，只存下三角（或上三角）矩阵，将nn个元素压缩到n(n+1)/2个空间中。,5.2.2 三角矩阵 如图5.5的矩阵称为三角矩阵，其中c为某个常数。其中5.5(a)为下三角矩阵：主对角线以上均为同一个常数；(b)为上三角矩阵，主对角线以下均为同一个常数；下面讨论它们的压缩存储方法。,（1）下三角矩阵中元素aij(ij)在一维数组A中的位置为：Loci,j=Loc1,1+前i-1行非零元个数+第i行中aij前非零元个数 即：Loci,j=Loc1,1+i(i-1)/2+j-1设存入向量：SAn*(n+1)/2+1中，SA k与aij的对应关系为：,（2）上三角矩阵，也可以将其压缩存储到一个大小为n(n+1)/2的一维数组C中。其中元素aij(ij)在数组C中的存储位置为：,图5.8 带状矩阵A,三对角带状矩阵有如下特点：i=1,j=1,2;1in,j=i-1,i,i+1;i=n,j=n-1,n;时，aij非零，其它元素均为零。,当,5.2.3 带状矩阵,1.确定存储该矩阵所需的一维向量空间的大小 假设每个非零元素所占空间的大小为1个单元。所需一维向量空间的大小为2+2+3（n-2）=3n-2，如图5.9所示。,图5.9 带状矩阵的压缩形式,2.确定非零元素在一维数组空间中的位置 Loci,j=Loc1,1+前i-1行非零元个数+第i行中aij前非零元个数；前i-1行元素个数=3(i-1)-1（因为第1行只有2个非零元素）；第i行中aij前非零元素个数=j-i+1，其中,由此得到,Loci,j=Loc1,1+3(i-1)-1+j-i+1=Loc1,1+2(i-1)+j-1,5.3 稀疏矩阵的压缩存储 设mn矩阵中有t个非零元素且tmn，这样的矩阵称为稀疏矩阵。,5.3.1 稀疏矩阵 非零元个数远远小于零元个数。,图5.10 稀疏矩阵,三元组表的类型说明如下：define SMAX 1024 typedef struct int i,j;datatype v;SPNode;typedef struct int mu,nu,tu;SPNode dataSMAX;SPMatrix;,1)用三元组表实现稀疏矩阵的转置运算如图所示的67矩阵M，它的转置矩阵就是76的矩阵N，并且N（row，col）=M（col，row），其中，1row7，1col6。,采用矩阵的正常存储方式时，实现矩阵转置的经典算法如下：void TransMatrix（datatype sourcenm,datatype destmn）int i,j;for(i=0;im;i+)for(j=0;j n;j+)desti j=sourcej i;,矩阵source的三元组表A的行、列互换就可以得到B中的元素，如图5.13所示。,(i,j,x)(j,i,x)A B,图5.13 稀疏矩阵的转置示例,为了保证转置后的矩阵的三元组表B也是以“行序为主序”进行存放，则需要对行、列互换后的三元组表B按B的行下标（即A的列下标）大小重新排序，如图5.14所示。,图5.14 矩阵的转置(用三元组表示矩阵),方法一：,图5.15 矩阵的转置,附设一个位置计数器j，用于指向当前转置后元素应放入三元组表B中的位置。处理完一个元素后，j加1，j的初值为1。,具体转置算法如下：Void TransposeTSMatrix(TSMatrix A,TSMatrix*B)int i,j,k;B-mu=A.nu;B-nu=A.mu;B-tu=A.tu;if(B-tu0),j=1;for(k=1;kdataj.row=A.datai.col B-dataj.col=A.datai.row;B-dataj.e=A.datai.e;j+;,【算法5.1 基于稀疏矩阵的三元组表示矩阵的转置算法】,时间复杂度为O（A.nA.len）,最坏情况当A.len=A.mA.n时，时间复杂度为O（A.mA.n2）。采用正常方式实现矩阵转置的算法时间复杂度为O（A.mA.n）。方法二：依次按三元组表A的次序进行转置，转置后直接放到三元组表B的正确位置上。这种转置算法称为快速转置算法。,为了能将待转置三元组表A中元素一次定位到三元组表B的正确位置上，需要预先计算以下数据：(1)待转置矩阵每一列中非零元素的个数。(2)待转置矩阵每一列中第一个非零元素在三元组表B中的正确位置。,为此，需要设两个数组 numcol用来存放A中第col列非零元素个数 positioncol用来存放A中第col列中第一个非零元素在三元组表B中的正确位置。其中：（1）numcol的计算方法：将三元组表A扫描一遍，对于其中列号为k的元素，给相应的numk加1。（2）positioncol的计算方法：position1=1，positioncol=position col-1+numcol-1，其中2colA.nu。,具体算法如下：,FastTransposeTSMatrix(TSMatrix*A)/*基于矩阵的三元组表示，采用快速转置法，将矩阵A转置为B所指的矩阵*/int col,t,p，q;int numMAXSIZE,positionMAXSIZE;B-tu=A-tu;B-nu=A-mu;B-mu=A-nu;if(B-tu)for(col=1;colnu;col+)numcol=0;for(t=1;ttu;t+)numA-datat.col+;/*计算每一列的非零元素的个数*/,position1=1;for(col=2;colnu;col+)/*求col列第一个非零元素在B.data的位置*/positioncol=positioncol-1+numcol-1;for(p=1;pdataq.row=A.datap.col;B-dataq.col=A.datap.row;B-dataq.e=A.datap.e positioncol+;,【算法5.2 快速稀疏矩阵转置算法】,快速转置算法时间耗费在四个并列的单循环上，这四个并列的单循环分别执行了A.nu，A.tu，A.nu，A.tu次，因而总的时间复杂度为O(A.nu)+O(A.tu)+O(A.nu)+O(A.tu)。当待转置矩阵M中非零元素个数接近于A.muA.nu 时，其时间复杂度接近于经典算法的时间复杂度O(A.muA.nu)。空间耗费上除了三元组表所占用的空间外，还需要两个辅助向量空间，即num1.A-nu，position1.A-nu。可见，算法在时间上的节省，是以更多的存储空间为代价的。,2)用三元组表实现稀疏矩阵的乘法运算 两个矩阵相乘也是矩阵的一种常用的运算。设矩阵M是m1n1矩阵，N是m2n2矩阵；若可以相乘，则必须满足矩阵M的列数n1与矩阵N的行数m2相等，才能得到结果矩阵Q=MN（一个m1n2的矩阵）。数学中矩阵Q中的元素的计算方法如下：,其中：1im1,1jn2。,图5.17 Q=MN,图5.17给出了一个矩阵相乘的例子。当矩阵M、N是稀疏矩阵时，我们可以采用三元组表的表示形式来实现矩阵的相乘。,图5.18 矩阵M、N、Q的三元组表,因为三元组表只对矩阵的非零元素做存储。所以可以采用固定三元组表a中的元素（i，k，Mik）（1im1，1kn1），在三元组表b中找所有行号为k的对应元素（k，j，Nkj）（1km2，1jn2）进行相乘、累加，从而得到Qij，即以三元组表a中的元素为基准，依次求出其与三元组表b的有效乘积。算法中附设两个向量num、first，其中numrow表示三元组表b中第row行非零元素个数（1rowm2），firstrow表示三元组表b中第row行第一个非零元素所在的位置。显然，firstrow+1-1指向三元组表b中第row行最后一个非零元素的位置。,5.3.2 稀疏矩阵的十字链表存储*与用二维数组存储稀疏矩阵比较，用三元组表表示的稀疏矩阵不仅节约了空间，而且使得矩阵某些运算的运算时间比经典算法还少。但是在进行矩阵加法、减法和乘法等运算时，有时矩阵中的非零元素的位置和个数会发生很大的变化。如A=A+B，将矩阵B加到矩阵A上，此时若还用三元组表表示法，势必会为了保持三元组表“以行序为主序”而大量移动元素。,在十字链表中，矩阵的每一个非零元素用一个结点表示，该结点除了（row，col，value）以外，还要有以下两个链域：right：用于链接同一行中的下一个非零元素；down：用于链接同一列中的下一个非零元素。,再附设一个存放所有行链表的头指针的一维数组和一个存放所有列链表的头指针的一维数组。图5.15(b)给出了稀疏矩阵图5.15(a)的十字链表。,十字链表的结构类型说明如下：,typedef struct OLNode int row,col;/*非零元素的行和列下标*/datatype value;struct OLNode*right,*down;/*非零元所在行、列表的后继链域*/OLNode;*OLink;typedef struct OLink*row-head,*col-head;/*行、列链表的头指针向量*/int m,n,len;/*稀疏矩阵的行数、列数、非零元素的个数*/CrossList;,CreateCrossList(CrossList*M)/*采用十字链表存储结构，创建稀疏矩阵M*/if(M!=NULL)free(M);scanf(,else/*寻找行表中的插入位置*/for(q=M-row-headi;q-right/*完成插入*/,【算法5.4 建立稀疏矩阵的十字链表】,建十字链表的算法的时间复杂度为O（ts），s=MAX（m，n)。,5.4 广 义 表*,广义表的定义 广义表是n个数据元素a1，a2，ai，an的有序序列。一般记为：ls=（a1，a2，a3，an）广义表广泛地应用于人工智能等领域的表处理语言LISP语言中。,List(D,R)D=ai|ai Atomset 或 ai Lists R=|ai,ai+1 D 1=i=n-1其中（1）ai是单个元素或是一个广义表，称为ls的原子或子表（2）长度：n是广义表的长度。（3）表头：a1是广义表ls的表头（4）表尾：其余元素组成的表是表尾。（5）广义表示一个递归定义的表。,下面给出一些广义表的例子，以加深对广义表概念的理解。D=（）空表；其长度为零。A=(a，(b，c)表长度为2的广义表，其中第一个元素是单个数据a，第二个元素是一个子表(b，c)。B=(A，A，D)长度为3的广义表，其前两个元素为表A，第三个元素为空表D。C=(a，C)长度为2递归定义的广义表，C相当于无穷表(a，(a,(a，()。,下面以广义表A为例，说明求表头、表尾的操作：head（A）=a 表A的表头是a。tail（A）=（b，c）表A的表尾是（b，c）。广义表的表尾一定是一个表。,广义表的性质从上述广义表的定义和例子可以得到广义表的重要性质：广义表是一种多层次的数据结构。广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表，。广义表可以是递归的表。例如表C 就是一个递归的表。广义表可以为其它表所共享。如广义表B就共享表A。在表B中不必列出表A的内容，只要通过子表的名称就可以引用该表。,广义表基本运算 基本操作，取头操作（Head）和取尾操作（Tail）。根据广义表的表头、表尾的定义可知，对于任意一个非空的广义表，其表头可能是单元素也可能是广义表，而表尾必为广义表。例如：A（）B（e）C（a，（b，c，d）D（A，B，C）E（a，E）F（）,那么：head（B）e tail（B）（）head（C）a tail（C）（b，c，d）head（D）A tail（D）（B，C）head（E）a tail（E）（E）head（F）（）tail（F）（）,例如：L=(a，(b，(c，d)，e)，f)如何访问到d？,在广义表上可以定义与线性表类似的一些操作，如建立、插入、删除、拆开、连接、复制、遍历等。CreateLists(ls)：根据广义表的书写形式创建一个广义表ls。IsEmpty(ls)：若广义表ls空，则返回True；否则返回False。Length(ls)：求广义表ls的长度。Depth(ls)：求广义表ls的深度。Locate(ls，x)：在广义表ls中查找数据元素x。Merge(ls1，ls2)：以ls1为头、ls2为尾建立广义表。CopyGList(ls1，ls2)：复制广义表，即按ls1建立广义表ls2。Head(ls)：返回广义表ls的头部。Tail(ls)：返回广义表的尾部。,5.4.2 广义表的存储 广义表的存储结构：顺序存储结构无法实现，单链表无法存储。例如：L=(a，(b，(c，d)，e)，f)如何访问到d？head(tail(head(tail(head(tail(L)=d,任何一个非空的广义表都可以分解成表头和表尾两部分，表中的每个元素可用一个结点来表示。有两类结点：（1）单个元素结点：有两个域：标志域和值域。（2）表结点：由三个域构成：标志域、指向表头的指针域和指向表尾的指针域。,typedef enum ATOM,LISTElemtag;/*ATOM=0单元素；LIST=1子表*/typedef struct GLNode Elemtag tag;/*标志域，用于区分元素结点和表结点*/union/*元素结点和表结点的联合部分*/datatype data;/*data是元素结点的值域*/struct struct GLNode*hp,*tp ptr;/*ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾*/;*GList;,例如：有以下广义表：A=(a,b,c)B=(A,A,D)C=(a,C)D=(),采用头尾表示法容易分清广义表中单元素或子表所在的层次。例如，在广义表A中，单元素a、b和c在同一层次上。最高层的表结点的个数即为广义表的长度。例如，广义表A的最高层有三个表结点，广义表长度为3。,