五章数组和广义表ppt课件

1、第五章第五章 数组和广义表数组和广义表5.1 广义表的定义广义表的定义5.2 广义表的根本运算广义表的根本运算5.3 广义表的存储构造广义表的存储构造5.1 5.1 数组和广义表的定义数组和广义表的定义 广义表定义广义表定义 广义表可定义为：数据元素可以是表的线性表。广义表可定义为：数据元素可以是表的线性表。 记为：记为：LSLS(d1,d2,dn)(d1,d2,dn) LS LS为表名，为表名， di (i di (i1,2,n)1,2,n)，可以是单元素，可以是单元素( (用小写字母表示用小写字母表示) )； 也可以是广义表也可以是广义表( (称为子表，用大写字母表示称为子表，用大写字母表

2、示) )； n n为表的长度，当长度为为表的长度，当长度为0 0时称为空表；时称为空表； 称非空表的第一个元素称非空表的第一个元素d1d1为表头，为表头， 其他元素组成的表其他元素组成的表(d2,dn)(d2,dn)称为表尾。称为表尾。5.2 5.2 数组和广义表的根本运算数组和广义表的根本运算 数组的根本运算数组的根本运算 给定下标，存取相应的数据元素；给定下标，存取相应的数据元素； 给定下标，修正相应的数据元素；给定下标，修正相应的数据元素； 广义表的根本运算广义表的根本运算 取表头取表头 HEAD(LS) HEAD(LS)； 取表尾取表尾 TAIL(LS) TAIL(LS)。5.3 5.

3、3 广义表的存储构造广义表的存储构造 广义表中的数据元素可以是单元素，或是广义表，很难用顺序存储构造表示，常采用链式存储构造。 1.表头表尾链存储构造 有两类结点：表结点和单元素结点。 tag=1 hp tp 表结点 tag=0 data 单元素结点 tag标志域，0表示结点为单元素结点，1表示为表结点；hp：表头指针域； tp：表尾指针域； data： 值域。5.3 5.3 广义表的存储构造广义表的存储构造方式描画为：方式描画为： TYPE nodeptr=nodetypeTYPE nodeptr=nodetypenodetype=RECORDnodetype=RECORD tag:0.1

4、tag:0.1 CASE tag OF CASE tag OF 0:(data:elemtp) 0:(data:elemtp) 1:(hp,tp:nodeptr) 1:(hp,tp:nodeptr) END END；5.3 5.3 广义表的存储构造广义表的存储构造这种存储构造的特点是：这种存储构造的特点是：最上层的表结点数即为广义表的长度；最上层的表结点数即为广义表的长度； 层次清楚；层次清楚；表结点数目多，与广义表中括号对的数目不匹配。表结点数目多，与广义表中括号对的数目不匹配。 5.3 5.3 广义表的存储构造广义表的存储构造2. 2. 同层结点链存储构造同层结点链存储构造 有两类结点：表

5、结点和单元素结点。有两类结点：表结点和单元素结点。 tag=1 hp tp tag=1 hp tp 表结点表结点 tag=0 data tp tag=0 data tp 单元素结点单元素结点 tp tp为链接同层下一结点的指针域，其它域的含义为链接同层下一结点的指针域，其它域的含义同表头表尾链构造。同表头表尾链构造。5.3 5.3 广义表的存储构造广义表的存储构造同层结点链构造的特点是：同层结点链构造的特点是：表结点的数目与广义表的括号对数目一致；表结点的数目与广义表的括号对数目一致；写递归算法不方便。写递归算法不方便。例例:P(x,y,z)=:P(x,y,z)=x10y3z2+2x6y3z2

6、+3x5y2z2+x4y4z+6x3y4z+2yz+1x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15 5=(x10y3+2x6y3+3x5y2)z2 =(x10y3+2x6y3+3x5y2)z2 +(x4y4+6x3y4+2y)z+15+(x4y4+6x3y4+2y)z+15=(x10+2x6)y3+3x5y2)z2 =(x10+2x6)y3+3x5y2)z2 +(x4+6x3)y4+2y)z+15+(x4+6x3)y4+2y)z+15=Az2+Bz+15z0=Az2+Bz+15z0其中其中: A=Cy3+Dy2 C=x10+2x6 : A=Cy3+Dy2 C=x10+2x6 D=3x5D=3x5可用广义表表示为可用广义表表示为: :P(x,y,z)=z(A,2),(B,1),(15,0)P(x,y,z)=z(A,2),(B,1),(15,0)A=y(c,3),(D,2) B=y(E,4),(2,1)A=y(c,3),(D,2) B=y(E,4),(2,1)C=x(1,10),(2,6) E=x(1,4),(6,3) C=x(1,10),(2,6) E=x(1,4),(6,3) D=x(3,5)D=x(3,5)三类表结点三类表结点(tag=1): 整个表的