数据结构课件数组和广义表

数据结构课件数组和广义表第一页，共六十四页，编辑于2023年，星期三数组(array)是最常用的数据结构之一。几乎所有的程序设计语言都把数组类型设定为固有类型。数组的定义线性结构中的数据都是非结构的原子类型，元素的值是不再分解的。而数组可以看成是线性表在下述含义上的扩展：5.1数组的逻辑结构2数组的基本操作表中的数据元素本身也是一种数据结构。第二页，共六十四页，编辑于2023年，星期三数组是由下标和值组成的序对集合。在数组中，一旦给定下标，都存在一个与其相对应的值，这个值就称为数组元素。也可以说，数组中的每个数据元素都对应于一组下标（j1

,j2

,…,jn），每个下标取值范围是1≤ji≤bi，bi称为第i

维的长度（i=1,2,…,n）。显然，当n=1时，n维数组就退化为定长的线性表。反之，n

维数组也可以看成是线性表的推广。3 5.1.1数组的定义第三页，共六十四页，编辑于2023年，星期三

可以把二维数组看成是这样一个定长线性表：它的每个数据元素也是一个定长线性表。Am×n=a11a21…am1a12a22…am2a13a23…am3…………a1.na2,n…am,n4例如，下面是一个二维数组，且以m

行n

列的矩阵形式表示。第四页，共六十四页，编辑于2023年，星期三 每个数据元素α

j是一个列向量形式的线性表Am×n=…a1,na2,n…am,na13a23…am,3a12a22…am,2a11a21…am,1

二维数组A

还可以看成是一个线性表：A=(α1,α

2,…,α

n)

α

j=(a1j

,a2j

,…,am,j) 1≤j≤n 每个数据元素是一个行向量形式的线性表

B=(β1β2β3…,

βm)Am×n=((a11

a12

…a1,n

),…,(am,1am,2…am,n

))(a21

a22

…a2,n

),…,βi=(ai1,ai2,…,ai,n) 1≤i≤m5第五页，共六十四页，编辑于2023年，星期三数组一旦被定义，它的维数和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取数据元素和修改数据元素值的操作。6第六页，共六十四页，编辑于2023年，星期三 5.1.2数组的抽象类型定义ADTArray{

D={aj1j2j3…..jn|n>0,称为数组的维数,ji是数组的第i维下标,1≤ji

≤bi,

bi为数组第i维的长度，aj1j2j3…..jn∈ElementSet}数据关系：Ｒ

={R1,R2,…….Rn}Ri=<aj1…ji….jn,aj1…ji+1…jn>|1≤jk≤bk,1≤k≤n且k≠i,1≤ji

≤bi-1,aj1…j2….jn,aj1…ji+1…jn∈D,i=1,…n}基本操作:InitArray(A,n,bound1,…,boundn); 操作结果：如果维数n

和各维长度合法，则构造 相应的数组A，并且返回TRUE。第七页，共六十四页，编辑于2023年，星期三8 5.1.2数组的抽象类型定义DestroyArray(A):销毁数组A。GetValue(A,e,index1,…,indexn):初始条件：A

是n

维数组，e

为元素变量，随后是

n

个下标值。 操作结果：若各下标合法，则用e返回数组Ａ中由由index1,…indexn所指定的元素的值.SetValue(A,e,index1,…,indexn); 初始条件：A

是n

维数组，e

为元素变量，随后是

n

个下标值。 操作结果：若各下标合法，则将数组A中由index1,…indexn所指定的元素的值置为e.第八页，共六十四页，编辑于2023年，星期三由于内存储器的结构是一维的。一维数组可直接采用顺序存储。用一维的内存存储表示多维数组时，需按某种次序将数组中元素排成一线性序列，再将这个线性序列存放在一维的内存中，即数组的顺序存储结构表示。顺序存储的定位公式5.2数组的顺序存储结构9数组的顺序存储表示基本操作的算法描述第九页，共六十四页，编辑于2023年，星期三

用顺序存储结构来存储数组中的元素，一定要按照某种次序将元素排成一个线性序列。有两种存储方式：(1)以列为主序(columnmajororder)的存储方式，即按列优先，逐列顺序存储。(2)以行为主序(rowmajororder)的存储方式，即按行优先，逐行顺序存储。10 5.2.1顺序存储的定位公式第十页，共六十四页，编辑于2023年，星期三a21a11…am,1a22a12…am,2a1,n…a2,n…am,na21a11…am,1a21a11…Am,1a21a11…am,1a22a12…am,2a22a12…am,2a22a12…am,2………a1,na2,n…am,na1,na2,n…am,na1,na2,n…am

n11列主次序存放第十一页，共六十四页，编辑于2023年，星期三a12a11…a1.na22a21…a2,nam,1…am,2…am,na12a11…a1.na22a21…a2,n………am,1am,2…am,na12a11…a1,na12a11…a1,na22a21…a2,na22a21…a2,nam,1am,2…am,nam,1am,2…am,n12行主次序存放第十二页，共六十四页，编辑于2023年，星期三对于数组，一旦规定了它的维数和各维的长度，便可以为它分配存储空间。反之，只要给出一组下标，便可以求得相应数组的存储位置。13第十三页，共六十四页，编辑于2023年，星期三（１）一维数组的地址计算：设一维数组为：Ａ=(a1,a2,…,ai,…,an),数组中每个元素占size个存储单元，则元素ai的存储地址为：Loc(A[i])=Loc(A[1])+(i-1)*size。

数组的地址计算14第十四页，共六十四页，编辑于2023年，星期三

⑵二维数组的地址计算

假设每个数据元素占1

个存储单元，且以行序为主序的进行存储，则二维数组A

中任一元素aij

的存储位置可以由下面定位公式确定LOC(A[i],[j])=LOC(A[1],[1])+n*(i-1)+(j-1)其中：

LOC(A[i[,[j]) 是aij

的存储位置；

LOC(A[1],[1]) 是a11

的存储位置，即二维数组A

的起始存储位置，也称为基地址或基址；n 是数组第二维的长度。15

假设每个数据元素占size个存储单元，则二维数组A

中任一元素aij

的存储位置可以由下面定位公式确定LOC(A[i],[j])=LOC(A[1],[1])+(n*(i-1)+(j-1))*size第十五页，共六十四页，编辑于2023年，星期三

⑶三维数组的地址计算

三维数组A(1:r,1:m,1:n)。假设每个数据元素占size个存储单元，且以行序为主序的进行存储，首元素a111的地址为Loc(A[1][1][1]),求任意元素aijk的地址。

显然，ai11地址为

Ｌoc(A[i][1][1])=Loc(A[1][1][1])+(i-1)*m*n,因为在该元素之前有i-1个m*n的二维数组。16不难得到三维数组任意元素aijk的地址：Loc(A[i][j][k])=Loc(A[1][1][1])+((i-1)*m*n+(j-1)*n+(k-1))*size,其中：１≤i≤r,１≤j≤m,１≤k≤n。第十六页，共六十四页，编辑于2023年，星期三矩阵(matrix)是很多科学与工程计算问题中研究的数学对象。在数据结构中，我们感兴趣的不是矩阵本身，而是如何存储矩阵的元素而使矩阵的各种运算能够有效地进行。

特殊矩阵包括两个部份：①元素分布有特殊规律的矩阵,找到规律对应的公式，实现压缩存储。②非零元素很少的稀疏矩阵，可采用只存非零元素的方法实现压缩存储。5.3矩阵的压缩存储17第十七页，共六十四页，编辑于2023年，星期三特殊矩阵的压缩存储所谓压缩存储是指：为多个值相同的元素只分配一个存储空间；对零元不分配空间。18稀疏矩阵的逻辑结构稀疏矩阵的存储结构第十八页，共六十四页，编辑于2023年，星期三

假若相同的元素或者零元素在矩阵中的分布有一定规律，则称特殊矩阵。特殊矩阵主要有3种：对称矩阵、三角矩阵、带状矩阵。

在所有这些统称为“特殊矩阵”的矩阵中，非零元的分布都有一个明显的规律，从而都可以将其压缩存储到一维数组中，并且找到每个非零元在一维数组中的对应关系。19 5.3.1特殊矩阵的压缩存储第十九页，共六十四页，编辑于2023年，星期三

若一个n

阶矩阵M

中的元素满足下述性质1.对称矩阵aij=aji

1≤i，j≤n则称为n

阶对称矩阵。20第二十页，共六十四页，编辑于2023年，星期三

对于对称矩阵，可以为每一对对称元只分配一个存储空间，这样就可以将n2

个元压缩存储到n(n+1)/2个元的空间中。假设以行序为主序存储对称矩阵的下三角（包括对角线）中的元。以一维数组B[n(n+1)/2]作为n

阶对称矩阵M

的存储结构，21a31a22a21a11an,n…an,1…BLoc(A[i][j]=1234……

Loc(A[i][j])=Loc(A[1][1])+i*(i-1)/2+j-1(i>j)第二十一页，共六十四页，编辑于2023年，星期三

三角矩阵分为下三角矩阵和上三角矩阵。所谓下(上)三角矩阵是指矩阵的上(下)三角(不包括对角线)中的元均为常数c

或为零的n

阶矩阵。2.三角矩阵22下三角矩阵

三角矩阵除了和对称矩阵一样，只存储矩阵的下(上)三角中的元之外，再加上一个存储常数c

的存储空间即可。上三角矩阵第二十二页，共六十四页，编辑于2023年，星期三一个n

阶方阵，若它的全部非零元素落在一个以对角线为中心的带状区域中，则称该矩阵为带状矩阵，或对角矩阵。这个带状区域若包含主对角线上下各b

条对角线道上元素，那么，b

称为该带状矩阵的半带宽，或称该带状矩阵的带宽为(2b+1)。3.带状矩阵00b

条b

条23第二十三页，共六十四页，编辑于2023年，星期三在带状矩阵中，当|i-j|>b

时，aij=0。该方阵共有(2b+1)n-(b+1)b

个非零元素。a11D=a12a1300a21a22a23a240a31a32a33a34a350a42a43a44a4500a53a54a55

D

矩阵是一个5阶、半带宽为2的带状矩阵，在其主对角线a11、a22、a33、a44、a55上下各有2条对角线，共有(2b+1)n-(b+1)b=19个非零元素。24例如：第二十四页，共六十四页，编辑于2023年，星期三带状矩阵中最常见的是三对角带状矩阵。25特点：当i=1j=1,21<i<n,j=i-1,i,i+1

i=n,j=n-1,n

aij非零，其它元素均为零

a11Ann=a12０00a21a22a23０00a32a33a34０0０a43a44a4500………第二十五页，共六十四页，编辑于2023年，星期三

1.确定存储该矩阵所需的一维向量空间的大小除第一行和最后一行只有两个元素外，其余各行均有3个非零元素，由此得到一维向量所需的空间大小为：３n-2

2.确定非零元素在一维数组空间中的位置Ｌoc(a[i][j])=Loc(a[1][1])+2(i-1)+j-126

三对角带状矩阵的压缩存储，以行序为主序进行存储，且只存储非零元素。其方法为第二十六页，共六十四页，编辑于2023年，星期三27一般来说，当矩阵中非零元素的个数远远小于矩阵元素的总数时，称之为稀疏矩阵。假设在m×n

的矩阵中，若有t

个元素不为零，令=t/(m×n)，则称为矩阵的稀疏因子。通常认为≤25%-30%时称为稀疏矩阵。 5.3.2稀疏矩阵的逻辑结构1.稀疏矩阵的定义第二十七页，共六十四页，编辑于2023年，星期三按照压缩存储的概念，只存储稀疏矩阵的非零元素。因此，除了存储非零元素的值aij

之外，还必须同时记下非零元素所在矩阵的行i号和列j号。反之，一个三元组(i,j,aij)唯一确定了矩阵的一个非零元素。因此，稀疏矩阵可以由表示非零元的三元组及其矩阵的总的行列数唯一确定。假设以顺序存储结构表示三元组表，则可以得到稀疏矩阵的一种压缩存储方式，这种方式称之为三元组顺序表。28 5.3.3稀疏矩阵的存储结构1.三元组顺序表第二十八页，共六十四页，编辑于2023年，星期三012900000000000-3000014000240000018000001500-7000M=矩阵M

可以由三元组表(1,3,-3)，(1,6,15)，(2,1,12)，(2,5,18)，(3,1,9)，(3,4,24)，(4,6,-7)，(6,3,14)再加上（7,6）这一对总的行列值来描述。29第二十九页，共六十四页，编辑于2023年，星期三#defineMAXSIZE 1000//假设非零元个数的最大值为1000typedefstruct{ //三元组顺序表的元素结构定义int row,;col //该非零元的行下标和列下标

ElementTypee; //该非零元的值}Triple;typedefstruct{ //三元组顺序表存储结构定义Tripledata[MAXSIZE+1];//非零元三元组表，data[0]未用

int m,n,len; //矩阵的行数、列数和非零个数}TSMatrix; //三元组顺序表的类型名30(1)三元组顺序存储表示

在这里，data域中表示非零元的三元组是以行序为主序顺序排列的。第三十页，共六十四页，编辑于2023年，星期三012900000000000-3000014000240000018000001500-7000M=13-3161521122518319342446-76314rowcoleA.data[1]A.data[2]A.data[3]A.data[4]A.data[5]A.data[6]A.data[7]A.data[8](a)稀疏矩阵(b)三元组顺序表31第三十一页，共六十四页，编辑于2023年，星期三(2)利用三元组顺序表实现矩阵的转置运算 将矩阵的行列值相互交互；在这3点中，最关键的是第3条，即如何使B.data中的三元组以Ｔ的行（Ｍ的列）为主序依次排列。32显然，一个稀疏矩阵的转置矩阵仍是稀疏矩阵。假设A

和B

是TSMatrix（三元组顺序表）类型变量，分别表示矩阵Ｍ和其转置矩阵Ｔ。那么，只要做到下面3点就可以由A

得到B，实现矩阵的转置。 将每三元组中的row

和col

相互调换； 重排三元组之间的次序。第三十二页，共六十四页，编辑于2023年，星期三33原始的三元组表原矩阵012900000000000-3000014000240000018000001500-7000Ｍ=A.data[1]A.data[2]A.data[3]A.data[4]A.data[5]A.data[6]A.data[7]A.data[8]A.data13-3161521122518319342446-76314rowcole转置矩阵00-3001512000180900240000000-70000000014000000000Ｔ=转置的三元组表B.data[1]B.data[2]B.data[3]B.data[4]B.data[5]B.data[6]B.data[7]B.data[8]B.data121213931-3361443245218611564-7rowcole第三十三页，共六十四页，编辑于2023年，星期三使b.data中的三元组以T

的行（M

的列）为主序依次排列的方法有如下两种：34方法一：按照B.data中三元组的次序，依次在a.data中找到相应的三元组进行转置。方法二：按照A.data中三元组的次序进行转置，并将转置后的三元组置入B.data中恰当的位置。采用方法一第三十四页，共六十四页，编辑于2023年，星期三①算法思想在A中按三元组的列域值(col)开始扫描，依序将三元组A.data的列域值(col

)与行域值(row

)进行对换，并且存入B中。由于A是以M的行序为主序来存放每个非零元的，由此得到转置后矩阵的三元组表B恰是以“行序为主序”。35

按照方法一，即按照“被转置矩阵”M的三元组表A

的“列序”递增顺序进行转置。为了找到矩阵M

的每一列中所有的非零元素，需要对其三元组A.data从第一行起进行扫描，方法如下：第三十五页，共六十四页，编辑于2023年，星期三

转置的三元组表B->data原始的三元组表A.datar

c

v

1

2

12

1

3

9

3

1

-3

3

6

14

4

3

24

5

2

18

6

1

15

6

4

-736利用三元组顺序表存储实现矩阵的转置c

36151463r

11223346v

-3151218924-714

第三十六页，共六十四页，编辑于2023年，星期三voidTransposeTSMatrix(TSMatrixA,TSMatrix*B){//采用三元组表结构，求稀疏矩阵A

的转置矩阵B。在程序中，inti,j,k;//j

指示B->data中三元组的序号，//i

指示A.data中三元组的序号，//k指示A的列号（即B的行号）

B->m=A.n; //将稀疏矩阵A

的列数值作为其转置矩阵B

的行数值B->n=A.m; //将稀疏矩阵A

的行数值作为其转置矩阵B

的列数值B->len=A.len; //转置矩阵B与稀疏矩阵A的非零元个数相等②算法编(稀疏矩阵“列序”递增转置算法)

if(B->len>0){

j=1;37第三十七页，共六十四页，编辑于2023年，星期三for(k=1;k<=A.n;k++) for(i=1;i<=A.len;i++) if(A.data[i].col==k){ //进行转置

returnOK;}//TransposeSMatrix B->data[j].row=A.data[i].col; //稀疏矩阵A的列域值成为其转置矩阵B

的行域值 B->data[j].col=A.data[i].row; //稀疏矩阵A

的行域值成为其转置矩阵M

的列域值 B->data[j].e=A.data[i].e; //将稀疏矩阵M

的非零元值赋给其转置矩阵T

j++; //B->data中三元组的序号加1 }//if(A.data)结束}//if(B->len>0)结束38第三十八页，共六十四页，编辑于2023年，星期三③算法分析一般矩阵的转置算法（经典算法）为：39for(col=0;col<n;++col) for(row=0;row<m;++row)

dest[col][row]=source[row][col];时间复杂度为O(m×n)。

前面给出的求转置矩阵算法的主要工作是在i

和k的两重循环中完成的，所以此算法的时间复杂度为O(A.n×A.len)即和矩阵A

的列数和非零元的个数的乘积成正比。第三十九页，共六十四页，编辑于2023年，星期三40当矩阵M

中非零元个数几乎和矩阵元素个数相等时，即len

和m×n等数量级时，算法时间复杂度就为O(m×n2)，虽然节省了存储空间，但时间复杂度提高了。由此可见，上述求转置矩阵算法只适合于len<<m×n

的情况。第四十页，共六十四页，编辑于2023年，星期三当矩阵非零元素的位置或个数经常变动时，就不易采用顺序存储结构表示三元组的线性表。例如，在进行“将矩阵

B

加到矩阵A

上”的操作时，由于非零元素的插入或删除将会引起A.data中元素的大量移动。为此，对这种类型的矩阵，采用链式存储结构表示三元组的线性表更为恰当。412.十字链表第四十一页，共六十四页，编辑于2023年，星期三(1)稀疏矩阵的十字链表存储表示

矩阵中非零元的行号row；

矩阵中非零元的列号col；

矩阵中非零元的值e；

向右域right，用以链接同一行中下一个非零元；

向下域down，用以链接同一列中下一个非零元。42rowdowncolvalueright非零元行号非零元列号非零元的值向下域向右域在链表中，矩阵的非零元素可用如下结点表示：同一行的非零元通过right域链接成一个线性链表，同一列的非零元通过down域链接成一个线性链表，每个非零元Mij既是第i个行链表中的一个结点，又是第j个列链表中的一个结点，整个矩阵构成了一个十字交叉的链表，故称这样的存储结构为十字链表。第四十二页，共六十四页，编辑于2023年，星期三typedefstructOLNode{ //结点定义int row,col; //该非零元的行和列下标ElementTypevalue; //该非零元的值

structOLNode *right,*down;//该非零元所在的行表和列表的后继链域}OLNode;*Olink;typedefstruct{ //十字链表定义int m,n,len; //稀疏矩阵行数、列数和非零元个数Olink *row_head,*col_head;//行和列链表头指针向量，由CreateSMatrix分配}CrossList; //十字链表存储结构的类型名43将行链表的头指针存储在一维数组M.row_head中将列链表的头指针存储在一维数组M.col_head中第四十三页，共六十四页，编辑于2023年，星期三3020-10500000113145∧22-1∧312∧M.col_headM.row_head∧∧∧∧44第四十四页，共六十四页，编辑于2023年，星期三CreateSMatrix_OL(CrossList*M){//创建稀疏矩阵M。采用十字链表存储表示。(2)利用十字链表实现创建稀疏矩阵的运算if(!(M->row_head=(Olink*)malloc((m+1)*sizeof(Olink))))exit(OVERFLOW);if(!(M->col_head=(Olink*)malloc((n+1)*sizeof(Olink))))exit(OVERFLOW);if(M)free(M);scanf(&m,&n,&t); //输入M

的行数、列数和非零元个数

M->m=m;M->n=n;M->len=t;45①算法编写第四十五页，共六十四页，编辑于2023年，星期三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; //生成新结点的值域46M->row_head[]=NULL;//初始化行头指针向量；令各行链表为空链表M->col_head[]=NULL;//初始化列头指针向量；令各列链表为空链表第四十六页，共六十四页，编辑于2023年，星期三if(M->row_head[i]==NULL){M->row_head[i]=p;p->right=NULL;}else{for(q=M->row_head[i];(q->right)&&q->right->col<j; q=q->right); p->right=q->right;q->right=p;}//完成行插入elseif(M->row_head[i]->col>j){//寻找在行表中的插入位置 p->right=M->row_head[i];M->row_head[i]=p;}47第四十七页，共六十四页，编辑于2023年，星期三if(M->col_head[j]==NULL){ M_col_head[j]=p;p->down=NULL;}else{for(q=M->col_head[j];(q->down)&&q->down->row<i; q=q->down); p->down=q->down;q->down=p;}//完成列插入elseif(M->col_head[j]->row>i){//寻找在列表中的插入位置p->down=M->row_head[j];M->col_head[j]=p;}}//for结束

returnOK;}//CreateSMatrix_OL48第四十八页，共六十四页，编辑于2023年，星期三∧∧∧∧∧∧∧M->col_headM->row_head(1)输入(1,1,3)1∧13∧p(2)输入(1,3,5)p135q∧(3)输入(1,4,9)∧149pq∧∧(4)输入(3,1,2)312∧p∧q49(5)输入(2,3,4)234q∧∧(6)输入(2,2,8)q创建稀疏矩阵M

的十字链表if(M.rhead[i]==NULL){M.rhead[i]=p;p->right=NULL;}for(q=M->col_head[i];(q->down)&&q->down->row<i; q=q->down);p->down=q->down;q->down=p;if(M->row_head[i]->j>j){p->right=M->row_head[i];M->row_head[i]=p;}if(M->col_head[j]==NULL){M->col_head[j]=p;p->down=NULL;}pq∧p228if(M->col_head[j]==NULL){M->col_head[j]=p;p->down=NULL;}for(q=M->row_head[i];(q->right)&&q->right->col<j; q=q->right);p->right=q->right;q->right=p;if(M->col_head[j]==NULL){M->col_head[j]=p;p->down=NULL;}for(q=M->row_head[i];(q->right)&&q->right->col<j; q=q->right);p->right=q->right;q->right=p;if(M->col_head[j]==NULL){M->col_head[j]=p;p->down=NULL;}if(M->row_head[i]==NULL){M->row_head[i]=p;p->right=NULL;}for(q=M->col_head[i];(q->down)&&q->down->row<i; q=q->down);p->down=q->down;q->down=p;if(M->row_head[i]==NULL){M->row_head[i]=p;p->right=NULL;}第四十九页，共六十四页，编辑于2023年，星期三对于一个m

行n

列，并且有t

个非零元的稀疏矩阵，CreateSMatrix_OL算法执行时间为O(t×s)，其中s=max{m,n}。这是因为：每建立一个非零元的结点时都需要寻查它在行表和列表中的插入位置，此算法对非零元输入的先后次序没有任何要求。反之，若按以行序为主序的次序依次输入三元组，即可以将建立十字链表表示的算法改写成O(t)数量级的（t

为非零元个数）的算法。②算法分析50第五十页，共六十四页，编辑于2023年，星期三广义表(generalizedlist)是线性表的推广，有时也称为列表（lists，用复数形式以示与统称的表list的区别）。广泛地应用于人工智能等领域的LISP（表处理语言），把广义表作为基本的数据结构，就连程序也表示为一系列的广义表。515.4广义表第五十一页，共六十四页，编辑于2023年，星期三广义表的逻辑结构和数组一样，广义表也可以看成是线性表在下述含义上的扩展：表中的数据元素本身也是一种数据结构。52广义表的存储结构第五十二页，共六十四页，编辑于2023年，星期三53 5.4.1广义表的逻辑结构广义表一般记作：GL=(a1,a2,…,an)其中：

n

是广义表GL

的长度；

ai 可以是单个元素，也可以是广义表，分别称为广义表GL

的原子和子表，习惯上用大写字母表示广义表的名称，用小写字母表示原子的名称。GL

是广义表(a1,a2,…,an)的名称；1.广义表的定义第五十三页，共六十四页，编辑于2023年，星期三54当广义表GL为非空时，称第一个元素a1

为GL的表头（head），其余元素组成的表(a2,a3,…,an)是GL的表尾（tail）。显然，广义表的定义是一个递归的定义，因为在描述广义表时又用到了广义表的概念。第五十四页，共六十四页，编辑于2023年，星期三

例5-1

A=()，A

是一个空表，它的长度为零。

例5-2

B=(e)，B

只有一个原子e，它的长度为1。

例5-3

C=(a,(b,c,d))，C

的长度为2，两个元素分别为原子a

和子表(b,c,d)。

例5-4

D=(A,B,C)，D

的长度为3，三个元素分别为A、B和C，都是广义表。显然，将上面所述三个子表的值代入以后，则有D=((),(e),(a,(b,c,d)))。

例5-5

E=(a,E)，这是一个递归表，它的长度为2，E相当于一个无限的广义表E=(a,(a,(a,…)))。552.广义表的三个重要结论第五十五页，共六十四页，编辑于2023年，星期三从上述定义和例子推出如下广义表的三个重要结论(1)广义表的元素可以是子表，而子表的元素还可以是子表，…。由此，广义表是一个多层次结构。(2)广义表可以为其他广义表所共享。例如在上述例子中，广义表A、B

和C

为D

的子表，则在D

中可以不必列出广义表的值，而是通过子表的名称引用。(3)广义表可以是一个递归表，即广义表也可以是其本身的一个子表。例如广义表E

就是一个递归的表。56第五十六页，共六十四页，编辑于2023年，星期三ecdbaBACD表示广义表表示原子57第五十七页，共六十四页，编辑于2023年，星期三

和线性表相类似，