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

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为例来看一下它的结构图：

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

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

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

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

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

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

下面是具体实现的代码：

先构造一个三元结构体：

enum Type{	HEAD,	VALUE,	SUB,};template
     
      struct GeneralizedNode{	Type _type;	GeneralizedNode
      
       * _next;	union	{		char _value;		GeneralizedNode
       
        * _sublink;   //子表的头结点	};public:	GeneralizedNode(Type type = HEAD,char value = '\0')		:_type(type)		,_next(NULL)	{			if (type == VALUE)			{				_value = value;			}			else if (type == SUB)			{				_sublink = NULL;			}		}};
       
      
     

下面来构造一个广义表类

template
     
      class GeneralizedList{public:	GeneralizedList()		:_head(new GeneralizedNode
      
       (HEAD))	{}	GeneralizedList(const char* str)	{		_head=_CreateList(str);	}	GeneralizedList(const GeneralizedList& g)    //拷贝构造	{		_head = Copy(g._head;)	}	size_t Size()	{		return size(_head);	}	size_t depth()	{		return Depth(_head);	}		void print()	{		Print(_head);	}protected:	GeneralizedNode
       
        * _CreateList(const char*& str)	{		assert(str && *str == '(');			++str;		GeneralizedNode
        
         * Head = new GeneralizedNode
         
          (HEAD,NULL);		GeneralizedNode
          
           * cur = Head; while (*str) { if (_IsValue(*str)) { cur->_next = new GeneralizedNode
           
            (VALUE,*str); cur = cur->_next; str++; } else if (*str == '(') { GeneralizedNode
            
             * newNode= new GeneralizedNode
             
              (SUB);        //将一个子表结点加入到链表中 cur->_next = newNode; cur = cur->_next; cur->_sublink = _CreateList(str); str++;//递归创建一个子表结点 } else if (*str == ')')               //表示一个表已经结束 { str++; return Head; } else { str++;     //不需要处理的情况 } } assert(false); return Head; } size_t Depth(GeneralizedNode
              
               * head) { GeneralizedNode
               
                * cur = head; size_t depth = 1; while (cur) { if (cur->_type == SUB) { size_t subdepth = Depth(cur->_sublink); if (subdepth+1 > depth) { depth=subdepth;//保存较大的深度 } } cur = cur->_next; } return depth; } size_t size(GeneralizedNode
                
                 * head) { GeneralizedNode
                 
                  * cur = head; size_t count = 0; while (cur) { if (cur->_type != SUB) { count++; } else { count += size(cur->_sublink); } cur = cur->_next; } return count; } 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 != NULL) { cout << ',' ; } } else if (cur->_type == SUB) { Print(cur->_sublink); if (cur->_next != NULL) { cout << ','; } } cur = cur->_next; } cout << ')'; } bool _IsValue(char ch)   //检查是否为合法值 { if ((ch >= '0'&&ch<='9') || (ch>='a'&&ch<='z') || (ch>='A'&&ch <= 'Z')) { return true; } return false; }protected: GeneralizedNode
                    
                     * _head;};
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     

下面给出测试代码：

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

运行结果：

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