// c5-5.h 广义表的头尾链表存储结构(见图5.16)
enum ElemTag{ATOM,LIST}; // ATOM==0：原子，LIST==1：子表
typedef struct GLNode
{
ElemTag tag; // 公共部分，用于区分原子结点和表结点
union // 原子结点和表结点的联合部分
{
AtomType atom; // atom是原子结点的值域，AtomType由用户定义
struct
{
GLNode *hp,*tp;
}ptr; // ptr是表结点的指针域，prt.hp和ptr.tp分别指向表头和表尾
};
}*GList,GLNode; // 广义表类型
图517 是根据c5-5.h 定义的广义表(a,(b,c,d))的存储结构。它的长度为2，第1
个元素为原子a，第2 个元素为子表(b,c,d)。
// c5-6.h 广义表的扩展线性链表存储表示(见图5.18)
enum ElemTag{ATOM,LIST};
// ATOM==0：原子，LIST==1：子表
typedef struct GLNode1
{
ElemTag tag; // 公共部分，用于区分原子结点和表结点
union // 原子结点和表结点的联合部分
{
AtomType atom; // 原子结点的值域
GLNode1 *hp; // 表结点的表头指针
};
GLNode1 *tp; // 相当于线性链表的next，指向下一个元素结点
}*GList1,GLNode1; // 广义表类型GList1是一种扩展的线性链表
为了和c5-5.h 定义的存储结构相区别，令c5-6.h 定义的结构类型名为GList1 和
GLNode1。
图519 是根据c5-6.h 定义的广义表(a,(b,c,d))的扩展线性链表存储结构。在这种
结构中，广义表的头指针所指结点的tag 域值总是1(表)，其tp 域总是NULL。这样看
来，广义表的头指针所指结点相当于表的头结点。和图517 相比，图519 这种结构更
简洁些。
广义表的递归算法
求广义表的深度
算法5.5 在bo5-5.cpp 中。
复制广义表
算法5.6 在bo5-5.cpp 中。
// func5-1.cpp 广义表的书写形式串为SString类型，包括算法5.8。bo5-5.cpp和bo5-6.cpp调用
#include"c4-1.h" // 定义SString类型
#include"bo4-1.cpp" // SString类型的基本操作
void sever(SString str,SString hstr) // 算法5.8改。SString是数组，不需引用类型
{ // 将非空串str分割成两部分：hstr为第一个′,′之前的子串，str为之后的子串
int n,k,i; // k记尚未配对的左括号个数
SString ch,c1,c2,c3;
n=StrLength(str); // n为串str的长度
StrAssign(c1,","); // c1=′,′
StrAssign(c2,"("); // c2=′(′
StrAssign(c3,")"); // c3=′)′
SubString(ch,str,1,1); // ch为串str的第1个字符
for(i=1,k=0;i<=n&&StrCompare(ch,c1)||k!=0;++i) // i小于串长且ch不是’,’
{ // 搜索最外层的第一个逗号
SubString(ch,str,i,1); // ch为串str的第i个字符
if(!StrCompare(ch,c2)) // ch=′(′
++k; // 左括号个数+1
else if(!StrCompare(ch,c3)) // ch=′)′
--k; // 左括号个数-1
}
if(i<=n) // 串str中存在′,′，它是第i-1个字符
{
SubString(hstr,str,1,i-2); // hstr返回串str′,′前的字符
SubString(str,str,i,n-i+1); // str返回串str′,′后的字符
}
else // 串str中不存在′,′
{
StrCopy(hstr,str); // 串hstr就是串str
ClearString(str); // ′,′后面是空串
}
}
// bo5-5.cpp 广义表的头尾链表存储(存储结构由c5-5.h定义)的基本操作(11个),包括算法5.5,5.6,5.7
#include"func5-1.cpp" // 算法5.8
void InitGList(GList &L)
{ // 创建空的广义表L
L=NULL;
}
void CreateGList(GList &L,SString S) // 算法5.7
{ // 采用头尾链表存储结构，由广义表的书写形式串S创建广义表L。设emp="()"
SString sub,hsub,emp;
GList p,q;
StrAssign(emp,"()"); // 空串emp="()"
if(!StrCompare(S,emp)) // S="()"
L=NULL; // 创建空表
else // S不是空串
{
if(!(L=(GList)malloc(sizeof(GLNode)))) // 建表结点
exit(OVERFLOW);
if(StrLength(S)==1) // S为单原子，只会出现在递归调用中
{
L->tag=ATOM;
L->atom=S[1]; // 创建单原子广义表
}
else // S为表
{
L->tag=LIST;
p=L;
SubString(sub,S,2,StrLength(S)-2); // 脱外层括号(去掉第1个字符和最后1个字符)给串sub
do
{ // 重复建n个子表
sever(sub,hsub); // 从sub中分离出表头串hsub
CreateGList(p->ptr.hp,hsub);
q=p;
if(!StrEmpty(sub)) // 表尾不空
{
if(!(p=(GLNode *)malloc(sizeof(GLNode))))
exit(OVERFLOW);
p->tag=LIST;
q->ptr.tp=p;
}
}while(!StrEmpty(sub));
q->ptr.tp=NULL;
}
}
}
void DestroyGList(GList &L)
{ // 销毁广义表L
GList q1,q2;
if(L)
{
if(L->tag==LIST) // 删除表结点
{
q1=L->ptr.hp; // q1指向表头
q2=L->ptr.tp; // q2指向表尾
DestroyGList(q1); // 销毁表头
DestroyGList(q2); // 销毁表尾
}
free(L);
L=NULL;
}
}
void CopyGList(GList &T,GList L)
{ // 采用头尾链表存储结构，由广义表L复制得到广义表T。算法5.6
if(!L) // 复制空表
T=NULL;
else
{
T=(GList)malloc(sizeof(GLNode)); // 建表结点
if(!T)
exit(OVERFLOW);
T->tag=L->tag;
if(L->tag==ATOM)
T->atom=L->atom; // 复制单原子
else
{
CopyGList(T->ptr.hp,L->ptr.hp); // 递归复制子表
CopyGList(T->ptr.tp,L->ptr.tp);
}
}
}
int GListLength(GList L)
{ // 返回广义表的长度，即元素个数
int len=0;
while(L)
{
L=L->ptr.tp;
len++;
}
return len;
}
int GListDepth(GList L)
{ // 采用头尾链表存储结构，求广义表L的深度。算法5.5
int max,dep;
GList pp;
if(!L)
return 1; // 空表深度为1
if(L->tag==ATOM)
return 0; // 原子深度为0，只会出现在递归调用中
for(max=0,pp=L;pp;pp=pp->ptr.tp)
{
dep=GListDepth(pp->ptr.hp); // 递归求以pp->ptr.hp为头指针的子表深度
if(dep>max)
max=dep;
}
return max+1; // 非空表的深度是各元素的深度的最大值加1
}
Status GListEmpty(GList L)
{ // 判定广义表是否为空
if(!L)
return TRUE;
else
return FALSE;
}
GList GetHead(GList L)
{ // 生成广义表L的表头元素，返回指向这个元素的指针
GList h,p;
if(!L) // 空表无表头
return NULL;
p=L->ptr.hp; // p指向L的表头元素
CopyGList(h,p); // 将表头元素复制给h
return h;
}
GList GetTail(GList L)
{ // 将广义表L的表尾生成为广义表，返回指向这个新广义表的指针
GList t;
if(!L) // 空表无表尾
return NULL;
CopyGList(t,L->ptr.tp); // 将L的表尾拷给t
return t;
}
void InsertFirst_GL(GList &L,GList e)
{ // 初始条件：广义表存在。操作结果：插入元素e(也可能是子表)作为广义表L的第1元素(表头)
GList p=(GList)malloc(sizeof(GLNode)); // 生成新结点
if(!p)
exit(OVERFLOW);
p->tag=LIST; // 结点的类型是表
p->ptr.hp=e; // 表头指向e
p->ptr.tp=L; // 表尾指向原表L
L=p; // L指向新结点
}
void DeleteFirst_GL(GList &L,GList &e)
{ // 初始条件：广义表L存在。操作结果：删除广义表L的第一元素，并用e返回其值
GList p=L; // p指向第1个结点
e=L->ptr.hp; // e指向L的表头
L=L->ptr.tp; // L指向原L的表尾
free(p); // 释放第1个结点
}
void Traverse_GL(GList L,void(*v)(AtomType))
{ // 利用递归算法遍历广义表L
if(L) // L不空
if(L->tag==ATOM) // L为单原子
v(L->atom);
else // L为广义表
{
Traverse_GL(L->ptr.hp,v); // 递归遍历L的表头
Traverse_GL(L->ptr.tp,v); // 递归遍历L的表尾
}
}
// main5-5.cpp 检验bo5-5.cpp的主程序
#include"c1.h"
typedef char AtomType; // 定义原子类型为字符型
#include"c5-5.h" // 定义广义表的头尾链表存储
#include"bo5-5.cpp"
void visit(AtomType e)
{
printf("%c ", e);
}
void main()
{
char p[80];
SString t;
GList l,m;
InitGList(l);
InitGList(m);
printf("空广义表l的深度=%d l是否空？%d(1:是0:否)\n",GListDepth(l),GListEmpty(l));
printf("请输入广义表l(书写形式：空表:(),单原子:(a),其它:(a,(b),c)):\n");
gets(p);
StrAssign(t,p);
CreateGList(l,t);
printf("广义表l的长度=%d\n",GListLength(l));
printf("广义表l的深度=%d l是否空？%d(1:是0:否)\n",GListDepth(l),GListEmpty(l));
printf("遍历广义表l：\n");
Traverse_GL(l,visit);
printf("\n复制广义表m=l\n");
CopyGList(m,l);
printf("广义表m的长度=%d\n",GListLength(m));
printf("广义表m的深度=%d\n",GListDepth(m));
printf("遍历广义表m：\n");
Traverse_GL(m,visit);
DestroyGList(m);
m=GetHead(l);
printf("\nm是l的表头元素，遍历m：\n");
Traverse_GL(m,visit);
DestroyGList(m);
m=GetTail(l);
printf("\nm是由l的表尾形成的广义表，遍历广义表m：\n");
Traverse_GL(m,visit);
InsertFirst_GL(m,l);
printf("\n插入广义表l为m的表头，遍历广义表m：\n");
Traverse_GL(m,visit);
printf("\n删除m的表头，遍历广义表m：\n");
DestroyGList(l);
DeleteFirst_GL(m,l);
Traverse_GL(m,visit);
printf("\n");
DestroyGList(m);
}
代码的运行结果：
空广义表l的深度=1 l是否空？1(1:是0:否)
请输入广义表l(书写形式：空表:(),单原子:(a),其它:(a,(b),c)):
((),(e),(a,(b,c,d)))
广义表l的长度=3
广义表l的深度=3 l是否空？0(1:是0:否)
遍历广义表l：
e a b c d
复制广义表m=l
广义表m的长度=3
广义表m的深度=3
遍历广义表m：
e a b c d
m是l的表头元素，遍历m：
m是由l的表尾形成的广义表，遍历广义表m：
e a b c d
插入广义表l为m的表头，遍历广义表m：
e a b c d e a b c d
删除m的表头，遍历广义表m：
e a b c d
Press any key to continue
// bo5-6.cpp 广义表的扩展线性链表存储(存储结构由c5-6.h定义)的基本操作(13个)
#include"func5-1.cpp" // 算法5.8
void InitGList(GList1 &L)
{ // 创建空的广义表L
L=NULL;
}
void CreateGList(GList1 &L,SString S) // 算法5.7改
{ // 采用扩展线性链表存储结构，由广义表的书写形式串S创建广义表L。设emp="()"
SString emp,sub,hsub;
GList1 p;
StrAssign(emp,"()"); // 设emp="()"
if(!(L=(GList1)malloc(sizeof(GLNode1)))) // 建表结点不成功
exit(OVERFLOW);
if(!StrCompare(S,emp)) // 创建空表
{
L->tag=LIST;
L->hp=L->tp=NULL;
}
else if(StrLength(S)==1) // 创建单原子广义表
{
L->tag=ATOM;
L->atom=S[1];
L->tp=NULL;
}
else // 创建一般表
{
L->tag=LIST;
L->tp=NULL;
SubString(sub,S,2,StrLength(S)-2); // 脱外层括号(去掉第1个字符和最后1个字符)给串sub
sever(sub,hsub); // 从sub中分离出表头串hsub
CreateGList(L->hp,hsub);
p=L->hp;
while(!StrEmpty(sub)) // 表尾不空，则重复建n个子表
{
sever(sub,hsub); // 从sub中分离出表头串hsub
CreateGList(p->tp,hsub);
p=p->tp;
};
}
}
void DestroyGList(GList1 &L)
{ // 初始条件：广义表L存在。操作结果：销毁广义表L
GList1 ph,pt;
if(L) // L不为空表
{ // 由ph和pt接替L的两个指针
if(L->tag) // 是子表
ph=L->hp;
else // 是原子
ph=NULL;
pt=L->tp;
DestroyGList(ph); // 递归销毁表ph
DestroyGList(pt); // 递归销毁表pt
free(L); // 释放L所指结点
L=NULL; // 令L为空
}
}
void CopyGList(GList1 &T,GList1 L)
{ // 初始条件：广义表L存在。操作结果：由广义表L复制得到广义表T
T=NULL;
if(L) // L不空
{
T=(GList1)malloc(sizeof(GLNode1));
if(!T)
exit(OVERFLOW);
T->tag=L->tag; // 复制枚举变量
if(L->tag==ATOM) // 复制共用体部分
T->atom=L->atom; // 复制单原子
else
CopyGList(T->hp,L->hp); // 复制子表
if(L->tp==NULL) // 到表尾
T->tp=L->tp;
else
CopyGList(T->tp,L->tp); // 复制子表
}
}
int GListLength(GList1 L)
{ // 初始条件：广义表L存在。操作结果：求广义表L的长度，即元素个数
int len=0;
GList1 p=L->hp; // p指向第1个元素
while(p)
{
len++;
p=p->tp;
};
return len;
}
int GListDepth(GList1 L)
{ // 初始条件：广义表L存在。操作结果：求广义表L的深度
int max,dep;
GList1 pp;
if(L==NULL||L->tag==LIST&&!L->hp)
return 1; // 空表深度为1
else if(L->tag==ATOM)
return 0; // 单原子表深度为0，只会出现在递归调用中
else // 求一般表的深度
for(max=0,pp=L->hp;pp;pp=pp->tp)
{
dep=GListDepth(pp); // 求以pp为头指针的子表深度
if(dep>max)
max=dep;
}
return max+1; // 非空表的深度是各元素的深度的最大值加1
}
Status GListEmpty(GList1 L)
{ // 初始条件：广义表L存在。操作结果：判定广义表L是否为空
if(!L||L->tag==LIST&&!L->hp)
return OK;
else
return ERROR;
}
GList1 GetHead(GList1 L)
{ // 生成广义表L的表头元素，返回指向这个元素的指针
GList1 h,p;
if(!L||L->tag==LIST&&!L->hp) // 空表无表头
return NULL;
p=L->hp->tp; // p指向L的表尾
L->hp->tp=NULL; // 截去L的表尾部分
CopyGList(h,L->hp); // 将表头元素复制给h
L->hp->tp=p; // 恢复L的表尾(保持原L不变)
return h;
}
GList1 GetTail(GList1 L)
{ // 将广义表L的表尾生成为广义表，返回指向这个新广义表的指针
GList1 t,p;
if(!L||L->tag==LIST&&!L->hp) // 空表无表尾
return NULL;
p=L->hp; // p指向表头
L->hp=p->tp; // 在L中删去表头
CopyGList(t,L); // 将L的表尾拷给t
L->hp=p; // 恢复L的表头(保持原L不变)
return t;
}
void InsertFirst_GL(GList1 &L,GList1 e)
{ // 初始条件：广义表存在。操作结果：插入元素e(也可能是子表)作为广义表L的第1元素(表头)
GList1 p=L->hp;
L->hp=e;
e->tp=p;
}
void DeleteFirst_GL(GList1 &L,GList1 &e)
{ // 初始条件：广义表L存在。操作结果：删除广义表L的第一元素，并用e返回其值
if(L&&L->hp)
{
e=L->hp;
L->hp=e->tp;
e->tp=NULL;
}
else
e=L;
}
void Traverse_GL(GList1 L,void(*v)(AtomType))
{ // 利用递归算法遍历广义表L
GList1 hp;
if(L) // L不空
{
if(L->tag==ATOM) // L为单原子
{
v(L->atom);
hp=NULL;
}
else // L为子表
hp=L->hp;
Traverse_GL(hp,v);
Traverse_GL(L->tp,v);
}
}
// main5-6.cpp 检验bo5-6.cpp的主程序
#include"c1.h"
typedef char AtomType; // 定义原子类型为字符型
#include"c5-6.h" // 定义广义表的扩展线性链表存储结构
#include"bo5-6.cpp" // 广义表的扩展线性链表存储结构基本操作
void visit(AtomType e)
{
printf("%c ", e);
}
void main()
{
char p[80];
GList1 l,m;
SString t;
InitGList(l); // 建立空的广义表l
printf("空广义表l的深度=%d l是否空？%d(1:是0:否)\n",GListDepth(l),GListEmpty(l));
printf("请输入广义表l(书写形式：空表:(),单原子:(a),其它:(a,(b),c)):\n");
gets(p);
StrAssign(t,p);
CreateGList(l,t);
printf("广义表l的长度=%d\n",GListLength(l));
printf("广义表l的深度=%d l是否空？%d(1:是0:否)\n",GListDepth(l),GListEmpty(l));
printf("遍历广义表l：\n");
Traverse_GL(l,visit);
printf("\n复制广义表m=l\n");
CopyGList(m,l);
printf("广义表m的长度=%d\n",GListLength(m));
printf("广义表m的深度=%d\n",GListDepth(m));
printf("遍历广义表m：\n");
Traverse_GL(m,visit);
DestroyGList(m);
m=GetHead(l);
printf("\nm是l的表头元素，遍历m：\n");
Traverse_GL(m,visit);
DestroyGList(m);
m=GetTail(l);
printf("\nm是由l的表尾形成的广义表，遍历广义表m：\n");
Traverse_GL(m,visit);
InsertFirst_GL(m,l);
printf("\n插入广义表l为m的表头，遍历广义表m：\n");
Traverse_GL(m,visit);
DeleteFirst_GL(m,l);
printf("\n删除m的表头，遍历广义表m：\n");
Traverse_GL(m,visit);
printf("\n");
DestroyGList(m);
}
代码的运行结果：
空广义表l的深度=1 l是否空？1(1:是0:否)
请输入广义表l(书写形式：空表:(),单原子:(a),其它:(a,(b),c)):
(a,(b),c)
广义表l的长度=3
广义表l的深度=2 l是否空？0(1:是0:否)
遍历广义表l：
a b c
复制广义表m=l
广义表m的长度=3
广义表m的深度=2
遍历广义表m：
a b c
m是l的表头元素，遍历m：
a
m是由l的表尾形成的广义表，遍历广义表m：
b c
插入广义表l为m的表头，遍历广义表m：
a b c b c
删除m的表头，遍历广义表m：
b c
Press any key to continue