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

讯享网

广义表的定义

1. 广义表定义
   
   约定：为了区分原子和子表，书写时用大写字母表示子表，用小写字母表示原子。
2. 广义表特性
   
3. 广义表表示方法
   
   
   
   
   用圆圈和方框分别表示表和单元素，并用线段把表和它的元素（元素结点应在其表结点的下方）连接起来。树根结点代表整个广义表，各层树枝结点代表相应的子表，树叶结点代表单元素或空表。
4. 广义表与其他数据结构的关系
   
5. 广义表的运算定义
   

广义表的存储

1. 广义表采用顺序存储结构的可行性如何？
   前面讨论的树的存储，是采用了顺序存储方式，这是因为它只是一种有规则的单一的非线性结构，即每个结点不再包含子结构；而广义表中的元素还可以包含子结构，这使得结点的邻接关系可以是线性的也可以是非线性的，而且一个广义表中往往线性与非线性结构同时并存，若用顺序的存储来表示其中的特例情形是可以的，但作为一种广义表通用的存储方法，是非常困难的。
2. 广义表采用链式存储结构的可行性如何？
   链式存储方式的特点，一是结点分配灵活，二是在存储非线性结构时，只要增加结点指针域，即可将线性结构扩展为非线性结构，这样的特性刚好符合广义表这种复杂结构的描述要求，易于解决广义表的共享与递归问题，所以通常都采用链式的存储结构来存储广义表。
3. 广义表中的结点有两类，存储时如何处理？
   广义表中的结点一类是原子，一类是子表，按照存储原则之一的“存数值、存联系”，我们首先要明确的是结点本身的信息及相互联系都有哪些，原子的构成要素是数值，子表的构成应该有多个指针域
   
   基于 C 语言对指针类型的要求，要在一个链表中实现这两类结点的链接，则原子结点与子表结点应该以一种统一的“规格”打包，即只能用一种同样的结构，才能完成设想的存储结构。（逻辑结构的存储实现与语言的特点密切相关，语言数据类型的特点决定了存储的结构。）
   这两种结点的数据项类型、个数都不一样，在 C 语言中有“共用体”这种类型，可以完成我们所要求的功能，可以增加一个标志位 tag ，通过 tag 取值的不同来区分共用体中的数据含义
   
   通过上述思考与讨论，广义表的存储方式采用链式方法，要把子表结点与原子结点构造成统一的结点形式。

   

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

1. 广义表的头尾表示法
   （ 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）子表分解法

3. 广义表的孩子兄弟表示法
   

讯享网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)

广义表的基本运算

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

1. 建立广义表的链式存储结构
   假定广义表中的元素类型 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!='\0') { 
    //字串处理未结束 switch(*s) { 
    case'(': //遇到左括号 //创建子表LIST结点 NodePtr=(GLNode *)malloc(sizeof(GLNode)); NodePtr->tag=LIST; NodePtr->val.firstchildPtr=NULL; NodePtr->siblingPtr=NULL; //判断当前左括号是一级子表 if(*(s-2)==')') { 
    //将栈2记录的上一个一级子表位置压入栈1 if(topB!=MAXSIZE) stack[++topH]=stack[topB++]; } if(flag==1) { 
    //若是首次遇到左括号 flag=0; head=NodePtr;//记录广义表表头地址 stack[++topH]=NodePtr;//LIST结点入栈1 break; } prePtr=stack[topH--];//从栈1取前一结点地址 stack[++topH]=NodePtr;//LIST结点入栈1 if(topB==MAXSIZE) { 
    //若LIST为一级子表则入栈2 stack[--topB]=NodePtr; } //LIST结点为其前一结点的右兄弟 prePtr->siblingPtr=NodePtr; break; case')': break; case',': break; default://遇到原子 //创建原子结点ATOM NodePtr=(GLNode *) malloc(sizeof(GLNode)); NodePtr->tag=ATOM; NodePtr->val.data=*s; NodePtr->siblingPtr=NULL; prePtr=stack[topH--];//从栈1取前一结点地址 stack[++topH]=NodePtr;//ATOM结点入栈1 if(prePtr->tag==LIST) { 
    //若前一结点为子表，则ATOM结点为其首孩子 prePtr->val.firstchildPtr=NodePtr; prePtr->siblingPtr=NULL; } else { 
    //若前一结点为原子，则ATOM结点为其右兄弟 prePtr->siblingPtr=NodePtr; } break; } s++;//取下一个扫描字符 } return head; //返回广义表头指针 } 

2. 输出广义表
   以 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);//递归输出逗号后续表的内容 } } } 

若为表结点重复1过程。