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