数据结构组广义表课件.ppt

《数据结构组广义表课件.ppt》由会员分享，可在线阅读，更多相关《数据结构组广义表课件.ppt（79页珍藏版）》请在三一办公上搜索。

1、数组和广义表可以看成是线性表在以下含义上的扩展：,表中的数据元素本身也是一个数据结构。,5.1 数组,数组是大家都已经很熟悉的一种数据类型，几乎所有高级程序设计语言中都设定了数组类型。在此，我们仅简单地讨论数组的逻辑结构及在计算机内的存储方式。,一.多维数组的概念,1一维数组 一维数组可以看成是一个线性表或一个向量，它在计算机内存放在一块连续的存储单元中，适合于随机查找。这在第2章的线性表的顺序存储结构中已经讨论。,2二维数组,二维数组可以看成是向量的推广。例如，设A是一个有m行n列的二维数组，则A可以表示为：,在此，可以将二维数组A看成是由m个行向量X0，X1，Xm-1T组成，其中，Xi=(

2、ai0,ai1,.,ain-1)，0im-1；也可以将二维数组A看成是由n个列向量Y0,Y1,Yn-1组成，其中 Yj=(a0j,a1j,.,am-1j)，0jn-1。由此可知二维数组中的每一个元素最多可有两个直接前驱和两个直接后继（边界除外）。,3多维数组,同理，三维数组最多可有三个直接前驱和三个直接后继，三维以上数组可以作类似分析。可以把三维以上的数组称为多维数组，多维数组可有多个直接前驱和多个直接后继。,二.多维数组在计算机内的存放,高级语言对数组的存储都是采取顺序存储的方式，由于计算机内存结构是一维的（线性的），因此，用一维内存存放多维数组就必须按某种次序将数组元素排成一个线性序列，然

3、后将这个线性序列顺序存放在存储器中，具体实现方法在下面介绍。,5.1.1 数组的类型定义,5.1.3 矩阵的压缩存储,5.1.2 数组的顺序表示和实现,（数组）提要,ADT Array 数据对象：Daj1,j2,.,jn|ji=0,.,bi-1,i=1,2,.,n(n0),aj1,j2,.,jn ElemSet 数据关系：RR1,R2,.,Rn Ri|0 jk bk-1,1 k n 且k i,0 ji bi-2,i=2,.,n ADT Array,基本操作:,5.1.1 数组的类型定义,数据对象:D=aij|0ib1-1,0 jb2-1,aijElemSet数据关系:R=ROW,COL ROW

4、=|0ib1-2,0jb2-1 COL=|0ib1-1,0 jb2-2,二维数组的定义:,基本操作：,InitArray(&A,n,bound1,.,boundn),DestroyArray(&A),Value(A,&e,index1,.,indexn),Assign(&A,e,index1,.,indexn),操作结果：若维数 n 和各维长度合法，则构造相应的数组A，并 返回OK。,InitArray(&A,n,bound1,.,boundn),DestroyArray(&A),操作结果：销毁数组A。,初始条件：A是n维数组，e为元素变量，随后是n 个下标值。操作结果：若各下标不超界，则e赋

5、值为 所指定的A 的元素值，并返 回OK。,Value(A,&e,index1,.,indexn),初始条件：A是n维数组，e为元素变量，随后是n 个下标值。操作结果：若下标不超界，则将e的值赋 给所指定的A的元素，并返回 OK。,Assign(&A,e,index1,.,indexn),类型特点:数组是多维的结构，而存储空间是一维的结构。,有两种顺序映象的方式:1)以行序为主序(行优先，低下标优先)；2)以列序为主序(列优先，高下标优先)。,5.1.2 数组的顺序表示和实现,由于一旦建立了数组，则结构中的数组元素个数和元素之间的关系就已确定，即它们的逻辑结构就固定下来了，不再发生变化；数组一

6、般不作插入或删除操作。因此，采用顺序存储结构表示数组是顺理成章的事了。,例如：,称为基地址或基址。,二维数组A中任一元素ai,j 的存储位置 LOC(i,j)=LOC(0,0)+(nij),L,L,以“行序为主序”的存储映象,按行号从小到大的顺序，先将第一行中元素全部存放完，再存放第二行元素，第三行元素，依次类推,二维数组Amn,同理，三维数组Almn按行优先存放的地址计算公式为：,LOC(i,j,k)=LOC(0,0,0)+(imn+jn+k)L,行序为主序排列规律：,最左边下标变化最慢，最右边下标变化最快，右边下标变化一遍，与之相邻的左边下标才变化一次。,称为 n 维数组的映象函数。数组元

7、素的存储位置是其下标的线性函数。,推广到一般情况，可得到 n 维数组数据元素存储位置的映象关系:,例如：,基地址或基址。,二维数组A中任一元素ai,j 的存储位置 LOC(i,j)=LOC(0,0)+(mji),L,L,以“列序为主序”的存储映象,按列号从小到大的顺序，先将第一列中元素全部存放完，再存放第二列元素，第三列元素，依次类推,二维数组Amn,列序为主序排列规律：,最右边下标变化最慢，最左边下标变化最快，左边下标变化一遍，与之相邻的右边下标才变化一次。,5.1.3 矩阵的压缩存储,1.特殊矩阵,2.稀疏矩阵,1.特殊矩阵,非零元在矩阵中的分布有一定的规律。例如:对称矩阵 三角矩阵 对角

8、矩阵,以对称矩阵为例，n阶对称矩阵A满足：,aij=aji 1i,jn,可为每一对对称元分配一个存储空间。若以行序为主序存储其下三角中的元，以一维数组sn(n+1)/2作为其存储结构，则sk和矩阵元aij之间的对应关系为：,k=,i(i-1)/2+j-1(i j),j(j-1)/2+i-1(i j),2.稀疏矩阵,非零元在矩阵中随机出现。,1)零值元素占了很大空间;,2)计算中进行了很多和零值的运算，遇除法，还需判别除数是否为零。,以常规方法，即以二维数组表示高阶的稀疏矩阵时会产生的问题:,例如：,1)尽可能少存或不存零值元素；,2)尽可能减少没有实际意义的运算；,3)操作方便。即：尽可能快地

9、找到与下标值(i，j)对应的元素，尽可能快地找到同一行或同一列的非零元素。,解决问题的原则:,一、三元组顺序表,二、行逻辑链接的顺序表,三、十字链表,稀疏矩阵的压缩存储方法:,#define MAXSIZE 12500 typedef struct int i,j;/该非零元的行下标和列下标 ElemType e;/该非零元的值 Triple;/三元组类型,typedef struct Triple dataMAXSIZE+1;/data0未用 int mu,nu,tu;TSMatrix;/稀疏矩阵类型,一、三元组顺序表,矩阵M可表示为：,(TSMatrix M),例如：,三元组顺序表表示的稀

10、疏矩阵的转置运算。,转置是矩阵中最简单的一种运算。对于一个mn的矩阵A，它的转置矩阵B是一个nm的矩阵，且Bij=Aji，1in,1jm。,在三元组表表示的稀疏矩阵中，怎样求得它的转置呢?,从转置的性质知道，将A转置为B，就是将A的三元组表a.data变为B的三元组表b.data，这时可以将a.data中i和j的值互换，则得到的b.data是一个按列序为主序排列的三元组表，再将它的顺序适当调整，变成行序为主序排列，即得到转置矩阵B。下面将用两种方法处理：,(1)按照A的列序进行转置 由于A的列即为B的行，在a.data中，按列扫描，同一列的元素必按行序递增，因此得到的b.data必按行优先存放

11、。但为了找到A的每一列中所有的非零元素，每次都必须从头到尾扫描A的三元组表（有多少列，则扫描多少遍）。,1 2 14,1 5-5,2 2-7,3 1 36,3 4 28,2 1 14,5 1-5,2 2-7,1 3 36,4 3 28,例如：,void transposeSMatrix(TSMatrix M,TSMatrix&T),/采用三元组表存储表示，求稀疏矩阵M的转置矩阵T T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)q=1;for(col=1;col=M.nu;+col)/按列号扫描 for(p=1;p=M.tu;+p)/对三元组扫描 if(M.data

12、p.j=col)/进行转置 T.dataq.j=M.datap.i;T.dataq.i=M.datap.j;T.dataq.e=M.datap.e;+q;/transposeSMatrix,算法的时间复杂度：O(nutu),其时间复杂度为:O(munu),for(col=1;col=nu;+col)for(row=1;row=mu;+row)Tcolrow=Mrowcol;,用常规的二维数组表示时的算法：,相比较后可以发现，当非零元的个数tu与munu同数量级时，transposeSMatrix算法的时间复杂度就成为O(munu2)了，比不压缩存储时的时间复杂度要大。因此，该算法仅适于tumu

13、nu的情况。,（2）按照A的行序进行转置(快速转置),即按a.data中三元组的次序进行转置，并将转置后的三元组放入b中恰当的位置。首先，在转置前求出矩阵A的每一列col（即B中每一行）的第一个非零元转置后在b.data中的正确位置cpotcol(1cola.nu)，然后，在对a.data的三元组依次作转置时，只要将三元组按列号col放置到b.datacpotcol中，之后将cpotcol内容加1，以指示第col列的下一个非零元的正确位置。为了求得位置向量cpot，要先求出A的每一列中非零元个数numcol，然后利用下面公式：cpot1=1 cpotcol=potcol-1+numcol-1(

14、2cola.nu),cpot1=1;for(col=2;col=a.nu;+col)cpotcol=cpotcol-1+numcol-1;,例如：,2 1 15,3,5 1-5,6,2 2-7,4,1 3 36,2,4 3 28,5,12345,12345,T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu)for(col=1;col=M.nu;+col)numcol=0;for(t=1;t=M.tu;+t)+numM.datat.j;cpot1=1;for(col=2;col=M.nu;+col)cpotcol=cpotcol-1+numcol-1;for(p=1;p

15、=M.tu;+p)/if return OK;/FastTransposeSMatrix,转置矩阵元素,Status FastTransposeSMatrix(TSMatrix M,TSMatrix&T),col=M.datap.j;q=cpotcol;T.dataq.i=M.datap.j;T.dataq.j=M.datap.i;T.dataq.e=M.datap.e;+cpotcol,时间复杂度为:O(M.nu+M.tu),for(col=1;col=M.nu;+col)for(t=1;t=M.tu;+t)for(col=2;col=M.nu;+col)for(p=1;p=M.tu;+p)

16、,分析算法FastTransposeSMatrix的时间复杂度：,三元组顺序表又称有序的双下标法，它的特点是，非零元在表中按行序有序存储，因此便于进行依行顺序处理的矩阵运算。然而，若需存取某一行中的非零元，则需从头开始进行查找。,二、行逻辑链接的顺序表,修改前述的稀疏矩阵的结构定义，增加一个数据成员rpos，其各分量的值为对应各行第一个非零元的位置(下标)（在稀疏矩阵的初始化函数中确定）。,#define MAXMN 500 typedef struct Triple dataMAXSIZE+1;int rposMAXMN+1;int mu,nu,tu;RLSMatrix;/行逻辑链接顺序表类

17、型,ElemType value(RLSMatrix M,int r,int c)p=M.rposr;while(p=M.tu/value,例如：给定一组下标，求矩阵的元素值,for(i=1;i=m1;+i)for(j=1;j=n2;+j)Qij=0;for(k=1;k=n1;+k)Qij+=Mik*Nkj;,其时间复杂度为:O(m1n2n1),矩阵乘法的精典算法:,Q初始化；if Q是非零矩阵/逐行求积 for(arow=1;arow=M.mu;+arow)/处理M的每一行 ctemp=0;/累加器清零 计算Q中第arow行的积并存入ctemp 中；将ctemp 中非零元压缩存储到Q.dat

18、a；/for arow/if,两个稀疏矩阵相乘（QMN）的过程可大致描述如下：,if(M.nu!=N.mu)return ERROR;Q.mu=M.mu;Q.nu=N.nu;Q.tu=0;if(M.tu*N.tu!=0)/Q是非零矩阵 for(arow=1;arow=M.mu;+arow)/处理M的每一行/for arow/if return OK;/MultSMatrix,Status MultSMatrix(RLSMatrix M,RLSMatrix N,RLSMatrix&Q),ctemp=0;/当前行各元素累加器清零 Q.rposarow=Q.tu+1;for(p=M.rposarow

19、;p MAXSIZE)return ERROR;Q.dataQ.tu=arow,ccol,ctempccol;/if,处理 的每一行,M,累加器ctemp初始化的时间复杂度为(M.muN.nu)，求Q的所有非零元的时间复杂度为(M.tuN.tu/N.mu)，进行压缩存储的时间复杂度为(M.muN.nu)，总的时间复杂度就是(M.muN.nu+M.tuN.tu/N.mu)。,若M是m行n列的稀疏矩阵，N是n行p列的稀疏矩阵，则M中非零元的个数 M.tu=Mmn，N中非零元的个数 N.tu=Nnp，相乘算法的时间复杂度就是(mp(1+nMN)，当M0.05 和N0.05及 n 1000时，相乘算法

20、的时间复杂度就相当于(mp)。,分析上述算法的时间复杂度,当稀疏矩阵中非零元的位置或个数经常变动时，三元组就不适合于作稀疏矩阵的存储结构，此时，采用链表作为存储结构更为恰当。,三、十字链表,十字链表是稀疏矩阵的链式存储方法，在该方法中，每一个非零元用一个结点表示，结点形式为：,i,j,e,down,right,其中 i,j,e表示非零元所在的行、列和值的三元组；,right：行指针域，用来指向本行中下一个非零元素；,down：列指针域，用来指向本列中下一个非零元素。,稀疏矩阵中同一行的非零元通过right指针链接成一个带表头结点的链表。同一列的非零元通过down指针链接成一个带表头结点的链表。

21、因此，每个非零元既是第i行链表中的一个结点，又是第j列链表中的一个结点，相当于处在一个十字交叉路口，故称链表为十字链表。,十字链表的类型定义,typedef struct OLNode int i,j;ElemType e;struct OLNode*down,*right;OLNode;*Olink;,typedef struct Olink*rhead,*chead;/行、列链表头指针向量基址 int mu,nu,tu;CrossList;,3 0 0 50-1 0 02 0 0 0,1,1,3,1,4,5,2,2,-1,3,1,2,例：,M.mu=3M.nu=4M.tu=4,5.2 广义

22、表,广义表的概念 广义表是线性表的推广，也称为列表。,线性表中的元素仅限于原子，即从结构上是不可以再分的，而广义表中的元素既可以是原子，也可以是广义表。,LISP语言把广义表作为基本的数据结构，就连程序也表示为一系列的广义表。,1.广义表,广义表一般记作：LS=(1,2,n)其中,LS为广义表的名字，n为广义表的长度，每一个i为广义表的元素。i可以是原子(或称单元素)，也可以是广义表(称为子表)。在习惯中，一般用大写字母表示广义表，小写字母表示原子。,2.广义表的长度,广义表的长度定义为最外层包含元素个数。,若广义表LS非空，则称第一个元素1为LS的表头，其余元素组成的表(2,n)为LS的表尾

23、。,4.表头和表尾,广义表的深度定义为所含括弧的重数。注意：“原子”的深度为 0“空表”的深度为 1,3.广义表的深度,任一非空的广义表，均可分解为表头和表尾；一对确定的表头和表尾，可唯一确定一个广义表。,5.广义表举例,（1）A=(e),GetHead(A)=e,GetTail(A)=(),（2）B=(a,(b,c),d),GetHead(B)=a,GetTail(B)=(b,c),d),（3）C=(),无表头、也无表尾,广义表A只有一个单元素，其长度为1，深度为1。,B是长度为3的广义表，其深度为2。,C是一个空表，其长度为0，深度为1。,广义表举例,（5）E=(a,E),（4）D=(A,

24、B,C),GetHead(D)=(e),GetTail(D)=(a,(b,c),d),(),GetHead(E)=a,GetTail(E)=(E),（6）F=(),GetHead(F)=(),GetTail(F)=(),D是长度为3的广义表，每一项都是上面提到的子表,即:D=(e),(a,(b,c),d),()，其深度为3。,E是长度为2的广义表，第一项为原子，第二项为它本身。即：E=(a,(a,(a,),其深度为无穷。,F是长度为1的广义表，其元素为空表，其深度为2。,（广义表）提要,5.2.1 广义表的类型定义,5.2.2 广义表的表示方法,ADT Glist 数据对象：Dei|i=1,2

25、,.,n;n0;eiAtomSet 或 eiGList,AtomSet为某个数据对象 数据关系：LR|ei-1,eiD,2in ADT Glist,基本操作:,5.2.1 广义表的类型定义,LS=(1,2,n)其中：i 或为原子 或为广义表,广义表 LS=(1,2,n)的结构特点:,2)广义表是递归定义的线性结构,1)广义表中的数据元素有相对次序；,例如：,D=(E,F),其中:E=(a,(b,c)F=(d,(e),3)广义表是一个多层次的线性结构,4)广义表可以共享；,5)广义表可以是一个递归的表。,例如：A=(e)B=(a,(b,c),d)C=(A,B)D=(d,A,f,B),例如：E=(

26、a,E),递归表的深度是无穷值，长度是有限值。,结构的创建和销毁 InitGList(,状态函数 GListLength(L);GListDepth(L);GListEmpty(L);GetHead(L);GetTail(L);,插入和删除操作 InsertFirst_GL(,遍历 Traverse_GL(L,Visit();,基本操作,由于广义表中的数据元素可以是原子，也可以是列表，即其中的元素可以有不同的结构，难以用顺序存储结构表示，因此，通常采用链式存储结构。在用链式结构时，需要两种结构的结点：(1)表结点，用以表示列表；(2)原子结点，用以表示原子。,5.2.2 广义表的表示方法,有两

27、种具体的表示方法：,(1)头尾链表存储表示,(2)扩展线性链表存储表示,typedef enum ATOM,LIST ElemTag;/枚举类型/ATOM=0:原子,LIST=1:子表typedef struct GLNode ElemTag tag;/公共部分，标志域 union/联合部分 AtomType atom;/原子结点的数据域 struct struct GLNode*hp,*tp;ptr;/表结点的指针域;*GList,(1)广义表的头尾链表存储表示：,表结点:,原子结点：,空表,非空表,指向表头的指针,指向表尾的指针,LS,LS=NULL,例如:,L,(a,(x,y),(x),

28、a,(x,y),(x),(x,y),(x),x,(y),y,(x),(x),x,L=(a,(x,y),(x),再看几个例子,（1）A=(e),（2）B=(a,(b,c),d),（3）C=(),（4）D=(A,B,C),C=NULL,（5）E=(a,E),（6）F=(),该存储结构的特点,由图中，我们可以容易地得到广义表的长度，深度，原子和子表所在的层数，也容易求表头和表尾，给广义表的某些操作（特别是递归操作）带来方便。但这种结构也存在这缺点：表结点多，与广义表中括号对数不匹配，占用存储空间较多。,(2)广义表的扩展线性链表存储表示,typedef enum ATOM,LIST ElemTag;

29、/枚举类型/ATOM=0:原子,LIST=1:子表typedef struct GLNode ElemTag tag;/公共部分，标志域 union/联合部分 AtomType atom;/原子结点的数据域 struct GLNode*hp;/表结点的表头指针;struct GLNode*tp；/指向下一个元素结点*GList,空表,非空表,指向表头的指针,表结点:原子结点：,指向下一个元素结点的指针,(同一层的结点以tp相连),例如:,L=(a,(x,y),(x),再看几个例子,（1）A=(e),（2）B=(a,(b,c),d),（3）C=(),（4）D=(A,B,C),该存储结构的特点,表结点个数少，且和广义表中的括号对数一致；但写递归算法不方便。,要求：主要掌握前一种存储结构。,1.了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。2.掌握对特殊矩阵进行压缩存储时的下标变换公式。3.了解稀疏矩阵的两类压缩存储方法(三元组顺序表和十字链表)的特点和适用范围，领会以三元组顺序表表示稀疏矩阵时进行矩阵运算采用的处理方法。,本章学习要点,4.掌握广义表的结构特点及其存储表示方法，熟练掌握第一种结构的链表，学会对非空广义表进行分解的方法：即可将一个非空广义表分解为表头和表尾两部分。,本章作业：,5.15.65.235.105.125.13,