广义表
1 广义表的定义
2 广义表的基本运算
3 广义表的存储结构
1 广义表 的定义一、广义表定义广义表可定义为：数据元素可以是表的线性表。
记为,LS＝ (d1,d2,…,dn)
LS为表名，
di (i＝ 1,2,…,n),可以是 单元素 (称为 原子,用小写字母表示 )，也可以是 广义表 (称为 子表,用大写字母表示 )；
若广义表 LS非空，则必有 n大于 0（即 n > 0）
n为表的长度，当长度为 0时称为 空表 ；
称非空表的第一个元素 d1为 表头,
其余元素组成的 表 (d2,…,dn)称为 表尾 。
注意,表尾可以可以是空表，而表头可以是原子，也可以是一个表 。
广义表的抽象类型定义采用递归定义如教材 P.107。
二,广义表的表达方式及例子
1,A=( ) A是一个空表，其长度为 0。
2,B=(e) 列表 B只有一个原子 e,其长度为 1。
3,C=(a,(b,c,d)) 列表 C的长度为 2，表头为原子，
第二个元素是一个列表 (b,c,d)。
4,D=(A,B,C) 列表 D的长度为 3，
表头也是一个列表 A,表尾是列表（ A,B）,
注意,这里引用了已有的列表 A,B,C作为该广义表 D的元素。
5,E=(a,E) 这是一个递归列表，其元素中有自己。
广义表也可以用图形表示，例如前述的广义表 D和 E可表示为：
b
e a
c d
a
D
A B C
广义表 D
E
广义表 E
2 广义表 的 基本运算广义表的基本运算
⑴ 取表头 HEAD(LS)；
⑵ 取表尾 TAIL(LS)。
3 广义表的 存储结构广义表中的数据元素可以是单元素，或是广义表,很难用顺序存储结构表示，常采用链式存储结构。
1.表头表尾链 存储结构有两类结点：表结点和单元素结点。 ┌───┬────┬───┐
│ tag=1 │ hp │ tp │ 表结点└───┴────┴───┘
┌───┬────────┐
│ tag=0 │ data │ 单元素结点└───┴────────┘
tag标志域,0表示结点为单元素结点,1表示为表结点；
hp,表头指针域； tp,表尾指针域； data,值域。
3 广义表的 存储结构形式描述为：
typedef enum{ ATOM,LIST }ElemTag
typedef struct GLNode { //定义广义表结点
ElemTage tag; //公共部分，用以区分原子结点和表结点
Union{ //原子结点和表结点的联合部分
AtomType atom;//原子类型结点域，
// AtomType由用户定义
Struct { struct GLNode *hp,*tp; }ptr; };
//表结点的指针域，
//ptr.hp 与 ptr.tp分别指向广义表的表头和表尾。
}*Glist; //广义表类型
3 广义表的 存储结构这种存储结构的特点是：
最上层的表结点数即为广义表的长度；
层次清楚；
表结点数目多，与广义表中括号对的数目不匹配。
例,C=(a,(b,c,d))
1 1
1 1 10 a
0 b 0 c 0 d
＾
＾
((b,c,d))
(b,c,d) (c,d) (d)
C
3 广义表的 存储结构
2,同层结点链存储结构有两类结点：表结点和单元素结点。
┌────┬───┬───┐
│ tag=1 │ hp │ tp │ 表结点└────┴───┴───┘
┌────┬───┬───┐
│ tag=0 │ data │ tp │ 单元素结点└────┴───┴───┘
结点结构 是无论什么结点都有三个域：
第一个域是结点类型标志 tag；
第二个域是指向一个列表的指针（当 tag=1时）
或一个原子（当 tag=0时）；
第三个域是指向下一个结点的指针 tp。
3 广义表的 存储结构形式描述为：
typedef enum{ ATOM,LIST }ElemTag
typedef struct GLNode { //定义广义表结点
ElemTage tag; //公共部分，用以区分原子结点和表结点
Unin{ //原子结点和表结点的联合部分
AtomType atom;//原子类型结点域，
// AtomType由用户定义
struct GLNode *hp,; //表结点的表头指针域
};
struct GLNode *tp;
//指向下一个结点的指针
}*Glist; //广义表类型
3 广义表的 存储结构同层结点链结构的特点是：
表结点的数目与广义表的括号对数目一致；
写递归算法不方便。
例,C=(a,(b,c,d))
1C ＾
0 a 1 ＾
0 b 0 c 0 d ＾
(b,c,d)
应用,M元多项式的表示对任何一个 M元多项式 P,先确定一个主变元，于是它可看成主变元的一元多项式，但它的系数可能是一个多项式，也可能是一个常数。于是 P可表为一个线性表
P=((α 1,expn1),(α 2,expn2),…,( α n,expnn))
其中每个 α i可能是一个常数，也可能又是一个多项式；对于每一个多项式 α j,又可以确定一个主变元（可称为原多项式的第二变元），从而，可表为下一级的一元多项式，其系数又可能性是常数，也可能是多项式； … ；直到最后纯粹的一元多项式。
所以 M元多项式，最好用广义表来表示。其元素结点如下图：
表结点（多项式结点） 原子结点（常系数结点）
tag=1 exp hp tp tag=0 exp coef tp
其形式定义如下：
typedef struct MPNode{
ElemTag tag; //区分原子结点和表结点
int expn; //指数域
union { //原子结点和表结点共享一个域
float coef; //系数域
struct MPNode *hp; //表结点的表头指针
}
struct MPNode *tp; //指向下一个元素结点
}*MPList; //M元多项广义表类型
M元多项式的表示例,P(x,y,z)=
x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15
=(x10y3+2x6y3+3x5y2)z2 +(x4y4+6x3y4+2y)z+15
=((x10+2x6)y3+3x5y2)z2 +((x4+6x3)y4+2y)z+15
=Az2+Bz+15z0
其中,A=Cy3+Dy2 C=x10+2x6 D=3x5
可用广义表表示为,
P(x,y,z)=z((A,2),(B,1),(15,0))
A=y((C,3),(D,2)) B=y((E,4),(2,1))
C=x((1,10),(2,6)) E=x((1,4),(6,3))
D=x((3,5))
M元多项式的表示存储表示
(1) 结点结构 表结点单元素结点
(2) 用一维数组存储多项式的所有变元
(3) 每一层增设一个表头结点,并用 exp域表明变元在数组中的下标
(4) 增设一个表头结点,表示整个表,用头指针 p指示,
并在 exp域填上变元个数
tag=1 exp hp tp
tag=0 exp coef tp
前例,P(x,y,z)=z((A,2),(B,1),(15,0))
A=y((c,3),(D,2)) C=x((1,10),(2,6))P
1 1
1 3 ＾
1 2 1 1 0 0 15 ＾
1 2 1 3 1 2
0 10 1 0 6 2 1 3 ＾
＾
D
z y x
BA
C
三类表结点 (tag=1):整个表的头结点一个,exp域为变元数,层头结点 (每层一个 ),exp域为相应变元在数组中的下标,一般表结点,exp域为指数。
1 广义表的定义
2 广义表的基本运算
3 广义表的存储结构
1 广义表 的定义一、广义表定义广义表可定义为：数据元素可以是表的线性表。
记为,LS＝ (d1,d2,…,dn)
LS为表名，
di (i＝ 1,2,…,n),可以是 单元素 (称为 原子,用小写字母表示 )，也可以是 广义表 (称为 子表,用大写字母表示 )；
若广义表 LS非空，则必有 n大于 0（即 n > 0）
n为表的长度，当长度为 0时称为 空表 ；
称非空表的第一个元素 d1为 表头,
其余元素组成的 表 (d2,…,dn)称为 表尾 。
注意,表尾可以可以是空表，而表头可以是原子，也可以是一个表 。
广义表的抽象类型定义采用递归定义如教材 P.107。
二,广义表的表达方式及例子
1,A=( ) A是一个空表，其长度为 0。
2,B=(e) 列表 B只有一个原子 e,其长度为 1。
3,C=(a,(b,c,d)) 列表 C的长度为 2，表头为原子，
第二个元素是一个列表 (b,c,d)。
4,D=(A,B,C) 列表 D的长度为 3，
表头也是一个列表 A,表尾是列表（ A,B）,
注意,这里引用了已有的列表 A,B,C作为该广义表 D的元素。
5,E=(a,E) 这是一个递归列表，其元素中有自己。
广义表也可以用图形表示，例如前述的广义表 D和 E可表示为：
b
e a
c d
a
D
A B C
广义表 D
E
广义表 E
2 广义表 的 基本运算广义表的基本运算
⑴ 取表头 HEAD(LS)；
⑵ 取表尾 TAIL(LS)。
3 广义表的 存储结构广义表中的数据元素可以是单元素，或是广义表,很难用顺序存储结构表示，常采用链式存储结构。
1.表头表尾链 存储结构有两类结点：表结点和单元素结点。 ┌───┬────┬───┐
│ tag=1 │ hp │ tp │ 表结点└───┴────┴───┘
┌───┬────────┐
│ tag=0 │ data │ 单元素结点└───┴────────┘
tag标志域,0表示结点为单元素结点,1表示为表结点；
hp,表头指针域； tp,表尾指针域； data,值域。
3 广义表的 存储结构形式描述为：
typedef enum{ ATOM,LIST }ElemTag
typedef struct GLNode { //定义广义表结点
ElemTage tag; //公共部分，用以区分原子结点和表结点
Union{ //原子结点和表结点的联合部分
AtomType atom;//原子类型结点域，
// AtomType由用户定义
Struct { struct GLNode *hp,*tp; }ptr; };
//表结点的指针域，
//ptr.hp 与 ptr.tp分别指向广义表的表头和表尾。
}*Glist; //广义表类型
3 广义表的 存储结构这种存储结构的特点是：
最上层的表结点数即为广义表的长度；
层次清楚；
表结点数目多，与广义表中括号对的数目不匹配。
例,C=(a,(b,c,d))
1 1
1 1 10 a
0 b 0 c 0 d
＾
＾
((b,c,d))
(b,c,d) (c,d) (d)
C
3 广义表的 存储结构
2,同层结点链存储结构有两类结点：表结点和单元素结点。
┌────┬───┬───┐
│ tag=1 │ hp │ tp │ 表结点└────┴───┴───┘
┌────┬───┬───┐
│ tag=0 │ data │ tp │ 单元素结点└────┴───┴───┘
结点结构 是无论什么结点都有三个域：
第一个域是结点类型标志 tag；
第二个域是指向一个列表的指针（当 tag=1时）
或一个原子（当 tag=0时）；
第三个域是指向下一个结点的指针 tp。
3 广义表的 存储结构形式描述为：
typedef enum{ ATOM,LIST }ElemTag
typedef struct GLNode { //定义广义表结点
ElemTage tag; //公共部分，用以区分原子结点和表结点
Unin{ //原子结点和表结点的联合部分
AtomType atom;//原子类型结点域，
// AtomType由用户定义
struct GLNode *hp,; //表结点的表头指针域
};
struct GLNode *tp;
//指向下一个结点的指针
}*Glist; //广义表类型
3 广义表的 存储结构同层结点链结构的特点是：
表结点的数目与广义表的括号对数目一致；
写递归算法不方便。
例,C=(a,(b,c,d))
1C ＾
0 a 1 ＾
0 b 0 c 0 d ＾
(b,c,d)
应用,M元多项式的表示对任何一个 M元多项式 P,先确定一个主变元，于是它可看成主变元的一元多项式，但它的系数可能是一个多项式，也可能是一个常数。于是 P可表为一个线性表
P=((α 1,expn1),(α 2,expn2),…,( α n,expnn))
其中每个 α i可能是一个常数，也可能又是一个多项式；对于每一个多项式 α j,又可以确定一个主变元（可称为原多项式的第二变元），从而，可表为下一级的一元多项式，其系数又可能性是常数，也可能是多项式； … ；直到最后纯粹的一元多项式。
所以 M元多项式，最好用广义表来表示。其元素结点如下图：
表结点（多项式结点） 原子结点（常系数结点）
tag=1 exp hp tp tag=0 exp coef tp
其形式定义如下：
typedef struct MPNode{
ElemTag tag; //区分原子结点和表结点
int expn; //指数域
union { //原子结点和表结点共享一个域
float coef; //系数域
struct MPNode *hp; //表结点的表头指针
}
struct MPNode *tp; //指向下一个元素结点
}*MPList; //M元多项广义表类型
M元多项式的表示例,P(x,y,z)=
x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15
=(x10y3+2x6y3+3x5y2)z2 +(x4y4+6x3y4+2y)z+15
=((x10+2x6)y3+3x5y2)z2 +((x4+6x3)y4+2y)z+15
=Az2+Bz+15z0
其中,A=Cy3+Dy2 C=x10+2x6 D=3x5
可用广义表表示为,
P(x,y,z)=z((A,2),(B,1),(15,0))
A=y((C,3),(D,2)) B=y((E,4),(2,1))
C=x((1,10),(2,6)) E=x((1,4),(6,3))
D=x((3,5))
M元多项式的表示存储表示
(1) 结点结构 表结点单元素结点
(2) 用一维数组存储多项式的所有变元
(3) 每一层增设一个表头结点,并用 exp域表明变元在数组中的下标
(4) 增设一个表头结点,表示整个表,用头指针 p指示,
并在 exp域填上变元个数
tag=1 exp hp tp
tag=0 exp coef tp
前例,P(x,y,z)=z((A,2),(B,1),(15,0))
A=y((c,3),(D,2)) C=x((1,10),(2,6))P
1 1
1 3 ＾
1 2 1 1 0 0 15 ＾
1 2 1 3 1 2
0 10 1 0 6 2 1 3 ＾
＾
D
z y x
BA
C
三类表结点 (tag=1):整个表的头结点一个,exp域为变元数,层头结点 (每层一个 ),exp域为相应变元在数组中的下标,一般表结点,exp域为指数。
