数据结构第8章广义表.ppt

广义表的基本概念广义表的存储结构,第8章广义表,一、广义表,定义:广义表（lists)是n(0)个元素的有限序列，记作:LS=(a1,a2,an),其中，ai或是原子或是一个广义表n是广义表的长度,通常用小写表示原子，大写表示广义表。,例：E=()L=(a,b)A=(x,L)=(x,(a,b)B=(A,y)=(x,L),y)=(x,(a,b),y)C=(A,B)=(x,(a,b),(x,(a,b),y)D=(a,D)=(a,(a,(a,),特点：（1）广义表的元素可以是子表（广义表）。（2）一个广义表可以为其他多个广义表共享。（3）广义表可以是递归表。,注：F=()与E=()的区别n=1n=0,广义表的逻辑结构,A=(1,2,3,n)二维数组A是由n个元素组成的广义表，其中每个元素是由一列元素组成的子表。,线性结构的推广,例：多维数组就是广义表,A=(1,2,3,m)二维数组A是由m个元素组成的广义表，其中每个元素是由一行元素组成的子表。,i=(ai1aijain),广义表的基本运算,取表头：HeadLS=a1取第一元素,例：headA=head(x,L)=xhead(a,b),(c,d)=(a,b),LS=(a1,a2,an),取表尾：TailLS=(a2,an)由第二个元素到最后一个元素组成的子表,例：tail(a,b,c,d)=(b,c,d)tailA=tail(x,L)=tail(x,(a,b)=(a,b)tail(e)=()tailheadtail(a,b),(c,d)=?,求表的深度：DepthLS括号嵌套的最大层数,求表的长度：LengthLS,(d),例：depth(a,(b,c),(d,(e),()=4,广义表的存储结构,由于广义表中元素可以是原子，也可以是子表，只能采用链方式。单链表示法：以单链表形式链接各结点。当元素为原子时，存储其元素值。当元素为子表时，存储指向子表的指针。,1元素为子表sublist指向子表,0元素为原子data存储元素值,typedefstructnodeinttag;structnode*link;unionstructnode*sublist;datatypedata;element;lists;,结点数据类型,LS=(a,(b,c),(),(d,e),f),0a,1,0b,0c,1,1,1,0f,0d,0e,单链表示法,1,求广义表的深度基本思想：依次求出每个元素的深度，则最大值+1为其表的深度。其中：原子元素的深度=0利用递归求出子表的深度,d=0,d=0,d=0,max=0,d=1,d=1,max=0,d=0,d=0,max=0,d=1,d=0,max=1,d=2,max=2,d=3,