4.10 广义表的基本运算算法
4.10 广义表的基本运算算法
对于广义表，可以定义如下一些基本运算。
（1）创建广义表CreatGL(s)：由字符串s建立一个广义表链式存储结构。
（2）输出广义表DispGL(g)：采用括号表示法输出广义表g。
（3）求广义表长度GLLength(g)：返回广义表g的长度。
（4）求广义表深度GLDepth(g)：返回广义表g的深度。
（5）复制广义表GLCopy(p)：返回由p广义表复制的新广义表的头节点指针。
（6）求表头head(g)：返回广义表g的表头。
（7）求表尾tail(g)返回：广义表g的表尾。
（8）表头和表尾的连接Append(gh,gt)：返回表头gh和表尾gt连接而成的广义表头节点指针。
在广义表的各种运算中，求表头和表尾是递归运算，尽管求表头的结果可能是原子，但由于在递归算法中增加了原子处理功能，可以将原子也看成广义表，这样求表头和表尾运算具有封闭性，下一节的算法就是利用这两个递归运算进行递归算法设计的。
1．创建广义表运算算法
假定广义表中的元素类型ElemType为char类型，每个原子的值被限定为英文字母。并假定广义表是一个表达式，其格式为：元素之间用一个逗号分隔，表元素的起止符号分别为左、右圆括号，空表在其圆括号内不包含任何字符。例如“(a,(b,c,d))”就是一个符合上述规定的广义表格式。
建立广义表存储结构的算法同样是一个递归算法。该算法使用一个具有广义表格式的字符串参数s，返回由它生成的广义表存储结构的头节点指针h。在算法的执行过程中，需要从头到尾扫描s的每一个字符。当碰到左括号时，表明它是一个表元素的开始，则应建立一个由h指向的表节点，并用它的sublist域作为子表的表头指针进行递归调用，来建立子表的存储结构；当碰到一个英文字母时，表明它是一个原子，则应建立一个由h指向的原子节点；当碰到一个右括号字符时，表明它是一个空表，则应置h为空。当建立了一个由h指向的节点后，接着碰到逗号字符时，表明存在后继节点，需要建立当前节点（即由h指向的节点）的后继表；当碰到右括号或分号字符时，表明当前所处理的表已结束，应该置当前节点的link域为空。
根据以上分析，对应的生成广义表链式存储结构的算法如下：
GLNode *CreatGL(char *&s)
{
GLNode *h;char ch;
ch=*s; /*取一个扫描字符*/
s++; /*串指针后移一位*/
if(ch!='\0') /*串未结束判断*/
{
h=(GLNode *)malloc(sizeof(GLNode));/*创建一个新节点*/
if(ch=='(') /*当前字符为左括号时*/
{
h->tag=1; /*新节点作为表头节点*/
h->val.sublist=CreatGL(s); /*递归构造子表并链到表头节点*/
}
else if(ch==')')
h=NULL; /*遇到')'字符，子表为空*/
else
{
h->tag=0; /*新节点作为原子节点*/
h->val.data=ch;
}
}
else h=NULL; /*串结束，子表为空*/
ch=*s; /*取下一个扫描字符*/
s++; /*串指针后移一位*/
if(h!=NULL) /*串未结束判断*/
if (ch==',') /*当前字符为','*/
h->link=CreatGL(s); /*递归构造后续子表*/
else /*串结束*/
h->link=NULL; /*处理表的最后一个元素*/
return h; /*返回广义表指针*/
}
2．输出广义表运算算法
以h作为带表头附加节点的广义表的表头指针，打印输出该广义表时，需要对子表进行递归调用。当h节点为表元素节点时，应首先输出作为一个表的起始符号的左括号，然后再输出以h->sublist为表头指针的表；当h节点为单元素节点时，则应输出该元素的值。当以h->sublist为表头指针的表输出完毕后，应在其最后输出一个作为表终止符的右括号。当h节点输出结束后，若存在后继节点，则应首先输出一个逗号作为分隔符，然后再递归输出由h->link指针所指向的后继表。输出一个广义表的算法如下：
void DispGL(GLNode *g) /*g为一个广义表的头节点指针*/
{
if(g!=NULL) /*表不为空判断*/
{
if (g->tag==1) /*为表节点时*/
{
printf("("); /*输出'('*/
if (g->val.sublist==NULL)
printf(""); /*输出空子表*/
else
DispGL(g->val.sublist); /*递归输出子表*/
}
else
printf("%c", g->val.data); /*为原子时输出元素值*/
if(g->tag==1)
printf(")"); /*为表节点时输出')'*/
if(g->link!=NULL)
{
printf(",");
DispGL(g->link); /*递归输出后续表的内容*/
}
}
}
3．求广义表长度运算算法
在广义表中，同一层次的每个节点都是通过link域链接起来的，所以可把它看作是由link域链接起来的单链表。这样，求广义表的长度就是求单链表的长度，可以采用以前介绍过的求单链表长度的方法求其长度。求广义表长度的非递归算法如下：
int GLLength(GLNode *g)
{
int n=0;
g=g->val.sublist; /*g指向广义表的第一个元素*/
while(g!=NULL)
{
n++;
g=g->link;
}
return n;
}
4．求广义表深度运算算法
对于带头节点的广义表g，广义表深度的递归定义是它等于所有子表中表的最大深度加1。若g为原子，其深度为0。对应的递归算法如下：
int GLDepth(GLNode *g)
{
int max=0,dep;
if(g->tag==0)
return 0;
g=g->val.sublist; /*g指向第一个元素*
if(g==NULL) /*为空表时返回1*/
return 1;
while(g!=NULL) /*遍历表中的每一个元素*/
{
if (g->tag==1) /*元素为子表的情况*/
{
dep=GLDepth(g); /*递归调用求出子表的深度*/
if(dep>max) max=dep; /*max为同一层所求过的子表中深度的最大值*/
}
g=g->link; /*使g指向下一个元素*/
}
return(max+1); /*返回表的深度*/
}
5．复制广义表运算算法
复制一个广义表的过程如下：对于广义表的头节点*p，若为空，则返回空指针；若为表节点，则递归复制子表；否则，复制原子节点，然后再递归复制后续表，返回复制后的广义表链表的指针。对应的算法如下：
GLNode *GLCopy(GLNode *p)
{
GLNode *q;
if(p==NULL) return NULL;
q=(GLNode *)malloc(sizeof(GLNode));
q->tag=p->tag;
if(p->tag==1)
q->val.sublist=GLCopy(p->val.sublist);
else
q->val.data=p->val.data;
q->link=GLCopy(p->link);
return q;
}
6．求表头运算算法
把广义表看成是含有n个并列子表（假设将原子也看作特殊的子表）的子表。求广义表的表头过程如下：空表和原子不能求表头；若表头节点是原子，则复制该节点并记为q；若表头节点是子表，则由于其link域不一定为NULL，所以复制该表头节点产生t，并置t->link=NULL，t称为虚拟表头节点。如图4-15是广义表“((a),(b))”求表头时设置虚拟表头节点t的情况。使用表复制运算LGCopy()将t复制为q。最后返回q。
图4-15 广义表“((a),(b))”求表头时设置虚拟表头节点t的情况
求广义表表头的算法如下：
GLNode *head(GLNode *g)
{
GLNode *p=g->val.sublist;
GLNode *q,*t;
if(p==NULL)
{
printf("空表不能求表头\n");
return NULL;
}
else if(g->tag==0)
{
printf("原子不能求表头\n");
return NULL;
}
if (p->tag==0) /*为原子节点时*/
{
q=(GLNode *)malloc(sizeof(GLNode));
q->tag=0;q->val.data=p->val.data;
q->link=NULL;
}
else /*为子表时，产生虚表t*/
{
t=(GLNode *)malloc(sizeof(GLNode));
t->tag=1;t->val.sublist=p->val.sublist;
t->link=NULL;
q=GLCopy(t);
free(t);
}
return q;
}
7．求表尾运算算法
求广义表的表尾过程如下：空表和原子不能求表尾；否则创建一个虚拟表头节点t，并置t->val.sublist=h->val.sublist->link。如图4-16是广义表“((a),(b))”求表尾时设置虚拟表头节点t的情况，使用表复制运算lcopy()将t复制为q。最后返回q。
图4-16 广义表“((a),(b))”求表尾时设置虚拟表头节点t的情况
求广义表表尾的算法如下：
GLNode *tail(GLNode *g) /*g为一个广义表的头节点指针*/
{
GLNode *p=g->val.sublist;
GLNode *q,*t;
if(g==NULL) /*为空表时*/
{
printf("空表不能求表尾\n");
return NULL;
}
else if(g->tag==0) /*为原子时*/
{
printf("原子不能求表尾\n");
return NULL;
}
p=p->link;
t=(GLNode *)malloc(sizeof(GLNode)); /*建立一个虚表t*/
t->tag=1;t->link=NULL;
t->val.sublist=p;
q=GLCopy(t);
free(t);
return q;
}
8．表头和表尾的连接运算算法
将表头gh插入到表尾gt的第一个元素位置。对应的算法如下：
GLNode *Append(GLNode *gh,GLNode *gt)
{
gh->link=gt->val.sublist;
gt->val.sublist=gh;
return(gt);
}