数据结构 c++ 广义表

// CTest.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;

typedef char ElemType;
struct GLNode{
    bool tag;   //标志位
    union{      //值域或子表的表头指针域
        ElemType data;
        GLNode *sublist;
    };
    GLNode *next;
};
//用来测试 （a,(b,(c)),(#),((d,e))),f,(g));
//求广义表的长度 广义表的长度就是求单链表的长度
int Lenth(GLNode *GL)
{
    if(GL!=NULL){
        return 1+Lenth(GL->next);
    }else{
        return 0;
    }
}
//求广义表的长度 广义表的长度就是求单链表的长度
int Depth(GLNode *GL)
{
    int max=0;
    while(GL!=NULL){
        if(GL->tag==true){
            int dep = Depth(GL->sublist);
            if(dep>max) max=dep;
        }
        GL=GL->next;
    }
    return max+1;
}
//创建广义表
void Create(GLNode* &GL){
    char ch;//读一个字符
    cin>>ch;
    //若输入#，则置GL为空
    if(ch=='#') GL=NULL;
    //若输入为左括号则建立由GL所指向的子表结点并递归构造字表
    else if(ch='('){
        GL = new GLNode;
        GL->tag=true;
        Create(GL->sublist);
    }
    else{
        GL=new GLNode;
        GL->tag=false;
        GL->data=ch;
    }
    //此处读入的字符必为逗号，右括号或分号
      cin>>ch;
   //若GL为空，此时输入的字符必然为')',则什么都不用做
      if(GL==NULL);
    //若输入为逗号则递归构造后继表
      else if(ch==',') Create(GL->next);
      //若输入为右括号或分号则置GL的后继指针域为空
      else if((ch==')')||(ch==';')) GL->next=NULL;
}
//打印输出广义表
void Print(GLNode *GL){
    if(GL->tag==true){
        cout<<'(';            //对于表结点，则先输出左括号，作为开始符号
        if(GL->sublist==NULL)
            cout<<'#';        //若字表指针为空，则输出‘#’字符
        else
            Print(GL->sublist);//若为非空字表，则递归输出此表
        cout<<')';             //当一个字表输出结束后，应输出右括号作为终止符
    }
    else cout<<GL->data;    //对于单元素结点，输出该结点的值
    if(GL->next!=NULL){     //输出GL结点的后继表
        cout<<',';            //先输出括号及分割符后
        Print(GL->next);    //再递归输出后继表
    }
}
int _tmain(int argc, _TCHAR* argv[])
{
    GLNode *g=NULL;
    Create(g);
    Print(g);
    cout<<endl;
    cout<<"广义表的长度："<<Lenth(g->sublist)<<endl;
    cout<<"广义表的深度："<<Depth(g->sublist)<<endl;
    system("pause");
    return 0;
}