广义表：非线性结构，是线性表的一种扩展，是有n个元素组成有限序列，是递归的，因为在表的描述中又得到了表，允许表中有表。

#include<cassert>#include<iostream>usingnamespacestd;enumType//枚举节点的类型{HEAD,//头结点VALUE,//有数据成员的节点SUB,//有子链的节点};template<classT>structGeneralizedNode//定义节点{Type_type;GeneralizedNode*_next;union//运用联合体使得该数据成员只含有一种节点{T_value;GeneralizedNode*_sublink;};GeneralizedNode(Typetype=HEAD,Tvalue=0)//构造节点:_type(type),_next(NULL){if(_type==VALUE){_value=value;}if(_type==SUB){_sublink=NULL;}}};template<classT>classGeneralized{public:Generalized():_head(NULL){}Generalized(constchar*str)//构造函数:_head(NULL){_head=_Creatlize(str);}Generalized(constGeneralized&g)//拷贝构造{_head=_Copy(g._head);}Generalized&operator=(constGeneralized&g)//传统写法{if(this!=&g){GeneralizedNode*temp=_Copy(g._head);_Destroy(_head);_head=temp;}return*this;}Generalized<T>&operator=(Generalizedg)//现代写法{swap(_head,g._head);return*this;}size_tSize()//求表中的结点个数{return_size(_head);}size_tDepth()//求深度{return_Depth(_head);}voidprint()//打印节点{_print(_head);}protected:boolISValue(charm){if(m>='a'&&m<='z'||m>='A'&&m<='Z'||m>='0'&&m<='9'){returntrue;}else{returnfalse;}}void_print(GeneralizedNode<T>*head)//打印节点运用递归方式进行{assert(head);GeneralizedNode<T>*cur=head;while(cur){if(cur->_type==HEAD){cout<<"("<<"";//cur=cur->_next;}elseif(cur->_type==VALUE)//如果是VALUE，则打印该节点{cout<<cur->_value;if(cur->_next==NULL){cout<<")";}else{cout<<",";}}elseif(cur->_type==SUB)//如果是SUB类型，则递归调用下一层{_print(cur->_sublink);if(cur->_next==NULL){cout<<")";}else{cout<<",";}}else{cout<<")";}cur=cur->_next;}}size_t_size(GeneralizedNode<T>*p){GeneralizedNode<T>*cur=p;intcount=0;while(cur){if(cur->_type==VALUE)//如果是VALUE，则count++{++count;}elseif(cur->_type==SUB)//如果是SUB，则调用下一层{count+=_size(cur->_sublink);}cur=cur->_next;}returncount;}int_Depth(GeneralizedNode<T>*head){GeneralizedNode<T>*cur=head;intdepth=1;while(cur){if(cur->_type==SUB){intsubdepth=_Depth(cur->_sublink);if(subdepth+1>depth){depth=subdepth+1;}}cur=cur->_next;}returndepth;}GeneralizedNode<T>*_Creatlize(constchar*&str)//构造广义表{assert(*str=='(');while(*str){if(*str=='('){GeneralizedNode<T>*_head=newGeneralizedNode<T>(HEAD);GeneralizedNode<T>*cur=_head;++str;while(*str){if(ISValue(*str)){GeneralizedNode<T>*temp=newGeneralizedNode<T>(VALUE);temp->_value=*str;cur->_next=temp;cur=cur->_next;++str;}elseif(*str=='('){GeneralizedNode<T>*sub=newGeneralizedNode<T>(SUB);sub->_sublink=_Creatlize(str);cur->_next=sub;cur=cur->_next;}elseif(*str==')'){++str;return_head;}else{++str;}}return_head;}}return_head;}GeneralizedNode<T>*_Copy(GeneralizedNode<T>*head)//拷贝{GeneralizedNode<T>*newhead=newGeneralizedNode<T>(HEAD);GeneralizedNode<T>*cur=head->_next;GeneralizedNode<T>*newcur=newhead;while(cur){if(cur->_type==VALUE){newcur->_next=newGeneralizedNode<T>(VALUE,cur->_value);newcur=newcur->_next;}elseif(cur->_type==SUB){newcur->_next=newGeneralizedNode<T>(SUB);newcur=newcur->_next;newcur->_sublink=_Copy(cur->_sublink);}cur=cur->_next;}returnnewhead;}protected:GeneralizedNode<T>*_head;};

测试代码如下：

voidtest4(){Generalized<char>a("(a,b)");Generalized<char>b("(a,(c,(f),d),b)");Generalized<char>c(a);Generalized<char>d(b);c.print();cout<<endl;d.print();cout<<endl;cout<<d.Depth()<<endl;cout<<d.Size()<<endl;}intmain(){test4();system("pause");return0;}

运行结果如下：