【教学课件】第5章数组和广义表.ppt

《【教学课件】第5章数组和广义表.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第5章数组和广义表.ppt（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第5章章 数组和广义表数组和广义表教学目标教学目标 数组和广义表，是扩展的线性数据结构，其中广义表是人工智能程序设计的基础。要求熟练掌握其逻辑结构、存储结构各种运算。重点、难点重点、难点 抽象数据类型数组的定义与实现，特殊矩阵的压缩存储，稀疏矩阵（分别用三元组表、十字链表实现转置、加减法等矩阵运），广义表的存储结构，稀疏矩阵的乘法运算。教学方法教学方法 设问解疑，激发学生对数组和广义表的求知欲望和积极的思维活动。第第5章章 数组和广义表数组和广义表5.1 数组的定义和运算数组的定义和运算5.2 数组的顺序存储和实现数组的顺序存储和实现5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储 5.3.1

2、三角矩阵三角矩阵 5.3.2 带状矩阵带状矩阵 5.3.3 稀疏矩阵稀疏矩阵5.4 广义表广义表5.5 总结与提高总结与提高 5.1 数组的定义和运算数组的定义和运算数组是一种数据类型。从逻辑结构上看，数组可以数组是一种数据类型。从逻辑结构上看，数组可以看成是一般线性表的扩充。二维数组可以看成是线看成是一般线性表的扩充。二维数组可以看成是线性表的线性表。例如：性表的线性表。例如：Amn=a12 a12 a1j a1na21 a22 a2j a2n ai1 ai2 aij ain am1 am2 amj amnAmn=a12 a12 a1j a1na21 a22 a2j a2n ai1 ai2

3、aij ain am1 am2 amj amnA=（1 2 j n)我们可以把二维数组看成一个线性表：我们可以把二维数组看成一个线性表：A=(1 2 j n)，其中，其中 j（1j n）本身）本身也是一个线性表，称为也是一个线性表，称为列向量列向量。矩阵矩阵Amn看成看成n个列向量的线性表个列向量的线性表,即即 j=(a1j,a2j,amj)Amn=a12 a12 a1j a1na21 a22 a2j a2n ai1 ai2 aij ain am1 am2 amj amnB 1 2 i m我们还可以将数组我们还可以将数组Amn看成另外一个线性表看成另外一个线性表:B=(1，,2,，m)，其中，

4、其中 i（1i m）本身也是一个线性）本身也是一个线性表，称为行向量，即：表，称为行向量，即：I=（ai1，ai2，aij，ain）。）。上面二维数组的例子，介绍了数组的结构特性，实上面二维数组的例子，介绍了数组的结构特性，实际上数组是一组有固定个数的元素的集合。由于这际上数组是一组有固定个数的元素的集合。由于这个性质，使得对数组的操作不象对线性表的操作那个性质，使得对数组的操作不象对线性表的操作那样，可以在表中任意一个合法的位置插入或删除一样，可以在表中任意一个合法的位置插入或删除一个元素。个元素。对于数组的操作一般只有两类：对于数组的操作一般只有两类：（1）获得特定位置的元素值；）获得特定

5、位置的元素值；（2）修改特定位置的元素值。）修改特定位置的元素值。数组的抽象数据类型定义（数组的抽象数据类型定义（ADT Array）数据对象：数据对象：D=aj1j2jn|n0，称为数组的维数，称为数组的维数，ji是是数组的第数组的第i维下标，维下标，1jibi，bi为数组第为数组第i维的长度，维的长度，aj1j2jn ElementSet 数据关系：数据关系：R=R1,R2,RnRi=|1jkbk，1kn 且且ki，1jibi-1，aj1 jijn，aj1 ji+1jn D，i=1，n 基本操作：基本操作：（1）InitArray(A,n,bound1,boundn)：若维数若维数n和各维

6、的长和各维的长度合法，则构造相应的数组度合法，则构造相应的数组A，并返回，并返回TRUE；（2）DestroyArray（A）：）：销毁数组销毁数组A；（3）GetValue（A，e,index1,indexn）：）：若下标合法，若下标合法，用用e返回数组返回数组A中由中由index1,indexn所指定的元素的值。所指定的元素的值。（4）SetValue（A，e，index1,indexn）：）：若下标合法，若下标合法，则将数组则将数组A中由中由index1,indexn所指定的元素的值置为所指定的元素的值置为e。注意：这里定义的数组下标是从注意：这里定义的数组下标是从1开始，与开始，与C语

7、言的语言的数组略有不同。数组略有不同。5.2 数组的顺序存储和实现数组的顺序存储和实现 对于数组对于数组A，一旦给定其维数，一旦给定其维数n及各维长度及各维长度bi（1in），则该数组中元素的个数是固定的，不可），则该数组中元素的个数是固定的，不可以对数组做插入和删除操作，不涉及移动元素操作，以对数组做插入和删除操作，不涉及移动元素操作，因此对于数组而言，采用顺序存储法比较合适。因此对于数组而言，采用顺序存储法比较合适。数组的顺序存储结构有两种：一种是数组的顺序存储结构有两种：一种是按行序按行序存存储，如高级语言储，如高级语言BASIC、COBOL和和PASCAL语言都语言都是以行序为主。另一

8、种是是以行序为主。另一种是按列序按列序存储，如高级语言中存储，如高级语言中的的FORTRAN语言就是以列序为主。语言就是以列序为主。对于二维数组对于二维数组Amxn以以行行为为主主的的存存储储序序列列为为：a11,a12,a1n,a21,a22,a2n,am1,am2,amn 以以列列为为主主存存储储序序列列为为：a11,a21,am1,a12,a22,am2,a1n,a2n,amn 假设有一个假设有一个342的三维数组的三维数组A，其逻辑结构图为：其逻辑结构图为：列列行行纵纵 以二维数组以二维数组Amn为例，假设每个元素只占一个存为例，假设每个元素只占一个存储单元，储单元，“以行为主以行为主

9、”存放数组，下标从存放数组，下标从1开始，首开始，首元素元素a11的地址为的地址为Loc1,1 求任意元素求任意元素aij的地址的地址，可由，可由如下计算公式得到：如下计算公式得到：Loci,j=Loc1,1+n(i-1)+(j-1)如果每个元素占如果每个元素占size个存储单元个存储单元，则任意元素，则任意元素aij的地址计算公式为：的地址计算公式为：Loci,j=Loc1,1+(n(i-1)+j-1)size 三维数组三维数组A（1.r,1.m,1.n）可以看成是）可以看成是r个个mn的的二维数组二维数组，如下图所示：如下图所示：假定每个元素占一个存储单元，采用以行为主序假定每个元素占一个

10、存储单元，采用以行为主序的方法存放的方法存放，首元素，首元素a111的地址为的地址为Loc1,1,1，ai11的地的地址为址为Loci,1,1=Loc1,1,1+(i-1)*m*n，那么求任意元，那么求任意元素素aijk的地址计算公式为：的地址计算公式为：Loci,j,k=Loc1,1,1+(i-1)*m*n+(j-1)*n+(k-1)其中其中1i，1j，1k。如如果果将将三三维维数数组组推推广广到到一一般般情情况况，即即：用用j1，j2，j3代代替替数数组组下下标标i，j，k；并并且且j1，j2，j3的的下下限限为为c1，c2，c3，上上限限分分别别为为d1，d2，d3，每每个个元元素素占占

11、一一个个存存储储单单元元。则则三三维维数数组组中中任任意意元元素素a(j1，j2，j3)的的地地址址为：为：Locj1，j2，j3=Locc1,c2,c3+1*(d2-c2+1)*(d3-c3+1)*(j1-c1)+1*(d3-c3+1)*(j2-c2)+1*(j3-c3)其中其中l为每个元素所占存储单元数。为每个元素所占存储单元数。令令1=1*(d2-c2+1)*(d3-c3+1),2=1*(d3-c3+1),3=1，则：，则：Locj1,j2,j3=Locc1,c2,c3+1*(j1-c1)+2*(j2-c2)+3(j3-c3)=Locc1,c2,c3+i*(ji-ci)（1i3）由公式可

12、知由公式可知Locj1,j2,j3与与j1,j2,j3呈线性关系。呈线性关系。对于维数组对于维数组A(c1:d1,c2:d2，,cn,dn)，我们只要把上式，我们只要把上式推广，就可以容易地得到维数组中任意元素推广，就可以容易地得到维数组中任意元素aj1j2jn的存的存储地址的计算公式。储地址的计算公式。Locj1，j2，jn=Locc1，c2，cn+i(ji-ci)i=1n其中其中i=l (dk-ck+1)（1in）k=i+1n5.3 特殊矩阵的压缩存储特殊矩阵的压缩存储特殊矩阵压缩存储的压缩原则是：对有规律的元素特殊矩阵压缩存储的压缩原则是：对有规律的元素和值相同的元素只分配一个存储单元，

13、对于零元素和值相同的元素只分配一个存储单元，对于零元素不分配空间。不分配空间。5.3.1 三角矩阵三角矩阵三角矩阵大体分为：下三角矩阵、上三角矩阵和对三角矩阵大体分为：下三角矩阵、上三角矩阵和对称矩阵。对于一个称矩阵。对于一个n阶矩阵阶矩阵A来说：若当来说：若当ij时，有时，有aij=0，则此矩阵称为上三角矩阵；若矩阵中的所有，则此矩阵称为上三角矩阵；若矩阵中的所有元素均满足元素均满足aij=aji，则称此矩阵为对称矩阵。，则称此矩阵为对称矩阵。对于下三角矩阵，按对于下三角矩阵，按“行序为主序行序为主序”进行存储，得到的进行存储，得到的序列为：序列为：a11,a21,a22,a31,a32,a

14、33an1,an2ann。由于下。由于下三角矩阵的元素个数为三角矩阵的元素个数为n(n+1)/2，所以可压缩存储到一，所以可压缩存储到一个大小为个大小为n(n+1)/2的一维数组中。下三角矩阵中元素的一维数组中。下三角矩阵中元素aij(ij)，在一维数组，在一维数组A中的位置为：中的位置为：LOC i,j=LOC1,1+i(i-1)/2+j-1 下三角矩阵：下三角矩阵：A=a11a21 a22a31 a32 a33 an1 an2 an3 ann 同同样样，对对于于上上三三角角矩矩阵阵，也也可可以以将将其其压压缩缩存存储储到到一一个个大大小小为为n(n+1)/2的的一一维维数数组组C中中。其其

15、中中元元素素aij(ij)在数组在数组C中的存储位置为：中的存储位置为：Loci,j=Loc1,1+j(j-1)/2+i-1 对于对称矩阵，因其元素满足对于对称矩阵，因其元素满足aij=aji，我们可以，我们可以为每一对相等的元素分配一个存储空间，即只存下为每一对相等的元素分配一个存储空间，即只存下三角（或上三角）矩阵，从而将三角（或上三角）矩阵，从而将n2个元素压缩到个元素压缩到n(n+1)/2个空间中。个空间中。5.3.2 带状矩阵带状矩阵带状矩阵带状矩阵：在矩阵：在矩阵A中，所有的非零元素都集中在以主对角线中，所有的非零元素都集中在以主对角线为中心的带状区域中。最常见的是三对角带状矩阵。

16、为中心的带状区域中。最常见的是三对角带状矩阵。Ann=a11 a12a21 a22 a23 a32 a33 a34 a43 a44 a45 特点特点:i=1,j=1,2;当当 1in，j=i-1,i,i+1 i=n,j=n-1,n;时，时，aij非零，其他元素均为零。非零，其他元素均为零。三对角带状矩阵的压缩存储，以行序为主序进行三对角带状矩阵的压缩存储，以行序为主序进行存储，并且只存储非零元素。其方法为：存储，并且只存储非零元素。其方法为：1.确定存储该矩阵所需的一维向量空间的大小确定存储该矩阵所需的一维向量空间的大小 从三对角带状矩阵中可看出：除第一行和最后一从三对角带状矩阵中可看出：除第

17、一行和最后一行只有两个元素外，其余各行均有行只有两个元素外，其余各行均有3个非零元素。由个非零元素。由此可得到一维向量所需的空间大小为：此可得到一维向量所需的空间大小为：3n-2。2.确定非零元素在一维数组空间中的位置确定非零元素在一维数组空间中的位置LOCi,j=LOC1,1+3（i-1）-1+j-i+1 =LOC1,1+2(i-1)+j-15.3.3 稀疏矩阵稀疏矩阵稀疏矩阵稀疏矩阵：指矩阵中大多数元素为零的矩阵。一般地，：指矩阵中大多数元素为零的矩阵。一般地，当非零元素个数只占矩阵元素总数的当非零元素个数只占矩阵元素总数的25%30%,或或低于这个百分数时，我们称这样的矩阵为稀疏矩阵。低

18、于这个百分数时，我们称这样的矩阵为稀疏矩阵。0 0 3 0 0 1512 0 0 0 18 0 9 0 0 24 0 0 0 0 0 0 0 -7 0 0 0 0 0 0 0 0 14 0 0 0 0 0 0 0 0 0M67=0 12 9 0 0 0 00 0 0 0 0 0 0-3 0 0 0 0 14 00 0 24 0 0 0 00 18 0 0 0 0 015 0 0 -7 0 0 0N67=1.稀疏矩阵的三元组表表示法稀疏矩阵的三元组表表示法 对于稀疏矩阵的压缩存储要求在存储非零元素的对于稀疏矩阵的压缩存储要求在存储非零元素的同时，还必须存储该非零元素在矩阵中所处的行号同时，还必须

19、存储该非零元素在矩阵中所处的行号和列号。我们将这种存储方法叫做稀疏矩阵的三元和列号。我们将这种存储方法叫做稀疏矩阵的三元组表示法。组表示法。row col value该该非非零零元元素素所在的行号所在的行号该该非非零零元元素素所所在的列号在的列号该该非非零零元元素素的的值值每个非零元素在一维数组中的表示形式每个非零元素在一维数组中的表示形式如图所示：如图所示：三元组表的类型说明：三元组表的类型说明：#define MAXSIZE 1000 /*非零元素的个数最多为非零元素的个数最多为1000*/typedef structint row,col;/*该非零元素的行下标和列下标该非零元素的行下标

20、和列下标*/ElementType e；/*该非零元素的值该非零元素的值*/Triple;typedef struct Triple dataMAXSIZE+1;/*非非零零元元素素的的三三元元组组表表。data0未未用用*/int m,n,len;/*矩矩阵阵的的行行数数、列列数数和和非非零零元元素素的的个个数数*/TSMatrix；1）用三元组表实现稀疏矩阵的转置运算）用三元组表实现稀疏矩阵的转置运算矩阵转置：指变换元素的位置，把位于（矩阵转置：指变换元素的位置，把位于（row，col）位）位置上的元素换到（置上的元素换到（col，row）位置上，也就是说，把元）位置上，也就是说，把元素的

21、行列互换。素的行列互换。采用矩阵的正常存储方式时，实现矩阵转置的经典算法采用矩阵的正常存储方式时，实现矩阵转置的经典算法如下如下：Void TransMatrix（ElementType sourcenm,ElementType destmn）/*Source和和dest分别为被转置的矩阵和转置后的矩阵（用二维数组表示）分别为被转置的矩阵和转置后的矩阵（用二维数组表示）*/int i,j;for(i=0;im;i+)for(j=0;jm=A.n;B-n=A.m;B-len=A.len;if(B-len0)j=1;for(k=1;k=A.n;k+)for(i=1;idataj.row=A.dat

22、ai.col B-dataj.col=A.datai.row;B-dataj.e=A.datai.e;j+;算法二、算法二、FastTransposeTSMatrix(TSMatrix A,TSMatrix *B)/*基于矩阵的三元组表示，采用快速转置法，将矩阵基于矩阵的三元组表示，采用快速转置法，将矩阵A转置为转置为B所指的矩阵所指的矩阵*/int col,t,p，q;int numMAXSIZE,positionMAXSIZE;B-len=A.len;B-n=A.m;B-m=A.n;if(B-len)for(col=1;col=A.n;col+)numcol=0;for(t=1;t=A.l

23、en;t+)numA.datat.col+;/*计算每一列的非零元素的个数计算每一列的非零元素的个数*/position1=1;for(col=2;colA.n;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.epositioncol+;用三元组表实现稀疏矩阵的乘法运算用三元组表实现稀疏矩阵的乘法运算 设矩阵设矩阵M是是m1

24、n1矩阵，矩阵，N是是m2n2矩阵；若可以矩阵；若可以相乘，则必须满足矩阵相乘，则必须满足矩阵M的列数的列数n1与矩阵与矩阵N的行数的行数m2相等，才能得到结果矩阵相等，才能得到结果矩阵Q=MN（一个（一个m1n2的矩的矩阵）。阵）。数学中矩阵数学中矩阵Q中的元素的计算方法如下：中的元素的计算方法如下：Qij =MikNkj n1 k=1其中：其中：1im1，1jn2 根据数学上矩阵相乘的原理，我们可以得到矩根据数学上矩阵相乘的原理，我们可以得到矩阵相乘的经典算法：阵相乘的经典算法：for(i=1;i=m1;i+)for(j=1;j=n2;j+)Qij=0;for(k=1;km=M.m;Q-n

25、=N.n;Q-len=0;if(M.len*N.len!=0)for(arow=1;arow=M.m;arow+)/*逐行处理逐行处理M*/for(p=1;pfirstarow=Q-len+1;for(p=M.firstarow;pM.firstarow+1;p+)/*p指指向向M当当前前行行中每一个非零元素中每一个非零元素*/brow=M.datap.col;/*M中的列号应与中的列号应与N中的行号相等中的行号相等*/if(browN.n)t=N.firstbrow+1;else t=N.len+1;for(q=N.firstbrow;qt;q+)ccol=N.dataq.col;/*乘积元

26、素在乘积元素在Q中列号中列号*/ctempccol+=M.datap.e*N.dataq.e;/*for q*/*求得求得Q中第中第crow行的非零元行的非零元*/for(ccol=1;ccoln；col+)/*压缩存储该非零元压缩存储该非零元*/if(ctempccol)if(+Q-lenMAXSIZE)return 0;Q-dataQ-len=arow,ccol,ctempccol;/*if*/*for arow*/*if*/return(TRUE);/*返回返回TRUE表示求矩阵乘积成功表示求矩阵乘积成功*/2.稀疏矩阵的链式存储结构：十字链表稀疏矩阵的链式存储结构：十字链表优点：优点：

27、它能够灵活地插入因运算而产生的新的非零元素，删它能够灵活地插入因运算而产生的新的非零元素，删除因运算而产生的新的零元素，实现矩阵的各种运算。除因运算而产生的新的零元素，实现矩阵的各种运算。在十字链表中，矩阵的每一个非零元素用一个结点表示，该在十字链表中，矩阵的每一个非零元素用一个结点表示，该结点除了（结点除了（row，col，value）以外，还要有两个域：）以外，还要有两个域：right：用于链接同一行中的下一个非零元素；用于链接同一行中的下一个非零元素；down：用以链接同一列中的下一个非零元素。：用以链接同一列中的下一个非零元素。rowcolvaluedownright十字链表中结点的结

28、构示意图：十字链表中结点的结构示意图：十字链表的结构类型说明如下：十字链表的结构类型说明如下：typedef struct OLNode int row,col;/*非零元素的行和列下标非零元素的行和列下标*/ElementType value;struct OLNode*right,*down;/*非零元素所在行表列表的后继链域非零元素所在行表列表的后继链域*/OLNode;*OLink;typedef struct OLink *row_head,*col_head;/*行、列链表的头指针向量行、列链表的头指针向量*/int m,n,len;/*稀疏矩阵的行数、列数、非零元素的个数稀疏矩阵

29、的行数、列数、非零元素的个数*/CrossList;建立稀疏矩阵的十字链表算法：建立稀疏矩阵的十字链表算法：CreateCrossList(CrossList*M)/*采用十字链表存储结构，创建稀疏矩阵采用十字链表存储结构，创建稀疏矩阵M*/if(M!=NULL)free(M);scanf(&m,&n,&t);/*输入输入M的行数的行数,列数和非零元素的个数列数和非零元素的个数*/M-m=m;M-n=n;M-len=t;If(!(M-row_head=(Olink*)malloc(m+1)sizeof(OLink)exit(OVERFLOW);If(!(M-col_head=(OLink*)m

30、alloc(n+1)sizeof(OLink)exit(OVERFLOW);M-row_head=M-col_head=NULL;/*初初始始化化行行、列列头头指指针针向向量量，各各行、列链表为空的链表行、列链表为空的链表*/for(scanf(&i,&j,&e);i!=0;scanf(&i,&j,&e)if(!(p=(OLNode*)malloc(sizeof(OLNode)exit(OVERFLOW);p-row=i;p-col=j;p-value=e;/*生成结点生成结点*/if(M-row_headi=NULL)M-row_headi=p;else /*寻找行表中的插入位置寻找行表中的

31、插入位置*/for(q=M-row_headi;q-right&q-right-colright)p-right=q-right;q-right=p;/*完成插入完成插入*/if(M-col_headj=NULL)M-col_headj=p;else /*寻找列表中的插入位置寻找列表中的插入位置*/for(q=M-col_headj;q-down&q-down-rowdown)p-down=q-down;q-down=p;/*完成插入完成插入*/5.4 广义表广义表广义表广义表也是线性表的一种推广。广义表也是也是线性表的一种推广。广义表也是n n个数据个数据元素（元素（d d1 1，d d2

32、2，d d3 3，d dn n）的有限序列，但不同的）的有限序列，但不同的是，广义表中的是，广义表中的d di i既可以是单个元素，还可以是一个既可以是单个元素，还可以是一个广义表，广义表，通常通常记记作：作：GLGL=（d d1 1，d d2 2，d d3 3，d dn n）。）。GLGL是广是广义义表的名字表的名字，通常用，通常用大写字母大写字母表示。表示。n n是广是广义义表表的的长长度。度。若若 d di i是一个广义表，则称是一个广义表，则称d di i是广义表是广义表GLGL的的子表。子表。在在GLGL中，中，d d1 1是是GLGL的表头，其余部分组成的表的表头，其余部分组成的表

33、（d d2 2，d d3 3，d dn n）称为称为GLGL的表尾。由此可见，广义的表尾。由此可见，广义表的定义是递归定义的。表的定义是递归定义的。l l D=（）（）空表；其长度为零。空表；其长度为零。l lA=(a，(b，c)表长度为表长度为2的广义表，其中第一个的广义表，其中第一个元素是单个数据元素是单个数据a，第二个元素是一个子表（，第二个元素是一个子表（b，c）。）。l lB=（A，A，D）长度为）长度为3的广义表，其前两个元的广义表，其前两个元素为表素为表A，第三个元素为空表，第三个元素为空表D。l lC=（a，C）长度为长度为2递归定义的广义表，递归定义的广义表，C相当于相当于无

34、穷表无穷表C=（a，（，（a，（，（a，（，（）。）。例如：例如：head(A)=a 表表A的表头是的表头是a。tail(A)=(b，c)表表A的表尾是的表尾是(b，c)，广义表的表尾一定，广义表的表尾一定是一个表。是一个表。从上面的例子可以看出：从上面的例子可以看出：（1）广义表的元素可以是子表，而子表还可以是子）广义表的元素可以是子表，而子表还可以是子表表，由此，广义表是一个多层的结构。，由此，广义表是一个多层的结构。（2）广义表可以被其他广义表共享。如：广义表）广义表可以被其他广义表共享。如：广义表B就共享表就共享表A。在表。在表B中不必列出表中不必列出表A的内容，只要通的内容，只要通过

35、子表的名称就可以引用该表。过子表的名称就可以引用该表。（3）广义表具有递归性，如广义表）广义表具有递归性，如广义表C。广义表中有广义表中有两类结点两类结点，一类是，一类是单个元素结点单个元素结点，一类是，一类是子表结点子表结点。任何一个非空的广义表都可以将其分解成任何一个非空的广义表都可以将其分解成表头表头和和表尾表尾两部分，两部分，反之，一对确定的表头和表尾可以唯一地确定一个广义表。由反之，一对确定的表头和表尾可以唯一地确定一个广义表。由此，一个此，一个表结点表结点可由三个域构成：可由三个域构成：标志域标志域，指向表头的指针域指向表头的指针域，指向表尾的指针域指向表尾的指针域。而。而元素结点

36、元素结点只需要两个域：只需要两个域：标志域标志域和和值域值域。D 111Ac0b0a0 11 111BCa0广义表广义表A、B、C、D的存储结构图的存储结构图 广义表的头尾链表存储结构：广义表的头尾链表存储结构：typedef enum ATOM,LIST ElemTag;/*ATOM0，表示原子；，表示原子；LIST1，表示子表，表示子表*/typedef struct GLNode ElemTag tag;/*标志位标志位tag用来区别原子结点和表结点用来区别原子结点和表结点*/union AtomType atom;/*原子结点的值域原子结点的值域atom*/struct struct

37、GLNode *hp,*tp;htp;/*表结点的指针域表结点的指针域htp，包括表头指针域包括表头指针域hp和表尾指针域和表尾指针域tp*/atom_htp;/*atom_htp 是原子结点的值域是原子结点的值域atom和表结点的指针域和表结点的指针域htp的联合体域的联合体域*/*GList；另外，还有一种广义表存储结构，在这种结构中，无论是单另外，还有一种广义表存储结构，在这种结构中，无论是单元素结点还是子表结点均由三个域构成。元素结点还是子表结点均由三个域构成。其结点结构图为：其结点结构图为：tpatomtag=0tphptag=1表结点表结点原子结点原子结点 1 1a0b0 1 c0

38、 11 1a0DABC 11 1广义表的第二种存储结构图广义表的第二种存储结构图typedef enum ATOM,LIST ElemTag;/*ATOM0，表示原子；，表示原子；LIST1，表示子表，表示子表*/typedef struct GLNode ElemTag tag;union AtomType atom;struct GLNode *hp;atom_hp;struct GLNode *tp;*GList;广义表的扩展线性链表存储结构广义表的扩展线性链表存储结构：下下面面以以广广义义表表的的头头尾尾链链表表存存储储结结构构为为例例，介介绍绍广义表的几个基本操作。广义表的几个基本操

39、作。5.4.3 广义表的操作实现举例广义表的操作实现举例 GList Head(GList L)if(L=NULL)return(NULL);/*空表无表头空表无表头*/if(L-tag=ATOM)exit(0);/*原子不是表原子不是表*/else return(L-atom_htp.htp.hp);GList Tail(GList L)if(L=NULL)return(NULL);/*空表无表尾空表无表尾*/if(L-tag=ATOM)exit(0);/*原子不是表原子不是表*/else return(L-atom_htp.htp.tp);1、求广义表的表头和表尾、求广义表的表头和表尾in

40、t Length(GList L)int n=0;GLNode*s;if(L=NULL)return(0);/*空表长度为空表长度为0*/if(L-tag=ATOM)exit(0);/*原子不是表原子不是表*/s=L;while(s!=NULL)/*统计最上层表的长度统计最上层表的长度*/k+;s=s-atom_htp.htp.tp;return(k);2、求广义表的长度、求广义表的长度 int Depth(GList L)int d,max;GLNode*s;if(L=NULL)return(1);/*空表深度为空表深度为1*/if(L-tag=ATOM)return(0);/*原子深度为原

41、子深度为0*/s=L;while(s!=NULL)/*求每个子表的深度的最大值求每个子表的深度的最大值*/d=Depth(s-atom_htp.htp.hp);if(dmax)max=d;s=s-atom_htp.htp.tp;return(max+1);/*表的深度等于最深子表的深度加表的深度等于最深子表的深度加1*/2、求广义表的深度、求广义表的深度 int CountAtom(GList L)int n1,n2;if(L=NULL)return(0);/*空表中没有原子空表中没有原子*/if(L-tag=ATOM)return(1);/*L指向单个原子指向单个原子*/n1=CountAt

42、om(L-atom_htp.htp.hp);/*求表头中的原子数求表头中的原子数*/n2=CountAtom(L-atom_htp.htp.tp);/*求表尾中的原子数求表尾中的原子数*/return(n1+n2);3、统计广义表中原子数目、统计广义表中原子数目 int CopyGList(GList S,GList*T)if(S=NULL)*T=NULL;return(OK);/*复制空表复制空表*/*T=(GLNode*)malloc(sizeof(GLNode);if(*T=NULL)return(ERROR);(*T)-tag=S-tag;if(S-tag=ATOM)(*T)-atom

43、=S-atom;/*复制单个原子复制单个原子*/else CopyGList(S-atom_htp.htp.hp,&(*T)-atom_htp.htp.hp);/*复制表头复制表头*/CopyGList(S-atom_htp.htp.tp,&(*T)-atom_htp.htp.tp);/*复制表尾复制表尾*/return(OK);4、复制广义表、复制广义表 5.5.1 主要知识点主要知识点1、数组的基本概念、数组的基本概念 n维数组可以看成是这样的一个线性表，其中每个数据元素均维数组可以看成是这样的一个线性表，其中每个数据元素均是一个是一个n-1维数组。维数组。n维数组中的每一个元素由一个值和

44、维数组中的每一个元素由一个值和n个下标来描述。个下标来描述。“值值”代表元素的数据信息，代表元素的数据信息，n个下标用来描述该元素在数组中的相个下标用来描述该元素在数组中的相对位置。对位置。一旦定义了数组的维数和每一维的上下限，数组中元素的的一旦定义了数组的维数和每一维的上下限，数组中元素的的个数就固定了，因此，不能对数组进行插入或删除操作。对于个数就固定了，因此，不能对数组进行插入或删除操作。对于数组的操作一般只有两类：数组的操作一般只有两类：（1）获得特定位置的元素值；）获得特定位置的元素值；（2）修改特定位置的元素值。）修改特定位置的元素值。5.5 总结与提高总结与提高 2、数组的存储结

45、构、数组的存储结构由于数组中元素的个数是固定的，因此采用顺序存储结构。由于数组中元素的个数是固定的，因此采用顺序存储结构。二维数组的顺序存储结构有两种：一种是按行序存储，另一种二维数组的顺序存储结构有两种：一种是按行序存储，另一种是按列序存储。是按列序存储。给定数组的起始地址和每个元素的大小，则根据任意元素的下给定数组的起始地址和每个元素的大小，则根据任意元素的下标，可以计算出该元素在存储器中的地址。因此，数组是一种标，可以计算出该元素在存储器中的地址。因此，数组是一种随机存取结构。随机存取结构。假设二维数组按行序存储，每个元素占假设二维数组按行序存储，每个元素占size个存储单元，数组个存储

46、单元，数组的行下标是从的行下标是从1到到m，列下标是从列下标是从1到到n，首元素首元素a11的地址为的地址为Loc1,1，则任意元素则任意元素aij的地址计算公式为：的地址计算公式为：Loci,j=Loc1,1 (n(i1)j1)size 假设二维数组按行序存储，每个元素占假设二维数组按行序存储，每个元素占size个存储单元，数组个存储单元，数组的行下标是从的行下标是从c1到到d1，列下标是从列下标是从c2到到d2，首元素首元素a(c1,c2)的的地址为地址为Locc1,c2，则任意元素则任意元素aij的地址计算公式为：的地址计算公式为：Loci,j=Locc1,c2 (d2c21)(ic1)

47、jc2)size 假设三维数组采用以行为主序的方法存放，即行下标变化最假设三维数组采用以行为主序的方法存放，即行下标变化最慢，纵下标变化最快，每个元素占慢，纵下标变化最快，每个元素占size个存储单元，数组的行个存储单元，数组的行下标是从下标是从c1到到d1，列下标是从列下标是从c2到到d2，纵下标是从纵下标是从c3到到d3，首首元素元素a(c1,c2,c3)的地址为的地址为Locc1,c2,c3，则任意元素则任意元素a(i，j，k)的地址计算公式为：的地址计算公式为：Loci,j,k=Locc1,c2,c3 (d2c21)(d3c31)(ic1)(d3c31)(jc2)(kc3)size 3

48、、特殊矩阵的压缩存储、特殊矩阵的压缩存储 非零元素的分布有一定规律的矩阵，叫做特殊矩阵（通常为非零元素的分布有一定规律的矩阵，叫做特殊矩阵（通常为高阶矩阵）。高阶矩阵）。可以利用非零元素的分布规律，只存储非零元素，从而实现可以利用非零元素的分布规律，只存储非零元素，从而实现有效的压缩存储。有效的压缩存储。常见的特殊矩阵包括上三角矩阵、下三角矩阵、带状矩阵。常见的特殊矩阵包括上三角矩阵、下三角矩阵、带状矩阵。4、稀疏矩阵、稀疏矩阵非零元素个数只占元素总数的非零元素个数只占元素总数的25%30%或低于这个或低于这个百分数，并且分布没有规律的矩阵，称为稀疏矩阵百分数，并且分布没有规律的矩阵，称为稀疏

49、矩阵（通常为高阶矩阵）。（通常为高阶矩阵）。稀疏矩阵的顺序存储结构：三元组表稀疏矩阵的顺序存储结构：三元组表稀疏矩阵的链式存储结构：十字链表稀疏矩阵的链式存储结构：十字链表5、广义表、广义表 广义表是广义表是n个数据元素（个数据元素（d1，d2，d3，dn）的的有限序列，其中有限序列，其中di 既可以是单个元素，也可以是一个既可以是单个元素，也可以是一个广义表。广义表。在广义表（在广义表（d1，d2，d3，dn）中，中，d1是广义表是广义表的表头，而（的表头，而（d2，d3，dn）称为广义表的表尾。称为广义表的表尾。广义表的头尾链表存储结构广义表的头尾链表存储结构 广义表的扩展线性链表存储结构

50、广义表的扩展线性链表存储结构 广义表的简单操作广义表的简单操作 5.5.2 典型题选解典型题选解例例1 已知数组M1.10,1.6,0.3，求：（1）数组的元素总数；（2）若数组以下标顺序为主序存储，起始地址为1000，且每个数据元素占用3个存储单元，试分别计算M2,4,2,M5,1,3的地址。解：（1）数组的元素总数为：(1011)(6(1)1)(301)=320（2）地址计算公式为：Loci,j,k=Locc1,c2,c3 (d2c21)(d3c31)(ic1)(d3c31)(jc2)(kc3)size在此c1=1，d1=10，c2=1，d2=6，c3=0，d3=3，所以：Loc2,4,2