广义表是数据结构中非常关键的一部分,它的学习对于树和二叉树有很大的起承作用。那么,它是怎么实现的呢?广义表的实现应用到了一个很熟悉的算法——递归。来看看它的代码吧!
#pragma once
#include<iostream>
#include<cassert>
using namespace std;
enum Type
{
HEAD,//头
VALUE, //值
SUB, //子表
};
struct GeneralizedNode
{
Type _type;
GeneralizedNode* _next;
union
{
char _value;
GeneralizedNode* _sublink;
};
GeneralizedNode(Type type=HEAD,char value=0)
:_type(type)
,_next(NULL)
{
if(_type==VALUE)
{
_value=value;
}
else if(_type==SUB)
{
_sublink=NULL;
}
}
};
class Generalized
{
public:
Generalized(const char* str)
:_head(NULL)
{
_head=_CreateList(str);
}
Generalized()
:_head(new GeneralizedNode())
{}
~ Generalized()
{
_Clear(_head);
_head=NULL;
}
size_t Depth() //深度
{
return _Depth(_head);
}
void Print()
{
_Print(_head);
cout<<endl;
}
size_t Size()
{
return _Size(_head);
}
Generalized(const Generalized &g)
{
_head=_Copy(g._head);
}
Generalized& operator=( Generalized g)
{
swap(this->_head,g._head);
return *this;
}
protected:
GeneralizedNode* _head;
GeneralizedNode* _CreateList(const char* &str)
{
assert(str && *str=='(');
++str;
GeneralizedNode* head=new GeneralizedNode(HEAD);
GeneralizedNode* cur=head;
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;
}
bool _Isvalue(char ch)
{
if( (ch>='0'&&ch<='9') || (ch>='a'&&ch<='z') || (ch>='A'&&ch<='z'))
{
return true;
}
else
{
return false;
}
}
/*int _Depth(GeneralizedNode* head)
{
GeneralizedNode* cur=head;
int max=0;
if(!cur)
{
return 1;
}
if(cur->_type==VALUE)
{
return 0;
}
for( max=0;cur;cur=cur->_next)
{
int dep=_Depth(cur->_next);
if(dep>max)
{
max=dep;
}
}
return max+1;
}*/
size_t _Depth(GeneralizedNode* head)
{
size_t dep=1;
GeneralizedNode* cur=head;
while(cur!=NULL)
{
if(cur->_type==SUB)
{
if(_Depth(cur->_sublink)+1> dep)
{
dep=_Depth(cur->_sublink)+1 ;
}
}
cur=cur->_next;
}
return dep;
}
void _Clear(GeneralizedNode* head)
{
GeneralizedNode* cur = head;
while(cur != NULL)
{
GeneralizedNode* del = cur;
cur = cur->_next;
if(del->_type == SUB)
{
_Clear(del->_sublink);
}
delete del;
}
}
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)
{
cout<<"," ;
}
}
else
{
_Print(cur->_sublink);
if(cur->_next)
{
cout<<",";
}
}
cur=cur->_next;
}
cout<<")";
}
size_t _Size(GeneralizedNode* head)
{
GeneralizedNode* cur=head;
size_t size=0;
while(cur)
{
if(cur->_type==VALUE)
{
++size;
}
else if(cur->_type==SUB)
{
size+=_Size(cur->_sublink);
}
cur=cur->_next;
}
return size;
}
GeneralizedNode* _Copy(GeneralizedNode* head)
{
GeneralizedNode* newHead=new GeneralizedNode(HEAD);
assert(head->_type==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);
}
cur=cur->_next;
}
return newHead;
}
};
代码虽然看起来很长,但是只要你理解了其结构,相信是不难的。
博主也是调试了好久的~~~~~~~~~~~~
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。