单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章,数组和,5.1广义表的定义,5.2广义表的基本运算,5.3广义表的存储结构,5.1 数组和,广义表,的定义,广义表定义,广义表可定义为：数据元素可以是表的线性表记为：,LS(d,1,d,2,d,n,),LS,为表名，,d,i,(i1,2,n)，,可以是,单元素,(用小写字母表示)；,也可以是,广义表,(称为子表，用大写字母表示)；,n,为表的长度，当长度为0时称为,空表,；,称非空表的第一个元素,d,1,为,表头,，,其余元素组成的表(,d,2,d,n,),称为,表尾,5.2 数组和,广义表,的,基本运算,数组的基本运算,给定下标，存取相应的数据元素；,给定下标，修改相应的数据元素,；,广义表的基本运算,取表头,HEAD(LS)；,取表尾,TAIL(LS)5.3 广义表的,存储结构,广义表中的数据元素可以是单元素，或是广义表，很难用顺序存储结构表示，常采用链式存储结构1.,表头表尾链,存储结构,有两类结点：表结点和单元素结点tag=1 hp tp ,表结点,tag=0 data ,单元素结点,tag,标志域，0表示结点为单元素结点，1表示为表结点；,hp：,表头指针域；,tp：,表尾指针域；,data：,值域。
5.3 广义表的,存储结构,这种存储结构的特点是：,最上层的表结点数即为广义表的长度；,层次清楚；,表结点数目多，与广义表中括号对的数目不匹配例:,C=(a,(b,c,d),1,1,1,1,1,0,a,0,b,0,c,0,d,(,b,c,d,),(,b,c,d,),(,c,d,),(,d,),C,5.3 广义表的,存储结构,2.同层结点链存储结构,有两类结点：表结点和单元素结点tag=1 hp tp ,表结点,tag=0 data tp ,单元素结点,tp,为链接同层下一结点的指针域，其它域的含义同表头表尾链结构5.3 广义表的,存储结构,同层结点链结构的特点是：,表结点的数目与广义表的括号对数目一致；,写递归算法不方便例:,C=(a,(b,c,d),1,C,0,a,1,0,b,0,c,0,d,(,b,c,d),存储表示,(1)结点结构 表结点,单元素结点,(2)用一维数组存储多项式的所有变元,(3)每一层增设一个表头结点,并用,exp,域表明变元在数组中的下标,(4)增设一个表头结点,表示整个表,用头指针,p,指示,并在,exp,域填上变元个数,tag=1 exp hp tp,tag=0 exp coef tp,前例:,P(x,y,z)=z(A,2),(B,1),(15,0),A=y(c,3),(D,2)C=x(1,10),(2,6),P,1 1,1 3,1 2,1 1,0 0 15,1 2,1 3,1 2,0 10 1,0 6 2,1 3,D,z y x,B,A,C,三类表结点(,tag=1,):,整个表的头结点一个,exp,域为变元数，,层头结点(每层一个),exp,域为相应变元在数组中的下标，,一般表结点,exp,域为指数。