广义表的实现

#pragma once

enum Type
{
 HEAD,
 SUB,
 VALUE
};

struct GeneralListNode
{
  GeneralListNode(Type type)
     :_type(type)
     ,_next(NULL)
     ,_SubLink(NULL)
  {}
  GeneralListNode(Type type,char s)
     :_type(type)
     ,_next(NULL)
      ,_value(s)
  {}
 Type _type;
 GeneralListNode * _next;

 union
 {
    char _value;
    GeneralListNode *_SubLink;
 };
};

class GeneralList
{
public:
    GeneralList()
        :_head(NULL)
    {}
    GeneralList(char *s)
    {
        _head = _CreatGeneralList(s);
    }
    void Print()
    {
        _Print(_head);
        cout<<endl;
    }
    size_t size()
    {
        return _size(_head);
    }
    GeneralList(const GeneralList &g)
    {
        _head = _Copy(g._head);

    }
//     GeneralList operator=(const GeneralList &g)
//     {
//         if(this != &g)
//         {
//             this->_Destroy(_head);
//             _head = _Copy(g._head);
//         }
//         return *this;
//     }
    GeneralList& operator=(GeneralList g)
    {
        swap(_head,g._head);
        return *this;
    }
    ~GeneralList()
    {
        _Destroy(_head);
    }
    size_t Depth()
    {
        return _Depth(_head);
    }
protected:
    size_t _Depth(GeneralListNode *head)
    {
        GeneralListNode *cur = head;
        size_t dep = 1;
        while(cur)
        {
            if(cur->_type == SUB)
            {
                size_t SubDep = _Depth(cur->_SubLink);
                if (SubDep+1 > dep)
                {
                    dep = SubDep + 1;
                }
            }
            cur = cur->_next;
        }
        return dep;
    }
    GeneralListNode * _Copy(GeneralListNode* head)
    {
        assert(head);
        GeneralListNode *newHead = new GeneralListNode(HEAD);
        GeneralListNode *cur =head->_next;
        GeneralListNode *newCur = newHead;

        while(cur)
        {
            if(cur->_type == VALUE)
            {
                newCur->_next = new GeneralListNode(VALUE,cur->_value);
                newCur = newCur->_next;
            }
            else if(cur->_type == SUB)
            {
                newCur->_next = new GeneralListNode(SUB);
                newCur = newCur->_next;

                newCur->_SubLink = _Copy(cur->_SubLink);
            }
            cur =cur->_next;
        }
        return newHead;
    }
    void _Destroy(GeneralListNode *head)
    {
        GeneralListNode* cur = head;

        while(cur)
        {

            GeneralListNode *del = cur;
            cur = cur->_next;

            if(del->_type == SUB)
            {
                _Destroy(del->_SubLink);
            }
            delete del;
        }
    }
    size_t _size(GeneralListNode *head)
    {
        GeneralListNode* 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;
    }
    void _Print(GeneralListNode *head)
    {
        GeneralListNode *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<<")";
    }
    bool IsValue(char ch)
    {
        if((ch >= '0' && ch <= '9')
            ||(ch >= 'a' && ch <= 'z')
            ||(ch >= 'A' && ch <= 'Z'))
        {
            return true;
        }
        return false;
    }
    GeneralListNode* _CreatGeneralList(char *&s)
    {
        assert(*s == '(');
        GeneralListNode *head = new GeneralListNode(HEAD);
        ++s;
        GeneralListNode *cur = head;

        while(*s)
        {
            if(*s == '(')
            {
                GeneralListNode *SubNode = new GeneralListNode(SUB);

                cur->_next = SubNode;
                cur = cur->_next;

                   SubNode->_SubLink = _CreatGeneralList(s);
            }
            else if (*s == ')')
            {
                ++s;
                break;
            }
            else if(IsValue(*s))
            {
                GeneralListNode *ValueNode = new GeneralListNode(VALUE,*s);

                cur->_next = ValueNode;
                cur = cur->_next;

                ++s;
            }
            else
            {
                ++s;
            }
        }
        return head;
    }
protected:
    GeneralListNode * _head;
};

测试：

#include "GeneralList.h"

void test()
{
    GeneralList g1("()");
    GeneralList g2("(a,b)");
    GeneralList g3("(a,b,(c,d))");
    GeneralList g4("(a,b,(c,d),(e,(f),h))");
    GeneralList g5;
    g5 = g4;

   g4.Print();
   cout<<g4.size()<<endl;
   cout<<g4.Depth()<<endl;
   g5.Print();
}