《数据结构广义表》PPT课件.ppt
《《数据结构广义表》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《数据结构广义表》PPT课件.ppt(21页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、8.1 8.1 广义表的定义广义表的定义第第8 8章章 广义表广义表8.2 8.2 广义表的存储结构广义表的存储结构8.3 8.3 广义表的运算广义表的运算本章小结本章小结8.1 8.1 广义表的定义广义表的定义 广广义义表表简简称称表表,它它是是线线性性表表的的推推广广。一一个个广广义义表表是是n(n0)个个元元素素的的一一个个序序列列,若若n=0时时则则称称为为空空表表。设设ai为为广广义义表表的的第第i个个元元素素,则则广广义义表表GL的的一一般表示与线性表相同:般表示与线性表相同:GL=(a1,a2,ai,an)其中其中n表示广义表的长度表示广义表的长度,即广义表中所含元即广义表中所含
2、元素的个数素的个数,n0。如果。如果ai是单个数据元素是单个数据元素,则则ai是是广义表广义表GL的原子;如果的原子;如果ai是一个广义表是一个广义表,则则ai是广是广义表义表GL的子表。的子表。广义表具有如下重要的特性:广义表具有如下重要的特性:(1)广义表中的数据元素有相对次序;广义表中的数据元素有相对次序;(2)广义表的长度定义为最外层包含元素个数;广义表的长度定义为最外层包含元素个数;(3)广广义义表表的的深深度度定定义义为为所所含含括括弧弧的的重重数数。其其中中,原原子的深度为子的深度为0,空表的深度为空表的深度为1;(4)广广义义表表可可以以共共享享;一一个个广广义义表表可可以以为
3、为其其他他广广义义表共享;这种共享广义表称为再入表;表共享;这种共享广义表称为再入表;(5)广广义义表表可可以以是是一一个个递递归归的的表表。一一个个广广义义表表可可以以是是自自已已的的子子表表。这这种种广广义义表表称称为为递递归归表表。递递归归表表的的深度是无穷值深度是无穷值,长度是有限值;长度是有限值;(6)任何一个非空广义表任何一个非空广义表GL均可分解为表头均可分解为表头head(GL)=a1和表尾和表尾tail(GL)=(a2,an)两部分。两部分。为为了了简简单单起起见见,下下面面讨讨论论的的广广义义表表不不包包括括前前面面定定义义的的再再入入表表和和递递归归表表,即即只只讨讨论论
4、一一般般的的广广义义表表。另另外外,我我们们规规定定用用小小写写字字母母表表示示原原子子,用用大大写写字字母母表表示示广义表的表名。例如:广义表的表名。例如: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)若若用用圆圆圈圈和和方方框框分分别别
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)8.2 8.2 广义表的存储结构广义表的存储结构 广广义义表表是是一一种种递递归归的的数数据据结结构构,因因此此很很难难为为每每个个广广义义表表分分配配固固定定大大小小的的存存储储空空间间,所所以
6、以其其存存储储结结构构只只好采用动态链式结构。好采用动态链式结构。我我们们将将一一个个广广义义表表看看成成一一棵棵树树,为为了了方方便便存存储储,将将其其转转换换成成一一棵棵二二叉叉树树。其其转转换换过过程程已已在在第第6章章中中介介绍绍过过,这这里里以以示示例例中中的的广广义义表表C说说明明其其转转换换过过程程。如如下下图图所所示示,左左边边的的图图表表示示转转换换的的中中间间状状态态,右右边边的的图图表表示示转转换换的的最最终终状状态态,即即一一棵棵二二叉叉树树。从从二二叉叉树树中中看看到到,有有两两类类结结点点,一一类类为为圆圆圈圈结结点点,在在这这里里对对应应子子表表;另一类为方形结点
7、另一类为方形结点,在这里对应原子。在这里对应原子。广义表的存储结构广义表的存储结构 typedef struct lnode int tag;/*结点类型标识结点类型标识*/union ElemType data;struct lnode*sublist;val;struct lnode*link;/*指向下一个元素指向下一个元素*/GLNode;/*广义表结点类型定义广义表结点类型定义*/广义表的两种基本情况广义表的两种基本情况 :为原子的情况为原子的情况:8.3 8.3 广义表的运算广义表的运算1.求广义表的长度求广义表的长度 在在广广义义表表中中,同同一一层层次次的的每每个个结结点点是是
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构广义表 数据结构 广义 PPT 课件
限制150内