GeneralList-广义表：
广义表是非线性的结构，是线性表的一种扩展，是有n个元素组成有限序列。
广义表的定义是递归的，因为在表的描述中又得到了表，允许表中有表。
广义表结构
计算
安全
数据库
网络和加速
企业服务
protected:
GeneralizedNode* _head;节点结构
struct GeneralizedNode
{
GeneralizedNode(Type type=HEAD,char value=0)
:_type(type)
,_next(NULL)
{
if(_type==VALUE)
{
_value=value;
}
else if(_type==SUB)
{
_sublink=NULL;
}
}
Type _type;
GeneralizedNode* _next;
union//联合（共用体）
{
GeneralizedNode* _sublink;
char _value;
};
};利用联合来实现不同节点的成员不同
enum Type
{
HEAD,
VALUE,
SUB,
};构造函数：构造函数调用_CreateList函数
GeneralizedNode* _CreateList(const char*& str)//加引用避免子表递归返回时str跳到递归之前的位置
{
assert(str&&*str=='(');
GeneralizedNode* head=new GeneralizedNode(HEAD);
GeneralizedNode* cur = head;
++str;
while(*str)
{
if(IsValue(*str))
{
cur->_next=new GeneralizedNode(VALUE,*str);
cur=cur->_next;
++str;
}
else if(*str=='(')
{
cur->_next=new GeneralizedNode(SUB);
cur=cur->_next;
cur->_sublink=_CreateList(str);
}
else if(*str==')')
{
++str;
return head;
}
else
{
++str;//遇见其他字符直接跳过
}
}
assert(false);
return head;
}析构函数：调用_Destroy
void _Destory(GeneralizedNode* head)
{
GeneralizedNode* cur=head;
while(cur)
{
GeneralizedNode* del=cur;//记录要删除的节点
if(cur->_type==SUB)
{
_Destory(cur->_sublink);//递归的条件：遇到SUB类型的节点
}
cur=cur->_next;
delete del;
}
}打印函数：调用_Print
void _Print(GeneralizedNode* head)
{
GeneralizedNode* cur=head;
while(cur)
{
if(cur->_type==HEAD)//遇到头结点，打印前括号
{
cout<<"(";
}
else if(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_t size=0;
while(cur)
{
if(cur->_type==VALUE)//遇到value，size++
{
++size;
}
else if(cur->_type==SUB)
{
size+=_Size(cur->_sublink);//递归的条件：遇到SUB类型的节点
}
cur=cur->_next;
}
return size;
}求广义表的深度：调用_Depth
size_t _Depth(GeneralizedNode* head)
{
size_t index=1;//广义表为空时，深度为1
GeneralizedNode* cur=head;
while(cur)
{
if(cur->_type==SUB)
{
size_t subDepth=_Depth(cur->_sublink);//递归的条件：遇到SUB类型的节点
if(subDepth+1>index)//更新深度
{
index=subDepth+1;
}
}
cur=cur->_next;
}
return index;
}拷贝构造函数：调用_Copy
GeneralizedNode* _Copy(GeneralizedNode* head)
{
assert(head->_type==HEAD);//传入的是头结点才正确
GeneralizedNode* newhead=new GeneralizedNode(HEAD);//构造新广义表的头结点
GeneralizedNode* cur=head->_next;
GeneralizedNode* newcur=newhead;
while(cur)
{
if(cur->_type==VALUE)
{
newcur->_next=new GeneralizedNode(VALUE,cur->_value);
newcur=newcur->_next;
}
else if(cur->_type==SUB)
{
newcur->_next=new GeneralizedNode(SUB);
newcur=newcur->_next;
newcur->_sublink=_Copy(cur->_sublink);//递归进入子表
//递归的条件：遇到SUB类型的节点
}
cur=cur->_next;
}
return newhead;
}赋值操作符的重载（采用现代写法）
Generalized& operator=(Generalized g)//现代写法
{
swap(_head,g._head);
return *this;
}亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
