《数据结构广义表》PPT课件.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,8.1 广义表的定义,第8章 广义表,8.2 广义表的存储结构,8.3 广义表的运算,本章小结,8.1 广义表的定义,广义表简称表,它是线性表的推广一个广义表是n(n0)个元素的一个序列,若n=0时则称为空表设a,i,为广义表的第i个元素,则广义表GL的一般表示与线性表相同：,GL=(a,1,a,2,a,i,a,n,),其中n表示广义表的长度,即广义表中所含元素的个数,n0如果a,i,是单个数据元素,则a,i,是广义表GL的原子；如果a,i,是一个广义表,则a,i,是广义表GL的子表广义表具有如下重要的特性：,(1)广义表中的数据元素有相对次序；,(2)广义表的长度定义为最外层包含元素个数；,(3)广义表的深度定义为所含括弧的重数其中,原子的深度为0,空表的深度为1；,(4)广义表可以共享；一个广义表可以为其他广义表共享；这种共享广义表称为再入表；,(5)广义表可以是一个递归的表一个广义表可以是自已的子表这种广义表称为递归表递归表的深度是无穷值,长度是有限值；,(6)任何一个非空广义表GL均可分解为表头head(GL)=a,1,和表尾tail(GL)=(a,2,a,n,)两部分。

为了简单起见,下面讨论的广义表不包括前面定义的再入表和递归表,即只讨论一般的广义表另外,我们规定用小写字母表示原子,用大写字母表示广义表的表名例如：,A=(),B=(e),C=(a,(b,c,d),D=(A,B,C)=(),(e),(a,(b,c,d),E=(a,(a,b),(a,b),c),如果把每个表的名字(若有的话)写在其表的前面,则上面的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),若用圆圈和方框分别表示表和单元素,并用线段把表和它的元素(元素结点应在其表结点的下方)连接起来,则可得到一个广义表的图形表示例如,上面五个广义表的图形表示如下图所示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 广义表的存储结构,广义表是一种递归的数据结构,因此很难为每个广义表分配固定大小的存储空间,所以其存储结构只好采用动态链式结构我们将一个广义表看成一棵树,为了方便存储,将其转换成一棵二叉树其转换过程已在第6章中介绍过,这里以示例中的广义表C说明其转换过程。

如下图所示,左边的图表示转换的中间状态,右边的图表示转换的最终状态,即一棵二叉树从二叉树中看到,有两类结点,一类为圆圈结点,在这里对应子表；另一类为方形结点,在这里对应原子广义表的存储结构,typedef struct lnode,int tag;/*结点类型标识*/,union,ElemType 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;/*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;/*g指向第一个元素*/,if (g=NULL)return 1;/*为空表时返回1*/,while(g!=NULL)/*遍历表中的每一个元素*/,if(g-tag=1)/*元素为子表的情况*/,dep=GLDepth(g);/*递归调用求出子表的深度*/,if(depmax)max=dep;,/*max为同一层所求过的子表中深度的最大值*/,g=g-link;/*使g指向下一个元素*/,return(max+1);/*返回表的深度*/,3.建立广义表的链式存储结构,假定广义表中的元素类型ElemType为char类型,每个原子的值被限定为英文字母并假定广义表是一个表达式,其格式为：元素之间用一个逗号分隔,表元素的起止符号分别为左、右圆括号,空表在其圆括号内不包含任何字符。

例如“(a,(b,c,d)”就是一个符合上述规定的广义表格式生成广义表链式存储结构的算法如下：,GLNode*CreatGL(char*&s),GLNode*h;char ch=*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=*s+;/*取下一个扫描字符*/,if(h!=NULL)/*串未结束判断*/,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();/*输出(*/,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)掌握广义表的定义2)重点掌握广义表的链式存储结构3)掌握广义表的基本运算,包括创建广义表、输出广义表、求广义表的长度和深度4)灵活运用广义表这种数据结构解决一些综合应用问题练习,教材中p182习题1和2。