第五章 数组和广义表
5.1 数组的定义
5.2 数组的顺序表示和实现
5.3 矩阵的压缩存储
一维数组具有线性表的结构，但操作简单，一般不进行插入和删除操作，只定义给定下标读取元素和修改元素的操作
二维数组中，每个数据元素对应一对数组下标，在行方向上和列方向上都存在一个线性关系，即存在两个前驱（前件）和两个后继（后件）。也可看作是以线性表为数据元素的线性表。
n维数组中，每个数据元素对应 n个下标，受 n个关系的制约，其中任一个关系都是线性关系。可看作是数据元素为 n-1维数组的一维数组。
因此，多维数组和广义表是对线性表的扩展：线性表中的数据元素本身又是一个多层次的线性表。
对于多维数组,有两种存储方式：
一是以行为主序 （ 或先行后列 ） 的顺序存放,如
BASIC,PASCAL,C等程序设计语言中用的是以行为主的顺序分配,即一行分配完了接着分配下一行 。
另一种是以列为主序（先列后行）的顺序存放，
如 FORTRAN语言中，用的是以列为主序的分配顺序，
即一列一列地分配。
不论按何种方式存储，只要确定了数组的首地址以及每个数组元素所占用的单元数，就可以将数组元素的存储地址表示为其下标的线性函数。设有 m× n二维数组
Amn，以,以行为主序,的分配为例，按照元素的下标确定其地址的计算方法如下。
设数组的基址为 LOC(a11),每个数组元素占据 L个地址单元,计算 aij的物理地址的函数为：
LOC(aij) = LOC(a11) + ( (i-1)*n + j-1 ) * L
同理,对于三维数组 Amnp,即 m× n× p数组,对于数组元素 aijk其物理地址为：
LOC(aijk)=LOC(a111)+( ( i-1) *n*p+ (j-1)*p +k-1) )*L
注意：
在 C语言中,数组中每一维的下界定 义为 0,则：
LOC(aij) = LOC(a00) + ( i*n + j ) * L
5.1 数组的定义
ADT Array{
数据对象 D:
具有相同类型的数据元素构成的有序集合。
数据关系 R:
对于 n维数组，其每一个元素均位于 n
个向量中，每个元素最多具有 n个前驱结点和 n个后继结点。
基本操作：
InitArray(&A,n,index1,…,indexn)
新建一个 n维数组 A,其每维的大小由 index1,index2,……,indexn确定 。
DestroyArray(&A)
销毁数组 A,收回其占用的空间 。
Value(A,&x,index1,…,indexn)
取出 A[index1][index2]…… [indexn]数组元素的值存入变量 x中 。
Assign(&A,e,index1,…,indexn)
将表达式 e的值赋给数组元素 A[index1][index2]…… [indexn]
}ADT Array
5.2 数组的顺序表示
多维数组用一维的存储单元存放需约定次序。
PASCAL和 C语言是以行序为主序,FORTRAN以列序为主序。
给定维数和各维长度，数组的存储空间确定。
二维数组中任一元素 aij的存储地址,
Loc(i,j)=Loc(0,0)+(b2*i+j)*L
n维数组：教材 p93
Loc（ j1,j2,…,jn)=Loc(0,0,…,0)+ ∑ciji
其中 cn=L,ci-1=bi*ci,1<i≤n
类型定义
#include <stdarg.h>
#define MAX_ARRAY_DIM 8 //数组维数最大值
typedef struct{
ElemType *base; //数组元素基址
int dim; //数组维数
int *bounds; //数组维界基址
int *constants; //数组映象函数常量基址
}Array;
5.3 矩阵的压缩存储
矩阵一般可用二维数组实现，特殊矩阵采用压缩存储。
压缩存储：为多个值相同的元只分配一个存储空间，
对零元不分配空间。
特殊矩阵：值相同的元素或者零元素在矩阵中的分布有一定规律
稀疏矩阵：非零元较零元少，且分布没有一定规律的矩阵
5.3.1,特殊矩阵
对称矩阵,aij=aji 1≤i,j≤n
压缩存储方法：为每一对对称元分配一个存储空间
将下三角的元素，按行存储到一维数组 sa中
共有 n(n+1)/2个存储单元，
aij在一维数组中的位置 k为,i(i-1)/2+j-1 当 i>=j 否则 j(j-1)/2+i-1
三角矩阵,上（下）三角中的元均为常数 c或 0
压缩存储方法：同上，只存储上（下）三角元素。
下三角,k=i*(i-1)/2+j-1
上三角,k=(2n-i)(i-1)/2+j-1 (按行 )
k=j(j-1)/2+i-1 （按列）
注意,k从零开始,i,j从 1开始
对角矩阵：所有非零元都集中在以主对角线为中心的带状区域中。
压缩方法：压缩存储到一维数组 sa[ ]中，三对角矩阵有 3n-2个元素。
k=2*i+j-3
5.3.2,稀疏矩阵
1,三元组的表示
稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。
t个非零元,t/(m*n)称为稀疏因子 <0.05
用三元组 (i,j,aij)存储行和列的位置，及非零元数值。
0000015
00390170
000000
0006022
2800000
0000110
0910000
B
00002800
00000091
03900000
0006000
017000110
150022000
A
6776
（ 1）稀疏矩阵 (Sparse Matrix)
行数 m = 6,列数 n = 7,非零元素个数 t = 6
0000015
00390170
000000
0006022
2800000
0000110
0910000
B
00002800
00000091
03900000
0006000
017000110
150022000
A
67
76
稀疏矩阵转置矩阵用三元组表表示的稀疏矩阵及其转置行行
(( rr oo ww ))
列列
(( cc oo ll ))
值值
(( vv aa ll uu ee ))
行行
(( rr oo ww ))
列列
(( cc oo ll ))
值值
(( vv aa ll uu ee ))
[0] 11 44 22 22 [0] 11 55 99 11
[1] 11 77 11 55 [1] 22 22 11 11
[2] 22 22 11 11 [2] 33 66 22 88
[3] 22 66 11 77 [3] 44 11 22 22
[4] 33 44 -- 66 [4] 44 33 -- 66
[5] 44 66 33 99 [5] 66 22 11 77
[6] 55 11 99 11 [6] 66 44 33 99
[7] 66 33 22 88 [7] 77 11 11 66
（ 2） 三元组顺序表
#define MAXSIZE 12500 //非零元个数最大值
typedef struct {
int i,j; //行下标和列下标
ElemType e;
} Triple;
typedef struct{
Triple data[MAXSIZE+1]; //非零元三元组表
int mu,nu,tu; //行数、列数、非零元个数
}TSMatrix;
TSMatrix a,b;
(3)三元组表稀疏矩阵的转置运算
方法：按照 b.data中的三元组的次序，
即 M的列序，依次在 a.data中找到相应的三元组进行转置。
步骤：从 k=1开始依 次扫描找寻所有列号为 k的项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。
其时间复杂度为 O ( a.nu* a.tu )。
例：若矩阵有 200行,200列,10,000个非零元素，总共有 2,000,000次处理。
稀疏矩阵的转置 (算法 5.1)
Status TransposeSMatrix(TSMatrix M,TSMatrix &T)
{ int q,col,p;
T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;
if (T.tu)
{ q=1;
for (col=1;col<=T.mu;++col)
for(p=1;p<=M.tu;++p)
if (M.data[p].j==col)
{ T.data[q].i=M.data[p].j;
T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e;
++q;
}
}
return OK;
}
快速转置算法
方法：按 a.data中三元组的次序进行转置，并将转置后的三元组置入 b中恰当的位置。
建立辅助数组 num和 cpot,num[col]表示矩阵第 col列中非零元的个数,cpot[col]指示第 col列的第一个非零元素在
b.data中的恰当位置。
显然有,cpot[1]=1
cpot[col]=cpot[col-1]+num[col-1]
按行扫描矩阵三元组表，根据某项的列号，确定它转置后的行号，查 cpot表，按查到的位置直接将该项存入转置三元组表中。
转置时间复杂度为 O(nu+tu+nu+tu)=O(tu)。若矩阵有 200
列,10000个非零元素，总共需 10000次处理。
稀疏矩阵的快速转置
Status FastTransposeSMatrix(TSMatrix M,TSMatrix &T)
{ T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;
if (T.tu)
{ for (col=1;col<=M.nu;++col) num[col]=0;
for (t=1;t<=M.tu;++t) ++num[M.data[t].j];
cpot[1]=1;
for (col=2;col<=M.nu;++col)
cpot[col]=cpot[col-1]+num[col-1];
for (p=1;p<=M.tu;++p)
{ col=M.data[p].j; q=cpot[col];
T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e; ++cpot[col];
}
}
return OK;
}
2,十字链表
当矩阵中非零元素的 个数 和 位置 经过运算后 变化较大 时，就不宜采用顺序存储结构，而应采用 链式存储结构 来表示三元组。
稀疏矩阵的链接表示采用十字链表,行链表 与 列链表 十字交叉。
行链表与列链表都是 带表头结点的循环链表 。用表头结点表征是第几行，第几列。
元素结点
right—— 指向同一行中下一个非零元素的指针（向右域）
down—— 指向同一列中下一个非零元素的指针（向下域）
表头结点
行表头结点
列表头结点
next用于表示头结点的链接
row col val
down right
col=0 next
right
row=0 next
down
由于行、列表头结点互相不冲突，所以可以合并起来：
总表头结点：
row=0 col=0 next
down right
row col next
稀疏矩阵的十字链表表示的示例
需要辅助结点作链表的表头，同时每个结点要增加两个指针域，所以只有在矩阵较大和较稀疏时才能起到节省空间的效果。
分别用两个一维数组存储行链表的头指针和列链表的头指针，可加快访问速度。
十字链表的类型定义
typedef struct OLNode{ //元素结点
int i,j; //非零元的行和列下标
ElemType e;
struct OLNode *right,*down;
//该非零元所在行表和列表的后继链域
} OLNode,*OLink;
typedef struct {
OLink *rhead,*chead;
//行和列链表头指针数组
int mu,nu,tu;
} CrossList;
广义表 (Lists，又称列表 )是线性表的推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。
1、广义表定义广义表是 n(n≥0)个元素 a1,a2,…,ai,…,an的有限序列。
其中：
① ai--或者是原子或者是一个广义表。
②广义表通常记作：
Ls=( a1,a2,…,ai,…,an)。
③ Ls是广义表的名字,n为它的长度。
④若 ai是广义表，则称它为 Ls的子表。
注意：
①广义表通常用圆括号括起来，用逗号分隔其中的元素。
②为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。
③若广义表 Ls非空 (n≥1)，则 al是 LS的表头，其余元素组成的表 (a2,…,
an)称为 Ls的表尾。
④广义表是递归定义的。
5.4 广义表
2、广义表表示
（ 1）广义表常用表示
① E=() E是一个空表，其长度为 0。
② L=(a,b)
L是长度为 2的广义表，它的两个元素都是原子，因此它是一个线性表
③ A=(x,L)=(x,(a,b))
A是长度为 2的广义表，第一个元素是原子 x，第二个元素是子表 L。
④ B=(A,y)=((x,(a,b)),y)
B是长度为 2的广义表，第一个元素是子表 A，第二个元素是原子 y。
⑤ C=(A,B)=((x,(a,b)),((x,(a,b)),y))
C的长度为 2，两个元素都是子表。
⑥ D=(a,D)=(a,(a,(a,(…))))
D的长度为 2，第一个元素是原子，第二个元素是 D自身，
展开后它是一个无限的广义表。
（ 2）广义表的深度一个表的 "深度 "是指表展开后所含括号的层数。
【 例 】 表 L,A,B,C的深度为分别为 1,2,3,4，表 D的深度为 ∞。
（ 3）带名字的广义表表示如果规定任何表都是有名字的，为了既表明每个表的名字，
又说明它的组成，则可以在每个表的前面冠以该表的名字，于是上例中的各表又可以写成：
① E()
② L(a,b)
③ A(x,L(a,b))
④ B(A(x,L(a,b)),y)
⑤ C(A(x,l(a,b)),B(A(x,L(a,b)),y))
⑥ D(a,D(a,D(…)))
广义表的存储结构广义表的头尾链表存储表示
typedef emnu{ATOM,LIST} ElemTag;
// ATOM==0:原子,LIST==1:子表
typedef struct GLNode
{
ElemTag tag;
union{
AtomType atom;//原子结点的值域
struct{struct GLNode *hp,*tp;}ptr;
//ptr是表结点的指针域,ptr.hp和 ptr.tp分别指向表头和表尾
}
}
5.1 数组的定义
5.2 数组的顺序表示和实现
5.3 矩阵的压缩存储
一维数组具有线性表的结构，但操作简单，一般不进行插入和删除操作，只定义给定下标读取元素和修改元素的操作
二维数组中，每个数据元素对应一对数组下标，在行方向上和列方向上都存在一个线性关系，即存在两个前驱（前件）和两个后继（后件）。也可看作是以线性表为数据元素的线性表。
n维数组中，每个数据元素对应 n个下标，受 n个关系的制约，其中任一个关系都是线性关系。可看作是数据元素为 n-1维数组的一维数组。
因此，多维数组和广义表是对线性表的扩展：线性表中的数据元素本身又是一个多层次的线性表。
对于多维数组,有两种存储方式：
一是以行为主序 （ 或先行后列 ） 的顺序存放,如
BASIC,PASCAL,C等程序设计语言中用的是以行为主的顺序分配,即一行分配完了接着分配下一行 。
另一种是以列为主序（先列后行）的顺序存放，
如 FORTRAN语言中，用的是以列为主序的分配顺序，
即一列一列地分配。
不论按何种方式存储，只要确定了数组的首地址以及每个数组元素所占用的单元数，就可以将数组元素的存储地址表示为其下标的线性函数。设有 m× n二维数组
Amn，以,以行为主序,的分配为例，按照元素的下标确定其地址的计算方法如下。
设数组的基址为 LOC(a11),每个数组元素占据 L个地址单元,计算 aij的物理地址的函数为：
LOC(aij) = LOC(a11) + ( (i-1)*n + j-1 ) * L
同理,对于三维数组 Amnp,即 m× n× p数组,对于数组元素 aijk其物理地址为：
LOC(aijk)=LOC(a111)+( ( i-1) *n*p+ (j-1)*p +k-1) )*L
注意：
在 C语言中,数组中每一维的下界定 义为 0,则：
LOC(aij) = LOC(a00) + ( i*n + j ) * L
5.1 数组的定义
ADT Array{
数据对象 D:
具有相同类型的数据元素构成的有序集合。
数据关系 R:
对于 n维数组，其每一个元素均位于 n
个向量中，每个元素最多具有 n个前驱结点和 n个后继结点。
基本操作：
InitArray(&A,n,index1,…,indexn)
新建一个 n维数组 A,其每维的大小由 index1,index2,……,indexn确定 。
DestroyArray(&A)
销毁数组 A,收回其占用的空间 。
Value(A,&x,index1,…,indexn)
取出 A[index1][index2]…… [indexn]数组元素的值存入变量 x中 。
Assign(&A,e,index1,…,indexn)
将表达式 e的值赋给数组元素 A[index1][index2]…… [indexn]
}ADT Array
5.2 数组的顺序表示
多维数组用一维的存储单元存放需约定次序。
PASCAL和 C语言是以行序为主序,FORTRAN以列序为主序。
给定维数和各维长度，数组的存储空间确定。
二维数组中任一元素 aij的存储地址,
Loc(i,j)=Loc(0,0)+(b2*i+j)*L
n维数组：教材 p93
Loc（ j1,j2,…,jn)=Loc(0,0,…,0)+ ∑ciji
其中 cn=L,ci-1=bi*ci,1<i≤n
类型定义
#include <stdarg.h>
#define MAX_ARRAY_DIM 8 //数组维数最大值
typedef struct{
ElemType *base; //数组元素基址
int dim; //数组维数
int *bounds; //数组维界基址
int *constants; //数组映象函数常量基址
}Array;
5.3 矩阵的压缩存储
矩阵一般可用二维数组实现，特殊矩阵采用压缩存储。
压缩存储：为多个值相同的元只分配一个存储空间，
对零元不分配空间。
特殊矩阵：值相同的元素或者零元素在矩阵中的分布有一定规律
稀疏矩阵：非零元较零元少，且分布没有一定规律的矩阵
5.3.1,特殊矩阵
对称矩阵,aij=aji 1≤i,j≤n
压缩存储方法：为每一对对称元分配一个存储空间
将下三角的元素，按行存储到一维数组 sa中
共有 n(n+1)/2个存储单元，
aij在一维数组中的位置 k为,i(i-1)/2+j-1 当 i>=j 否则 j(j-1)/2+i-1
三角矩阵,上（下）三角中的元均为常数 c或 0
压缩存储方法：同上，只存储上（下）三角元素。
下三角,k=i*(i-1)/2+j-1
上三角,k=(2n-i)(i-1)/2+j-1 (按行 )
k=j(j-1)/2+i-1 （按列）
注意,k从零开始,i,j从 1开始
对角矩阵：所有非零元都集中在以主对角线为中心的带状区域中。
压缩方法：压缩存储到一维数组 sa[ ]中，三对角矩阵有 3n-2个元素。
k=2*i+j-3
5.3.2,稀疏矩阵
1,三元组的表示
稀疏矩阵可由表示非零元的三元组及其行列数唯一确定。
t个非零元,t/(m*n)称为稀疏因子 <0.05
用三元组 (i,j,aij)存储行和列的位置，及非零元数值。
0000015
00390170
000000
0006022
2800000
0000110
0910000
B
00002800
00000091
03900000
0006000
017000110
150022000
A
6776
（ 1）稀疏矩阵 (Sparse Matrix)
行数 m = 6,列数 n = 7,非零元素个数 t = 6
0000015
00390170
000000
0006022
2800000
0000110
0910000
B
00002800
00000091
03900000
0006000
017000110
150022000
A
67
76
稀疏矩阵转置矩阵用三元组表表示的稀疏矩阵及其转置行行
(( rr oo ww ))
列列
(( cc oo ll ))
值值
(( vv aa ll uu ee ))
行行
(( rr oo ww ))
列列
(( cc oo ll ))
值值
(( vv aa ll uu ee ))
[0] 11 44 22 22 [0] 11 55 99 11
[1] 11 77 11 55 [1] 22 22 11 11
[2] 22 22 11 11 [2] 33 66 22 88
[3] 22 66 11 77 [3] 44 11 22 22
[4] 33 44 -- 66 [4] 44 33 -- 66
[5] 44 66 33 99 [5] 66 22 11 77
[6] 55 11 99 11 [6] 66 44 33 99
[7] 66 33 22 88 [7] 77 11 11 66
（ 2） 三元组顺序表
#define MAXSIZE 12500 //非零元个数最大值
typedef struct {
int i,j; //行下标和列下标
ElemType e;
} Triple;
typedef struct{
Triple data[MAXSIZE+1]; //非零元三元组表
int mu,nu,tu; //行数、列数、非零元个数
}TSMatrix;
TSMatrix a,b;
(3)三元组表稀疏矩阵的转置运算
方法：按照 b.data中的三元组的次序，
即 M的列序，依次在 a.data中找到相应的三元组进行转置。
步骤：从 k=1开始依 次扫描找寻所有列号为 k的项，将其行号变列号、列号变行号，顺次存于转置矩阵三元组表。
其时间复杂度为 O ( a.nu* a.tu )。
例：若矩阵有 200行,200列,10,000个非零元素，总共有 2,000,000次处理。
稀疏矩阵的转置 (算法 5.1)
Status TransposeSMatrix(TSMatrix M,TSMatrix &T)
{ int q,col,p;
T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;
if (T.tu)
{ q=1;
for (col=1;col<=T.mu;++col)
for(p=1;p<=M.tu;++p)
if (M.data[p].j==col)
{ T.data[q].i=M.data[p].j;
T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e;
++q;
}
}
return OK;
}
快速转置算法
方法：按 a.data中三元组的次序进行转置，并将转置后的三元组置入 b中恰当的位置。
建立辅助数组 num和 cpot,num[col]表示矩阵第 col列中非零元的个数,cpot[col]指示第 col列的第一个非零元素在
b.data中的恰当位置。
显然有,cpot[1]=1
cpot[col]=cpot[col-1]+num[col-1]
按行扫描矩阵三元组表，根据某项的列号，确定它转置后的行号，查 cpot表，按查到的位置直接将该项存入转置三元组表中。
转置时间复杂度为 O(nu+tu+nu+tu)=O(tu)。若矩阵有 200
列,10000个非零元素，总共需 10000次处理。
稀疏矩阵的快速转置
Status FastTransposeSMatrix(TSMatrix M,TSMatrix &T)
{ T.mu=M.nu; T.nu=M.mu; T.tu=M.tu;
if (T.tu)
{ for (col=1;col<=M.nu;++col) num[col]=0;
for (t=1;t<=M.tu;++t) ++num[M.data[t].j];
cpot[1]=1;
for (col=2;col<=M.nu;++col)
cpot[col]=cpot[col-1]+num[col-1];
for (p=1;p<=M.tu;++p)
{ col=M.data[p].j; q=cpot[col];
T.data[q].i=M.data[p].j; T.data[q].j=M.data[p].i;
T.data[q].e=M.data[p].e; ++cpot[col];
}
}
return OK;
}
2,十字链表
当矩阵中非零元素的 个数 和 位置 经过运算后 变化较大 时，就不宜采用顺序存储结构，而应采用 链式存储结构 来表示三元组。
稀疏矩阵的链接表示采用十字链表,行链表 与 列链表 十字交叉。
行链表与列链表都是 带表头结点的循环链表 。用表头结点表征是第几行，第几列。
元素结点
right—— 指向同一行中下一个非零元素的指针（向右域）
down—— 指向同一列中下一个非零元素的指针（向下域）
表头结点
行表头结点
列表头结点
next用于表示头结点的链接
row col val
down right
col=0 next
right
row=0 next
down
由于行、列表头结点互相不冲突，所以可以合并起来：
总表头结点：
row=0 col=0 next
down right
row col next
稀疏矩阵的十字链表表示的示例
需要辅助结点作链表的表头，同时每个结点要增加两个指针域，所以只有在矩阵较大和较稀疏时才能起到节省空间的效果。
分别用两个一维数组存储行链表的头指针和列链表的头指针，可加快访问速度。
十字链表的类型定义
typedef struct OLNode{ //元素结点
int i,j; //非零元的行和列下标
ElemType e;
struct OLNode *right,*down;
//该非零元所在行表和列表的后继链域
} OLNode,*OLink;
typedef struct {
OLink *rhead,*chead;
//行和列链表头指针数组
int mu,nu,tu;
} CrossList;
广义表 (Lists，又称列表 )是线性表的推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。
1、广义表定义广义表是 n(n≥0)个元素 a1,a2,…,ai,…,an的有限序列。
其中：
① ai--或者是原子或者是一个广义表。
②广义表通常记作：
Ls=( a1,a2,…,ai,…,an)。
③ Ls是广义表的名字,n为它的长度。
④若 ai是广义表，则称它为 Ls的子表。
注意：
①广义表通常用圆括号括起来，用逗号分隔其中的元素。
②为了区分原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。
③若广义表 Ls非空 (n≥1)，则 al是 LS的表头，其余元素组成的表 (a2,…,
an)称为 Ls的表尾。
④广义表是递归定义的。
5.4 广义表
2、广义表表示
（ 1）广义表常用表示
① E=() E是一个空表，其长度为 0。
② L=(a,b)
L是长度为 2的广义表，它的两个元素都是原子，因此它是一个线性表
③ A=(x,L)=(x,(a,b))
A是长度为 2的广义表，第一个元素是原子 x，第二个元素是子表 L。
④ B=(A,y)=((x,(a,b)),y)
B是长度为 2的广义表，第一个元素是子表 A，第二个元素是原子 y。
⑤ C=(A,B)=((x,(a,b)),((x,(a,b)),y))
C的长度为 2，两个元素都是子表。
⑥ D=(a,D)=(a,(a,(a,(…))))
D的长度为 2，第一个元素是原子，第二个元素是 D自身，
展开后它是一个无限的广义表。
（ 2）广义表的深度一个表的 "深度 "是指表展开后所含括号的层数。
【 例 】 表 L,A,B,C的深度为分别为 1,2,3,4，表 D的深度为 ∞。
（ 3）带名字的广义表表示如果规定任何表都是有名字的，为了既表明每个表的名字，
又说明它的组成，则可以在每个表的前面冠以该表的名字，于是上例中的各表又可以写成：
① E()
② L(a,b)
③ A(x,L(a,b))
④ B(A(x,L(a,b)),y)
⑤ C(A(x,l(a,b)),B(A(x,L(a,b)),y))
⑥ D(a,D(a,D(…)))
广义表的存储结构广义表的头尾链表存储表示
typedef emnu{ATOM,LIST} ElemTag;
// ATOM==0:原子,LIST==1:子表
typedef struct GLNode
{
ElemTag tag;
union{
AtomType atom;//原子结点的值域
struct{struct GLNode *hp,*tp;}ptr;
//ptr是表结点的指针域,ptr.hp和 ptr.tp分别指向表头和表尾
}
}
