广义表是一种数据结构，是线性表的推广。也有人称之为列表（lists）。广泛的用于人工智能等领域的表处理结构。

对于广义表，我们需要了解它的结构，通过学习广义表，也加深了对递归的了解。整个广义表都是了利用递归的特性实现的。

（一）首先我们要确定表中每个节点的结构，因为在广义表中有三种不同结构的节点，我们可以使用枚举enum列出我们所用到的结构节点类型。

enumType{HEAD,SUB,VALUE};

（二）有了type类型，只要定义一个type类型的一个对象就可以轻松定义不同类型的节点。

structGeneralizedNode{Type_type;union{int_value;GeneralizedNode*_SubLink;};GeneralizedNode*_next;GeneralizedNode(Typetype){if(type==HEAD){_type=HEAD;_next=NULL;}elseif(type==VALUE){_type=VALUE;_value=0;_next=NULL;}else{_type=SUB;_SubLink=NULL;_next=NULL;}}};

我们可以看到一个广义表节点的结构就定义出来了。对于HEAD类型的节点不需要_value和_SubLink这两个数据成员，但是VALUE类型的节点需要_value，而SUB类型需要_SubLink。所以可以使用联合union来把_value和_SubLink放在同一块内存，以节省空间。

（三）有了节点的结构，下面就开始定义广义表的框架。

对于广义表，我们在意的是广义表的结构，也就是说我们实现构造，拷贝构造，赋值重载，打印表，析构等函数即可。

classGeneralizedList{public:GeneralizedList(constchar*str);GeneralizedList();~GeneralizedList();GeneralizedList(constGeneralizedList&g);GeneralizedListoperator=(GeneralizedListg);size_tSize();//表中数据的个数size_tDeepth();//表的深度voidPrint();//打印表private:size_t_Size(GeneralizedNode*head);size_t_Deepth(GeneralizedNode*head);bool_IsValue(constchar&c);GeneralizedNode*_CreatList(constchar*&str);void_Print(GeneralizedNode*head);GeneralizedNode*_Copy(GeneralizedNode*head);void_Release(GeneralizedNode*head);private:GeneralizedNode*_head;};

其实广义表的结构并不难，也就是一个主表上链了一些子表。在这里我们可以把子表看作是一个主表，利用递归的特性，达到分治的效果。这样实现起来会非常的好理解。

要使用递归就不能使用公有成员函数，因为我们需要一个变量来控制递归的开始和结束。显然一个私有成员变量_head是不能实现的，所以我们要定义一些内部私有函数来实现公有函数的功能，

GeneralizedList::GeneralizedList(constchar*str){_head=_CreatList(str);}GeneralizedList::GeneralizedList():_head(NULL){}GeneralizedList::~GeneralizedList(){_Release(_head);}GeneralizedList::GeneralizedList(constGeneralizedList&g){_head=_Copy(g._head);}GeneralizedListGeneralizedList::operator=(GeneralizedListg)//不能加const和&{//if(this!=&g)//{//GeneralizedNode*tmp=_Copy(g._head);//_Release(_head);//_head=tmp;//}//return*thisswap(_head,g._head);//现代写法return*this;}voidGeneralizedList::Print(){_Print(_head);}size_tGeneralizedList::Size(){return_Size(_head);}size_tGeneralizedList::Deepth(){return_Deepth(_head);}

可以看到我们通过间接调用私有方法，不仅利用了类的封装的特性，还控制了递归的层数。

（四）下面是私有方法的实现。

voidGeneralizedList::_Release(GeneralizedNode*head){GeneralizedNode*cur=head;while(cur){GeneralizedNode*del=cur;cur=cur->_next;if(del->_type==SUB){_Release(del->_SubLink);}deletedel;}}boolGeneralizedList::_IsValue(constchar&c){if(c>='1'&&c<='9'||c>='a'&&c<='z'||c>='A'&&c<='Z'){returntrue;}returnfalse;}GeneralizedNode*GeneralizedList::_CreatList(constchar*&str){assert(*str=='(');++str;GeneralizedNode*newhead=newGeneralizedNode(HEAD);//biaozhiGeneralizedNode*cur=newhead;while(*str){if(_IsValue(*str)){GeneralizedNode*tmp=newGeneralizedNode(VALUE);tmp->_value=*str;cur->_next=tmp;cur=cur->_next;str++;}elseif(*str=='('){GeneralizedNode*subNode=newGeneralizedNode(SUB);cur->_next=subNode;cur=cur->_next;subNode->_SubLink=_CreatList(str);//如果是'('说明后面是一个子表，我们递归的创建子表，然后返回子表的头指针，将头指针链到主表上}elseif(*str==')'){str++;returnnewhead;}else{++str;}}assert(false);return_head;}voidGeneralizedList::_Print(GeneralizedNode*head){GeneralizedNode*cur=head;while(cur){if(cur->_type==HEAD){cout<<'(';}elseif(cur->_type==VALUE){cout<<cur->_value;if(cur->_next)//不为NULL打印',',防止在最后一个值后面打印一个','{cout<<',';}}else{_Print(cur->_SubLink);if(cur->_next)//(1,2,(3,4))cur为空,不打印','{cout<<',';}}cur=cur->_next;}cout<<')';}size_tGeneralizedList::_Size(GeneralizedNode*head){GeneralizedNode*cur=head;size_tsize=0;while(cur){if(cur->_type==VALUE){size++;}elseif(cur->_type==SUB){size+=_Size(cur->_SubLink);}cur=cur->_next;}returnsize;}size_tGeneralizedList::_Deepth(GeneralizedNode*head){GeneralizedNode*cur=head;size_tmaxDeep=1;while(cur){if(cur->_type==SUB){size_tdeep=_Deepth(cur->_SubLink);//最深的一层子表返回1，//每返回一层deep就会+1；if(deep+1>maxDeep){maxDeep=deep+1;}}cur=cur->_next;}returnmaxDeep;}GeneralizedNode*GeneralizedList::_Copy(GeneralizedNode*head){GeneralizedNode*cur=head->_next;GeneralizedNode*newHead=newGeneralizedNode(HEAD);GeneralizedNode*newCur=newHead;while(cur){if(cur->_type==VALUE){newCur->_next=newGeneralizedNode(VALUE);newCur=newCur->_next;newCur->_value=cur->_value;}elseif(cur->_type==SUB){newCur->_next=newGeneralizedNode(SUB);newCur=newCur->_next;newCur->_SubLink=_Copy(cur->_SubLink);//如果是子表节点，//就递归拷贝子表，将子表的头节点返回链接到SUB节点上，//通过SubLink可以找到子表}cur=cur->_next;}newCur=NULL;returnnewHead;}