广义表 1广义表的定义 2广义表的基本运算 3广义表的存储结构
广义表 1 广义表的定义 2 广义表的基本运算 3 广义表的存储结构
1义表的定义 广义表定义 广义表可定义为:数据元素可以是表的线性表。 记为:LS=(d1,d2…,dn) LS为表名, d;(i=1,2,…,n),可以是单元素(称为原子,用小写 字母表示),也可以是广义表(称为子表,用大写字母表 示); 若广义表LS非空,则必有n大于0(即n>0) n为表的长度,当长度为0时称为空表; 称非空表的第一个元素d1为表头, 其余元素组成的表(d2,,d)称为表尾
1 广义表的定义 一、广义表定义 广义表可定义为：数据元素可以是表的线性表。 记为：LS＝(d1,d2,…,dn) LS为表名， di (i＝1,2,…,n)，可以是单元素(称为原子，用小写 字母表示)，也可以是广义表(称为子表，用大写字母表 示)； 若广义表LS非空，则必有n大于0（即 n > 0） n为表的长度，当长度为0时称为空表； 称非空表的第一个元素d1为表头， 其余元素组成的表(d2,…,dn)称为表尾
注意:表尾可以可以是空表,而表头可以是原子,也可 以是一个表 广义表的抽象类型定义采用递归定义如教材P.107。 二、广义表的表达方式及例子 1.A=()A是一个空表,其长度为0。 2.B=(e)列表B只有一个原子e,其长度为1。 3.C=(a,(b,c,d)列表C的长度为2,表头为原子, 第二个元素是一个列表(b,c,d)。 4.D=(A,B,C)列表D的长度为3, 表头也是一个列表A,表尾是列表(A,B), 注意:这里引用了已有的列表A、B、C作为该广义表D的 元素
注意：表尾可以可以是空表，而表头可以是原子，也可 以是一个表。 广义表的抽象类型定义采用递归定义如教材P.107。 二、 广义表的表达方式及例子 1．A=( ) A是一个空表，其长度为0。 2．B=(e) 列表B只有一个原子e，其长度为1。 3．C=(a,(b,c,d)) 列表C的长度为2，表头为原子， 第二个元素是一个列表(b,c,d)。 4. D=(A,B,C) 列表D的长度为3， 表头也是一个列表A，表尾是列表（A, B）, 注意：这里引用了已有的列表A、B、C作为该广义表D的 元素
5.E=(a,E)这是一个递归列表,其元素中有自己 广义表也可以用图形表示,例如前述的广义表D和E可表示为: 广义表D 广义表E ④(B a
5． E=(a,E) 这是一个递归列表，其元素中有自己。 广义表也可以用图形表示，例如前述的广义表D和E可表示为： b e a c d a D A B C 广义表D E 广义表E
2广义表的基本运算 广义表的基本运算 (1)取表头HEAD(LS); (2)取表尾TAIL(LS)
2 广义表的基本运算 广义表的基本运算 ⑴ 取表头 HEAD(LS)； ⑵ 取表尾 TAIL(LS)