GeneralList-广义表：

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

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

广义表结构

protected:GeneralizedNode*_head;

节点结构

structGeneralizedNode{GeneralizedNode(Typetype=HEAD,charvalue=0):_type(type),_next(NULL){if(_type==VALUE){_value=value;}elseif(_type==SUB){_sublink=NULL;}}Type_type;GeneralizedNode*_next;union//联合（共用体）{GeneralizedNode*_sublink;char_value;};};

利用联合来实现不同节点的成员不同

enumType{HEAD,VALUE,SUB,};

构造函数：构造函数调用_CreateList函数

GeneralizedNode*_CreateList(constchar*&str)//加引用避免子表递归返回时str跳到递归之前的位置{assert(str&&*str=='(');GeneralizedNode*head=newGeneralizedNode(HEAD);GeneralizedNode*cur=head;++str;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;}

析构函数：调用_Destroy

void_Destory(GeneralizedNode*head){GeneralizedNode*cur=head;while(cur){GeneralizedNode*del=cur;//记录要删除的节点if(cur->_type==SUB){_Destory(cur->_sublink);//递归的条件：遇到SUB类型的节点}cur=cur->_next;deletedel;}}

打印函数：调用_Print

void_Print(GeneralizedNode*head){GeneralizedNode*cur=head;while(cur){if(cur->_type==HEAD)//遇到头结点，打印前括号{cout<<"(";}elseif(cur->_type==VALUE){cout<<cur->_value;if(cur->_next)//当前value节点后面不为空，打印逗号{cout<<",";}}else{_Print(cur->_sublink);//递归的条件：遇到SUB类型的节点if(cur->_next)//子表递归返回时的next不为空{cout<<",";}}cur=cur->_next;}cout<<")";//表遍历完成之后，打印表的后括号}

求广义表的size：调用_Size

size_t_Size(GeneralizedNode*head){GeneralizedNode*cur=head;size_tsize=0;while(cur){if(cur->_type==VALUE)//遇到value，size++{++size;}elseif(cur->_type==SUB){size+=_Size(cur->_sublink);//递归的条件：遇到SUB类型的节点}cur=cur->_next;}returnsize;}

求广义表的深度：调用_Depth

size_t_Depth(GeneralizedNode*head){size_tindex=1;//广义表为空时，深度为1GeneralizedNode*cur=head;while(cur){if(cur->_type==SUB){size_tsubDepth=_Depth(cur->_sublink);//递归的条件：遇到SUB类型的节点if(subDepth+1>index)//更新深度{index=subDepth+1;}}cur=cur->_next;}returnindex;}

拷贝构造函数：调用_Copy

GeneralizedNode*_Copy(GeneralizedNode*head){assert(head->_type==HEAD);//传入的是头结点才正确GeneralizedNode*newhead=newGeneralizedNode(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);//递归进入子表//递归的条件：遇到SUB类型的节点}cur=cur->_next;}returnnewhead;}

赋值操作符的重载（采用现代写法）

Generalized&operator=(Generalizedg)//现代写法{swap(_head,g._head);return*this;}