电子科大(罗吴曼)数据结构5

1、第五章 数组和广义表,5.1 广义表的定义 5.2 广义表的基本运算 5.3 广义表的存储结构,5.1 数组和广义表的定义,广义表定义 广义表可定义为：数据元素可以是表的线性表。 记为：LS(d1,d2,dn) LS为表名， di (i1,2,n)，可以是单元素(用小写字母表示)； 也可以是广义表(称为子表，用大写字母表示)； n为表的长度，当长度为0时称为空表； 称非空表的第一个元素d1为表头， 其余元素组成的表(d2,dn)称为表尾。,5.2 数组和广义表的基本运算, 数组的基本运算 给定下标，存取相应的数据元素； 给定下标，修改相应的数据元素；, 广义表的基本运算 取表头 HEAD(LS

2、)； 取表尾 TAIL(LS)。,5.3 广义表的存储结构,广义表中的数据元素可以是单元素，或是广义表，很难用顺序存储结构表示，常采用链式存储结构。 1.表头表尾链存储结构 有两类结点：表结点和单元素结点。, tag=1 hp tp 表结点 tag=0 data 单元素结点 tag标志域，0表示结点为单元素结点，1表示为表结点； hp：表头指针域； tp：表尾指针域； data： 值域。,5.3 广义表的存储结构,形式描述为： TYPE nodeptr=nodetype nodetype=RECORD tag:0.1 CASE tag OF 0:(data:elemtp) 1:(hp,tp:n

3、odeptr) END；,5.3 广义表的存储结构,这种存储结构的特点是： 最上层的表结点数即为广义表的长度； 层次清楚； 表结点数目多，与广义表中括号对的数目不匹配。,例: C=(a, (b, c, d),(b, c, d),(b, c, d),(c, d),(d),5.3 广义表的存储结构,2. 同层结点链存储结构 有两类结点：表结点和单元素结点。 tag=1 hp tp 表结点 tag=0 data tp 单元素结点 tp为链接同层下一结点的指针域，其它域的含义同表头表尾链结构。,5.3 广义表的存储结构,同层结点链结构的特点是： 表结点的数目与广义表的括号对数目一致； 写递归算法不方便

4、。,例: C=(a, (b, c, d),(b, c, d),例:P(x,y,z)= x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z+2yz+15 =(x10y3+2x6y3+3x5y2)z2 +(x4y4+6x3y4+2y)z+15 =(x10+2x6)y3+3x5y2)z2 +(x4+6x3)y4+2y)z+15 =Az2+Bz+15z0 其中: A=Cy3+Dy2 C=x10+2x6 D=3x5 可用广义表表示为: P(x,y,z)=z(A,2),(B,1),(15,0) A=y(c,3),(D,2) B=y(E,4),(2,1) C=x(1,10),(2,6) E=x(1,4),(6,3) D=x(3,5),存储表示 (1) 结点结构 表结点 单元素结点 (2) 用一维数组存储多项式的所有变元 (3) 每一层增设一个表头结点, 并用exp域表明变元在数组中的下标 (4) 增设一个表头结点, 表示整个表,用头指针p指示, 并在exp域填上变元个数,前例: P(x,y,z)=z(A,2),(B,1),(15,0) A=y(c,3),(D,2) C=x(1,10),(2,6),P,D,B,A,C,三类表结点