广义表是非线性的结构，是线性表的一种扩展，是有n个元素组成有限序列。

广义表的定义是递归的，因为在表的描述中又得到了表，允许表中有表。

<1> A = ()

<2> B = (a,b)

<3> C = (a,b,(c,d))

<4> D = (a,b,(c,d),(e,(f),h))

<5> E =(((),()))

如下图所示：

广义表主要使用递归实现，表与表之间使用链式结构来存储。下面就来看看代码怎样实现的：

#pragmaonce#include<iostream>#include<assert.h>usingnamespacestd;//节点类型enumType{HEAD,//头节点VALUE,//数据项SUB,//子表的头节点};//广义表结构structGeneralizedNode{public:GeneralizedNode()//无参构造函数:_type(HEAD),_next(NULL){}GeneralizedNode(Typetype,charch=0):_type(type),_next(NULL){if(_type==VALUE){_value=ch;//数据节点}if(_type==SUB){_sublink=NULL;//子表节点}}public:Type_type;//节点类型GeneralizedNode*_next;union{char_value;//数据GeneralizedNode*_sublink;//子表的头指针};};//广义表类classGeneralized{public:Generalized()//无参构造函数:_head(newGeneralizedNode(HEAD)){}Generalized(constchar*str)//构造函数:_head(NULL){_head=_CreateList(str);}Generalized(constGeneralized&g)//拷贝构造{_head=_CopyList(g._head);}Generalized&operator=(Generalizedg)//赋值运算符的重载{swap(_head,g._head);//现代写法return*this;}~Generalized()//析构函数{_Delete(_head);//递归析构}public:voidprint()//打印{_Print(_head);}size_tsize()//元素个数{size_tret=_Size(_head);returnret;}size_tdepth()//广义表的深度{size_tret=_Depth(_head);returnret;}public:GeneralizedNode*_CreateList(constchar*&str)//创建广义表{assert(str&&*str=='(');//判断传入的广义表是否正确str++;//跳过'('GeneralizedNode*head=newGeneralizedNode();//创建头节点GeneralizedNode*cur=head;while(*str){if(_IsVaild(*str)){cur->_next=newGeneralizedNode(VALUE,*str);//创建数据节点cur=cur->_next;//节点后移str++;//指针后移}elseif(*str=='(')//子表{GeneralizedNode*SubNode=newGeneralizedNode(SUB);//创建字表的头节点SubNode->_sublink=_CreateList(str);//递归调用_CreateList函数cur->_next=SubNode;cur=cur->_next;}elseif(*str==')')//表的结束{str++;//跳过')'returnhead;//返回头节点}else//其他字符（''或者','）{str++;}}assert(false);//强制判断程序是否出错returnhead;}bool_IsVaild(constcharch)//判断输入是否合理{if((ch>='0'&&ch<='9')||(ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')){returntrue;}else{returnfalse;}}GeneralizedNode*_CopyList(GeneralizedNode*head)//复制{GeneralizedNode*cur=head;//创建新的头节点GeneralizedNode*newHead=newGeneralizedNode();GeneralizedNode*tmp=newHead;while(cur){if(cur->_type==VALUE)//数据节点{tmp->_next=newGeneralizedNode(VALUE,cur->_value);tmp=tmp->_next;}elseif(cur->_type==SUB)//子表节点{GeneralizedNode*SubNode=newGeneralizedNode(SUB);tmp->_next=SubNode;SubNode->_sublink=_CopyList(cur->_sublink);//递归调用tmp=tmp->_next;}cur=cur->_next;}returnnewHead;}void_Delete(GeneralizedNode*head){GeneralizedNode*cur=head;while(cur){GeneralizedNode*del=cur;if(cur->_type==SUB)//子表节点时递归析构{_Delete(cur->_sublink);}cur=cur->_next;deletedel;}}void_Print(GeneralizedNode*head)//打印{GeneralizedNode*cur=head;if(cur==NULL){return;}while(cur){if(cur->_type==HEAD){cout<<"(";}elseif(cur->_type==VALUE&&cur->_next){cout<<cur->_value<<",";}elseif(cur->_type==VALUE&&cur->_next==NULL){cout<<cur->_value;}elseif(cur->_type==SUB){_Print(cur->_sublink);if(cur->_next){cout<<",";}}cur=cur->_next;}if(cur==NULL){cout<<")";return;}}size_t_Size(GeneralizedNode*head)//元素的个数{GeneralizedNode*cur=head;size_tcount=0;while(cur){if(cur->_type==VALUE){count++;}elseif(cur->_type==SUB){count+=_Size(cur->_sublink);}cur=cur->_next;}returncount;}size_t_Depth(GeneralizedNode*head)//广义表的深度{GeneralizedNode*cur=head;size_tdepth=1;while(cur){if(cur->_type==VALUE){depth++;}elseif(cur->_type==SUB){size_tnewdepth=_Depth(cur->_sublink);if(newdepth++>depth)//当后面子表的深度比现在的深时，更新深度{depth=newdepth++;}}cur=cur->_next;}returndepth;}private:GeneralizedNode*_head;};

测试代码和结果如下：

voidTest(){Generalizedg1("(a,b(c,d),(e,(f),h))");Generalizedg2;g1.print();cout<<endl;cout<<"g1.size()="<<g1.size()<<endl<<endl;cout<<"g1.depth()="<<g1.depth()<<endl<<endl;g2=g1;g2.print();cout<<endl;cout<<"g2.size()="<<g1.size()<<endl<<endl;cout<<"g2.depth()="<<g1.depth()<<endl<<endl;}