分层次的非线性结构 |
您所在的位置：网站首页 › 什么叫做广义表 › 分层次的非线性结构 |
分层次的非线性结构
|
包含子结构的线性结构，线性表的推广——广义表 广义表定义 广义表特性 广义表表示方法 广义表与其他数据结构的关系 广义表的运算定义 广义表采用顺序存储结构的可行性如何？ 前面讨论的树的存储，是采用了顺序存储方式，这是因为它只是一种有规则的单一的非线性结构，即每个结点不再包含子结构；而广义表中的元素还可以包含子结构，这使得结点的邻接关系可以是线性的也可以是非线性的，而且一个广义表中往往线性与非线性结构同时并存，若用顺序的存储来表示其中的特例情形是可以的，但作为一种广义表通用的存储方法，是非常困难的。 广义表采用链式存储结构的可行性如何？ 链式存储方式的特点，一是结点分配灵活，二是在存储非线性结构时，只要增加结点指针域，即可将线性结构扩展为非线性结构，这样的特性刚好符合广义表这种复杂结构的描述要求，易于解决广义表的共享与递归问题，所以通常都采用链式的存储结构来存储广义表。 广义表中的结点有两类，存储时如何处理？ 广义表中的结点一类是原子，一类是子表，按照存储原则之一的“存数值、存联系”，我们首先要明确的是结点本身的信息及相互联系都有哪些，原子的构成要素是数值，子表的构成应该有多个指针域 广义表的链式存储结构可以分为不同的两种存储方式，一种称为头尾表示法，其中包括“头尾分解法”与“子表分解法”，另一种称为孩子兄弟表示法。 广义表的头尾表示法 （ 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）表头表尾分解法 
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!='\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; //返回广义表头指针 }每次读入一个字符后，先放入栈内，再链入前一结点。 通过上例图，结合第二个纯表结合较易清楚。 输出广义表 以 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.从构建的链表至最左下结点，其中每遇到一个表结点打印一个“（”，直到遇到原子结点打印该结点，且若其右兄弟全为原子，依次打印，然后判断左下其父结点右兄弟是否非空，空则打印“）”，非空则打印“），”， 若为表结点重复1过程。 |
约定：为了区分原子和子表，书写时用大写字母表示子表，用小写字母表示原子。
用圆圈和方框分别表示表和单元素，并用线段把表和它的元素（元素结点应在其表结点的下方）连接起来。树根结点代表整个广义表，各层树枝结点代表相应的子表，树叶结点代表单元素或空表。
基于 C 语言对指针类型的要求，要在一个链表中实现这两类结点的链接，则原子结点与子表结点应该以一种统一的“规格”打包，即只能用一种同样的结构，才能完成设想的存储结构。（逻辑结构的存储实现与语言的特点密切相关，语言数据类型的特点决定了存储的结构。） 这两种结点的数据项类型、个数都不一样，在 C 语言中有“共用体”这种类型，可以完成我们所要求的功能，可以增加一个标志位 tag ，通过 tag 取值的不同来区分共用体中的数据含义 
通过上述思考与讨论，广义表的存储方式采用链式方法，要把子表结点与原子结点构造成统一的结点形式。
2）子表分解法 
【本文地址】
今日新闻 |
推荐新闻 |