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

《【教学课件】第5章数组和广义表.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第5章数组和广义表.ppt（63页珍藏版）》请在三一办公上搜索。

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

2、运算,数组是一种数据类型。从逻辑结构上看，数组可以看成是一般线性表的扩充。二维数组可以看成是线性表的线性表。例如：,我们可以把二维数组看成一个线性表：A=(1 2 j n)，其中j（1j n）本身也是一个线性表，称为列向量。,矩阵Amn看成n个列向量的线性表,即j=(a1j,a2j,amj),我们还可以将数组Amn看成另外一个线性表:B=(1，,2,，m)，其中i（1i m）本身也是一个线性表，称为行向量，即：I=（ai1，ai2，aij，ain）。,上面二维数组的例子，介绍了数组的结构特性，实际上数组是一组有固定个数的元素的集合。由于这个性质，使得对数组的操作不象对线性表的操作那样，可以在表

3、中任意一个合法的位置插入或删除一个元素。,对于数组的操作一般只有两类：（1）获得特定位置的元素值；（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和各维的长度合法，则构造相应的数组A，并返回TRUE；

4、,（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语言的数组略有不同。,5.2 数组的顺序存储和实现,对于数组A，一旦给定其维数n及各维长度bi（1in），则该数组中元素的个数是固定的，不可以对数组做插入和删除操作，不涉及移动元素操作，因此对于数组而言，采用顺序存储法比较合适。

5、,数组的顺序存储结构有两种：一种是按行序存储，如高级语言BASIC、COBOL和PASCAL语言都是以行序为主。另一种是按列序存储，如高级语言中的FORTRAN语言就是以列序为主。,对于二维数组Amxn以行为主的存储序列为：a11,a12,a1n,a21,a22,a2n,am1,am2,amn 以列为主存储序列为：a11,a21,am1,a12,a22,am2,a1n,a2n,amn,假设有一个342的三维数组A，其逻辑结构图为：,以二维数组Amn为例，假设每个元素只占一个存储单元，“以行为主”存放数组，下标从1开始，首元素a11的地址为Loc1,1 求任意元素aij的地址，可由如下计算公式得

6、到：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的二维数组，如下图所示：,假定每个元素占一个存储单元，采用以行为主序的方法存放，首元素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。,如果将三维数组推广

7、到一般情况，即：用j1，j2，j3代替数组下标i，j，k；并且j1，j2，j3的下限为c1，c2，c3，上限分别为d1，d2，d3，每个元素占一个存储单元。则三维数组中任意元素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-c

8、3)=Locc1,c2,c3+i*(ji-ci)（1i3）,由公式可知Locj1,j2,j3与j1,j2,j3呈线性关系。,对于维数组A(c1:d1,c2:d2，,cn,dn)，我们只要把上式推广，就可以容易地得到维数组中任意元素aj1j2jn的存储地址的计算公式。,5.3 特殊矩阵的压缩存储,特殊矩阵压缩存储的压缩原则是：对有规律的元素和值相同的元素只分配一个存储单元，对于零元素不分配空间。,5.3.1 三角矩阵,三角矩阵大体分为：下三角矩阵、上三角矩阵和对称矩阵。对于一个n阶矩阵A来说：若当ij时，有aij=0，则此矩阵称为上三角矩阵；若矩阵中的所有元素均满足aij=aji，则称此矩阵为对

9、称矩阵。,对于下三角矩阵，按“行序为主序”进行存储，得到的序列为：a11,a21,a22,a31,a32,a33an1,an2ann。由于下三角矩阵的元素个数为n(n+1)/2，所以可压缩存储到一个大小为n(n+1)/2的一维数组中。下三角矩阵中元素aij(ij)，在一维数组A中的位置为：LOC i,j=LOC1,1+i(i-1)/2+j-1,下三角矩阵：,同样，对于上三角矩阵，也可以将其压缩存储到一个大小为n(n+1)/2的一维数组C中。其中元素aij(ij)在数组C中的存储位置为：Loci,j=Loc1,1+j(j-1)/2+i-1,对于对称矩阵，因其元素满足aij=aji，我们可以为每一

10、对相等的元素分配一个存储空间，即只存下三角（或上三角）矩阵，从而将n2个元素压缩到n(n+1)/2个空间中。,5.3.2 带状矩阵,带状矩阵：在矩阵A中，所有的非零元素都集中在以主对角线为中心的带状区域中。最常见的是三对角带状矩阵。,特点:,时，aij非零，其他元素均为零。,三对角带状矩阵的压缩存储，以行序为主序进行存储，并且只存储非零元素。其方法为：,1.确定存储该矩阵所需的一维向量空间的大小,从三对角带状矩阵中可看出：除第一行和最后一行只有两个元素外，其余各行均有3个非零元素。由此可得到一维向量所需的空间大小为：3n-2。,2.确定非零元素在一维数组空间中的位置,LOCi,j=LOC1,1

11、+3（i-1）-1+j-i+1=LOC1,1+2(i-1)+j-1,5.3.3 稀疏矩阵,稀疏矩阵：指矩阵中大多数元素为零的矩阵。一般地，当非零元素个数只占矩阵元素总数的25%30%,或低于这个百分数时，我们称这样的矩阵为稀疏矩阵。,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 0,1.稀疏矩阵的三元组表表示法,对于稀疏矩阵的压缩存储要求在存储非零元素的同时，还必须存储该非零元素在矩阵中所处的行号和列号。我们将这种存储方法叫做稀疏矩阵的三元组表示法。,每个非零元素在一维

12、数组中的表示形式如图所示：,三元组表的类型说明：,#define MAXSIZE 1000/*非零元素的个数最多为1000*/typedef structint row,col;/*该非零元素的行下标和列下标*/ElementType e；/*该非零元素的值*/Triple;typedef struct Triple dataMAXSIZE+1;/*非零元素的三元组表。data0未用*/int m,n,len;/*矩阵的行数、列数和非零元素的个数*/TSMatrix；,1）用三元组表实现稀疏矩阵的转置运算,矩阵转置：指变换元素的位置，把位于（row，col）位置上的元素换到（col，row）位

13、置上，也就是说，把元素的行列互换。,采用矩阵的正常存储方式时，实现矩阵转置的经典算法如下：,Void TransMatrix（ElementType sourcenm,ElementType destmn）/*Source和dest分别为被转置的矩阵和转置后的矩阵（用二维数组表示）*/int i,j;for(i=0;im;i+)for(j=0;j n;j+)desti j=sourcej i;,实现转置的简单方法：,矩阵source的三元组表A的行、列互换就可以得到B中的元素，如图：,为了保证转置后的矩阵的三元组表B也是以“行序为主序”进行存放，则需要对行、列互换后的三元组B，按B的行下标（即

14、A的列下标）大小重新排序。,两种处理转置算法如下：,算法一、,void TransposeTSMatrix(TSMatrix A,TSMatrix*B)/*把矩阵A转置到B所指向的矩阵中去。矩阵用三元组表表示*/int i,j,k;B-m=A.n;B-n=A.m;B-len=A.len;if(B-len0)j=1;for(k=1;kdataj.row=A.datai.col B-dataj.col=A.datai.row;B-dataj.e=A.datai.e;j+;,算法二、,FastTransposeTSMatrix(TSMatrix A,TSMatrix*B)/*基于矩阵的三元组表示，采

15、用快速转置法，将矩阵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;coldataq.row=A.datap.col;B-dataq.col=A.datap.row;B-dataq.e=A.datap.epositioncol+;,用三元组表实现稀疏矩阵的乘法运算,设矩阵M是m1n1矩阵，N是m2n2矩阵；若可以相乘，则必须满足矩阵M的列数n1与矩阵N的行数m2相等，才能得到结果矩阵Q=MN（一个m1n2的矩阵）。,数学中矩阵Q中的元素

16、的计算方法如下：,其中：1im1，1jn2,根据数学上矩阵相乘的原理，我们可以得到矩阵相乘的经典算法：,for(i=1;i=m1;i+)for(j=1;j=n2;j+)Qij=0;for(k=1;k=n1;k+)Qij=Qij+Mik*Nkj;,经典算法中，不论Mik，Nkj是否为零，都要进行一次乘法运算，而实际上，这是没有不必要的。采用三元组表的方法来实现时，因为三元组只对矩阵的非零元素做存储，所以可以采用固定三元组a中元素（i，k，Mik）（1im1，1kn1），在三元组b中找所有行号为k的的对应元素（k，j，Nkj）（1km2，1jn2）进行相乘、累加从而得到Qij。即：以三元组a中的元

17、素为基准，依次求出其与三元组b的有效乘积。,相乘基本操作：对于三元组a中每个元素a.datap（p=1，2，3，a.len），找出三元组b中所有满足条件a.datap.col=b.dataq.row的元素b.dataq，求得a.datap.e与b.dataq.e的乘积，而这个乘积只是Qi，j的一部分，应对每个元素设一个累计和变量，其初值为0。扫描完三元组a，求得相应元素的乘积并累加到适当的累计和的变量上。,注意：两个稀疏矩阵相乘的结果不一定是稀疏矩阵。反之，相乘的每个分量Mi，kNk，j不为零，但累加的结果Qi，j可能是零。例如：,#define MAXSIZE 1000/*非零元素的个数最多

18、为1000*/#define MAXROW 1000/*矩阵最大行数为1000*/typedef structint row,col;/*该非零元素的行下标和列下标*/ElementType e；/*该非零元素的值*/Triple;typedef struct Triple dataMAXSIZE+1;/*非零元素的三元组表，data0未用*/int firstMAXROW+1;/*三元组表中各行第一个非零元素所在的位置。*/int m,n,len;/*矩阵的行数、列数和非零元素的个数*/TriSparMatrix；,为方便实现，将三元组表的类型说明修改如下：,具体算法如下：,int MulS

19、Matrix(TriSparMatrix M,TriSparMatrix N,TriSparMatrix*Q)/*采用改进的三元组表表示法，求矩阵乘积QMN*/int arow,brow,p;int ctempMAXSIZE;if(M.n!=N.m)return FALSE;/*返回FALSE表示求矩阵乘积失败*/Q-m=M.m;Q-n=N.n;Q-len=0;if(M.len*N.len!=0)for(arow=1;arowfirstarow=Q-len+1;for(p=M.firstarow;pM.firstarow+1;p+)/*p指向M当前行中每一个非零元素*/,brow=M.data

20、p.col;/*M中的列号应与N中的行号相等*/if(brown；col+)/*压缩存储该非零元*/if(ctempccol)if(+Q-lenMAXSIZE)return 0;Q-dataQ-len=arow,ccol,ctempccol;/*if*/*for arow*/*if*/return(TRUE);/*返回TRUE表示求矩阵乘积成功*/,2.稀疏矩阵的链式存储结构：十字链表,优点：它能够灵活地插入因运算而产生的新的非零元素，删除因运算而产生的新的零元素，实现矩阵的各种运算。,在十字链表中，矩阵的每一个非零元素用一个结点表示，该结点除了（row，col，value）以外，还要有两个域

21、：,right：用于链接同一行中的下一个非零元素；down：用以链接同一列中的下一个非零元素。,十字链表中结点的结构示意图：,十字链表的结构类型说明如下：,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;/*稀疏矩阵的行数、列数、非零元素的个数*/CrossLis

22、t;,建立稀疏矩阵的十字链表算法：,CreateCrossList(CrossList*M)/*采用十字链表存储结构，创建稀疏矩阵M*/if(M!=NULL)free(M);scanf(/*生成结点*/,if(M-row_headi=NULL)M-row_headi=p;else/*寻找行表中的插入位置*/for(q=M-row_headi;q-right/*完成插入*/,5.4 广义表,广义表也是线性表的一种推广。广义表也是n个数据元素（d1，d2，d3，dn）的有限序列，但不同的是，广义表中的di既可以是单个元素，还可以是一个广义表，通常记作：GL=（d1，d2，d3，dn）。GL是广义表

23、的名字，通常用大写字母表示。n是广义表的长度。若 di是一个广义表，则称di是广义表GL的子表。在GL中，d1是GL的表头，其余部分组成的表（d2，d3，dn）称为GL的表尾。由此可见，广义表的定义是递归定义的。,l D=（）空表；其长度为零。,lA=(a，(b，c)表长度为2的广义表，其中第一个元素是单个数据a，第二个元素是一个子表（b，c）。,lB=（A，A，D）长度为3的广义表，其前两个元素为表A，第三个元素为空表D。,lC=（a，C）长度为2递归定义的广义表，C相当于无穷表C=（a，（a，（a，（）。,例如：,head(A)=a 表A的表头是a。tail(A)=(b，c)表A的表尾是(

24、b，c)，广义表的表尾一定是一个表。,从上面的例子可以看出：,（1）广义表的元素可以是子表，而子表还可以是子表，由此，广义表是一个多层的结构。,（2）广义表可以被其他广义表共享。如：广义表B就共享表A。在表B中不必列出表A的内容，只要通过子表的名称就可以引用该表。,（3）广义表具有递归性，如广义表C。,广义表中有两类结点，一类是单个元素结点，一类是子表结点。任何一个非空的广义表都可以将其分解成表头和表尾两部分，反之，一对确定的表头和表尾可以唯一地确定一个广义表。由此，一个表结点可由三个域构成：标志域，指向表头的指针域，指向表尾的指针域。而元素结点只需要两个域：标志域和值域。,广义表A、B、C、

25、D的存储结构图,广义表的头尾链表存储结构：typedef enum ATOM,LIST ElemTag;/*ATOM0，表示原子；LIST1，表示子表*/typedef struct GLNode ElemTag tag;/*标志位tag用来区别原子结点和表结点*/union AtomType atom;/*原子结点的值域atom*/struct struct GLNode*hp,*tp;htp;/*表结点的指针域htp，包括表头指针域hp和表尾指针域tp*/atom_htp;/*atom_htp 是原子结点的值域atom和表结点的指针域htp的联合体域*/*GList；,另外，还有一种广义表

26、存储结构，在这种结构中，无论是单元素结点还是子表结点均由三个域构成。其结点结构图为：,广义表的第二种存储结构图,typedef enum ATOM,LIST ElemTag;/*ATOM0，表示原子；LIST1，表示子表*/typedef struct GLNode ElemTag tag;union AtomType atom;struct GLNode*hp;atom_hp;struct GLNode*tp;*GList;,广义表的扩展线性链表存储结构：,下面以广义表的头尾链表存储结构为例，介绍广义表的几个基本操作。,5.4.3 广义表的操作实现举例,GList Head(GList L)

27、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、求广义表的表头和表尾,int Length(GList L)int n=0;GLNode*s;if(L=NULL)return(0);/*空表长度为0*/if(L-tag=ATOM

28、)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);/*原子深度为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+

29、1);/*表的深度等于最深子表的深度加1*/,2、求广义表的深度,int CountAtom(GList L)int n1,n2;if(L=NULL)return(0);/*空表中没有原子*/if(L-tag=ATOM)return(1);/*L指向单个原子*/n1=CountAtom(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;retur

30、n(OK);/*复制空表*/*T=(GLNode*)malloc(sizeof(GLNode);if(*T=NULL)return(ERROR);(*T)-tag=S-tag;if(S-tag=ATOM)(*T)-atom=S-atom;/*复制单个原子*/else CopyGList(S-atom_htp.htp.hp,4、复制广义表,5.5.1 主要知识点1、数组的基本概念 n维数组可以看成是这样的一个线性表，其中每个数据元素均是一个n-1维数组。n维数组中的每一个元素由一个值和n个下标来描述。“值”代表元素的数据信息，n个下标用来描述该元素在数组中的相对位置。一旦定义了数组的维数和每一维

31、的上下限，数组中元素的的个数就固定了，因此，不能对数组进行插入或删除操作。对于数组的操作一般只有两类：（1）获得特定位置的元素值；（2）修改特定位置的元素值。,5.5 总结与提高,2、数组的存储结构由于数组中元素的个数是固定的，因此采用顺序存储结构。二维数组的顺序存储结构有两种：一种是按行序存储，另一种是按列序存储。给定数组的起始地址和每个元素的大小，则根据任意元素的下标，可以计算出该元素在存储器中的地址。因此，数组是一种随机存取结构。假设二维数组按行序存储，每个元素占size个存储单元，数组的行下标是从1到m，列下标是从1到n，首元素a11的地址为Loc1,1，则任意元素aij的地址计算公式

32、为：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)jc2)size 假设三维数组采用以行为主序的方法存放，即行下标变化最慢，纵下标变化最快，每个元素占size个存储单元，数组的行下标是从c1到d1，列下标是从c2到d2，纵下标是从c3到d3，首元素a(c1,c2,c3)的地址为Locc1,c2,c3，则任意元素a(i，j，k)的地址计算公式为：Loc

33、i,j,k=Locc1,c2,c3(d2c21)(d3c31)(ic1)(d3c31)(jc2)(kc3)size,3、特殊矩阵的压缩存储 非零元素的分布有一定规律的矩阵，叫做特殊矩阵（通常为高阶矩阵）。可以利用非零元素的分布规律，只存储非零元素，从而实现有效的压缩存储。常见的特殊矩阵包括上三角矩阵、下三角矩阵、带状矩阵。,4、稀疏矩阵非零元素个数只占元素总数的25%30%或低于这个百分数，并且分布没有规律的矩阵，称为稀疏矩阵（通常为高阶矩阵）。稀疏矩阵的顺序存储结构：三元组表稀疏矩阵的链式存储结构：十字链表,5、广义表 广义表是n个数据元素（d1，d2，d3，dn）的有限序列，其中di 既可

34、以是单个元素，也可以是一个广义表。在广义表（d1，d2，d3，dn）中，d1是广义表的表头，而（d2，d3，dn）称为广义表的表尾。广义表的头尾链表存储结构 广义表的扩展线性链表存储结构 广义表的简单操作,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)

35、(d3c31)(jc2)(kc3)size在此c1=1，d1=10，c2=1，d2=6，c3=0，d3=3，所以：Loc2,4,2=1000(6(1)1)(301)(21)(301)(4(1)(20)3=1162Loc5,1,3=1000(6(1)1)(301)(51)(301)(1(1)(30)size=1393,例2 已知上三角矩阵Ann，当 ij时，aij=c，要求将其压缩存储到一维数组B1.m中。请说明压缩存储方法，并给出任意元素aij与Bk的对应关系：k=f(i,j)。解：显然，上三角中共有n(n+1)/2个元素，下三角中所有相同元素c可以共享一个存储单元，所以一维数组B1.m的上界

36、m=n(n+1)/2+1。将上三角中n(n+1)/2个元素逐行存放到一维数组B的前m1个单元中，相同元素c存放在最后一个单元Bm中。,上三角中第t行共有n-t+1个元素，所以，对于上三角中任意元素aij而言，排在前面的i-1行中共有元素：在上三角的第i行中，排在aij前面的元素数目为：j-(i-1)-1=j-i。所以，对于上三角中任意元素aij而言，排在aij前面的元素数目为：,因此，上三角中任意元素aij在一维数组B中的位置为：综上所述，上三角矩阵Ann中任意元素aij与Bk的对应关系为：当 ij时，当 i=j时，思考题：如何编写从一维数组B中取出任意元素aij的函数 GetValue(i,

37、j)？,例3 已知广义表L=(x,y,z),a,(u,t,w)，从L表中取出原子u的运算是：A)head(tail(tail(L)B)tail(head(head(tail(L)C)head(tail(head(tail(L)D)head(head(tail(tail(L)解：取出原子u的过程如下：1）用tail运算去掉表头(x,y,z)，即：tail(L)=(a,(u,t,w)2）再用tail运算去掉表头a，即：tail(tail(L)=(u,t,w)3）用head运算取出表头(u,t,w)，即：head(tail(tail(L)=(u,t,w)4）再用head运算取出表头u，即：head(head(tail(tail(L)=u,