广义表的C++简单实现(广义表,数据,结构,编程语言)

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

#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; }};

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

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