广义表的定义：

广义表是非线性的结构，是n个元素的有限序列。

举例：A=（a,b,(c,d)）

我们先定义它的结构：

（1）它有三种节点，头节点、值节点、子表节点。

（2）两种指向下一节点的指针：指向下一值值节点的指针_next，指向子表节点的指针_sublink.

enumType//用枚举形式来定义广义表中三种节点类型
{
HEAD,//头类型
VALUE,//值类型
SUB,//子表类型
};

structGeneralizedNode
{
Type_type;//类型
GeneralizedNode*_next;//指向下一节点的指针
union
{
int_value;//一个节点下一节点可能是值节点，也可能是子表节点
GeneralizedNode*_sublink;
};

GeneralizedNode(Typetype)
:_next(NULL),_type(type)
{}

GeneralizedNode(Typetype,intvalue)
:_next(NULL),_type(type),_value(value)
{}
};

下面，我们来看下实现的代码：

classGeneralized
{
public:
Generalized()
:_head(NULL)
{}

Generalized(constchar*str)
{
_head=_CreateList(str);//调用函数创建节点
}

Generalized(constGeneralized&gr)
{
_head=_Copy(gr._head);//调用函数拷贝节点
}

Generalized&operator=(constGeneralized&gr)
{
if(&gr!=this)
{
_Copy(gr._head);
_Destroy(_head);
}
return*this;
}

~Generalized()
{
_Destroy(_head);
}

voidPrint()
{
_Print(_head);
}

size_tSize()
{
return_Size(_head);
}

size_tDepth()
{
return_Depth(_head);
}

protected:
//拷贝广义表
GeneralizedNode*_Copy(GeneralizedNode*grhead)
{
GeneralizedNode*grcur=grhead;

GeneralizedNode*newHead=newGeneralizedNode(HEAD);
GeneralizedNode*newcur=newHead;

while(grcur)
{
if(grcur->_type==VALUE)
{
GeneralizedNode*tmp=newGeneralizedNode(VALUE);
newcur->_next=tmp;
newcur=newcur->_next;
newcur->_value=grcur->_value;
}

elseif(grcur->_type==SUB)
{
GeneralizedNode*tmp=newGeneralizedNode(SUB);
newcur->_next=tmp;
newcur=newcur->_next;
newcur->_sublink=_Copy(grcur->_sublink);
}
grcur=grcur->_next;
}
newcur=NULL;
returnnewHead;
}

//释放广义表
void_Destroy(GeneralizedNode*head)
{
GeneralizedNode*cur=head;
while(cur)
{
GeneralizedNode*del=cur;
cur=cur->_next;
if(del->_type==SUB)
{
_Destroy(del->_sublink);
}
else
{
deletedel;
del=NULL;
}
}
}

//打印
void_Print(GeneralizedNode*head)
{
GeneralizedNode*cur=head;
while(cur)
{
if(cur->_type==HEAD)
{
cout<<"(";
}
elseif(cur->_type==VALUE)
{
cout<<(char)(cur->_value);
if(cur->_next)
{
cout<<",";
}
}
elseif(cur->_type==SUB)
{
_Print(cur->_sublink);
if(cur->_next)
{
cout<<",";
}
}
cur=cur->_next;
}
cout<<")";
}

//判断是否是值
bool_IsValue(constchar*str)
{
if(*str>0&&*str<9
||*str>'a'&&*str<'z'
||*str>'A'&&*str<'Z')
{
returntrue;
}
else
{
returnfalse;
}
}

//创建节点
GeneralizedNode*_CreateList(constchar*str)
{
assert(*str=='(');
++str;
GeneralizedNode*head=newGeneralizedNode(HEAD);
GeneralizedNode*cur=head;
while(cur)
{
if(_IsValue(str))
{
cur->_next=newGeneralizedNode(VALUE,*str);
cur=cur->_next;
str++;
}
elseif(*str=='(')
{
GeneralizedNode*SubNode=newGeneralizedNode(SUB);
cur->_next=SubNode;
cur=cur->_next;
SubNode->_sublink=_CreateList(str);
str++;
}
elseif(*str==')')
{
str++;
returnhead;
}
else
{
str++;
}
}
cout<<"广义表出错！"<<endl;
assert(false);
returnhead;
}

//大小（值节点数）
size_t_Size(GeneralizedNode*head)
{
GeneralizedNode*cur=head;
size_tsize=0;
while(cur)
{
if(cur->_type==VALUE)
{
size++;
}
elseif(cur->_type==SUB)
{
size+=_Size(cur->_sublink);
}
cur=cur->_next;
}
returnsize;
}

//深度
size_t_Depth(GeneralizedNode*head)
{
size_tdepth=1;
GeneralizedNode*cur=head;
while(cur)
{
if(cur->_type==SUB)
{
size_tcurdepth=_Depth(cur->_sublink);

if(curdepth+1>depth)
{
depth=curdepth+1;
}
}
cur=cur->_next;
}
returndepth;
}

private:
GeneralizedNode*_head;
};

voidTest()
{
Generalizedgr1("()");
Generalizedgr2("(a,d))");
Generalizedgr3("(a,(d),e))");
Generalizedgr4(gr3);
gr1.Print();
cout<<endl;
gr2.Print();
cout<<endl;

gr3.Print();
cout<<endl;

gr4.Print();
cout<<endl;

size_tsize=gr4.Size();
cout<<"gr4大小："<<size<<endl;
intdepth=gr4.Depth();
cout<<"gr4深度:"<<depth<<endl;
}

intmain()
{
Test();
system("pause");
return0;
}