广义表定义及其实现

广义表定义及其实现

#include<iostream>
#include<cstring>
#include<stdlib.h>
using namespace std;

class GListNode //广义表结构
{
    public:
    int type;
    union
    {
        char data;
        GListNode * sublist;
    };
    GListNode *next;
};
class GList
{public:
    GListNode *head; //头指针
    GListNode *DoCreate(char s[],int &i);//创建广义表
    GListNode *Copy(GListNode *p);//复制广义表
    void Traverse(GListNode *p);//遍历广义表
    void Free(GListNode *p);//释放广义表
    int Depth(GListNode *p);//返回广义表深度

    GList();//创建广义表
    GList(char s[]);
    GList(GList &gl);
    ~GList();
    void Traverse();
    int Length();//广义表长度

};
GList::GList()
{
    head=new GListNode;
    head->type=1;
    head->sublist=head->next=NULL;
}
GListNode * GList::DoCreate(char s[],int &i)
{
    GListNode *p;
    while(s[i]==' '||s[i]==',')
        i++;
    char e=s[i];
    i++;
    if(e=='(')
    {
        p=new GListNode;
        p->type=1;
        p->sublist=DoCreate(s,i);
        p->next=DoCreate(s,i);
        return p;
    }
    if(e==')'||e=='\0')
    {
        return NULL;
    }
    p=new GListNode;
    p->type=0;
    p->data=e;
    p->next=DoCreate(s,i);
    return p;
}
GList::GList(char s[])
{
    int i=0;
    head=DoCreate(s,i);
}
void GList::Traverse(GListNode *p)
{
    if(p==NULL)
    return ;
    if(p->type==0)
    cout<<p->data;
    else
    {
        cout<<"(";
        Traverse(p->sublist);
        cout<<")";
    }
    if(p->next)
        cout<<",";
    Traverse(p->next);
}
void GList::Traverse()
{
    Traverse(this->head);
}
void GList::Free(GListNode * p)
{
    if(p==NULL)
        return ;
    if(p->type==1)
        Free(p->next);
    Free(p->next);
    delete p;
}
GList::~GList()
{Free(head);}
GListNode *GList::Copy(GListNode *p)
{
    if(p==NULL)
        return NULL;
    GListNode *newp=new GListNode;
    newp->type=p->type;
    if(p->type==1)
        newp->sublist=Copy(p->next);
    else
    {
            newp->data=p->data;
            newp->next=Copy(p->next);
    return newp;
    }
    
}
int GList::Length()
{
    GListNode *p;
    int n=0;
    p=head->sublist;
    while(p)
    {
        p=p->next;
        n++;
    }
    return n;
}
int GList::Depth(GListNode *p)
{   
    if(p->type==0)
    return 0;
    int maxdepth=0;
    GListNode * q;
    q=p->sublist;
    while(q)
    {
        depth=Depth(q);
        if(depth>maxdepth)
            maxdepth=depth;
        q=q->next;
    }
    return maxdepth+1;
}
int main()
{

    char s[200];
    cin>>s;
    GList gl(s);
    gl.Traverse();
    system("pause");
    return 0;

}