《数据结构第8章广义表》由会员分享，可在线阅读，更多相关《数据结构第8章广义表（23页珍藏版）》请在金锄头文库上搜索。
1、8.1 广义表的定义第8章 广义表8.2 广义表的存储结构8.3 广义表的运算本章小结8.1 广义表的定义 广义表简称表,它是线性表的推广。一个广义表是n(n0)个元素的一个序列,若n=0时则称 为空表。设ai为广义表的第i个元素,则广义表GL 的一般表示与线性表相同：GL=(a1,a2,ai,an)其中n表示广义表的长度,即广义表中所含元素的个数,n0。如果ai是单个数据元素,则ai是 广义表GL的原子；如果ai是一个广义表,则ai是广 义表GL的子表。 广义表具有如下重要的特性：(1)广义表中的数据元素有相对次序；(2)广义表的长度定义为最外层包含元素个数；(3)广义表的深度定义为所含括弧
2、的重数。其中,原子 的深度为0,空表的深度为1；(4)广义表可以共享；一个广义表可以为其他广义表 共享；这种共享广义表称为再入表；(5)广义表可以是一个递归的表。一个广义表可以是 自已的子表。这种广义表称为递归表。递归表的深度 是无穷值,长度是有限值；(6)任何非空广义表GL均可分解为两部分。 表头head(GL) = a1和表尾tail(GL) = ( a2,an)约定用小写字母表示原子，用大写字母表示广 义表的表名。例如：A=()B=(e)C=(a,(b,c,d)D=(A,B,C)=(),(e),(a,(b,c,d)E=(a,(a,b),(a,b),c)若用圆圈和方框分别表示表和单元素,并
3、用线段 把表和它的元素(元素结点应在其表结点的下方)连 接起来,则可得到一个广义表的图形表示。例如,上面 五个广义表的图形表示如下图所示。A=() B=(e)eA BC=(a,(b,c,d) D=(A,B,C)=(), (e), (a,(b,c,d)E=(a,(a,b),(a,b),c)8.2 广义表的存储结构广义表是一种递归的数据结构，因此很难为每 个广义表分配固定大小的存储空间，所以其存储结 构只好采用动态链式结构。将一个广义表看成一棵树，为了方便存储,将其 转换成一棵二叉树。其转换过程已在“树”一章中 介绍过，这里以示例中的广义表C说明其转换过程。 如下图所示，左边的图表示转换的中间状态
4、，右边 的图表示转换的最终状态，即一棵二叉树。从二叉 树中看到，有两类结点，一类为圆圈结点，在这里 对应子表；另一类为方形结点，在这里对应原子。typedef struct lnodeint tag; /*结点类型标识*/union ElemType data;struct lnode *sublist; val;struct lnode *link;/*指向下一个元素*/ GLNode;/*广义表结点类型定义*/广义表的两种基本情况 ：为原子的情况 ：8.3 广义表的运算1. 求广义表的长度在广义表中,同一层次的每个结点是通过link域链接起来的,所以可把它看做是由link域链接起来的单链表
5、。这样,求广义表的长度就是求单链表的长度,可以采用以前介绍过的求单链表长度的方法求其长度。求广义表长度的非递归算法如下：int GLLength(GLNode *g) /*g为一个广义表头结点 的指针*/int n=0;g=g-val.sublist; /*g指向广义表的第一个元素*/while (g!=NULL) n+;g=g-link;return n;2. 求广义表的深度对于带头结点的广义表g，广义表深度的递归 定义是它等于所有子表中表的最大深度加1。若g为 原子，其深度为0。求广义表深度的递归模型f( )如下：f(g)= 0 若g为原子 1 若g为空表MAXf(subg)+1 其他情况
6、，subg为g的 子表 1 1 0 a 0 b 0 c 0 d C0 e 1 1 C= ( (a) , ( b , c, d ) , ( e ) )1 int GLDepth(GLNode *g) /*求带头结点的广义表g的深度*/ int max=0,dep;if (g-tag=0) return 0; /*为原子时返回0*/g=g-val.sublist; /*g指向第一个元素*/if (g=NULL) return 1; /*为空表时返回1*/while (g!=NULL) /*遍历表中的每一个元素*/ if (g-tag=1) /*元素为子表的情况*/ dep=GLDepth(g);
7、/*递归调用求出子表的深度*/if (depmax) max=dep; /*max为同一层所求过的子表中深度的最大值*/g=g-link; /*使g指向下一个元素*/return(max+1); /*返回表的深度*/ 3. 建立广义表的链式存储结构假定广义表中的元素类型ElemType为char类型，每个原子的值被限定为英文字母。并假定广义表是一个表达式，其格式为：元素之间用一个逗号分隔，表元素的起止符号分别为左、右圆括号，空表在其圆括号内不包含任何字符。例如“(a,(b,c,d)”就是一个符合上述规定的广义表格式。 生成广义表链式存储结构的算法如下：GLNode *CreatGL(char
8、*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=
9、*s; /*取下一个扫描字符*/s+; /*串指针后移一位*/if (h!=NULL) /*串未结束判断*/if (ch=,) /*当前字符为,*/h-link=CreatGL(s); /*递归构造后续子表*/else /*串结束*/h-link=NULL; /*处理表的最后一个元素*/return h; /*返回广义表指针*/ 1 1 0 a 0 b 0 c 0 d C0 e 1 1 C= ( a , ( b , c, d ) , ( e ) )4. 输出广义表以h作为带表头附加结点的广义表的表头指针，打印输出该广义表时，需要对子表进行递归调用。输出一个广义表的算法如下：void DispG
10、L(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); /*递归输出后续表的内容*/ 1 1 0 a 0 b 0 c 0 d C0 e 1 1 ( a , ( b , c , d ) , ( e ) )C= 本章小结本章的基本学习要点如下：(1)掌握广义表的定义。(2)重点掌握广义表的链式存储结构。(3)掌握广义表的基本运算,包括创建广义表、 输出广义表、求广义表的长度和深度。(4)灵活运用广义表这种数据结构解决一些综合 应用问题。
