#include<stdio.h>
#include<stdlib.h>
typedef struct GNode{//广义表 int NodeTag; //标志域union{ char data;struct GNode *sublist;};struct GNode *next;
}*PGNode,PG;
void CreateGList(PGNode &GL)
{char ch;scanf("%c", &ch);//读入一个字符，此处只可能读入空格#、左括号或英文字母if(ch=='#')//若输入为空格，则置表头指针为空{GL = NULL;}else if(ch=='(') {GL = (PGNode)malloc(sizeof(struct GNode));GL->NodeTag = 1;CreateGList(GL->sublist);}else{ GL = (PGNode) malloc(sizeof(struct GNode));GL->NodeTag = 0;GL->data = ch;}scanf("%c", &ch);//逗号、右括号或分号if(GL==NULL) //若*GL为空，则什么都不做
{
return ;
}else if(ch==',')//若输入逗号则递归构造后继表{
CreateGList(GL->next);
}else if((ch==')') || (ch==';')){GL->next = NULL;
}
}int DepthGList(PGNode GL)
{int max=0;//遍历表中每一个结点，求出所有子表的最大深度while(GL!=NULL){if(GL->NodeTag==1){int dep = DepthGList(GL->sublist);if(dep > max)max = dep;}GL = GL->next;}return(max + 1);//返回表的深度
}int LengthGList(PGNode GL)
{if(GL!=NULL)return(1 + LengthGList(GL->next));elsereturn(0);
}void PrintGList(PGNode GL)
{if(GL->NodeTag==1){ printf("(");if(GL->sublist==NULL)//若子表为空则输出'#'字符{
printf("#");}else{PrintGList(GL->sublist);
}
printf(")");}else//对于单元素结点{printf("%c", GL->data);}
if(GL->next!=NULL){printf(",");//先输出逗号分隔符PrintGList(GL->next);//再递归输出后继表}
}int main()
{//建议尝试案例(a,b,c,(d,e,f,g,(h,i,j,k,(l,m,n),o),p),q);
PGNode GL;
int depth,length;
printf("请输入一个广义表，以分号结束 : ");
CreateGList(GL);printf("\n此方法输出的输出广义表-> ：");PrintGList(GL);printf("\n\n");
depth = DepthGList( GL->sublist );
printf("广义表的深度depth为-> %d \n",depth);
length = LengthGList( GL->sublist );
printf("广义表的长度width为-> %d \n",length);
return 0;
}
