数据和广义表精品ppt课件

1、第第5章章 数组和广义表数组和广义表5.1数组的定义与运算数组的定义与运算 5.2数组的顺序存储构造数组的顺序存储构造5.3矩阵的紧缩存储矩阵的紧缩存储5.4广义表广义表习题习题5.1 数组的定义与运算数组的定义与运算 数组定义：类似于线性表，一个两维数组的逻辑构造数组定义：类似于线性表，一个两维数组的逻辑构造可方式地表示为可方式地表示为 2_Array=(D,R)其中其中D=aij|i=0,1,m-1,j=0,1,n-1，aij是同类型数据元是同类型数据元素的集合。素的集合。 R=ROW,COL是数据元素上关系的集合。是数据元素上关系的集合。 ROW=|0im-1,0jn-2每一行上的列关系

2、。每一行上的列关系。 COL=|0im-2,0jn-1每一个列上的行关每一个列上的行关系。系。 行列关系跟线性表曾经大不一样了行列关系跟线性表曾经大不一样了,见图见图5.1所示。所示。a01 a02 a0n-1a11 a12 a1n-1 am-11am-12am-1n-1 图图5.1 二维数组元素关系二维数组元素关系 二维数组中的每一个元素二维数组中的每一个元素aij都遭到两个关系都遭到两个关系的约束：的约束：ROW(行关系行关系)和和COL(列关系列关系)。aij+1是是aij在行关系中的直接后续元素；而在行关系中的直接后续元素；而ai+1j是是aij在列在列关系中的直接后续元素。和线性表一

3、样，一切的关系中的直接后续元素。和线性表一样，一切的数据元素属于同一数据类型。每个数据元素对应数据元素属于同一数据类型。每个数据元素对应于一组下标于一组下标(i,j)。将这个概念依次类推，可以写出。将这个概念依次类推，可以写出n维数组的逻辑构造，但最常用的是二维数组。维数组的逻辑构造，但最常用的是二维数组。 也可以从另一个角度来定义二维数组，即将二维数组也可以从另一个角度来定义二维数组，即将二维数组看成这样一个线性表：它的每一个数据元素是一个线性表看成这样一个线性表：它的每一个数据元素是一个线性表(一维数组一维数组)。例如，图。例如，图5.1所示的是一个二维数组，以所示的是一个二维数组，以m行

4、行n列的矩阵方式表示。它可以看成是一个线性表：列的矩阵方式表示。它可以看成是一个线性表： A =(0 ,1 ,2 ,3 ,P) (p=m-1或或n-1)其中每一个数据元素其中每一个数据元素j 是一个列向量的线性表是一个列向量的线性表 j =(a0j ,a1j ,a2j ,am-1j)或者或者i 是一个行向量的线性表：是一个行向量的线性表： i =(ai0 ,ai1 ,ai2 ,ain-1) 这种定义二维数组的方法也可以推行到这种定义二维数组的方法也可以推行到n维数组，即以维数组，即以为为n维数组是一个线性表，它的每一个数据元素是一个维数组是一个线性表，它的每一个数据元素是一个n-1维数组。维数

5、组。 在数组构造最常用的操作：给定数组的下标在数组构造最常用的操作：给定数组的下标i，对相应，对相应元素元素ai作取数、赋值的操作，操作方法根据其存储构造决作取数、赋值的操作，操作方法根据其存储构造决议。议。5.2 数组的顺序存储构造数组的顺序存储构造 由于数组普通不作插入或删除操作，也就是说，一旦由于数组普通不作插入或删除操作，也就是说，一旦建立了数组，那么构造中的数据元素个数和元素之间的关建立了数组，那么构造中的数据元素个数和元素之间的关系就不再发生变动，因此，采用顺序存储构造表示数组。系就不再发生变动，因此，采用顺序存储构造表示数组。 顺序构造即是用一组延续的存储单元来存放数组构造。顺序

6、构造即是用一组延续的存储单元来存放数组构造。内存地址是一维的，而数组构造能够是多维的。如何将多内存地址是一维的，而数组构造能够是多维的。如何将多维的数组挤入一维的地址中，就有了战略问题：维的数组挤入一维的地址中，就有了战略问题： 按行序为主序按行序为主序(row major order)。首先，存放数组的。首先，存放数组的第一行，然后，按顺序存放数组的各行；第一行，然后，按顺序存放数组的各行； 按列序为主序按列序为主序(column major order)。首先，存放数组。首先，存放数组的第一列，然后，按顺序存放数组的各列，的第一列，然后，按顺序存放数组的各列， 如图如图5.2所示。大多数程

7、序设计言语是按行主序来陈列所示。大多数程序设计言语是按行主序来陈列数组元素的，但列主序也是常见的。数组元素的，但列主序也是常见的。 (a)二维数组 (b)行序 (c)列序图5.2 二维数组的两种存储方式 数组的顺序存储方式，给对数组元素的随机存数组的顺序存储方式，给对数组元素的随机存取带来方便。由于，数组是同类型数据元素的集取带来方便。由于，数组是同类型数据元素的集合，所以，每一个数据元素所占用的内存空间的合，所以，每一个数据元素所占用的内存空间的单元数是一样的，故只需给出首地址，可以运用单元数是一样的，故只需给出首地址，可以运用一致的地址公式，求出数组中恣意元素的地址。一致的地址公式，求出数

8、组中恣意元素的地址。这里以二维数组的行主序为例，讨论数组元素的这里以二维数组的行主序为例，讨论数组元素的地址计算方法。二维数组地址计算方法。二维数组aij(mn) LOC(i,j)=LOC(0,0)+(in+j)s (0im-1, 0jn-1) 其中，其中，s是每个数据元素所占存储单元的个数。是每个数据元素所占存储单元的个数。 可将二维数组的元素想象为一个一维数组，大可将二维数组的元素想象为一个一维数组，大小为小为p，那么推出三维数组的地址计算方法。，那么推出三维数组的地址计算方法。 三维数组三维数组aijk(mnp)： LOC(i,j,k)=LOC(0,0,0)+(in+j)sp+ks LO

9、C(i,j,k)=LOC(0,0,0)+(inp+jp+k)s (0im-1, 0jn-1，0kp-1) 可将概念依次类推，可以写出可将概念依次类推，可以写出n维数组地址计算维数组地址计算方法。方法。 5.3 矩阵的紧缩存储矩阵的紧缩存储 在工程运用中，矩阵有着重要的作用。许多在工程运用中，矩阵有着重要的作用。许多实践问题的处理需求大量数据的综合计算，而这实践问题的处理需求大量数据的综合计算，而这些大量数据之间总是表现出二维数组的逻辑构造。些大量数据之间总是表现出二维数组的逻辑构造。而这种二维数组构造在数学上称为矩阵。而这种二维数组构造在数学上称为矩阵。 为了使矩阵的各种运算能有效地进展，必需

10、为了使矩阵的各种运算能有效地进展，必需在算法的空间和时间复杂度上下功夫。首先我们在算法的空间和时间复杂度上下功夫。首先我们思索如何减少空间复杂度，即找一种高效的存储思索如何减少空间复杂度，即找一种高效的存储方法，再在相应的存储构造上找高效的算法。许方法，再在相应的存储构造上找高效的算法。许多矩阵的数据分布是有特征的，那就要利用这种多矩阵的数据分布是有特征的，那就要利用这种特征，尽量减少数据的存储量。特征，尽量减少数据的存储量。 5.3.1 特殊矩阵特殊矩阵 a.对称矩阵对称矩阵 定义：假设有一个定义：假设有一个n阶矩阵阶矩阵A中的元素满足下述中的元素满足下述性质性质 aij=aji 1i,jn

11、那么称为那么称为n阶对称矩阵。对称矩阵可以只给每一对阶对称矩阵。对称矩阵可以只给每一对对称元素分配一个存储空间，那么可将对称元素分配一个存储空间，那么可将nn的二的二维矩阵，紧缩存储到维矩阵，紧缩存储到n(n+1)/2个元的空间中。在这个元的空间中。在这里讨论以行序为主序存储其下三角里讨论以行序为主序存储其下三角(包括对角线包括对角线)中中的对称矩阵元素。假设以一维数组的对称矩阵元素。假设以一维数组sn(n+1)/2作为作为n阶对称矩阵阶对称矩阵A的存储构造，数组元素的存储构造，数组元素sk于矩阵于矩阵元素元素aij之间转换公式如下。之间转换公式如下。jiijjjijiik21)21()( 存

12、储表示：存储表示： 对于恣意给出的数组下标对于恣意给出的数组下标(i,j)，均可以在，均可以在sa中找到中找到 矩阵元素矩阵元素aij，反之，对一切的，反之，对一切的k=1,2,n(n+1)/2,都都能确定能确定sak中的矩阵元素在矩阵中的位置中的矩阵元素在矩阵中的位置(i,j)。由。由此，称此，称san(n+1)/2为为n阶对称矩阵阶对称矩阵A的紧缩存储的紧缩存储,如如图图5.3所示。所示。 a00 a10 a11 an1 an-1n-1 k= 1 2 3n(n+1)/2-1图5.3 对称矩阵的紧缩存储 运算运算算法算法5.1 紧缩存储的对称矩阵中的取值算法。紧缩存储的对称矩阵中的取值算法。

13、 /* 取对称矩阵取对称矩阵s中第中第i行第行第j列的元素列的元素 */ int Matrix_Get(int s,int i,int j) if(i=j) return(si*(i+1)/2+j); else return(sj*(j+1)/2+i); 算法算法5.2 紧缩存储的对称矩阵中的赋值算法。紧缩存储的对称矩阵中的赋值算法。 void Matrix_Set(int s,int i,int j,int value) if(i=j) si*(i+1)/2+j=value; else sj*(j+1)/2+i=value; b.三角矩阵三角矩阵 上述的这种紧缩存储的方法同样也适用于三角上述

14、的这种紧缩存储的方法同样也适用于三角矩阵。下矩阵。下(上上)三角矩阵是指矩阵的主对角线以上三角矩阵是指矩阵的主对角线以上(下下)的元素均为的元素均为0或某个常数或某个常数c的的n阶矩阵。例如，阶矩阵。例如，上三角矩阵上三角矩阵: 只需存储其上三角中元素即可，假设下三角不为零，只需存储其上三角中元素即可，假设下三角不为零，那么再加一个存储常数那么再加一个存储常数c的存储空间。的存储空间。 算法算法5.3 紧缩存储的上三角矩阵中的取值算法。紧缩存储的上三角矩阵中的取值算法。 int Matrix_Get(int s,int i,int j) if(ij) return(0); else retur

15、n(sj*(j+1)/2+i); 算法算法5.4 紧缩存储的上三角矩阵中的赋值算法。紧缩存储的上三角矩阵中的赋值算法。 void Matrix_Set(int s,int i,int j,int value) if(i=j) sj*(j+1)/2+i=value; c. 对角矩阵对角矩阵 在这种矩阵中，一切非在这种矩阵中，一切非0元素都集中在以主对角元素都集中在以主对角线为中心的带状区域。即除了主对角线上和直接线为中心的带状区域。即除了主对角线上和直接在对角线上、下方假设干条对角线上的元素之外，在对角线上、下方假设干条对角线上的元素之外，一切其它的元素皆为一切其它的元素皆为0。也称为半带宽为。

16、也称为半带宽为d的带状的带状矩阵矩阵(带宽为带宽为2d+1)，d为直接在对角线上、下方不为直接在对角线上、下方不为为0的对角线数。当对角矩阵带宽为的对角线数。当对角矩阵带宽为d时，其非零时，其非零元素个数如下：元素个数如下：带宽非零元素个数d=0 d=1 d=2 d=3 d=dnn+2(n-1)n+2(n-1)+(n-2)n+2(n-1)+(n-2)+(n-3)n+2(n-1)+(n-2)+(n-d)=n+2(n-1)+(n-d)d/2=n+(2n-1-d)d=n+2nd-1d-dd=(2d+1)n-(1+d)d 所以，对于所以，对于n阶阶2d+1对角矩阵，只需存放对角对角矩阵，只需存放对角区

17、域内区域内n(2d+1)-d(d+1)个非零元素。但为计算方便，个非零元素。但为计算方便，以为每一行都有以为每一行都有2d+1个元素，假设少于个元素，假设少于2d+1个元个元素，那么添素，那么添0补足。这样用补足。这样用s(2d+1)n作为存储构作为存储构造，扩展了上下二个三角区域，多了造，扩展了上下二个三角区域，多了(1+d)d个单个单元。例如，当元。例如，当d=1，n=5，n阶矩阵为阶矩阵为 0 a00 a01 a10 a11 a12 a21 a22 a23 a32 a33 a34 a43 a44 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14其存储方式为其存储方

18、式为 数组元素数组元素sk于矩阵元素于矩阵元素aij之间转换公式如下：之间转换公式如下： k=i(2d+1)+d+(j-i) 如如a23 所对应所对应sk,k=2(2d+1)+d+(3-2)=8算法算法5.5 紧缩存储的紧缩存储的2d+1对角矩阵中的取值算法。对角矩阵中的取值算法。 int Matrix_Get(int s,int d,int i,int j) if(abs(i-j)=d) return(si(2d+1)+d+(j-i); return(0); 算法算法5.6 紧缩存储的紧缩存储的2d+1对角矩阵中的赋值算法。对角矩阵中的赋值算法。 void Matrix_Set(int s,

19、int d,int i,int j,int value) if(abs(i-j)mu=Ma.nu; Mb-nu=Ma.mu; Mb-tu=Ma.tu; if(Mb-tu=0) return; for(k=0,col=0; colMa.nu; col+) for(i=0; idatak.i=Ma.datai.j; Mb-datak.j=Ma.datai.i; Mb-datak.value=Ma.datai.value; k+; /* k为为Mb中下一个三元组的位置中下一个三元组的位置 */ 快速转置运算。快速转置运算。 快速转置运算以快速转置运算以A矩阵的三元组表为中心，依矩阵的三元组表为中心，

20、依次取出次取出Ma.data中每一个三元组，交换行列后，中每一个三元组，交换行列后，找到其在找到其在Mb.data中的适宜位置，直接写入。中的适宜位置，直接写入。 这样操作的根底是：需求确定这样操作的根底是：需求确定A矩阵中每列矩阵中每列(B中每行中每行)的非零元素个数，也就确定了的非零元素个数，也就确定了A中每列第中每列第一个非零元素在一个非零元素在Mb.data中的存放位置。为此，中的存放位置。为此，需求两个辅助数组需求两个辅助数组num和和pos，numcol(0coln-1)表示表示A中第中第col列非零元素的个数。列非零元素的个数。poscol(0coln-1)表示表示A中第中第co

21、l列非零元素在列非零元素在mb中的位置。显然有：中的位置。显然有： pos0=1 poscol=poscol-1+numcol-1例如，对图例如，对图5.4中的稀疏矩阵中的稀疏矩阵A，num和和pos的值如表的值如表5.1所示。即第所示。即第col列第一个非零元素的位置是：第列第一个非零元素的位置是：第col-1列的第一个非零元素位置与第列的第一个非零元素位置与第col-1列的非零元素个列的非零元素个数之和。这样每从数之和。这样每从Ma.data取出一个元素取出一个元素Ma.datai，根据根据col= Ma.datai.j，其在，其在Mb.data中的位置是中的位置是k=poscol，并将，

22、并将poscol加加1，当再次取到，当再次取到col列元素列元素时，它在时，它在Mb.data中的位置是中的位置是k+1，恰好是排在该列，恰好是排在该列上一个元素之后，满足矩阵上一个元素之后，满足矩阵B行序的要求。快速转置行序的要求。快速转置运算如下：运算如下： Col 0 1 2 3 4 5 6numcol 2 2 2 1 0 1 0 poscol 0 2 4 6 7 7 8表表5.1 矩阵矩阵A的辅助数组的值的辅助数组的值 算法算法5.8 三元组中，快速转置算法。三元组中，快速转置算法。 void TriList_FastTranspose(TriList Ma, TriList *Mb)

23、 int i,j,col,k,numMAX,posMAX; Mb-mu=Ma.nu; Mb-nu=Ma.mu; Mb-tu=Ma.tu; if(Mb-tu=0) return; for(i=0; iMa.nu; i+) numi=0; /*统计统计M中每列的三元组中每列的三元组个数个数*/ for(i=0; iMa.tu; i+) numMa.datai.j+; for(pos0=0,col=1; colMa.nu; col+) /* 计算计算pos数组数组 */ poscol=poscol-1+numcol-1; for(i=0; idatak.i=Ma.datai.j; Mb-datak.

24、j=Ma.datai.i; Mb-datak.value=Ma.datai.value; poscol+; (2)十字链表的存储构造十字链表的存储构造 以三元组表示的稀疏矩阵，在运算中，假设非以三元组表示的稀疏矩阵，在运算中，假设非零元素的位置发生变化，会引起数组元素的频繁挪零元素的位置发生变化，会引起数组元素的频繁挪动。例如，要做运算动。例如，要做运算A=A+B，即将矩阵，即将矩阵B加到矩阵加到矩阵A上，那么会产生大量的数据元素挪动。此时，采上，那么会产生大量的数据元素挪动。此时，采用十字链表构造将更恰当。用十字链表构造将更恰当。例如，有一个例如，有一个44稀疏矩阵稀疏矩阵A ,其所对其所对

25、应的十字链表如图应的十字链表如图5.6所示在十字链表所示在十字链表中，稀疏矩阵中的中，稀疏矩阵中的每一个非零元素可每一个非零元素可以用一个结点表示，以用一个结点表示，每一个结点中有五每一个结点中有五个域：行个域：行,列列, 值值, 下下指针指针,右指针右指针. 阐明：行阐明：行row,列列col,值值value，表示一个非零元素，下指针，表示一个非零元素，下指针(down)指向同一列中下一个非零元素，右指针指向同一列中下一个非零元素，右指针(right)指向指向同一行中下一个非零元素。稀疏矩阵中同一行的非零元素同一行中下一个非零元素。稀疏矩阵中同一行的非零元素由由right,链接成一个带有头结

26、点的行循环链表。同一列的非链接成一个带有头结点的行循环链表。同一列的非零元素由零元素由down，链接成一个带有头结点的列循环链表。因，链接成一个带有头结点的列循环链表。因此此,每个非零元素每个非零元素aij既是第既是第i行循环链表中的一个结点，又行循环链表中的一个结点，又是第是第j列循环链表中的一个结点。这样恰好构成一个十字，列循环链表中的一个结点。这样恰好构成一个十字，所以称为十字链表。结点的数据构造如下：所以称为十字链表。结点的数据构造如下： struct node int row,col,val； struct node *down,*right； ； typedef struct no

27、de NODE； 另外：在表示十字链表的表头结点中，另外：在表示十字链表的表头结点中，row、col和和value分别存放矩阵的行数、列数和非零元素个数；分别存放矩阵的行数、列数和非零元素个数；right和和down分别指向行分别指向行(列列)循环链表的表头结点循环链表的表头结点所构成的链表。在行所构成的链表。在行(列列)循环链表的表头结点中，循环链表的表头结点中，row、col和和value皆为皆为0，行循环链表的表头结点，行循环链表的表头结点right域指向该行的第一个非零元素的结点，而域指向该行的第一个非零元素的结点，而down域为域为NULL；列循环链表的表头结点；列循环链表的表头结点

28、down域域指向该列的第一个非零元素的结点，而指向该列的第一个非零元素的结点，而right域为域为NULL。 建立和输出十字链表的算法如下：建立和输出十字链表的算法如下： 算法算法5.9 建立十字链表算法建立十字链表算法 NODE * create() NODE *head,*new,*pre,*p,*row_p,*col_p; int i,count; head=(NODE *)malloc(sizeof(NODE); scanf(“%d,%d,%dn,&head-row,&head-col, &head-val);/* 读行列数读行列数,非零元素非零元素 */ /*接下页接下页 / /*

29、* 行头结点用行头结点用downdown域和表头结点组成循环链表域和表头结点组成循环链表 * */ / for(pre=head,i=0;irow;i+) for(pre=head,i=0;irow;i+) p=(NODE p=(NODE * *)malloc(sizeof(NODE); p-val=p-row=p-col=0;)malloc(sizeof(NODE); p-val=p-row=p-col=0; p-right=p; pre-down=p; pre=p; p-right=p; pre-down=p; pre=p; p-down=head; p-down=head; / /* *

30、 列头结点用列头结点用rightright域和表头结点组成循环链表域和表头结点组成循环链表 * */ / for(pre=head,i=0;icol;i+) for(pre=head,i=0;icol;i+) p=(NODE p=(NODE * *)malloc(sizeof(NODE); p-val=p-row=p-col=0;)malloc(sizeof(NODE); p-val=p-row=p-col=0; p-down=p; pre-right=p; pre=p; p-down=p; pre-right=p; pre=p; p-right=head; p-right=head; cou

31、nt=0; count=0; / /* *接下页接下页 while(countval) count+; new=(NODE *)malloc(sizeof(NODE); scanf(%d,%d,%dn,&new-row,&new-col,&new-val); /* 定位行头结点定位行头结点 */ for(row_p=head,i=0;irow;i+) row_p=row_p-down; p=row_p; /* 在循环行表中，定位插入位置在循环行表中，定位插入位置 */ while(p-right!=row_p & p-right-colcol) p=p-right; new-right=p-r

32、ight; p-right=new; /* 将将*new插入为插入为*p的后续的后续 */ /* 定位列头结点定位列头结点 */ for(col_p=head,i=0;icol;i+) col_p=col_p-right; p=col_p; /* 在循环列表中，定位插入位置在循环列表中，定位插入位置 */ while(p-down!=col_p & p-down-rowrow) p=p-down; new-down=p-down; p-down=new; /* 将将*new插入为插入为*p的后续的后续 */ return(head); 算法算法5.10 输出行主序的十字链表算法。输出行主序的十

33、字链表算法。 void print(NODE *head) /* 按行主序输出按行主序输出 */ NODE *row_p,*p; printf(%d,%d,%dn,head-row,head-col,head-val); row_p=head-down; while(row_p!=head) p=row_p; while(p-right!=row_p) p=p-right; printf(%d,%d,%dn,p-row,p-col,p-val); row_p=row_p-down; 5.4 广义表广义表 假设将线性表的定义推行，即不限制线性表中每一个元素假设将线性表的定义推行，即不限制线性表中

34、每一个元素都是一个结点，那么所得到的表就是一个广义表。都是一个结点，那么所得到的表就是一个广义表。 5.4.1 广义表定义广义表定义 广义表是广义表是n个元素的有限序列。广义表普通记作个元素的有限序列。广义表普通记作 LS=(d0,d1,dn-1)其中，其中，LS是广义表的称号，是广义表的称号，n为表长度。为表长度。di可为根本数据元素，可为根本数据元素，也可为广义表，分别称为广义表的单元素和子表。习惯上，用也可为广义表，分别称为广义表的单元素和子表。习惯上，用大写字母表示广义表的称号，用小写字母表示单元素。当广义大写字母表示广义表的称号，用小写字母表示单元素。当广义表非空时，称第一个元素表非

35、空时，称第一个元素d0为为LS表头表头(head)，其他元素组成的，其他元素组成的表表(d1,dn-1)为表尾为表尾(tail)。下面是几个广义表的实例。下面是几个广义表的实例。 实例：实例： (1) A=()，A是一个空广义表。是一个空广义表。 (2) B=(a,(b,c,d)，B包含两个元素，其中一个是单包含两个元素，其中一个是单元素元素a，另一个是子表，另一个是子表(b,c,d)。 (3) C=(e)，C只需一个单元素只需一个单元素e。(4) D=(A,B,C,f)，D包含四个元素，前三个是子表，包含四个元素，前三个是子表，第四个是单元素。第四个是单元素。(5) E=(a,E)，这是一个

36、递归表，包含两个元素，这是一个递归表，包含两个元素，一个是单元素一个是单元素a，另一个是子表，但该子表是其本，另一个是子表，但该子表是其本身。所以，身。所以，E相当于一个无限的广义表相当于一个无限的广义表 (a,(a,(a,)。 从上面的定义和实例中可知：从上面的定义和实例中可知： (1) 广义表的元素可以是子表，而子表中元素还广义表的元素可以是子表，而子表中元素还可以是个子表。可以是个子表。 (2) 一个广义表可以为其它所共享。一个广义表可以为其它所共享。 (3) 广义表可以是一个递归表。广义表可以是一个递归表。 另外，广义表的元素之间除了存在次序关系外，另外，广义表的元素之间除了存在次序关

37、系外，还存在层次关系，如图还存在层次关系，如图5.7表示了这种关系。在图表示了这种关系。在图中以圆圈表示广义表，方块表示单元素。中以圆圈表示广义表，方块表示单元素。图图5.7广义表的图形表示广义表的图形表示 运算：运算： 和线性表类似，可以对广义表的操作有查询、插和线性表类似，可以对广义表的操作有查询、插入和删除等。但广义表还有两个特殊的操作：取广义入和删除等。但广义表还有两个特殊的操作：取广义表的表头表的表头HEAD(LS)和取广义表的表尾和取广义表的表尾TAIL(LS)。 根据前面对表头和表尾的定义可知：任何一个非根据前面对表头和表尾的定义可知：任何一个非空广义表其表头可以是单元素，也可以

38、是子表，而其空广义表其表头可以是单元素，也可以是子表，而其表尾必定为一个广义表表尾必定为一个广义表(子表子表)。例如，广义表为前面。例如，广义表为前面所定义的所定义的A到到E表，表，HEAD和和TAIL运算有：运算有： HEAD(B)=a， TAIL(B)=(b,c,d), HEAD(C)=e， TAIL(C)=(), HEAD(D)=A， TAIL(D)=(B,C,f)，另外运算也可以嵌套，如：另外运算也可以嵌套，如： HEAD(TAIL(B)=b， TAIL(TAIL(B)=(c,d)。 5.4.2 广义表的存储构造广义表的存储构造 由于广义表中数据元素可以具有不同构造，通由于广义表中数据

39、元素可以具有不同构造，通常采用链表存储构造，每一个数据元素可用一个常采用链表存储构造，每一个数据元素可用一个结点结点(可以是子表或单元素可以是子表或单元素)。表示子表的表结点与。表示子表的表结点与表示单元素的数据元素结点之间是有差别的，以表示单元素的数据元素结点之间是有差别的，以下是一种常用的存储构造。下是一种常用的存储构造。 struct node /* 表结点表结点 */ int tag; /* =1标识子表结点标识子表结点 */ struct node *child； /* 指向该子表的指针指向该子表的指针 */ struct node *next； /* 指向下个元素的指针指向下个元素

40、的指针 */ ； struct node /* 数据元素结点数据元素结点 */ int tag; /* =0标识原子结点标识原子结点 */ int val； /* 值域值域 */ struct node *next； /* 指向下个元素的指针指向下个元素的指针 */ ； 实践存储构造：为了便于处置，将实践存储构造：为了便于处置，将val域和域和child域以结合的域以结合的方式存储，表结点和数据结点合二为一，方式存储，表结点和数据结点合二为一，C言语定义的广言语定义的广义表结点构造如下：义表结点构造如下： struct glnode int tag; /* =1标识子表结点，标识子表结点，=0

41、标识原子结点标识原子结点 */ union struct glnode *child； /* 表结点中的子表指针域表结点中的子表指针域 */ int val; /* 原子结点中的系数域原子结点中的系数域 */ content struct glnode *next； /* 指向下个元素的指针指向下个元素的指针 */ ； typedef struct glnode GLNode; 留意：在该构造中，留意：在该构造中，tag=1表示该结点是表结点，结合中表示该结点是表结点，结合中取取child域，而域，而tag=0表示该结点是数据结点，在结合中取表示该结点是数据结点，在结合中取val域。域。 上一节所举广义表例子，它们的存储构造如图上一节所举广义表例子，它们的存储