广义表是数据结构中非常关键的一部分，它的学习对于树和二叉树有很大的起承作用。那么，它是怎么实现的呢？广义表的实现应用到了一个很熟悉的算法——递归。来看看它的代码吧！

#pragmaonce#include<iostream>#include<cassert>usingnamespacestd;enumType{HEAD,//头VALUE,//值SUB,//子表};structGeneralizedNode{Type_type;GeneralizedNode*_next;union{char_value;GeneralizedNode*_sublink;};GeneralizedNode(Typetype=HEAD,charvalue=0):_type(type),_next(NULL){if(_type==VALUE){_value=value;}elseif(_type==SUB){_sublink=NULL;}}};classGeneralized{public:Generalized(constchar*str):_head(NULL){_head=_CreateList(str);}Generalized():_head(newGeneralizedNode()){}~Generalized(){_Clear(_head);_head=NULL;}size_tDepth()//深度{return_Depth(_head);}voidPrint(){_Print(_head);cout<<endl;}size_tSize(){return_Size(_head);}Generalized(constGeneralized&g){_head=_Copy(g._head);}Generalized&operator=(Generalizedg){swap(this->_head,g._head);return*this;}protected:GeneralizedNode*_head;GeneralizedNode*_CreateList(constchar*&str){assert(str&&*str=='(');++str;GeneralizedNode*head=newGeneralizedNode(HEAD);GeneralizedNode*cur=head;while(*str){if(_Isvalue(*str)){cur->_next=newGeneralizedNode(VALUE,*str);cur=cur->_next;str++;}elseif(*str=='('){cur->_next=newGeneralizedNode(SUB);cur=cur->_next;cur->_sublink=_CreateList(str);}elseif(*str==')'){++str;returnhead;}else{++str;}}assert(false);returnhead;}bool_Isvalue(charch){if((ch>='0'&&ch<='9')||(ch>='a'&&ch<='z')||(ch>='A'&&ch<='z')){returntrue;}else{returnfalse;}}/*int_Depth(GeneralizedNode*head){GeneralizedNode*cur=head;intmax=0;if(!cur){return1;}if(cur->_type==VALUE){return0;}for(max=0;cur;cur=cur->_next){intdep=_Depth(cur->_next);if(dep>max){max=dep;}}returnmax+1;}*/size_t_Depth(GeneralizedNode*head){size_tdep=1;GeneralizedNode*cur=head;while(cur!=NULL){if(cur->_type==SUB){if(_Depth(cur->_sublink)+1>dep){dep=_Depth(cur->_sublink)+1;}}cur=cur->_next;}returndep;}void_Clear(GeneralizedNode*head){GeneralizedNode*cur=head;while(cur!=NULL){GeneralizedNode*del=cur;cur=cur->_next;if(del->_type==SUB){_Clear(del->_sublink);}deletedel;}}void_Print(GeneralizedNode*head){GeneralizedNode*cur=head;while(cur){if(cur->_type==HEAD){cout<<"(";}elseif(cur->_type==VALUE){cout<<cur->_value;if(cur->_next){cout<<",";}}else{_Print(cur->_sublink);if(cur->_next){cout<<",";}}cur=cur->_next;}cout<<")";}size_t_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;}GeneralizedNode*_Copy(GeneralizedNode*head){GeneralizedNode*newHead=newGeneralizedNode(HEAD);assert(head->_type==HEAD);GeneralizedNode*cur=head->_next;GeneralizedNode*newcur=newHead;while(cur){if(cur->_type==VALUE){newcur->_next=newGeneralizedNode(VALUE,cur->_value);newcur=newcur->_next;}elseif(cur->_type==SUB){newcur->_next=newGeneralizedNode(SUB);newcur=newcur->_next;newcur->_sublink=_Copy(cur->_sublink);}cur=cur->_next;}returnnewHead;}};

代码虽然看起来很长，但是只要你理解了其结构，相信是不难的。

博主也是调试了好久的~~~~~~~~~~~~