分层次的非线性结构——树（广义表）05

包含子结构的线性结构，线性表的推广——广义表

广义表的定义

广义表定义

约定：为了区分原子和子表，书写时用大写字母表示子表，用小写字母表示原子。
广义表特性
广义表表示方法

用圆圈和方框分别表示表和单元素，并用线段把表和它的元素（元素结点应在其表结点的下方）连接起来。树根结点代表整个广义表，各层树枝结点代表相应的子表，树叶结点代表单元素或空表。
广义表与其他数据结构的关系
广义表的运算定义

广义表的存储

广义表采用顺序存储结构的可行性如何？
前面讨论的树的存储，是采用了顺序存储方式，这是因为它只是一种有规则的单一的非线性结构，即每个结点不再包含子结构；而广义表中的元素还可以包含子结构，这使得结点的邻接关系可以是线性的也可以是非线性的，而且一个广义表中往往线性与非线性结构同时并存，若用顺序的存储来表示其中的特例情形是可以的，但作为一种广义表通用的存储方法，是非常困难的。
广义表采用链式存储结构的可行性如何？
链式存储方式的特点，一是结点分配灵活，二是在存储非线性结构时，只要增加结点指针域，即可将线性结构扩展为非线性结构，这样的特性刚好符合广义表这种复杂结构的描述要求，易于解决广义表的共享与递归问题，所以通常都采用链式的存储结构来存储广义表。
广义表中的结点有两类，存储时如何处理？
广义表中的结点一类是原子，一类是子表，按照存储原则之一的“存数值、存联系”，我们首先要明确的是结点本身的信息及相互联系都有哪些，原子的构成要素是数值，子表的构成应该有多个指针域

基于 C 语言对指针类型的要求，要在一个链表中实现这两类结点的链接，则原子结点与子表结点应该以一种统一的“规格”打包，即只能用一种同样的结构，才能完成设想的存储结构。（逻辑结构的存储实现与语言的特点密切相关，语言数据类型的特点决定了存储的结构。）
这两种结点的数据项类型、个数都不一样，在 C 语言中有“共用体”这种类型，可以完成我们所要求的功能，可以增加一个标志位 tag ，通过 tag 取值的不同来区分共用体中的数据含义

通过上述思考与讨论，广义表的存储方式采用链式方法，要把子表结点与原子结点构造成统一的结点形式。

广义表的链式存储结构可以分为不同的两种存储方式，一种称为头尾表示法，其中包括“头尾分解法”与“子表分解法”，另一种称为孩子兄弟表示法。

广义表的头尾表示法
（ a，（ x，y ），(（ z ）) ），大概可以把圆形序号看做一个左括号。

结点类型描述：

typedef enum {ATOM,LIST} ElemTag;// ATOM==0:原子, LIST==1:子表
typedef struct GLNode{ElemTag  tag; // 标志域union {AtomType actom;struct {struct GLNode *hp,*tp;} ptr;};
}Glist;

1）表头表尾分解法


2）子表分解法

广义表的孩子兄弟表示法

typedef  enum {ATOM, LIST} ElemTag; 	//ATOM=0：单元素；LIST=1：子表
typedef  struct  GLENode 
{ElemTag  tag;                	//标志域，用于区分原子结点和表结点union {                           	//原子结点和表结点的联合部分AtomType  data;            	//原子结点的值域struct GLENode  *firstchildPtr;	//表结点的表头指针};struct GLENode  *siblingPtr;   	//指向下一个结点
} GList                     			//广义表类型

例题：用孩子兄弟表示法表示下列各广义表的存储
空表： A=()
线性表： L=(a,b,c,d)
纯表： D=(a,(b,c))
纯表： D=(A,B,C)=(( ),(e),(a, (b, c)))
再入表： G(d,L(a,b),T(c,L(a,b)))
递归表： E=(a, E)

广义表的基本运算

约定所讨论的广义表都是非递归表且无共享子表，存储结构采用二叉链表方式（孩子兄弟存储）

建立广义表的链式存储结构
假定广义表中的元素类型 ElemType 为 char 类型，每个原子的值被限定为英文字母。
并假设广义表是一个表达式，其格式为：元素之间用一个逗号分隔，表元素的起止符号分别为左、右圆括号，空表在其圆括号内不包含任何字符。

树的括号表示到树的链表表示的转换算法——用栈实现。
从左到右扫描树的括号表示；
（1）遇到左括号，其前一个结点出栈1至prePtr
创建子表结点；
子表结点入栈1；
若为一级子表则入栈2；
将子表结点链入prePtr的右兄弟域；
（2）遇到原子，其前一个结点出栈1至prePtr
创建原子结点；
原子结点入栈1；
若prePtr为LIST结点，则将原子结点链入prePtr的首孩子域；
若prePtr为ATOM结点，则将原子结点链入prePtr的右兄弟域；
（3）遇到逗号或右括号时跳过。
注：一级子表对应逗号后的左括号

/*=======================================
函数功能：生成广义表链式存储结构
函数输入：char *s——树的括号表示字符串
函数输出：GLNode *head——链式广义表头地址
=========================================*/
GLNode *CreatGL(char *s) {GLNode *NodePtr,*prePtr,*head;//当前结点，前一结点，广义表头结点GLNode *stack[MAXSIZE];//双向栈//双向栈——左端栈1记录广义表结点地址，右端栈2只记录一级子表结点位置int topH=-1;//栈1顶指针int topB;//栈2顶指针topB=MAXSIZE;int flag=1;//首次'('标志while(*s!='') { //字串处理未结束switch(*s) {case'(':    //遇到左括号//创建子表LIST结点NodePtr=(GLNode *)malloc(sizeof(GLNode));NodePtr->tag=LIST;NodePtr->val.firstchildPtr=NULL;NodePtr->siblingPtr=NULL;//判断当前左括号是一级子表if(*(s-2)==')') {//将栈2记录的上一个一级子表位置压入栈1if(topB!=MAXSIZE) stack[++topH]=stack[topB++];}if(flag==1) { //若是首次遇到左括号flag=0;head=NodePtr;//记录广义表表头地址stack[++topH]=NodePtr;//LIST结点入栈1break;}prePtr=stack[topH--];//从栈1取前一结点地址stack[++topH]=NodePtr;//LIST结点入栈1if(topB==MAXSIZE) {//若LIST为一级子表则入栈2stack[--topB]=NodePtr;}//LIST结点为其前一结点的右兄弟prePtr->siblingPtr=NodePtr;break;case')':break;case',':break;default://遇到原子//创建原子结点ATOMNodePtr=(GLNode *) malloc(sizeof(GLNode));NodePtr->tag=ATOM;NodePtr->val.data=*s;NodePtr->siblingPtr=NULL;prePtr=stack[topH--];//从栈1取前一结点地址stack[++topH]=NodePtr;//ATOM结点入栈1if(prePtr->tag==LIST) {//若前一结点为子表，则ATOM结点为其首孩子prePtr->val.firstchildPtr=NodePtr;prePtr->siblingPtr=NULL;} else {//若前一结点为原子，则ATOM结点为其右兄弟prePtr->siblingPtr=NodePtr;}break;}s++;//取下一个扫描字符}return head;  //返回广义表头指针
}

每次读入一个字符后，先放入栈内，再链入前一结点。
通过上例图，结合第二个纯表结合较易清楚。

输出广义表
以 h 作为带表头附加结点的广义表的表头指针，打印输出该广义表时，需要对子表进行递归调用。

/*=======================================
函数功能：打印括号表示形式的广义表
函数输入：链式广义表头指针 GLNode *gPtr
函数输出：无
=========================================*/
void DispGL(GLNode *gPtr) {if (gPtr!=NULL) {  //表非空if (gPtr->tag==LIST) {  //为表结点时printf("(");//输出空子表if(gPtr->firstchildPtr==NULL) printf("");//递归输出子表else DispGL(gPtr->firstchildPtr);} else printf("%c",gPtr->data); //为原子时输出元素值if(gPtr->tag==LIST)  printf(")");//为子表结点时输出')'if(gPtr->siblingPtr!=NULL) {printf(",");DispGL(gPtr->siblingPtr);//递归输出逗号后续表的内容}}
}