第五章数组和广义表 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)给定下标,存取相应的数据元素; (2)给定下标,修改相应的数据元素; 2.广义表的基本运算 (1)取表头HEAD(LS); (2)取表尾TAIL(LS)
2 数组和广义表的基本运算 ⒈ 数组的基本运算 ⑴ 给定下标，存取相应的数据元素； ⑵ 给定下标，修改相应的数据元素； ⒉ 广义表的基本运算 ⑴ 取表头 HEAD(LS)； ⑵ 取表尾 TAIL(LS)
3广义表的存储结构 广义表中的数据元素可以是单元素,或是广义表, 很难用顺序存储结构表示,常采用链式存储结构。 表头表尾镀存储结构 有两类结点:表结点和单元素结点。 tag=l hp tp 表结点 tag=0 data 单元素结点 tag标志域,0表示结点为单元素结点,1表示为表结点; hp:表头指针域;tp:表尾指针域;data:值域
3 广义表的存储结构 广义表中的数据元素可以是单元素，或是广义表， 很难用顺序存储结构表示，常采用链式存储结构。 1.表头表尾链存储结构 有两类结点：表结点和单元素结点。 ┌───┬────┬───┐ │tag=1 │ hp │ tp │ 表结点 └───┴────┴───┘ ┌───┬────────┐ │tag=0 │ data │ 单元素结点 └───┴────────┘ tag标志域，0表示结点为单元素结点，1表示为表结点； hp：表头指针域； tp：表尾指针域； data： 值域
3广义表的存储结构 形式描述为: typedef enum( ATOM, LIST )ElemTag typedef struct GLNode{//定义广义表结点 ElemTage tag;//公共部分,用以区分 原子结点和表结点 Unin{/原子结点和表结点的联合部分 Atom Type atom;//原子类型结点域, // AtomType由用户定义 Struct struct GLNode *hp, *tp; ptr; y //表结点的指针域, //ptr.hp与ptr.tp分别指向广义表的表头和表尾。 }* Glist;//广义表类型
3 广义表的存储结构 形式描述为： typedef enum{ ATOM, LIST }ElemTag typedef struct GLNode { //定义广义表结点 ElemTage tag; //公共部分，用以区分 原子结点和表结点 Unin{ //原子结点和表结点的联合部分 AtomType atom;//原子类型结点域， // AtomType由用户定义 Struct { struct GLNode *hp, *tp; }ptr; }; //表结点的指针域， //ptr.hp 与ptr.tp分别指向广义表的表头和表尾。 }*Glist; //广义表类型
3广义表的存储结构 例:C=(a2(b,c,d) C ((b,C, d)) b, c, d)(c, d) 0 a 这种存储结构的特点是: 最上层的表结点数即为广义表的长度; 层次清楚; 表结点数目多,与广义表中括号对的数目不匹配
3 广义表的存储结构 这种存储结构的特点是： • 最上层的表结点数即为广义表的长度； • 层次清楚； • 表结点数目多，与广义表中括号对的数目不匹配。 例: C=(a, (b, c, d)) 1 1 0 a 1 1 1 0 b 0 c 0 d ＾ ＾ ((b, c, d)) (b, c, d) (c, d) (d) C
3广义表的存储结构 2.同层结点链存储结构 有两类结点:表结点和单元素结点。 tag=1 p tp 表结点 tag=0 data tp 单元素结点 结点结构是无论什么结点都有三个域 第一个域是结点类型标志tag; 第二个域是指向一个列表的指针(当tag=1时) 或一个原子(当tag=0时); 第三个域是指向下一个结点的指针t
3 广义表的存储结构 2. 同层结点链存储结构 有两类结点：表结点和单元素结点。 ┌────┬───┬───┐ │ tag=1 │ hp │ tp │ 表结点 └────┴───┴───┘ ┌────┬───┬───┐ │ tag=0 │ data │ tp │ 单元素结点 └────┴───┴───┘ 结点结构是无论什么结点都有三个域： 第一个域是结点类型标志tag； 第二个域是指向一个列表的指针（当tag=1时） 或一个原子（当tag=0时）； 第三个域是指向下一个结点的指针tp
3广义表的存储结构 形式描述为: typedef enum( ATOM, LIST )ElemTag typedef struct GLNode{//定义广义表结点 E1 emTage tag;//公共部分,用以区分 原子结点和表结点 Tn;n∫// nin //原子结点和表结点的联合部分 AtomType atom;//原子类型结点域 /′ AtomType由用户定义 struct Glnode*hp,;//表结点的表头指针域 struct glnode米tp //指向下一个结点的指针 }* Glist;//广义表类型
3 广义表的存储结构 形式描述为： typedef enum{ ATOM, LIST }ElemTag typedef struct GLNode { //定义广义表结点 ElemTage tag; //公共部分，用以区分 原子结点和表结点 Unin{ //原子结点和表结点的联合部分 AtomType atom;//原子类型结点域， // AtomType由用户定义 struct GLNode *hp,; //表结点的表头指针域 }; struct GLNode *tp; //指向下一个结点的指针 }*Glist; //广义表类型