最近学习了广义表，我们知道广义表也是一种线性表，而顾名思义广义表就是不止一个表，下面来举个栗子：

A=( )

B=（1 , 2，3）

C=(1 ,2 ,3, ( a , b ,c) )

D=(1, 2, 3, (a,( b,c),d),4)

以上A,B,C,D都是广义表，只不过深度不一样，也就是括号的对数不一样，A是个特殊的广义表，即空表。B里面有三个元素，C里面有6个元素，包括一个子表（a，b，c），C也同理，只不过多了一层子表。由此可总结为一句话：表里有表

这样看可能不太直观，下面以广义表C为例来看一下它的结构图：

（图画得有点丑，不要吐槽我）

每当遇到一个前括号，就要创建一个子表，直到遇见收括号。

那么如何创建一个广义表呢，在创建节点结构体的时候，我们要考虑每个节点的类型，有可能是头结

点，也有可能是子表节点，也有可能是普通的值节点，所以在构造节点的时候就要定义一个三元体，由

于是表里有表，我们可以用递归的方法来解决广义表的问题，每个子表都可以递归为一个子问题，就可

以很轻松的解决掉这个问题了。

下面是具体实现的代码：

先构造一个三元结构体：

enumType{HEAD,VALUE,SUB,};template<classT>structGeneralizedNode{Type_type;GeneralizedNode<T>*_next;union{char_value;GeneralizedNode<T>*_sublink;//子表的头结点};public:GeneralizedNode(Typetype=HEAD,charvalue='\0'):_type(type),_next(NULL){if(type==VALUE){_value=value;}elseif(type==SUB){_sublink=NULL;}}};

下面来构造一个广义表类

template<classT>classGeneralizedList{public:GeneralizedList():_head(newGeneralizedNode<T>(HEAD)){}GeneralizedList(constchar*str){_head=_CreateList(str);}GeneralizedList(constGeneralizedList&g)//拷贝构造{_head=Copy(g._head;)}size_tSize(){returnsize(_head);}size_tdepth(){returnDepth(_head);}voidprint(){Print(_head);}protected:GeneralizedNode<T>*_CreateList(constchar*&str){assert(str&&*str=='(');++str;GeneralizedNode<T>*Head=newGeneralizedNode<T>(HEAD,NULL);GeneralizedNode<T>*cur=Head;while(*str){if(_IsValue(*str)){cur->_next=newGeneralizedNode<T>(VALUE,*str);cur=cur->_next;str++;}elseif(*str=='('){GeneralizedNode<T>*newNode=newGeneralizedNode<T>(SUB);//将一个子表结点加入到链表中cur->_next=newNode;cur=cur->_next;cur->_sublink=_CreateList(str);str++;//递归创建一个子表结点}elseif(*str==')')//表示一个表已经结束{str++;returnHead;}else{str++;//不需要处理的情况}}assert(false);returnHead;}size_tDepth(GeneralizedNode<T>*head){GeneralizedNode<T>*cur=head;size_tdepth=1;while(cur){if(cur->_type==SUB){size_tsubdepth=Depth(cur->_sublink);if(subdepth+1>depth){depth=subdepth;//保存较大的深度}}cur=cur->_next;}returndepth;}size_tsize(GeneralizedNode<T>*head){GeneralizedNode<T>*cur=head;size_tcount=0;while(cur){if(cur->_type!=SUB){count++;}else{count+=size(cur->_sublink);}cur=cur->_next;}returncount;}voidPrint(GeneralizedNode<T>*head){GeneralizedNode<T>*cur=head;while(cur){if(cur->_type==HEAD){cout<<'(';}elseif(cur->_type==VALUE){cout<<cur->_value;if(cur->_next!=NULL){cout<<',';}}elseif(cur->_type==SUB){Print(cur->_sublink);if(cur->_next!=NULL){cout<<',';}}cur=cur->_next;}cout<<')';}bool_IsValue(charch)//检查是否为合法值{if((ch>='0'&&ch<='9')||(ch>='a'&&ch<='z')||(ch>='A'&&ch<='Z')){returntrue;}returnfalse;}protected:GeneralizedNode<T>*_head;};

下面给出测试代码：

#include"Generalized.h"voidTest(){char*ch="(a,b,c,(1,2),c)";GeneralizedList<char>gl1(ch);gl1.print();cout<<endl;cout<<"广义表深度为："<<gl1.depth()<<endl;cout<<"广义表大小为："<<gl1.Size()<<endl;}intmain(){Test();getchar();return0;}

运行结果：

以上就是C++实现广义表的方法啦，里面也许还存在着一些问题，希望大家能够指正出来，共同促进学习。