main.cpp

该程序用于实现建立一个广义表

#include <iostream>
using namespace std;
#define MAX 50
struct NODE
{
    bool tag;
    union
    {
        struct NODE *dlink;
        char data;
    }element;
    struct NODE *link;
};

NODE *GreatL(char **s)  //按用户输入创建一个广义表
{
    NODE *q;
    char ch;
    ch=**s;
    (*s)++;  //与其后的 ch=**s;(*s)++ 功能一样均用于依次访问每个字符
    if (ch!=' ')  //表不为空
    {
        q=new NODE;
        if (ch=='(')  //遇到左括号，说明有子表
        {
            q->tag=true;  //作标识
            q->element.dlink=GreatL(s);//建子表
        }
        else  //遇到字母，存入作为元素
        {
            q->tag=false;
            q->element.data=ch;
        }
    }
    else  //表为空，置空q
    {
        q=NULL;
        cout<<"表为空";
    }

    ch=**s;
    (*s)++;
    if (q!=NULL)  //表不为空
        if (ch==',')  //表中有别的元素
            q->link =GreatL(s);  //递归存入
        else
            q->link=NULL;  //否则将下一个地址置空
    return q;
}



void OutPutL(NODE *ptr)  //输出广义表
{
    if (ptr!=NULL)
    {
        if (ptr->tag==true)  //遇到子表
        {
            cout<<"(";   //输出左括号
            if (ptr->element.dlink !=NULL)  //子表元素不为空
                OutPutL(ptr->element.dlink );  //递归输出子表元素
        }
        else
            cout<<ptr->element.data;  //遇到字母，直接输出

        if (ptr->tag==true)  //子表中的字母均输出后，输出右括号
            cout<<")";
        if (ptr->link!=NULL)  //上一级链中的下一个结点不为空输出逗号
        {
            cout<<",";
            OutPutL(ptr->link);  //递归实现输出结点中的元素
        }
    }
}

NODE *copyL(NODE *A)  //复制该广义表,将A复制到B中去
{
    NODE *B;
    if (A==NULL)  //表为空
    {cout<<"表为空";
        return NULL;
    }

    B=new NODE;
    B->tag=A->tag;
    if (A->tag==true)  //标识为true，说明有子表
        B->element.dlink =copyL(A->element.dlink );  //复制子表
    else
        B->element.data =A->element.data;  //标识为false，复制元素

    B->link=copyL(A->link);
    return B;
}






int main()
{
    NODE *L,*cpy;
    char s[MAX],*p;
    cout<<"输入一个广义表，如(（a,b），c)"<<endl;
    cin>>s;

    p=s;

    L=GreatL(&p);
    cpy=copyL(L);
    cout<<"复制以后的结果为："<<endl;
    OutPutL(cpy);

    return 0;
}