数据结构广义表.ppt

第一页，共十六页，2022年，8月28日 1 广义表的定义 一、广义表定义 广义表可定义为：数据元素可以是表的线性表。 记为：LS＝(d1,d2,…,dn) LS为表名， di (i＝1,2,…,n)，可以是单元素(称为原子，用小写字母表示)，也可以是广义表(称为子表，用大写字母表示)； 若广义表LS非空，则必有n大于0（即 n > 0） n为表的长度，当长度为0时称为空表； 称非空表的第一个元素d1为表头， 其余元素组成的表(d2,…,dn)称为表尾。 第二页，共十六页，2022年，8月28日 注意：表尾可以可以是空表，而表头可以是原子，也可以是一个表。 广义表的抽象类型定义采用递归定义如教材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的元素。 第三页，共十六页，2022年，8月28日 5． E=(a,E) 这是一个递归列表，其元素中有自己。 广义表也可以用图形表示，例如前述的广义表D和E可表示为： b e a c d a D A B C 广义表D E 广义表E 第四页，共十六页，2022年，8月28日 2 广义表的基本运算 广义表的基本运算 ⑴ 取表头 HEAD(LS)； ⑵ 取表尾 TAIL(LS)。 第五页，共十六页，2022年，8月28日 3 广义表的存储结构 广义表中的数据元素可以是单元素，或是广义表，很难用顺序存储结构表示，常采用链式存储结构。 1.表头表尾链存储结构 有两类结点：表结点和单元素结点。 ┌───┬────┬───┐ │tag=1 │ hp │ tp │ 表结点 └───┴────┴───┘ ┌───┬────────┐ │tag=0 │ data │ 单元素结点 └───┴────────┘ tag标志域，0表示结点为单元素结点，1表示为表结点； hp：表头指针域； tp：表尾指针域； data： 值域。 第六页，共十六页，2022年，8月28日 3 广义表的存储结构 形式描述为： typedef enum{ ATOM, LIST }ElemTag typedef struct GLNode { //定义广义表结点 ElemTage tag; //公共部分，用以区分 原子结点和表结点 Union{ //原子结点和表结点的联合部分 AtomType atom;//原子类型结点域， // AtomType由用户定义 Struct { struct GLNode *hp, *tp; }ptr; }; //表结点的指针域， //ptr.hp 与ptr.tp分别指向广义表的表头和表尾。 }*Glist; //广义表类型 第七页，共十六页，2022年，8月28日 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 第八页，共十六页，2022年，8月28日 3 广义表的存储结构 2. 同层结点链存储结构 有两类结点：表结点和单元素结点。 ┌────┬───┬───┐ │ tag=1 │ hp │ tp │ 表结点 └────┴───┴───┘ ┌────┬───┬───┐ │ tag=0 │ data │ tp │ 单元素