7第4章(中)数组与串.pptVIP

第4章 数组与串 第4节 广义表 4.4.1 广义表的定义和基本运算 １. 概念 　　（１）广义表GL： n个元素a0, a1, …, an-1组成的有序序列，其中元素ai（0≤ai≤n-1)是数据元素（原子）或者是广义表（子表），记为GL=(a0, a1, …, an-1)。 GL是广义表的名称。　　 n是广义表的长度。 　　若元素ai是数据元素，则称为A的原子； 　　若元素ai是广义表，则称为A的子表。 第4章 数组与串 第4节 广义表 （２）广义表GL =(a0, a1, …, an-1)中， 　　　 a0为广义表GL的表头； (a1, …, an-1)为广义表GL的表尾(还是广义表），分别记为 head(GL)= a0 tail(GL)= (a1, …, an-1) （３）广义表的长度是指广义表中包含元素（包括原子和子表）的个数。 （４）广义表的深度是指广义表中所包含括号的层数。 第4章 数组与串 第4节 广义表 　　为了区分表与原子的书写区别，通常用大写字母表示广义表，用小写字母表示单个数据元素，广义表用括号括起来，括号内的数据元素用逗号分隔开。 　　如： A ＝（（））长度为1的表，其中表头是一个空表； B ＝（a，（b，c，d））是长度为2的表； C ＝（A，B，（））长度为3的表，前面二个元素都是广义表，后面一个是空表； D ＝（）为一个空表；长度为0的表； E ＝（a，E）长度为2的表，其中一个为原子，一个是子表． 第4章 数组与串 第4节 广义表 2．广义表的性质 　　从上述广义表的定义和例子可以得到广义表具有下列二个重要性质： 　　⑴　一个广义表可以被其它广义表共享，例如，表A、表B是表C的共享子表。 　　⑵　广义表可以是递归的表。广义表的定义并没有限制元素的递归，即广义表也可以是其自身的子表。例如表E就是一个递归的表。 　　广义表结构灵活，它可以兼容线性表、数组、树和有向图等各种常用的数据结构。（当二维数组的每行或每列作为子表处理时二维数组即为一个广义表 ） 第4章 数组与串 第4节 广义表 3．广义表基本运算 　　广义表主要有取头操作（Head）和取尾操作（Tail）操作。 　　根据广义表的表头、表尾的定义可知，对于任意一个非空的列表，其表头可能是单元素也可能是子表，而表尾必为子表。例如： Head（B）＝ a 　 Tail（B）＝（（b，c，d）） Head（C）＝ A Tail（C）＝（B，（）） Head（A）＝ （） Tail（A）＝（） Head（E）＝ a Tail（E）＝（E） 　　此外，在广义表上可以定义与线性表类似的一些操作，如建立、插入、删除、拆开、深度、长度、连接、复制、遍历等。 第4章 数组与串 第4节 广义表 4.4.2　广义表的存储 　　广义表都采用链式的存储结构来存储广义表。结点形式为 其中tag是标识域。若结点表示一个原子，则tag=0，且第二个字段为data，它表示原子的名称或数值；若结点表示的是一个广义表，则tag=1，且第二字段为dlink，存放相应子表第一个元素对应结点的地址。Link域是指向同层下一个元素，若没有，即是同层最后一个结点，则置link为空（NULL，或记为^ ）。 第4章 数组与串 第4节 广义表 第4章 数组与串 第4节 广义表 采用C语言其结点形式定义如下： typedef struct lnode { int tag; // 结点类型标识 union { char data; struct lnode *dlink; } val; struct lnode *link; // 指向下一个元素 } GLNode; 第4章 数组与串 第4节 广义表 4.4.3 广义表的递归算法 1． 创建一个链式存储结构的广义表 　　假定广义表是一个括号表达式组成的字符串，其格式为：元素之间用一个逗号分隔，表元素的起止符号分别为左、右圆括号，空表在其圆括号内不包含任何字符。每个原子的值被限定为英文字母。算法思想： 　　用字符串变量 s 来表示一个广义表的括号表达式，从头到尾扫描 s 的每一个符号： 　（1）当遇到是左括号，说明是一个表的开始，则建立一个由 h 指向的表的结点，并用它的dlink域作为子表的表头指针，进行递归调用； 　 第4章 数组与串 第4节 广义表 　（2）当扫描到一个字母，说明它是一个原子，则建立一个由h指向的原子结点； 　（