广义表.pptVIP

1. 广义表的定义（列表） 广义表是线性表的推广，是由零个或多个单元素或子表所 组成的有限序列。 LS=(a1,a2,…,ai,…,an) ai：是单个数据元素,则ai是广义表的原子；如果ai是一个广义表,则ai是广义表的子表。 规定用小写字母表示原子,用大写字母表示广义表的 表名。 广义表与线性表的区别： 线性表的成份都是结构上不可分的单个数据元素，而广 义表的成份即可以是单元素，也可以是有结构的表，其定义 是递归的定义。 广义表的长度：广义表中所含元素的个数n,n≥0。 广义表的深度：广义表展开后所含的括号的最大层数。（广义表中括号嵌套的最大次数，广义表中括弧的重数） D=( )空表，长度为0，深度为1。 A=(a, (b, c)) 长度为2，第一个元素为原子a，第二个元素为子表(b, c)，深度为2。 B=(A, A, D) 长度为3， 其前两个元素为表A， 第三个元素为空表D，深度为3。 C=(a, C) 长度为2递归定义的广义表，C相当于无穷表C=(a,(a, (a,…)))，深度无限。 递归表的深度是无穷值,长度是有限值。 F=((a, (a, b), ((a, b), c))) 长度为1，深度为4。 广义表的表头(Head)和表尾(Tail)： 当广义表非空时，称第一个元素a1为广义表的表头， 其余元素组成的表(a2, a3, …,an)称为广义表的表尾。 表头可能是原子，也可能是广义表，但表尾一定是广 义表。 广义表的图形表示 用方框表示原子，用圆圈表示广义表。 2. 广义表的基本操作 取表头 GetHead(LS) = a1。 取表尾 GetTail(LS) = (a2,a3,…,an)。 ①B=(e) GetHead(B) = e; GetTail(B) = ( ). ②A=(a, ((b, c), d, e)) GetHead( GetHead( GetTail(A))) = GetHead( GetHead( ( ((b, c), d, e) ) )) = GetHead( ((b, c), d, e) ) = (b, c). ③A=( ); B = ( ( ) ) A空表，长度0，深度1，无表头和表尾； B长度1，深度2，表头( )，表尾( )。 练习：从广义表A=(a,b,(c,d),(e,(f,g)))中取出原子f，应该采取什么样的操作？ 3. 广义表的存储结构 广义表是一种递归的数据结构,因此很难为每个广义表分配固定大小的存储空间,所以其存储结构只好采用动态链式结构。 广义表的头尾链表存储表示 广义表的头尾链表存储表示 C=(a, (b, c, d)) A=( ) A = NULL; D=( ); A= (a, b, c); B=(A, A, D); C = (a, C). 广义表的存储 给定一个字符串形式的广义表，如果将该广义表存储起来？ 递归建表 例如对C=(( ), a, (b, c, d)) 进行建表操作 求广义表的深度 递归求广义表的深度 练习：广义表的深度（depth.c/depth.in/depth.out）有一广义表，其每个原子都是小写字母，现在输入这个广义表的字符串形式，求这个广义表的深度输入样例：(a,(b,c,( )))输出样例：3 * 广义表 5.4 广义表 A=( ); B=(e); C=(a, (b, c, d)) D=(A, B, C); E=((a, (a, b), ((a, b), c))) atom Tag=0 hp:指向该表的表头；tp:指向该表的表尾。 typedef enum {ATOM, LIST} ElemTag; //ATOM＝0，表示原子；LIST＝1，表示子表 typedef struct GLNode { ElemTag tag; //标志位tag用来区别原子结点和表结点 union{  AtomType atom; //原子结点的值域atom struct { struct GLNode * hp, *tp; } ptr;//表结点的指针域 };  }*GList； tp hp Tag=1 表结点 原子结点 (a, (b, c, d)) ((b, c, d)) (b, c, d) (c, d) (