广义表是我第一次用递归接触链式的数据结构，其结构如下：

HEAD->VAL->VAL->LINK(->HEAD.....)->VAL->......

在这里，我们的头结点与link节点是不存储数据的，由此我们便可以定义出节点的数据结构：

typedefintDataType;enumNodeType//枚举类型定义节点类型{HEAD,VALUE,SUB,};structGeneralizedNode{public:GeneralizedNode():_next(NULL),_link(NULL){}NodeType_type;GeneralizedNode*_next;union//因为link与value是不可能同时存在的，故用共同体节省空间{GeneralizedNode*_link;DataType_value;};};

因为广义表是链式的嵌套结构，所以我们必须用递归来进行遍历，这里面递归的方式有很多种，可以循环套递归，也可以递归套递归，也可以递归套循环，根据我们不同的需求，可以吧这三种方法都运用在合适的地方，这里，我简单的实现了，返回对象的层数，数据个数，以及一些常用的成员函数，其代码如下：

classGeneralized{public:Generalized():_head(NULL){}Generalized(constchar*str)//构造函数是用字符串来体现广义表如（1,2，（2,3））{//这样可以更好的体现出广义表的结构_head=_CreatList(str);}~Generalized(){_Destory(_head);}voidPrint()//控制台打印广义表，也是打印出字符串类型{_Print(_head);}Generalized(constGeneralized&g){_head=_Copy(g._head);}Generalized&operator=(Generalizedg){swap(_head,g._head);return*this;}size_tDepth(){return_Depth(_head);}size_tSize(){size_tsize=0;_Size(_head,size);returnsize;}protected:size_t_Depth(GeneralizedNode*head){size_tdepth=1;GeneralizedNode*cur=head;while(cur){if(cur->_type==SUB){size_tnewdepth=_Depth(cur->_link)+1;depth=depth<newdepth?newdepth:depth;}cur=cur->_next;}returndepth;}void_Size(GeneralizedNode*head,size_t&size){GeneralizedNode*cur=head;while(cur){if(cur->_type==VALUE)++size;elseif(cur->_type==SUB)_Size(cur->_link,size);cur=cur->_next;}}GeneralizedNode*_Copy(GeneralizedNode*head){GeneralizedNode*cur=head;GeneralizedNode*newHead=newGeneralizedNode;GeneralizedNode*tail=newHead;tail->_type=HEAD;while(cur){if(cur->_type==SUB){tail->_next=newGeneralizedNode;tail=tail->_next;tail->_type=SUB;tail->_link=_Copy(cur->_link);}elseif(cur->_type==VALUE){tail->_next=newGeneralizedNode;tail=tail->_next;tail->_type=VALUE;tail->_value=cur->_value;}cur=cur->_next;}returnnewHead;}void_Print(GeneralizedNode*head){GeneralizedNode*cur=head;while(cur){if(cur->_type==HEAD){cout<<"(";}elseif(cur->_type==VALUE){cout<<cur->_value;if(cur->_next!=NULL&&cur->_next->_type==VALUE)cout<<",";}else_Print(cur->_link);cur=cur->_next;}cout<<")";}GeneralizedNode*_CreatList(constchar*&str){assert('('==*str);GeneralizedNode*head=newGeneralizedNode;GeneralizedNode*cur=head;head->_type=HEAD;while(*++str){if(IsValue(str)){cur->_next=newGeneralizedNode;cur=cur->_next;cur->_type=VALUE;cur->_value=*str;str++;}elseif(')'==*str){returnhead;}elseif('('){cur->_next=newGeneralizedNode;cur=cur->_next;cur->_type=SUB;cur->_link=_CreatList(str);}cur->_next=NULL;*str++;}returnhead;}boolIsValue(constchar*str)//判断表内存储数据是否为所需数据类型{if(*str<='9'&&*str>='0')returntrue;returnfalse;}void_Destory(GeneralizedNode*head){GeneralizedNode*cur=head;if(cur->_value==SUB)_Destory(cur->_link);elseif(cur->_next!=NULL)_Destory(cur->_next);deletecur;}protected:GeneralizedNode*_head;};

如有什么不足或疑问希望提出。