1
第七章 广义表
2
§ 7.1 广义表的逻辑结构
?广义表是一个二元组
Lists=(D,R)
其中,
D={di | i=1,2,…,n; n≥0; di∈ D0或属于某广义表,
D0是数据对象 }
R={LR}
LR={<di-1,di> | di∈ D,1≤i≤n}
§ 7.1.1 基本概念
3
§ 7.1.1 基本概念
?通常, 广义表记为 （ 称为 广义表表达式 ）,
Ls=(α1,α2,…,αn)
其中, 每个 αi或为数据对象成员, 或为 （ 广义 ）
表 。
?例如,
L = ((a,b),c,(d,(e)) )
4
相关概念
?子表,若某广义表 L的某元素结点 a本身也是一个广义表,
则称该元素对应的广义表为广义表 L的子表 。
?长度,我们仍然称 Ls中的元素个数 （ 即 αi的个数, 不计 αi
内部的元素个数 ） 为广义表 Ls的 长度, 它与线性表的长
度的概念是相同的 。
?单元素, 单元素表,若数据元素为非表元素 （ 即简单元
素, 如基本数据类型, 结构 /记录等 ）, 则称其为 单元素；
若 Ls中的元素均为 单元素, 则称其为 单元素表 。
?空表,表内无元素（长度为 0）的表称为空表。
5
相关概念 (续 )
?表头,称 Ls的第 1个元素为 Ls的表头 。
?表尾,称 Ls中除去表头后其余元素构成的表为表尾 。
显然, 表尾一定是表, 但表头不一定 。
?深度,Ls的深度 Depth(Ls)递归地定义为：
0,若 Ls为单元素
Depth(Ls) = 1,若 Ls为空表
1 + MAXi(Depth(αi)),其它情况
?从定义知, 广义表的深度, 相当于广义表表达式中括号的最大嵌套
层数 。
6
相关概念 (续 )
?层,我们将元素的深度值称做该元素的 层号, 层号相同者称为 同层
结点 。
?系列广义表,由于广义表的元素往往也是广义表, 所以需要一同考
虑 。 我们称可追塑到同属于某一广义表的所有广义表为一个广义表
系列 （ 或系列广义表 ） 。
?递归表,若表 Ls中某成员含有自己 (即 Ls),则称 Ls为递归表 。
?下面的叙述中, 我们用大写字母表示具体的广义表, 用小写字母代
表数据对象的成员 （ 单元素 ） 。 在同一个广义表系列中, 相同字母
表示同一对象 。
7
广义表例子
① A=( )：空表, 无头, 尾为空表, 长度为 0,深度为 1.
② B=(a,b,c)：单元素表, 头为 a,尾为 (b,c),长度为 3,深度为 1.
③ C=(a,(b,c,d) )：非单元素表, 头为 a,尾为 ((b,c,d)),长度为 2，
深度为 2.
④ D=(B,((a,b),c ) )：非单元素表, 头为 B,尾为 ( ((a,b),c)) ),长度为
2,深度为 3.
⑤ E=(a,E)：非单元素, 头为 a,尾为 (E),长度为 2,深度为 ∞
?事实上, E=(a,E) = (a,(a (,… ) ) )是个递归表 。
?有时, 为了强调广义表名称, 可将表名写在表的左括号前面, 如上
例中的 D 可写为：
D( B(a,b,c),F( G(a,b),c) )
8
§ 7.1.2 基本特性
?宏观线性性,对任意广义表, 若不考虑它的元素的内部结构, 则它
是一个线性表, 即它的直接元素之间是线性关系 。
?元素递归性,广义表的任一元素, 又可以是一个广义表 （ 其它广义
表或自身 ） 。 这种递归性使得广义表具有强有力的表达能力, 这是
广义表最重要的特性 。
?元素共享性,在同一广义表系列中, 任一元素 （ 单元素或表 ） 均可
以出现多次, 同一元素的多次出现都代表的是同一个目标, 可以认
为它们是共享同一目标, 具有该特性的表也称再入表 。
9
§ 7.1.3 基本操作
? 线性表的基本运算
? 求深度
? 求表头
? 求表尾
? 求成员
? 串行化
10
§ 7.2 广义表的存贮结构
? 具有较高的复杂性，因此一般只采用链式存贮
结构
? 分枝单链表法 ── 一种通用的存贮结构
§ 7.2.1 基本存储方法
11
分枝单链表存贮方法
(a) 为每个 αi设置一个结点 Hi,称其为 αi的头结点, 其结构为：
?tag：指示 αi是单元素还是广义表 (我们设 tag为 0时表示 αi为单元素 ） 。
?pElem：若 αi为单元素, 则指向 αi的内容, 否则指向 αi对应的广义表
(可以用第一个头结点 H1的指针代表广义表 ).
?next：单链表链指针, 即指向 Hi+1。
tag … pElem next
12
分枝单链表存贮方法
(b) αi为单元素时, αi的内容应对应一片连续区域, 可在
它中设置一个长度字段 。
(c) 直接元素构成的单链表, 根据具体问题的需要, 可以
是带头结点的, 或循环式的, 或双向链式的或这些的组
合 。
(d)如果不共享单元素内容, 且单元素内容的长度相等
（ 或差别不大 ）, 则可将单元素内容直接放到元素头结
点中 。
13
广义表存储结构示例
(a) B=(a,b,c)
0
a
0 0 ^
b c
B
0 1 ^
0 0 0 ^
b c d
(b) C=(a,(b,c,d) )
C
a
14
广义表存储结构示例
(c) D=(B,((a,b),c) )
0 ^
1 1 ^
1B
0 0 ^
a b
D 0 1
a
(d) E=(a,E)
15
广义表 C++描述
template <class TElem>
class TGListNode
{
char tag;
char name[CNST_SizeListNodeName];
TGListNode *next;
union
{
TElem *pElem;
TGListNode *pSub;
};
};
共享存储区
16
成员的含义
tag：广义表元素结点种类标志, 它表明对应结点是单元素
(0)还是表 (1)。
name：结点名称 。 当结点是表时, 也是该结点所对应的
（ 广义 ） 表的名称 。
next：指向同层中下个结点 。
pElem：指向结点对应的元素内容 。
pSub：指向结点对应的子表 （ 的头 ） 。
17
§ 7.3 广义表对象模型
? 将广义表作为一种抽象对象，建立它的访问接
口。
? 将访问接口分为两部分：
– 广义表结点接口
– 广义表接口
18
§ 7.3.1 广义表结点接口
template <class TElem>
struct TGListNode0
{
virtual GetNumSubNodes ( ) = 0; //返回本结点的子表中的元素个数
virtual char IsList ( ) = 0;
//若本结点是非单元素结点, 则返回假 （ 0）, 否则返回真 （ 1）
virtual TElem *GetElem ( ) = 0;
//返回本结点对应的元素的内容 （ 的地址 ） 。 若本结点为子表, 则返回
空
virtual TElem *SetElem (TElem *pe) = 0; //为本元素结点设置内容
19
virtual TGListNode0 *GetNext ( ) =0;
//返回本结点代表的元素的后继元素所对应的结点
virtual SetNext (TGListNode0 *p) = 0；
//为本结点代表的元素设置后继结点
virtual TGlistNode0 *GetSub (void ) = 0;
//返回本元素对应的子表的头结点
virtual TGlistNode0 *SetSub (TGListNode0 *pNode) = 0;
//为本元素设置子表 （ 用子表的头结点表示子表 ）
};
20
TGListNode0的派生类,TGListNode
template <class TElem>
class TGListNode, public TGListNode0<TElem>
{
char tag;
char name[CNST_SizeListNodeName];
TGListNode *next;
union
{
TElem *pElem;
TGListNode *pSub;
//下面是 TGListNode0中定义的成员函数的原形
… …
};
21
§ 7.3.2 广义表接口
template <class TElem>
class TGList0
{
public:
long GetLen ( ) =0; //返回本表的长度
long GetDepth(void)=0; //返回本表的深度
virtual TGList0<TElem> *GetList(TGListNode0<TElem> *pNode)=0;
//返回结点 pNode所对应的子表对象指针 。 若 pNode无相应的对象, 则返回
空, 并触发异常 。
22
virtual TGListNode0<TElem> *GetHead(void)=0;
//返回本表的的头所对应的结点的指针
virtual TGListNode0<TElem> *GetTail(void)=0;
//返回本表的尾所对应的结点的指针
virtual TElem &GetElem(longidx)=0;//返回本表中序号为 idx的元素的内容
virtual TGListNode0<TElem> &GetElemNode(longidx)=0;
//返回本表中序号为 idx的元素所对应的结点的地址
virtual TGlistNode0 *GetSub(TGListNode0<TElem> *pNode,ong idx)=0;
//返回结点 pNode对应的子表中的序号为 idx的结点 。 若无子表, 或无序号
为 idx的子表, 则返回空
virtual long GetFathers(TGListNode0<TElem> *pNode,
TGListNode0<TElem> **father)=0;
//结点 pNode的各父结点的指针存入 father数组中
23
virtual TGListNode0<TElem> *GetFirstFather(TGListNode0<TElem>
*pNode)=0; //返回结点 pNode对应的父结点中的第一个结点
virtual TGListNode0<TElem> *GetNextFather(TGListNode0<TElem>
*pNode)=0; //返回结点 p对应的父结点中的下一个结点
virtual long IsMenber(TGListNode0<TElem> *p)=0;
//检查结点 p是否是本结点 （ 对象本身 ） 的成员 。 若是, 则返回 p的层号 （ 相
对与本结点 ）, 否则返回 0
virtual long Locate(TElem &elem,TGList0<TElem> **pNodes)=0;
//在本表中查找值为 elem的结点, 将它们的地址存入数组 pNodes。 返回值为 elem的结
点的的数目
24
virtual long Cluster(TGListNode0<TElem>* pNode,
TElem **e,TTraverseMode tm)=0;
//串行化 （ 聚集 ） 操作 。 按遍历方式 tm,将结点 pNode的各子表中的结点的值的地址,
存入数组 e中, 返回数组中元素的个数 。
例如, 对广义表
L=(a,(c,(a,b),d),(e,(f)) )
深度优先 （ 前序 ） 串行化结果为：
a,c,a,b,d,e,f
返回值为 7
virtual long Cluster(TGListNode0<TElem>* pNode,
TGListNode0<TElem> **pe,TTraverseMode tm)=0;
//串行化 （ 聚集 ） 操作 。 按遍历方式 tm,将结点 pNode的各子表中的结点的
地址, 存入数组 pe中, 返回数组中元素的个数
25
virtual long ClusterJuniors(TGListNode0<TElem>* pNode,
TGListNode0<TElem> **pe,TTraverseMode travMode=PreOrder,
int startLevel=1,int endLevel=-1)=0;
//按遍历方式 travMode,将结点 pNode对应的子表中的, 层号 （ 相对于
pNode） 在 startLevel和 endLevel之间的结点的地址, 存入数组 pe,返回数组
中元素个数
virtual long ClusterSeniors(TGListNode0<TElem>* pNode,
TGListNode0<TElem> **pe,TTraverseMode travMode=PreOrder,
int startLevel=1,int endLevel=-1)=0;
//按遍历方式 travMode,将结点 pNode对应的子表中的, 层号在 startLevel和
endLevel之间的结点的地址, 存入数组 pe,返回数组中元素个数 。 这里,
pNode的层号为 1,pNode的父结点层号为 2,余类推
26
TGListNode *InsertNode(TGListNode *p,long sn)=0;
//在本表中的第 sn个结点之前插入结点 p。 返回被插入结点的地址 。 sn可正可
负, 具体含义同上
TGListNode *DeleteNode(longsn1,long sn2)=0;
//在对应结点的子表中删除其第 sn个结点, 并将其地址返回 。 sn含义同上
};
27
§ 7.4 广义表的分枝单链表对象
template <class TElem>
class TGListNode,public TGListNode0<TElem>
{
char tag;
char name[CNST_SizeListNodeName];
long numSubs;
TGListNode *next;
union
{
TElem *pElem;
TGListNode *pSub;
};
§ 7.4.1 结点对象
28
public:
TGListNode();
~TGListNode();
virtual GetNumSubNodes(){return numSubs;};
virtual char IsList() {return tag};
virtual TElem *GetElem() {return pElem;};
virtual TElem *SetElem(TElem *pe) {pElem = pe; return pElem;};
virtual TGListNode0 *GetNext() {return next;};
virtual TGListNode0 *SetNext(TGListNode0 *pNode) {next =
pNode;return next;};
virtual TGlistNode0 *GetSub(void) {return pSub;};
virtual TGlistNode0 *SetSub(TGListNode0 *pNode) {pSub =
pNode;return pSub;};
};
29
§ 7.4.2 分枝单链表对象
? 为分枝单链表设立一个总头结点（类型仍然为 TGListNode），令
它的 pSub指向广义表分枝单链表中的第一个元素对应的结点。
图 - 带总头结点的广义表分枝
单链表
d
0 1 ^
0 0 0 ^
b c
1 ^C
a
30
template <class TElem>
class TGList,public TGList0
{
TGListNode<TElem> *head;
public:
//下面是在 TGList0中定义的函数的声明 （ 不含, =0”部
分 ） 。
};
31
§ 7.5 广义表操作的实现
GetDepth()
GetFather()类
Locate()
Cluster()类
IsMenber(TGListNode *p)
InsertNode()
DeleteNode()
有一个重要问题需注意：循环问题
§ 7.5.1 一般问题
32
§ 7.5.2 遍历操作
? 以深度优先遍历操作说明广义表的遍历的实现
longTGList::Cluster(TGListNode *p,TElem **pE)
{
static long k=0;
long cnt=0;
if (p==NULL) return 0;
if (p->tag==0) return 0;
q = p->pSub;
33
while (q!=NULL)
{
if (q未被访问 )
{
置 q已访问标志；
if(q->tag == 0)
pE[k++]=q->pElem;
else
q.Cluster(q,pE);
}
q = q->next;
} //while
return k;
}
34
§ 7.5.3 广义表统计计数
? 统计计数操作有求深度、求层号、满足指定条件的结点个数等。
下面以广义表求深度操作说明 。
longTGListNode::Depth(TGListNode *p)
{
long h=0,mh=0;
if (p==NULL) return 0;
if (p->tag==0) return 0;
q = p->pSub;
35
while (q!=NULL)
{
if (q已被访问 )
return -1; //遇到循环, 深度为无穷大
else
{
置 q已访问标志；
h=Depth(q);
if (h > mh) mh = h;
}
q = q->next;
} //while
return 1+mh;
}
36
§ 7.6 广义表结构的应用
? 广义表最适合描述递归结构和分层结构，如分
层索引结构（如图书的目录、计算机操作系统
中的文件目录结构）及其它一些多叉树形结构
37
§ 7.6.1 多元多项式的表示
?多元多项式具有多个变元,
?例如下面是一个三元多项式
P(x1,x2,x3)=x15x23x3+2x15x22x34+5x15x23x33+3x1x24x32+x2x3+100
? 如果仿照一元多项式的结构，即令多项式每项对应一个结点，结点应含
一个系数域和 m个（ m为未知数个数）指数域。但这种表示法有下列几个方
面的缺陷：
– ①结点的结构随多项式的变数元数目而变化，这造成了概念上的不美观，
缺少通用性；
– ②不适合某些应用要求的操作的实现
? 最适合使用广义表结构
38
?对任意一个 m元多项式，都可以任选一个变元（称为第 1变元或主变
元），按此变元合并同类项，使该 m元多项式变为如下形式：
?这里,en>en-1>…>e 1,Ai为关于变元 x2…x m的 (m-1)元多项式，
i=1,2,…n
?下步可对 Ai选 x2为主变元进行类似的处理，如此进行，最后一回选
xm为主变元对各个以 xm-1为主变元的多项式进行同样的处理。
?例如, 对前面给出的 P3(x1,x2,x3)处理如下：
P(x1,x2,x3)=x15x23x3+2x15x22x34+5x15x23x33+3x1x24x32+x2x3+100
= (x23x3+2x22x34+5x23x33) x15 + (3x24x32) x1 + (x2x3+100)
=( (5x33+ x3) x23+(2x34) x22) x15 + (3x24x32) x1 + (x2x3+100)
11 111111,..)...( eenenmm xAxAxAxxp nn ???? ??
39
?将上式中每一项用一个如下形式的二元组表示：
（ 系数, 指数 ）
其中,,系数, 可能是一个多元多项式，也可能是基本元素。并且将
各二元组按指数降序排列，则所成结构为广义表，这就是 m元多项式
的广义表表示。
40
?对上式有：
P=((A3,5),(A2,1),(A1,0) ) //以 x1为主变量
A3=( (A32,3),(A31,2) ) //以 x2为主变量 A3=( 5x33+ x3) x23+(2x34) x22
A2=((A21,4)) //以 x2为主变量 A2 = (3 x32 )x24
A1=((A11,1),(100,0)) //以 x2为主变量 A1=x2x3
A32=((5,3),(1,1)) //以 x3为主变量 A32=5x33+ x3
A31=((2,4)) //以 x3为主变量 A31=2x34
A21=((3,2)) //以 x3为主变量 A21= 3x32
A11=((1,1)) //以 x3为主变量 A11=x3
P(x1,x2,x3)=x15x23x3+2x15x22x34+5x15x23x33+3x1x24x32+x2x3+100
= (x23x3+2x22x34+5x23x33) x15 + (3x24x32) x1 + (x2x3+100)
=( (5x33+ x3) x23+(2x34) x22) x15 + (3x24x32) x1 + (x2x3+100)
41
习 题 7
1,对下列广义表系列, 分别求出它们的长度, 深度, 头, 尾, 并画
出存贮结构图 （ 同名元素或表共享, 小写字母为单元素 ）
① A=((a,b),(a,c))
② c=((A,a),(b,c))
③ D=((a,(b,a)),A)
④ E=(E,a,b)
42
2。 请通过 GetHead()和 GetTail()操作, 将下列各表中的 apple分离出来 。
A1 = (banana,pear,orange)
A2 = ((apple,pear),orange)
A2 = (pear,(peach,(plum,apple),fig),apple,date)
3,给出一个 3元多项式
P(x1,x2,x3)=10x15x22x3+2x15x2x3+3x15+x12x22x3+x12x2x3+x22x3+10
写出它的广义表表达式 （ 逻辑表示 ）, 并画出相应的分枝单链表存
贮结构图 。
第七章 广义表
2
§ 7.1 广义表的逻辑结构
?广义表是一个二元组
Lists=(D,R)
其中,
D={di | i=1,2,…,n; n≥0; di∈ D0或属于某广义表,
D0是数据对象 }
R={LR}
LR={<di-1,di> | di∈ D,1≤i≤n}
§ 7.1.1 基本概念
3
§ 7.1.1 基本概念
?通常, 广义表记为 （ 称为 广义表表达式 ）,
Ls=(α1,α2,…,αn)
其中, 每个 αi或为数据对象成员, 或为 （ 广义 ）
表 。
?例如,
L = ((a,b),c,(d,(e)) )
4
相关概念
?子表,若某广义表 L的某元素结点 a本身也是一个广义表,
则称该元素对应的广义表为广义表 L的子表 。
?长度,我们仍然称 Ls中的元素个数 （ 即 αi的个数, 不计 αi
内部的元素个数 ） 为广义表 Ls的 长度, 它与线性表的长
度的概念是相同的 。
?单元素, 单元素表,若数据元素为非表元素 （ 即简单元
素, 如基本数据类型, 结构 /记录等 ）, 则称其为 单元素；
若 Ls中的元素均为 单元素, 则称其为 单元素表 。
?空表,表内无元素（长度为 0）的表称为空表。
5
相关概念 (续 )
?表头,称 Ls的第 1个元素为 Ls的表头 。
?表尾,称 Ls中除去表头后其余元素构成的表为表尾 。
显然, 表尾一定是表, 但表头不一定 。
?深度,Ls的深度 Depth(Ls)递归地定义为：
0,若 Ls为单元素
Depth(Ls) = 1,若 Ls为空表
1 + MAXi(Depth(αi)),其它情况
?从定义知, 广义表的深度, 相当于广义表表达式中括号的最大嵌套
层数 。
6
相关概念 (续 )
?层,我们将元素的深度值称做该元素的 层号, 层号相同者称为 同层
结点 。
?系列广义表,由于广义表的元素往往也是广义表, 所以需要一同考
虑 。 我们称可追塑到同属于某一广义表的所有广义表为一个广义表
系列 （ 或系列广义表 ） 。
?递归表,若表 Ls中某成员含有自己 (即 Ls),则称 Ls为递归表 。
?下面的叙述中, 我们用大写字母表示具体的广义表, 用小写字母代
表数据对象的成员 （ 单元素 ） 。 在同一个广义表系列中, 相同字母
表示同一对象 。
7
广义表例子
① A=( )：空表, 无头, 尾为空表, 长度为 0,深度为 1.
② B=(a,b,c)：单元素表, 头为 a,尾为 (b,c),长度为 3,深度为 1.
③ C=(a,(b,c,d) )：非单元素表, 头为 a,尾为 ((b,c,d)),长度为 2，
深度为 2.
④ D=(B,((a,b),c ) )：非单元素表, 头为 B,尾为 ( ((a,b),c)) ),长度为
2,深度为 3.
⑤ E=(a,E)：非单元素, 头为 a,尾为 (E),长度为 2,深度为 ∞
?事实上, E=(a,E) = (a,(a (,… ) ) )是个递归表 。
?有时, 为了强调广义表名称, 可将表名写在表的左括号前面, 如上
例中的 D 可写为：
D( B(a,b,c),F( G(a,b),c) )
8
§ 7.1.2 基本特性
?宏观线性性,对任意广义表, 若不考虑它的元素的内部结构, 则它
是一个线性表, 即它的直接元素之间是线性关系 。
?元素递归性,广义表的任一元素, 又可以是一个广义表 （ 其它广义
表或自身 ） 。 这种递归性使得广义表具有强有力的表达能力, 这是
广义表最重要的特性 。
?元素共享性,在同一广义表系列中, 任一元素 （ 单元素或表 ） 均可
以出现多次, 同一元素的多次出现都代表的是同一个目标, 可以认
为它们是共享同一目标, 具有该特性的表也称再入表 。
9
§ 7.1.3 基本操作
? 线性表的基本运算
? 求深度
? 求表头
? 求表尾
? 求成员
? 串行化
10
§ 7.2 广义表的存贮结构
? 具有较高的复杂性，因此一般只采用链式存贮
结构
? 分枝单链表法 ── 一种通用的存贮结构
§ 7.2.1 基本存储方法
11
分枝单链表存贮方法
(a) 为每个 αi设置一个结点 Hi,称其为 αi的头结点, 其结构为：
?tag：指示 αi是单元素还是广义表 (我们设 tag为 0时表示 αi为单元素 ） 。
?pElem：若 αi为单元素, 则指向 αi的内容, 否则指向 αi对应的广义表
(可以用第一个头结点 H1的指针代表广义表 ).
?next：单链表链指针, 即指向 Hi+1。
tag … pElem next
12
分枝单链表存贮方法
(b) αi为单元素时, αi的内容应对应一片连续区域, 可在
它中设置一个长度字段 。
(c) 直接元素构成的单链表, 根据具体问题的需要, 可以
是带头结点的, 或循环式的, 或双向链式的或这些的组
合 。
(d)如果不共享单元素内容, 且单元素内容的长度相等
（ 或差别不大 ）, 则可将单元素内容直接放到元素头结
点中 。
13
广义表存储结构示例
(a) B=(a,b,c)
0
a
0 0 ^
b c
B
0 1 ^
0 0 0 ^
b c d
(b) C=(a,(b,c,d) )
C
a
14
广义表存储结构示例
(c) D=(B,((a,b),c) )
0 ^
1 1 ^
1B
0 0 ^
a b
D 0 1
a
(d) E=(a,E)
15
广义表 C++描述
template <class TElem>
class TGListNode
{
char tag;
char name[CNST_SizeListNodeName];
TGListNode *next;
union
{
TElem *pElem;
TGListNode *pSub;
};
};
共享存储区
16
成员的含义
tag：广义表元素结点种类标志, 它表明对应结点是单元素
(0)还是表 (1)。
name：结点名称 。 当结点是表时, 也是该结点所对应的
（ 广义 ） 表的名称 。
next：指向同层中下个结点 。
pElem：指向结点对应的元素内容 。
pSub：指向结点对应的子表 （ 的头 ） 。
17
§ 7.3 广义表对象模型
? 将广义表作为一种抽象对象，建立它的访问接
口。
? 将访问接口分为两部分：
– 广义表结点接口
– 广义表接口
18
§ 7.3.1 广义表结点接口
template <class TElem>
struct TGListNode0
{
virtual GetNumSubNodes ( ) = 0; //返回本结点的子表中的元素个数
virtual char IsList ( ) = 0;
//若本结点是非单元素结点, 则返回假 （ 0）, 否则返回真 （ 1）
virtual TElem *GetElem ( ) = 0;
//返回本结点对应的元素的内容 （ 的地址 ） 。 若本结点为子表, 则返回
空
virtual TElem *SetElem (TElem *pe) = 0; //为本元素结点设置内容
19
virtual TGListNode0 *GetNext ( ) =0;
//返回本结点代表的元素的后继元素所对应的结点
virtual SetNext (TGListNode0 *p) = 0；
//为本结点代表的元素设置后继结点
virtual TGlistNode0 *GetSub (void ) = 0;
//返回本元素对应的子表的头结点
virtual TGlistNode0 *SetSub (TGListNode0 *pNode) = 0;
//为本元素设置子表 （ 用子表的头结点表示子表 ）
};
20
TGListNode0的派生类,TGListNode
template <class TElem>
class TGListNode, public TGListNode0<TElem>
{
char tag;
char name[CNST_SizeListNodeName];
TGListNode *next;
union
{
TElem *pElem;
TGListNode *pSub;
//下面是 TGListNode0中定义的成员函数的原形
… …
};
21
§ 7.3.2 广义表接口
template <class TElem>
class TGList0
{
public:
long GetLen ( ) =0; //返回本表的长度
long GetDepth(void)=0; //返回本表的深度
virtual TGList0<TElem> *GetList(TGListNode0<TElem> *pNode)=0;
//返回结点 pNode所对应的子表对象指针 。 若 pNode无相应的对象, 则返回
空, 并触发异常 。
22
virtual TGListNode0<TElem> *GetHead(void)=0;
//返回本表的的头所对应的结点的指针
virtual TGListNode0<TElem> *GetTail(void)=0;
//返回本表的尾所对应的结点的指针
virtual TElem &GetElem(longidx)=0;//返回本表中序号为 idx的元素的内容
virtual TGListNode0<TElem> &GetElemNode(longidx)=0;
//返回本表中序号为 idx的元素所对应的结点的地址
virtual TGlistNode0 *GetSub(TGListNode0<TElem> *pNode,ong idx)=0;
//返回结点 pNode对应的子表中的序号为 idx的结点 。 若无子表, 或无序号
为 idx的子表, 则返回空
virtual long GetFathers(TGListNode0<TElem> *pNode,
TGListNode0<TElem> **father)=0;
//结点 pNode的各父结点的指针存入 father数组中
23
virtual TGListNode0<TElem> *GetFirstFather(TGListNode0<TElem>
*pNode)=0; //返回结点 pNode对应的父结点中的第一个结点
virtual TGListNode0<TElem> *GetNextFather(TGListNode0<TElem>
*pNode)=0; //返回结点 p对应的父结点中的下一个结点
virtual long IsMenber(TGListNode0<TElem> *p)=0;
//检查结点 p是否是本结点 （ 对象本身 ） 的成员 。 若是, 则返回 p的层号 （ 相
对与本结点 ）, 否则返回 0
virtual long Locate(TElem &elem,TGList0<TElem> **pNodes)=0;
//在本表中查找值为 elem的结点, 将它们的地址存入数组 pNodes。 返回值为 elem的结
点的的数目
24
virtual long Cluster(TGListNode0<TElem>* pNode,
TElem **e,TTraverseMode tm)=0;
//串行化 （ 聚集 ） 操作 。 按遍历方式 tm,将结点 pNode的各子表中的结点的值的地址,
存入数组 e中, 返回数组中元素的个数 。
例如, 对广义表
L=(a,(c,(a,b),d),(e,(f)) )
深度优先 （ 前序 ） 串行化结果为：
a,c,a,b,d,e,f
返回值为 7
virtual long Cluster(TGListNode0<TElem>* pNode,
TGListNode0<TElem> **pe,TTraverseMode tm)=0;
//串行化 （ 聚集 ） 操作 。 按遍历方式 tm,将结点 pNode的各子表中的结点的
地址, 存入数组 pe中, 返回数组中元素的个数
25
virtual long ClusterJuniors(TGListNode0<TElem>* pNode,
TGListNode0<TElem> **pe,TTraverseMode travMode=PreOrder,
int startLevel=1,int endLevel=-1)=0;
//按遍历方式 travMode,将结点 pNode对应的子表中的, 层号 （ 相对于
pNode） 在 startLevel和 endLevel之间的结点的地址, 存入数组 pe,返回数组
中元素个数
virtual long ClusterSeniors(TGListNode0<TElem>* pNode,
TGListNode0<TElem> **pe,TTraverseMode travMode=PreOrder,
int startLevel=1,int endLevel=-1)=0;
//按遍历方式 travMode,将结点 pNode对应的子表中的, 层号在 startLevel和
endLevel之间的结点的地址, 存入数组 pe,返回数组中元素个数 。 这里,
pNode的层号为 1,pNode的父结点层号为 2,余类推
26
TGListNode *InsertNode(TGListNode *p,long sn)=0;
//在本表中的第 sn个结点之前插入结点 p。 返回被插入结点的地址 。 sn可正可
负, 具体含义同上
TGListNode *DeleteNode(longsn1,long sn2)=0;
//在对应结点的子表中删除其第 sn个结点, 并将其地址返回 。 sn含义同上
};
27
§ 7.4 广义表的分枝单链表对象
template <class TElem>
class TGListNode,public TGListNode0<TElem>
{
char tag;
char name[CNST_SizeListNodeName];
long numSubs;
TGListNode *next;
union
{
TElem *pElem;
TGListNode *pSub;
};
§ 7.4.1 结点对象
28
public:
TGListNode();
~TGListNode();
virtual GetNumSubNodes(){return numSubs;};
virtual char IsList() {return tag};
virtual TElem *GetElem() {return pElem;};
virtual TElem *SetElem(TElem *pe) {pElem = pe; return pElem;};
virtual TGListNode0 *GetNext() {return next;};
virtual TGListNode0 *SetNext(TGListNode0 *pNode) {next =
pNode;return next;};
virtual TGlistNode0 *GetSub(void) {return pSub;};
virtual TGlistNode0 *SetSub(TGListNode0 *pNode) {pSub =
pNode;return pSub;};
};
29
§ 7.4.2 分枝单链表对象
? 为分枝单链表设立一个总头结点（类型仍然为 TGListNode），令
它的 pSub指向广义表分枝单链表中的第一个元素对应的结点。
图 - 带总头结点的广义表分枝
单链表
d
0 1 ^
0 0 0 ^
b c
1 ^C
a
30
template <class TElem>
class TGList,public TGList0
{
TGListNode<TElem> *head;
public:
//下面是在 TGList0中定义的函数的声明 （ 不含, =0”部
分 ） 。
};
31
§ 7.5 广义表操作的实现
GetDepth()
GetFather()类
Locate()
Cluster()类
IsMenber(TGListNode *p)
InsertNode()
DeleteNode()
有一个重要问题需注意：循环问题
§ 7.5.1 一般问题
32
§ 7.5.2 遍历操作
? 以深度优先遍历操作说明广义表的遍历的实现
longTGList::Cluster(TGListNode *p,TElem **pE)
{
static long k=0;
long cnt=0;
if (p==NULL) return 0;
if (p->tag==0) return 0;
q = p->pSub;
33
while (q!=NULL)
{
if (q未被访问 )
{
置 q已访问标志；
if(q->tag == 0)
pE[k++]=q->pElem;
else
q.Cluster(q,pE);
}
q = q->next;
} //while
return k;
}
34
§ 7.5.3 广义表统计计数
? 统计计数操作有求深度、求层号、满足指定条件的结点个数等。
下面以广义表求深度操作说明 。
longTGListNode::Depth(TGListNode *p)
{
long h=0,mh=0;
if (p==NULL) return 0;
if (p->tag==0) return 0;
q = p->pSub;
35
while (q!=NULL)
{
if (q已被访问 )
return -1; //遇到循环, 深度为无穷大
else
{
置 q已访问标志；
h=Depth(q);
if (h > mh) mh = h;
}
q = q->next;
} //while
return 1+mh;
}
36
§ 7.6 广义表结构的应用
? 广义表最适合描述递归结构和分层结构，如分
层索引结构（如图书的目录、计算机操作系统
中的文件目录结构）及其它一些多叉树形结构
37
§ 7.6.1 多元多项式的表示
?多元多项式具有多个变元,
?例如下面是一个三元多项式
P(x1,x2,x3)=x15x23x3+2x15x22x34+5x15x23x33+3x1x24x32+x2x3+100
? 如果仿照一元多项式的结构，即令多项式每项对应一个结点，结点应含
一个系数域和 m个（ m为未知数个数）指数域。但这种表示法有下列几个方
面的缺陷：
– ①结点的结构随多项式的变数元数目而变化，这造成了概念上的不美观，
缺少通用性；
– ②不适合某些应用要求的操作的实现
? 最适合使用广义表结构
38
?对任意一个 m元多项式，都可以任选一个变元（称为第 1变元或主变
元），按此变元合并同类项，使该 m元多项式变为如下形式：
?这里,en>en-1>…>e 1,Ai为关于变元 x2…x m的 (m-1)元多项式，
i=1,2,…n
?下步可对 Ai选 x2为主变元进行类似的处理，如此进行，最后一回选
xm为主变元对各个以 xm-1为主变元的多项式进行同样的处理。
?例如, 对前面给出的 P3(x1,x2,x3)处理如下：
P(x1,x2,x3)=x15x23x3+2x15x22x34+5x15x23x33+3x1x24x32+x2x3+100
= (x23x3+2x22x34+5x23x33) x15 + (3x24x32) x1 + (x2x3+100)
=( (5x33+ x3) x23+(2x34) x22) x15 + (3x24x32) x1 + (x2x3+100)
11 111111,..)...( eenenmm xAxAxAxxp nn ???? ??
39
?将上式中每一项用一个如下形式的二元组表示：
（ 系数, 指数 ）
其中,,系数, 可能是一个多元多项式，也可能是基本元素。并且将
各二元组按指数降序排列，则所成结构为广义表，这就是 m元多项式
的广义表表示。
40
?对上式有：
P=((A3,5),(A2,1),(A1,0) ) //以 x1为主变量
A3=( (A32,3),(A31,2) ) //以 x2为主变量 A3=( 5x33+ x3) x23+(2x34) x22
A2=((A21,4)) //以 x2为主变量 A2 = (3 x32 )x24
A1=((A11,1),(100,0)) //以 x2为主变量 A1=x2x3
A32=((5,3),(1,1)) //以 x3为主变量 A32=5x33+ x3
A31=((2,4)) //以 x3为主变量 A31=2x34
A21=((3,2)) //以 x3为主变量 A21= 3x32
A11=((1,1)) //以 x3为主变量 A11=x3
P(x1,x2,x3)=x15x23x3+2x15x22x34+5x15x23x33+3x1x24x32+x2x3+100
= (x23x3+2x22x34+5x23x33) x15 + (3x24x32) x1 + (x2x3+100)
=( (5x33+ x3) x23+(2x34) x22) x15 + (3x24x32) x1 + (x2x3+100)
41
习 题 7
1,对下列广义表系列, 分别求出它们的长度, 深度, 头, 尾, 并画
出存贮结构图 （ 同名元素或表共享, 小写字母为单元素 ）
① A=((a,b),(a,c))
② c=((A,a),(b,c))
③ D=((a,(b,a)),A)
④ E=(E,a,b)
42
2。 请通过 GetHead()和 GetTail()操作, 将下列各表中的 apple分离出来 。
A1 = (banana,pear,orange)
A2 = ((apple,pear),orange)
A2 = (pear,(peach,(plum,apple),fig),apple,date)
3,给出一个 3元多项式
P(x1,x2,x3)=10x15x22x3+2x15x2x3+3x15+x12x22x3+x12x2x3+x22x3+10
写出它的广义表表达式 （ 逻辑表示 ）, 并画出相应的分枝单链表存
贮结构图 。
