#include <iostream>
using namespace std;
typedef enum{ATOM, LIST}ElemTag;
typedef struct GLNode
{
ElemTag tag;
union
{
char data;
GLNode *child;
}d_c;
GLNode *next;
}GLNode;
//1. 创建广义表算法
GLNode *GL_Create(char *&s)
{
char ch;
GLNode *p;
ch = *s;
s++;
if(ch=='\0')
p = NULL;
else
{
p = new GLNode;
if(ch=='(')
{
p->tag = LIST;
p->d_c.child = GL_Create(s);
}
else if(ch==')')
return NULL;
else
{
p->tag = ATOM;
p->d_c.data = ch;
}
}
ch = *s;
s++;
if(p)
if(ch==',')
p->next = GL_Create(s);
else
p->next = NULL;
return(p);
}
//2. 输出广义表算法
void GL_Print(GLNode *p)
{
if(p)
{
if(p->tag == LIST)
{
cout<<"(";
if(p->d_c.child)
GL_Print(p->d_c.child);
cout<<")";
}
else
cout<<p->d_c.data;
if(p->next)
{
cout<<",";
GL_Print(p->next);
}
}
}
//3. 求广义表长度算法
int GL_Length(GLNode *p)
{
int len=0;
if(p && p->tag == LIST)
p = p->d_c.child;
while(p)
{
len++;
p = p->next;
}
return(len);
}
//4. 求广义表深度算法
int GL_Depth(GLNode *p)
{
int dep, max=0;
if(!p) return(1);
if(p->tag==ATOM) return(0);
p = p->d_c.child;
while(p)
{
if(p->tag == LIST)
{
dep = GL_Depth(p);
if(dep>max) max=dep;
}
p = p->next;
}
return(max+1);
}
//5. 复制广义表算法
GLNode *GL_Copy(GLNode *p)
{
if(!p) return(NULL);
GLNode *q = new GLNode;
q->tag = p->tag;
if(p->tag==1)
q->d_c.child = GL_Copy(p->d_c.child);
else
q->d_c.data = p->d_c.data;
q->next = GL_Copy(p->next);
return(q);
}
//6. 求表头算法
GLNode *GL_Head(GLNode *p)
{
if(p==NULL || (!p->d_c.child && !p->next))
{
cout<<"空表不能求表头!";
return(NULL);
}
else if(p->tag == ATOM)
{
cout<<"原子不能求表头!";
return(NULL);
}
GLNode *q = p->d_c.child;
GLNode *r = new GLNode;
if(q->tag == ATOM)
{
r->tag = ATOM;
r->d_c.data = q->d_c.data;
}
else
{
r->tag = LIST;
r->d_c.child = q->d_c.child;
}
r->next = NULL;
return(r);
}
//7. 求表尾算法
GLNode *GL_Tail(GLNode *p)
{
if(p==NULL || (!p->next && !p->d_c.child))
{
cout<<"空表不能求表尾!";
return(NULL);
}
else if(p->tag == ATOM)
{
cout<<"原子不能求表尾!";
return(NULL);
}
GLNode *q = p->d_c.child->next;
GLNode *r = new GLNode;
r->tag = LIST;
r->next = NULL;
r->d_c.child = q;
return(r);
}
//8.表头表尾连接算法
GLNode *GL_Merge(GLNode *p1, GLNode *p2)
{
p1->next = p2->d_c.child;
p2->d_c.child = p1;
return(p2);
}
int main()
{
char c1[] = "((),(e),(a,(b,c,d)))";
char c2[] = "(f,(g,(h)),(i,j,(k,(l,())),m),n)";
char *s1 = c1;
char *s2 = c2;
GLNode *p1 = GL_Create(s1);
GLNode *p2 = GL_Create(s2);
cout<<"p1 = "; GL_Print(p1); cout<<endl;
cout<<"p2 = "; GL_Print(p2); cout<<endl;
cout<<endl;
cout<<"length(p1) = "; cout<<GL_Length(p1); cout<<endl;
cout<<"depth(p1) = "; cout<<GL_Depth(p1); cout<<endl;
cout<<"length(p2) = "; cout<<GL_Length(p2); cout<<endl;
cout<<"depth(p2) = "; cout<<GL_Depth(p2); cout<<endl;
cout<<endl;
GLNode *q;
cout<<"q = copy(p1) = "; q = GL_Copy(p1); GL_Print(q); cout<<endl;
cout<<"q = head(p1) = "; q = GL_Head(p1); GL_Print(q); cout<<endl;
cout<<"q = tail(p1) = "; q = GL_Tail(p1); GL_Print(q); cout<<endl;
cout<<endl;
GLNode *r;
cout<<"r = merge(p1, p2) = "; r = GL_Merge(p1, p2); GL_Print(r); cout<<endl;
cout<<endl;
getchar();
return(0);
system("pause");
}
