数据结构-广义表..ppt

1 广义表的定义 第5章-2 广义表 2 广义表的存储结构 3 广义表的运算 本章小结 5.1 广义表的定义 广义表简称表,它是线性表的推广一个广义 表是n(n≥0)个元素的一个序列,若n=0时则称为空 表设ai为广义表的第i个元素,则广义表GL的一 般表示与线性表相同： GL=(a1,a2,…,ai,…,an) 其中n表示广义表的长度,即广义表中所含元 素的个数,n≥0如果ai是单个数据元素,则ai是广 义表GL的原子；如果ai是一个广义表,则ai是广义 表GL的子表 广义表的应用： 人工智能领域的表处理语言LISP； 多元多项式的表示； 用来表示树、图 广义表具有如下重要的特性： (1)广义表中的数据元素有相对次序； (2)广义表的长度定义为最外层包含元素个数； (3)广义表的深度定义为所含括号的重数其中,原子 的深度为0,空表的深度为1； (4)广义表可以共享；一个广义表可以为其他广义表 共享；这种共享广义表称为再入表； (5)广义表可以是一个递归的表一个广义表可以是 自已的子表，这种广义表称为递归表递归表的深度 是无穷值,长度是有限值； (6)任何一个非空广义表GL均可分解为表头 head(GL) = a1和表尾tail(GL) = ( a2,…,an) 两部分。

为了简单起见,下面讨论的广义表不包括前面定 义的再入表和递归表,即只讨论一般的广义表另 外,我们规定用小写字母表示原子,用大写字母表示 广义表的表名例如： A=( ) B=(e) C=(a,(b,c,d)) D=(A,B,C)=((),(e),(a,(b,c,d))) E=((a,(a,b),((a,b),c))) 如果把每个表的名字(若有的话)写在其表的前面,则 上面的5个广义表可相应地表示如下： A() B(e) C(a,(b,c,d)) D(A(),B(e),C(a,(b,c,d))) E((a,(a,b),((a,b),c))) 若用圆圈和方框分别表示表和单元素,并用线段把表 和它的元素(元素结点应在其表结点的下方)连接起来,则 可得到一个广义表的图形表示例如,上面五个广义表 的图形表示如下图所示 A() B(e) C(a,(b,c,d)) D(A(),B(e),C(a,(b,c,d))) E((a,(a,b),((a,b),c))) 当广义表Ls非空时，称第一个元素为Ls的表头， 称其余元素组成的子表为Ls的表尾。

广义表的基本操作： 取表头：GetHead(Ls) 取表尾：GetTail(Ls) 5.2 广义表的存储结构 广义表是一种递归的数据结构,因此很难为每个 广义表分配固定大小的存储空间,所以其存储结构只 好采用动态链式结构 表结点 原子结点 typedef enum{ATOM, LIST} ElemTag; //ATOM==0: 原子; LIST==1:子表 typedef struct GLNode{ ElemTag tag; union{ AtomType atom; struct {Struct GLNode *hp, *tp;} ptr; } } *Glist; tag=1 hp tp tag=0 atom 第一种链式存储结构（存放表头和表尾） 空表 LS = NULL 若表头为原子，则为tag=0 atom 否则，依次类推 非空表 LS tag=1 指向表头的指针 指向表尾的指针 A = ( ) B= ( e ) C = ( a , ( b , c , d ) ) D=( A , B , C ) B 1 ^ 0 e 1 1 ^ 1 1 ^ 10 a 0 b 0 d0 c C 1 ^ 1 1 ^ D A=NULL 即: A ^ ls =( a , ( ) , ( ( b , c ) , d ) ) 1 1 ^ 1 ^ 1 1 ^ 1 1 ^ 0 a 0 b 0 c 0 d ls typedef struct lnode {int tag; //结点类型标识 union { ElemType data; struct lnode *sublist; } val; struct lnode *link;//指向下一个元素 } GLNode;//广义表结点类型定义 第二种链式存储结构（存放孩子和兄弟） 广义表的存储结构 广义表的两种基本情况 ： 为原子的情况 ： A = ( ) B= ( e ) C = ( a , ( b , c , d ) ) D=( A , B , C ) A 1 ^ ^ B 1 ^ 0 e ^ 1 ^ 1 1 ^ D 1 C 1 ^ 1 ^ 0 d 0 a 0 b 0 c 5.3 广义表的运算 1. 求广义表的长度 在广义表中,同一层次的每个结点是通过link域 链接起来的,所以可把它看做是由link域链接起来的 单链表。

这样,求广义表的长度就是求单链表的长度 ,可以采用以前介绍过的求单链表长度的方法求其长 度 求广义表长度的非递归算法如下： int GLLength(GLNode g) //g为一个广义表头结点的指针 { int n=0; g=g->val.sublist;//g指向广义表的第一个元素 while (g!=NULL) { n++; g=g->link; } return n; } 2. 求广义表的深度 对于带头结点的广义表g,广义表深度的递归定义 是它等于所有子表中表的最大深度加1若g为原子, 其深度为0 求广义表深度的递归模型f( )如下： f(g)= 0 若g为原子 1 若g为空表 MAX{f(subg)}+1 其他情况,subg为g的子表 int GLDepth(GLNode g) //求带头结点的广义表g的深度 { int max=0,dep; if (g->tag==0) return 0; //为原子时返回0 g=g->val.sublist; //g指向第一个元素 if (g==NULL) return 1; //为空表时返回1 while (g!=NULL) //遍历表中的每一个元素 { if (g->tag==1) //元素为子表的情况 { dep=GLDepth(g); //递归调用求出子表的深度 if (dep>max) max=dep; //max为同一层所求过的子表中深度的最大值 } g=g->link; //使g指向下一个元素 } return(max+1); //返回表的深度 } 本章小结 本章的基本学习要点如下： (1)掌握广义表的定义。

(2)重点掌握广义表的链式存储结构 (3)掌握广义表的基本运算,包括创建广义表、 输出广义表、求广义表的长度和深度 (4)灵活运用广义表这种数据结构解决一些综合 应用问题 。