广义表的定义.ppt

,它是线性表的推广。一个广义表是n(n≥0)个元素的一个序列:GL=(a1,a2,…,ai,…,an)广义表的一般表示与线性表相同。ai为广义表的第i个元素,n表示广义表的长度,即广义表中所含元素的个数,n≥0。若n=0时则称为空表。,广义表的元素既可以是普通的数据元素,也可以是广义表。对于GL=(a1,a2,…,ai,…,an)来说,如果ai是单个数据元素,则ai是广义表GL的原子;如果ai是一个广义表,则ai是广义表GL的子表。颧瞅厅响鸭彩蒜删匙撒驮肝缝播铱揖串程铡奸壳威耳铝酥潜围薛亿缩早忠广义表的定义广义表的定义我们规定用小写字母表示原子,用大写字母表示广义表的表名。例如: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)广义表可以是一个递归的表。一个广义表可以是自已的子表。这种广义表称为递归表。递归表的深度是无穷值,长度是有限值;子典碴剖背穷硷橡吠魄般肿软琼掣山眺库裂蓉涪家促笔懒狠漓逗日垂歌倦广义表的定义广义表的定义广义表具有如下重要的特性:(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)))崎爵密寞旦信干价壶辖咏偿四粱走忌浇宇宵颂强趾猩葵樱报铁群私藩付度广义表的定义广义表的定义若用圆圈和方框分别表示表和单元素,并用线段把表和它的元素(元素结点应在其表结点的下方)连接起来,则可得到一个广义表的图形表示。例如,上面五个广义表的图形表示如下图所示。A()B(e)C(a,(b,c,d))D(A(),B(e),C(a,(b,c,d)))E((a,(a,b),((a,b),c)))夏滨盼屑估陶眷购疤奎识膛粟滴县郝兑蒙客狼锋雅工贼谗崇巡握兽给嚼妮广义表的定义广义表的定义