数据结构广义表.ppt

数据结构广义表.ppt

ID:50023374

大小:105.50 KB

页数:22页

时间:2020-03-01

数据结构广义表.ppt_第1页
数据结构广义表.ppt_第2页
数据结构广义表.ppt_第3页
数据结构广义表.ppt_第4页
数据结构广义表.ppt_第5页
资源描述:

《数据结构广义表.ppt》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库

1、8.1广义表的定义第8章广义表8.2广义表的存储结构8.3广义表的运算本章小结8.1广义表的定义广义表简称表,它是线性表的推广。一个广义表是n(n≥0)个元素的一个序列,若n=0时则称为空表。设ai为广义表的第i个元素,则广义表GL的一般表示与线性表相同:GL=(a1,a2,…,ai,…,an)其中n表示广义表的长度,即广义表中所含元素的个数,n≥0。如果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)=

3、((),(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,

4、b),c)))8.2广义表的存储结构广义表是一种递归的数据结构,因此很难为每个广义表分配固定大小的存储空间,所以其存储结构只好采用动态链式结构。我们将一个广义表看成一棵树,为了方便存储,将其转换成一棵二叉树。其转换过程已在第6章中介绍过,这里以示例中的广义表C说明其转换过程。如下图所示,左边的图表示转换的中间状态,右边的图表示转换的最终状态,即一棵二叉树。从二叉树中看到,有两类结点,一类为圆圈结点,在这里对应子表;另一类为方形结点,在这里对应原子。广义表的存储结构typedefstructlnode{inttag;/*结点类型标识*/union{ElemTypedata;st

5、ructlnode*sublist;}val;structlnode*link;/*指向下一个元素*/}GLNode;/*广义表结点类型定义*/广义表的两种基本情况:为原子的情况:8.3广义表的运算1.求广义表的长度在广义表中,同一层次的每个结点是通过link域链接起来的,所以可把它看做是由link域链接起来的单链表。这样,求广义表的长度就是求单链表的长度,可以采用以前介绍过的求单链表长度的方法求其长度。求广义表长度的非递归算法如下:intGLLength(GLNode*g)/*g为一个广义表头结点的指针*/{intn=0;g=g->val.sublist;/*g指向广义表的

6、第一个元素*/while(g!=NULL){n++;g=g->link;}returnn;}2.求广义表的深度对于带头结点的广义表g,广义表深度的递归定义是它等于所有子表中表的最大深度加1。若g为原子,其深度为0。求广义表深度的递归模型f()如下:f(g)=0若g为原子1若g为空表MAX{f(subg)}+1其他情况,subg为g的子表intGLDepth(GLNode*g)/*求带头结点的广义表g的深度*/{intmax=0,dep;if(g->tag==0)return0;/*为原子时返回0*/g=g->val.sublist;/*g指向第一个元素*/if(g==NULL

7、)return1;/*为空表时返回1*/while(g!=NULL)/*遍历表中的每一个元素*/{if(g->tag==1)/*元素为子表的情况*/{dep=GLDepth(g);/*递归调用求出子表的深度*/if(dep>max)max=dep;/*max为同一层所求过的子表中深度的最大值*/}g=g->link;/*使g指向下一个元素*/}return(max+1);/*返回表的深度*/}3.建立广义表的链式存储结构假定广义表中的元素类型ElemType为char类型,每个原子的值被限定为英文字母。

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。