广义表是非线性结构，是线性表的一种扩展，是有N个元素组成的有限序列。

广义表的定义是递归的，因为在表的描述中又得到了表，允许表中有表。

<1>A=（）；

<2>B=（a, b）;

<3>C=（a, b,（c, d））;

<4>D=（a, b,（c, d），（e, （f）, h））

<5>E = （（（），（）））

那么广义表如何实现呢？

我们使用递归来实现它~~~~

#pragmaonce;#include<iostream>usingnamespacestd;#include<assert.h>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():_head(NULL){}Generalized(constchar*str):_head(NULL){_head=_CreateLized(str);}Generalized(constGeneralized&g){_head=_Copy(g._head);}Generalized&operator=(constGeneralized&g){if(_head!=g._head){GeneralizedNode*cur=_head;_Destory(_head);_head=_Copy(g._head);return*this;}}~Generalized(){_Destory(_head);}public:voidPrint(){_Print(_head);cout<<endl;}size_tSize(){size_tcount=_Size(_head);returncount;}size_tDepth(){size_tdep=_Depth(_head);returndep;}protected://创建表GeneralizedNode*_CreateLized(constchar*&str)//传参用引用是为了防止str在退出一层{//递归时发生回退assert(str&&*str=='(');//若当前str是不为‘（’，则传参错误str++;GeneralizedNode*head=newGeneralizedNode(HEAD);GeneralizedNode*cur=head;while(*str!='\0'){if(_Isvalue(*str)){GeneralizedNode*tmp=newGeneralizedNode(VALUE,*str);cur->_next=tmp;cur=cur->_next;str++;continue;}elseif(*str=='(')//遇到子表{GeneralizedNode*sub=newGeneralizedNode(SUB);cur->_next=sub;cur=cur->_next;sub->_sublink=_CreateLized(str);//进入递归创建子表continue;}elseif(*str==')')//一个表的结束{str++;returnhead;}else{str++;continue;}assert(false);//强制判断程序是否出错returnhead;}}//判断当前值是否为有效值bool_Isvalue(constcharc){if((c<='9'&&c>='0')||(c<='z'&&c>='a')||(c<='Z'&&c>='A')){returntrue;}else{returnfalse;}}//拷贝一个表GeneralizedNode*_Copy(GeneralizedNode*head){GeneralizedNode*Head=newGeneralizedNode(HEAD);//_head=Head;GeneralizedNode*cur=head->_next;GeneralizedNode*tmp=Head;while(cur){if(cur->_type==VALUE){tmp->_next=newGeneralizedNode(VALUE,cur->_value);cur=cur->_next;tmp=tmp->_next;}elseif(cur->_type==SUB){tmp->_next=newGeneralizedNode(SUB);//cur=cur->_next;tmp=tmp->_next;tmp->_sublink=_Copy(cur->_sublink);//进入拷贝表的递归cur=cur->_next;}}returnHead;}//打印表void_Print(GeneralizedNode*head){GeneralizedNode*cur=head;while(cur){if(cur->_type==HEAD){cout<<"("<<"";cur=cur->_next;continue;}elseif((cur->_type==VALUE)&&(cur->_next!=NULL)){cout<<cur->_value<<""<<",";cur=cur->_next;continue;}elseif((cur->_type==VALUE)&&(cur->_next==NULL))//遇到一个表的最后一个节点{cout<<cur->_value<<"";cur=cur->_next;continue;}elseif(cur->_type==SUB){_Print(cur->_sublink);//进入打印表的递归cur=cur->_next;if(cur!=NULL)//说明此时的表并不是最外层的表，需要打印‘，’{cout<<",";}continue;}}if(cur==NULL){cout<<")";return;}}//销毁表void_Destory(GeneralizedNode*head){GeneralizedNode*cur=head;while(cur){if(cur->_type==SUB){_Destory(cur->_sublink);//进入销毁表的递归}GeneralizedNode*del=cur;cur=cur->_next;deletedel;}return;}//求表的大小size_t_Size(GeneralizedNode*head){size_tcount=0;GeneralizedNode*cur=head;while(cur){if(cur->_type==VALUE){count++;cur=cur->_next;continue;}if(cur->_type==SUB){count+=_Size(cur->_sublink);//进入递归cur=cur->_next;continue;}cur=cur->_next;}returncount;}//求表的深度size_t_Depth(GeneralizedNode*head){assert(head);size_tdep=1;size_tDep=0;GeneralizedNode*cur=head;while(cur){if(cur->_type==SUB){dep+=_DepthSUB(cur->_sublink);}cur=cur->_next;if(Dep<dep)//用Dep来保存最深的深度{Dep=dep;dep=1;}}returnDep;}//求子表长度size_t_DepthSUB(GeneralizedNode*sub){GeneralizedNode*cur=sub;size_tdep=1;while(cur){if(cur->_type==SUB){dep=dep+_DepthSUB(cur->_sublink);}cur=cur->_next;}returndep;}protected:GeneralizedNode*_head;};

广义表的函数都用了递归，所以会比较绕。小伙伴们好好看，不懂可以来交流啊。写的不好多多指教~~~~