广义表是什么？如何实现广义表的递归？这篇文章运用了实例代码展示，代码非常详细，具有一定的参考价值，感兴趣的小伙伴们可以参考一下。

广义表的定义

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

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

例如

<1> A = ()

<2> B = (a,b)

<3> C = (a,b,(c,d))

<4> D = (a,b,(c,d),(e,(f),h))

<5> E =(((),())

广义表的节点结构定义：

enumType{HEAD,//头结点VALUE,//数据SUB,//子表};//广义表结构structGeneralizedNode{public://无参构造函数GeneralizedNode():_type(HEAD),_next(NULL){}//有参的构造函数GeneralizedNode(Typetype,charch);public:Type_type;GeneralizedNode*_next;//因为节点类型不可能既是数据节点又是子表结点，所以采用联合结构，//节省空间，便于管理。union{char_value;//数据结点GeneralizedNode*_subLink;//子表结点};};//有参的构造函数GeneralizedNode::GeneralizedNode(Typetype,charch=0):_type(type),_next(NULL){//数据节点则为数据初始化if(_type==VALUE){_value=ch;}//子表结点的初始化elseif(_type==SUB){_subLink=NULL;}}

广义表的定义：

注意：由于广义表的采用的是用递归实现。但构造函数，等成员函数不能够采用递归，而且在函数内部需要不断的传子表的head，对于成员函数直接使用成员变量_head,则无法递归下去。

//广义表类classGeneralized{public://无参构造函数Generalized():_head(newGeneralizedNode(HEAD)){}//有参构造函数Generalized(constchar*str):_head(NULL){_head=CreateList(str);}//拷贝构造函数Generalized(constGeneralized&g){_head=_CopyList(g._head);}GeneralizedNode*_CopyList(GeneralizedNode*head);//赋值运算符的重载Generalized&operator=(Generalizedg){swap(_head,g._head);return*this;}//析构函数~Generalized(){_Delete(_head);}void_Delete(GeneralizedNode*head);public://打印广义表voidPrint(){_Print(_head);}//求广义表的大小size_tSize(){return_Size(_head);}//求广义表的深度size_tDepth(){return_Depth(_head);}protected://判断数据是否有效boolIsVaild(constcharch);//创建广义表GeneralizedNode*CreateList(constchar*&str);void_Print(GeneralizedNode*head);size_t_Size(GeneralizedNode*head);size_t_Depth(GeneralizedNode*head);private:GeneralizedNode*_head;};

函数的实现

GeneralizedNode*Generalized::_CopyList(GeneralizedNode*head){GeneralizedNode*cur=head;//需要拷贝的广义表的当前节点GeneralizedNode*_head=newGeneralizedNode();//拷贝广义表的头结点GeneralizedNode*index=_head;//拷贝广义表的当前节点while(cur){//数据结点if(cur->_type==VALUE){index->_next=newGeneralizedNode(VALUE,cur->_value);index=index->_next;}//子表结点，递归复制elseif(cur->_type==SUB){GeneralizedNode*SubNode=newGeneralizedNode(SUB);index->_next=SubNode;SubNode->_subLink=_CopyList(cur->_subLink);index=index->_next;}cur=cur->_next;}return_head;}voidGeneralized::_Delete(GeneralizedNode*head){GeneralizedNode*cur=head;while(cur){GeneralizedNode*del=cur;//递归删除子表if(cur->_type==SUB){_Delete(cur->_subLink);}cur=cur->_next;deletedel;}}//判断广义表的数据是否合法boolGeneralized::IsVaild(constcharch){if((ch>='0'&&ch<='9')||(ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')){returntrue;//合法}returnfalse;//非法}GeneralizedNode*Generalized::CreateList(constchar*&str){assert(str&&*str=='(');//断言防止传的广义表格式不对，或者为空str++;//跳过第一个(GeneralizedNode*head=newGeneralizedNode();//创建头结点GeneralizedNode*cur=head;while(*str){if(IsVaild(*str)){cur->_next=newGeneralizedNode(VALUE,*str);cur=cur->_next;str++;}elseif(*str=='(')//新的子表{GeneralizedNode*SubNode=newGeneralizedNode(SUB);SubNode->_subLink=CreateList(str);cur->_next=SubNode;cur=cur->_next;}elseif(*str==')')//广义表结束{str++;//返回之前需要给str++指向下一个returnhead;}else//空格或者逗号{str++;}}assert(false);returnNULL;}voidGeneralized::_Print(GeneralizedNode*head){GeneralizedNode*cur=head;if(cur==NULL){cout<<"()"<<endl;return;}while(cur){if(cur->_type==HEAD){cout<<"(";}elseif(cur->_type==VALUE){cout<<cur->_value;//_value不是最后一个值if(cur->_next){cout<<",";}}elseif(cur->_type==SUB){_Print(cur->_subLink);if(cur->_next){cout<<",";}}cur=cur->_next;}//输出每个表最后一个(cout<<")";}size_tGeneralized::_Size(GeneralizedNode*head){GeneralizedNode*cur=head;size_tcount=0;while(cur){if(cur->_type==VALUE){count++;}//递归求取子表的大小if(cur->_type==SUB){count=count+_Size(cur->_subLink);}cur=cur->_next;}returncount;}size_tGeneralized::_Depth(GeneralizedNode*head){GeneralizedNode*cur=head;size_tdepth=1;//空表深度为1while(cur){if(cur->_type==SUB){size_tnewDepth=_Depth(cur->_subLink);//如果子表的深度+1大于当前广义表的最大深度，则更新广义表的深度if(newDepth+1>depth){depth=newDepth+1;}}cur=cur->_next;}returndepth;}

测试代码

#include"Generalized.h"voidTestGeneralized(){Generalizedl("(a,b,(c,d),(e,(f),h))");Generalizedl1;l1=l;l.Print();cout<<endl;cout<<"size:"<<l.Size()<<endl;cout<<"depth:"<<l.Depth()<<endl;l1.Print();cout<<endl;cout<<"size:"<<l1.Size()<<endl;cout<<"depth:"<<l1.Depth()<<endl;}intmain(){TestGeneralized();getchar();return0;}

测试结果

以上就是实现广义表的递归的具体操作，代码应该是足够清楚的，而且我也相信有相当的一些例子可能是我们日常工作可能会见得到的。通过这篇文章，希望你能收获更多。