广义表(Lists，又称列表)是一种非线性的数据结构，是线性表的一种推广。即广义表中放松对表元素的原子限制，容许它们具有其自身结构。

思想：广义表就类似下图的结构，他的大体（下图第一行）相当于一个带头结点的链表，

代码思想，首先要有一个头结点为HEAD类型，每一个广义表有且只有一个HEAD，而后每个节点如果有分支则把它定义为SUB类型，SUB便是它分支的一个新头他有一个sublink指针指向他的第一个元素，如果没有则是VALUE类型。

#pragmaonce#include<iostream>#include<assert.h>usingnamespacestd;enumType{HEAD,VALUE,SUB};structgeneralizelistNode{generalizelistNode*_next;Type_type;union{char_value;generalizelistNode*sublink;};generalizelistNode(Typetype=HEAD,charvalue=0):_type(type),_value(value),_next(NULL){}};classGeneralizelist{protected:boolisvalue(charc){if(c>='a'&&c<='z'||c>='A'&&c<='Z'||c>='0'&&c<='9'){returntrue;}else{returnfalse;}}public:Generalizelist(char*&str){_head=generallist(str);}~Generalizelist(){Empty(_head);}voidPrint(){_Print(_head);}Generalizelist&operator=(Generalizelistg){swap(_head,g._head);}Generalizelist(Generalizelist&g){_head=copy(g._head);}intSize(){return_Size(_head);}intDepth(){return_Depth(_head);}protected:generalizelistNode*generallist(char*&str){assert(*str=='(');generalizelistNode*head=newgeneralizelistNode(HEAD);generalizelistNode*cur=head;str++;while(*str){if(isvalue(*str)){generalizelistNode*Node=newgeneralizelistNode(VALUE,*str);cur->_next=Node;cur=Node;str++;}elseif(*str=='('){generalizelistNode*sub=newgeneralizelistNode(SUB);cur->_next=sub;cur=sub;sub->sublink=generallist(str);}elseif(*str==')'){++str;returnhead;}else{str++;}}}void_Print(generalizelistNode*head){generalizelistNode*cur=head;while(cur){if(cur->_type==HEAD){cout<<'(';}elseif(cur->_type==VALUE){cout<<cur->_value;if(cur->_next){cout<<",";}}else{_Print(cur->sublink);}cur=cur->_next;}cout<<")";}generalizelistNode*copy(generalizelistNode*&_cur){generalizelistNode*cur=_cur;generalizelistNode*newhead=newgeneralizelistNode(HEAD);generalizelistNode*tmp=newhead;cur=cur->_next;while(cur){if(cur->_type==VALUE){generalizelistNode*node=newgeneralizelistNode(VALUE,cur->_value);tmp->_next=node;tmp=node;cur=cur->_next;}else{generalizelistNode*node=newgeneralizelistNode(SUB);tmp->_next=node;tmp=node;tmp->sublink=copy(cur->sublink);cur=cur->_next;}}returnnewhead;}voidEmpty(generalizelistNode*&head){generalizelistNode*tmp=head;head=head->_next;deletetmp;while(head){if(head->_type==VALUE){generalizelistNode*tmp=head;head=head->_next;deletetmp;}elseif(head->_type==SUB){generalizelistNode*tmp=head;Empty(tmp->sublink);head=head->_next;}}}int_Size(generalizelistNode*&cur){intcount=0;generalizelistNode*tmp=cur;while(tmp){if(tmp->_type==VALUE){count++;tmp=tmp->_next;}elseif(tmp->_type==SUB){count+=_Size(tmp->sublink);tmp=tmp->_next;}else{tmp=tmp->_next;}}returncount;}int_Depth(generalizelistNode*&cur){generalizelistNode*tmp=cur;intdepth=1;while(tmp){intsub_depth=1;if(tmp->_type==SUB){sub_depth=_Depth(tmp->sublink);tmp=tmp->_next;if(sub_depth+1>depth){depth+=sub_depth;}}else{tmp=tmp->_next;}}returndepth;}private:generalizelistNode*_head;};voidTest(){char*str1="(a,b,(c,d),e,f)";GeneralizelistT1(str1);T1.Print();GeneralizelistT2(T1);cout<<endl;T2.Print();cout<<endl;GeneralizelistT3=T2;T3.Print();cout<<endl;cout<<T3.Size()<<endl;cout<<T3.Depth()<<endl;}#include"GeneralizeList.h"intmain(){Test();return0;}