三、广义表的运算建立广义表的存储结构

1、广义表一、广义表的定义广义表 广义表（Lists）简称表，它是线性表的推广。广义表在LISP语言中作为一种基本的数据结构，就连程序也表示成一系列的广义表。 一个广义表是n（n0）个元素的一个序列，当n=0时则称为空表。在一个非空的广义表中，其元素可以是某一确定类型的对象（这种元素被称做单元素），也可以是由单元素构成的表（这种元素可相对地被称做子表或表元素）。显然广义表的定义是递归的，广义表是种递归的数据结构。一、广义表的定义广义表的表示 设ai为广义表的第i个元素，则广义表的一般表示与线性表相同： （a1，a2，ai，ai+1，an） 其中n表示广义表的长度，即广义表中所含元素的个数，n0。

2、同线性表一样，也可以用一个标识符来命名一个广义表，如用LS命名命名上面的广义表，则为： LS=（a1，a2，ai，ai+1，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）一、广义表的定义广义表的表示 把每个表的名字（若有的话）写在表的前面也是一种表示广义表的方法，如对于上面的五个广义表可相应表示为： A（ ） B（e） C

3、（a ,（b , c , d） D（A（ ）, B（e）, C（a ,（b , c , d） E（a ,（a , b）,（a , b）, c）一、广义表的定义广义表的图形表示 若用圆圈和方框分别表示表（表元素）和单元素，并用线段把表和它的元素（元素结点应在其表结点的下方）连接起来，则可得到一个广义表的图形表示。上表五个广义表的图形表示如下 ：aabcabEeacbdDABCcdbaCAeB一、广义表的定义广义表的图形表示 从图可知：广义表的图形表示象倒着画的一棵树，树根结点代表整个广义表，各层树枝结点代表相应的子表，树叶结点代表单元素。当然，特殊的广义表还有比树更复杂的结构图结构。aabcab

4、EeacbdDABCcdbaCAeB一、广义表的定义广义表的术语 对于一个非空的广义表来说，它的第一个元素称为该广义表的表头（head），除第一个元素外的所有元素构成的表称为该广义表的表尾（tail）。如对于上术的五个广义表来说，A是空表，没有表头和表尾；B的表头为单元素e，表尾为空表（ ）；C的表头为a，表尾为（b , c , d），它又是一个非空表，表头为表元素（b , c , d），表尾为空表；D的表头为A，即一个空表，表尾为（B , C），它还可以分解为表头和表尾；E的表头为（a ,（a , b）,（a , b）, c），表尾为空表。一、广义表的定义广义表的术语 一个表的深度是指该表中

5、括号嵌套的最大次数，在图形表示中，则是指从树根结点到每个树枝结点（即表结点）所经过的结点个数的最大值。如表A和B的深度为1，表C，D，E的深度分别为2，3和4。aabcabEeacbdDABCcdbaCAeB二、广义表的存储结构广义表采用的存储结构 广义表是一种递归的数据结构，因此很难为每个广义表分配固定大小的存储空间，所以其存储结构只好采用动态链接结构。二、广义表的存储结构广义表的结点 在一个广义表中，其数据元素有单元素和子表之分，所以在对应的存储结构中，其存储结点也有单元素结点和子表结点之分。对于单元素结点，应包括值域和指向其后继结点的指针域；对于子表结点，应包括指向子表中第一个结点的表头

6、指针域和指向其后继结点的指针域。为了把广义表中的单元素结点和子表结点区别开来，还必须在每个结点中增设一个标志域，让标志域取两种不同的值，从而区分两种不同的结点。二、广义表的存储结构广义表结点类型的定义struct GLNode bool tag ; /标志域 union /值域或子表的表头指针域 ElemType data ; GLNode * sublist ; ; GLNode * next ; /指向后继结点的指针域 ;二、广义表的存储结构广义表结点类型的定义 其中tag作为标志域，取false时表示单元素结点，使用无名联合中的data域，用来存储元素值，取true时表示子表结点，使用无

7、名联合中的sublist域，用来存储子表的表头指针，通过它实现向子表的链接，即实现广义表的递归结构。结点中的nest作为指向其后继结点的指针域，通过它把表中的所有结点依次链接起来。二、广义表的存储结构广义表的链接存储结构 前面五个广义表的链接存储结构如：A=NULLe0Bb0ca001b0a011a01E0c0db01a0e0111Dd0e0b01a0C二、广义表的存储结构带表头附加结点的广义表链接存储结构 若把整个广义表也同样用一个表结构来表示的话，则应在每个广义表的表头结点（即表中第一个结点）之前增加一个表结点（称此为表头附加结点），此表结点的sublist域指向表头结点，next域为空，

8、表头指针则指向这个表结点。二、广义表的存储结构带表头附加结点的广义表链接存储结构 例如在广义表A，B，C的表头结点之前增加这样的表结点，则对应的结果如图，这种带表头附加结点的广义表表示，将给广义表的某些运算带来方便。d0e0b01a01Ce01B1A三、广义表的运算求广义表的长度 在广义表中，同一层次的每个结点是通过next域链接起来的，所以可把它看做是由next域链接起来的单链表。这样，求广义表的长度就是求单链表的长度，可以采用求单链表长度的方法。由于单链表的结构也是一种递归结构，即每个结点的指针域均指向一个单链表（称为该结点的后继单链表），它所指向的结点为该单链表的第一个结点（即表头结点）

9、，所以求单链表的长度也可以采用递归算法。若单链表为非空，其长度等于1加上其后继单链表的长度；若单链表为空，则长度为0，这是递归的终止条件。三、广义表的运算求广义表的长度 求广义表长度的递归算法：int Lenth ( GLNode * GL ) /求GL所指向的广义表的长度 if ( GL != NULL ) return 1+Lenth ( GL - next ) ; else return 0 ;三、广义表的运算求广义表的深度 广义表深度的递归定义是，它等于所有子表中表的最大深度加1。若一个表为空或仅由单元素所组成，则深度为1。设dep表示任一子表的深度，max表示所有子表中的最大深度，D

10、epth表示广义表的深度，则有： Depth = max + 1 因一个表不包含任何子表时，其深度为1，所以max的初值应为0.三、广义表的运算求广义表的深度求广义表的深度算法：int Depth ( GLNode * GL ) /求GL所指向的广义表的深度 int max = 0 ; /给max赋初值0 while ( GL != NULL ) /遍历表中的每一个结点 if ( GL - tag = true ) int dep = Depth ( GL - sublist ) ; /递归调用求出子表的深度 if ( dep max ) max = dep ; /让max始终为同一层所求过的

11、子表中深度的最大值 GL = GL - next ; /使GL指向同一层的下一个结点 return max + 1 ; /返回表的深度三、广义表的运算求广义表的深度 从这个算法可以看出，当GL为一个空表或仅由单元素组成的线性表时，不进入下一层次的递归调用，而结束本次调用并返回1。当GL含有子表时才会进入求子表深度的递归调用，返回后修改max的值，使之成为所求过的本层次子表中深度的最大值。本层次的所有结点都扫描完毕后，结束本次调用并返回表的深度。三、广义表的运算建立广义表的存储结构 假定广义表中的元素ElemType为字符类型char，每个单元素的值被限定为英文字母。并假定广义表由键盘输入，其格

12、式为：元素之间用一个逗号分隔，表元素的起、止符号分别为左、右圆括号，空表在其圆括号内使用一个“#”字符表示，整个表最后使用一个分号作为结束符。如“（a ,（#）, b , e（d ,（e）；”就是一个符合上述规定的广义表输入格式。三、广义表的运算建立广义表的存储结构 建立广义表存储结构的算法同样是一个递归算法，该算法使用一个具有GLNode * 类型的引用指针参数，用以返回所建广义表的表头指针，假定用GL表示。在算法的执行过程中，对于从键盘上输入的一个广义表，需要从头到尾扫描每一个字符。当碰到左括号时，表明它是一个表元素的开始，则应建立一个由GL指向的表结点，并用它的sublist域作为子表的

13、表头指针进行递归调用，来建立子表的存储结构；当碰到一个英文字母时，表明它是一个单元素，则应建立一个由GL指向的单元素结点；当碰到一个“#”字符时，表明它是一个空表，则应置GL为空。当建立了一个由GL指向的结点后，接着碰到逗号字符时，表明存在后继结点，需要建立当前结点（即由GL指向的结点）的后继表；当碰到右括号时，表明当前所处理的表已经结束，应置当前结点的next域为空。三、广义表的运算建立广义表存储结构 算法如下：void Create ( GLNode * GL ) /生成引用形参GL所指向的带表头附加结点的广义表 char ch ; cin ch ; /读入一个字符，此处只可能读入空格（#

14、） if ( ch = # ) GL = NULL ; /若输入空格，则置GL为空 else if ( ch = ( ) /建立由GL所指向的子表结点并递归构造子表 GL = new GLNode ; GL - tag = true ; Create ( GL - sublist ) ; 三、广义表的运算建立广义表的存储结构 else /建立由GL所指向的单元素结点 GL = new GLNode ; GL - tag = false ; GL - data = ch ; cin ch ; /此处读入的字符必为逗号、右括号或分号 if ( GL = NULL ) ; /此处的ch必然为）字符，

15、什么都不做 else if ( ch = , ) Create (GL - next ) ; /递归构造后继表 else if ( ( ch = ) ) | ( ch = ; ) GL - next = NULL ; /无后继表，置GL的后继指针域为空三、广义表的运算打印输出广义表 根据以GL为带表头附加结点的广义表的表头指针，打印输出该广义表同样需要向子表递归调用和向后继表递归调用。当GL结点为表元素结点时，则应首先输出作为一个表的起始符号的左括号，然后输出以GL - sublist 为表头指针的表，最后输出一个作为表终止符的右括号；当GL结点为单元素结点时，则应输出该元素的值。当GL结点输

16、出结束后，若存在后继结点，则应首先输出一个逗号作为分隔符，然后再递归输出由GL - next 指针所指向的后继表。三、广义表的运算打印输出广义表 算法如下：void Print ( GLNode * GL ) /输出由值参GL所指向的带有表头附加结点的广义表 if ( GL - tag = true ) /输出GL结点 cout sublise = NULL ) cout sublist ) ; /若为非空表，则递归输出此表 cout ) ; /当一个表输出结束后，在最后输出一个右括号终止符 else cout data ; /对于单元素结点，输出该结点的值 if ( GL - next !=

17、 NULL ) /若GL结点存在后继结点，则先输出逗号分隔符后，再递归输出后继表 cout next ) ; 四、简单程序举例广义表程序 编写一个程序，首先建立广义表：( ( a , ( b , c ) ) , ( d , e , ( ( # ) , ( f ) ) ) , g ) ;的存储结构，接着输出该广义表，然后求出该广义表的长度和深度。 假定广义表运算的算法保存在程序文件中。四、简单程序举例广义表程序#include #include typedef char ElemType ;struct GLNode bool tag ; union ElemType data ; GLNode * sublist ; ; GLNode * next ; ;四、简单程序举例广义表程序#include “”void main ( ) GLNode *