广义表的定义：

广义表是非线性的结构，是n个元素的有限序列。

举例：A=（a,b,(c,d)）

我们先定义它的结构：

（1）它有三种节点，头节点、值节点、子表节点。

（2）两种指向下一节点的指针：指向下一值值节点的指针_next，指向子表节点的指针_sublink.

enumType//用枚举形式来定义广义表中三种节点类型{HEAD,//头类型VALUE,//值类型SUB,//子表类型};structGeneralizedNode{Type_type;//类型GeneralizedNode*_next;//指向下一节点的指针union{int_value;//一个节点下一节点可能是值节点，也可能是子表节点GeneralizedNode*_sublink;};GeneralizedNode(Typetype):_next(NULL),_type(type){}GeneralizedNode(Typetype,intvalue):_next(NULL),_type(type),_value(value){}};

下面，我们来看下实现的代码：

classGeneralized{public:Generalized():_head(NULL){}Generalized(constchar*str){_head=_CreateList(str);//调用函数创建节点}Generalized(constGeneralized&gr){_head=_Copy(gr._head);//调用函数拷贝节点}Generalized&operator=(constGeneralized&gr){if(&gr!=this){_Copy(gr._head);_Destroy(_head);}return*this;}~Generalized(){_Destroy(_head);}voidPrint(){_Print(_head);}size_tSize(){return_Size(_head);}size_tDepth(){return_Depth(_head);}protected://拷贝广义表GeneralizedNode*_Copy(GeneralizedNode*grhead){GeneralizedNode*grcur=grhead;GeneralizedNode*newHead=newGeneralizedNode(HEAD);GeneralizedNode*newcur=newHead;while(grcur){if(grcur->_type==VALUE){GeneralizedNode*tmp=newGeneralizedNode(VALUE);newcur->_next=tmp;newcur=newcur->_next;newcur->_value=grcur->_value;}elseif(grcur->_type==SUB){GeneralizedNode*tmp=newGeneralizedNode(SUB);newcur->_next=tmp;newcur=newcur->_next;newcur->_sublink=_Copy(grcur->_sublink);}grcur=grcur->_next;}newcur=NULL;returnnewHead;}//释放广义表void_Destroy(GeneralizedNode*head){GeneralizedNode*cur=head;while(cur){GeneralizedNode*del=cur;cur=cur->_next;if(del->_type==SUB){_Destroy(del->_sublink);}else{deletedel;del=NULL;}}}//打印void_Print(GeneralizedNode*head){GeneralizedNode*cur=head;while(cur){if(cur->_type==HEAD){cout<<"(";}elseif(cur->_type==VALUE){cout<<(char)(cur->_value);if(cur->_next){cout<<",";}}elseif(cur->_type==SUB){_Print(cur->_sublink);if(cur->_next){cout<<",";}}cur=cur->_next;}cout<<")";}//判断是否是值bool_IsValue(constchar*str){if(*str>0&&*str<9||*str>'a'&&*str<'z'||*str>'A'&&*str<'Z'){returntrue;}else{returnfalse;}}//创建节点GeneralizedNode*_CreateList(constchar*str){assert(*str=='(');++str;GeneralizedNode*head=newGeneralizedNode(HEAD);GeneralizedNode*cur=head;while(cur){if(_IsValue(str)){cur->_next=newGeneralizedNode(VALUE,*str);cur=cur->_next;str++;}elseif(*str=='('){GeneralizedNode*SubNode=newGeneralizedNode(SUB);cur->_next=SubNode;cur=cur->_next;SubNode->_sublink=_CreateList(str);str++;}elseif(*str==')'){str++;returnhead;}else{str++;}}cout<<"广义表出错！"<<endl;assert(false);returnhead;}//大小（值节点数）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;}//深度size_t_Depth(GeneralizedNode*head){size_tdepth=1;GeneralizedNode*cur=head;while(cur){if(cur->_type==SUB){size_tcurdepth=_Depth(cur->_sublink);if(curdepth+1>depth){depth=curdepth+1;}}cur=cur->_next;}returndepth;}private:GeneralizedNode*_head;};voidTest(){Generalizedgr1("()");Generalizedgr2("(a,b,(c,d))");Generalizedgr3("(a,b,(c,(d),e))");Generalizedgr4(gr3);gr1.Print();cout<<endl;gr2.Print();cout<<endl;gr3.Print();cout<<endl;gr4.Print();cout<<endl;size_tsize=gr4.Size();cout<<"gr4大小："<<size<<endl;intdepth=gr4.Depth();cout<<"gr4深度:"<<depth<<endl;}intmain(){Test();system("pause");return0;}