首页 > 代码库 > 广义表 (五)

广义表 (五)

5.1广义表—广义表的定义和基本运算

 

顾名思义,广义表是线性表的推广。也有人称其为列表(Lists,用复数形式以示与统称的表List 的区别)。

⒈广义表的定义和性质


我们知道,线性表是由n 个数据元素组成的有限序列。其中每个组成元素被限定为单元素,有时这种限制需要拓宽。例如,中国举办的某体育项目国际邀请赛,参赛队清单可采用如下的表示形式:
(俄罗斯,巴西,(国家,河北,四川),古巴,美国,(),日本)

在这个拓宽了的线性表中,韩国队应排在美国队的后面,但由于某种原因未参加,成为空表。国家队、河北队、四川队均作为东道主的参赛队参加,构成一个小的线性表,成为原线性表的一个数据项。这种拓宽了的线性表就是广义表。

广义表(Generalized Lists)是n(n≥0)个数据元素a1,a2,…,ai,…,an 的有序序列,一般记作:
ls=(a1,a2,…,ai,…,an)

其中:ls 是广义表的名称,n 是它的长度。每个ai(1≤i≤n)是ls 的成员,它可以是单个元素,也可以是一个广义表,分别称为广义表ls 的单元素和子表。当广义表ls 非空时,称第一个元素a1 为ls 的表头(head),称其余元素组成的表(a2,…,ai,…,an)为ls 的表尾(tail)。显然,广义表的定义是递归的。

为书写清楚起见,通常用大写字母表示广义表,用小写字母表示单个数据元素,广义表用括号括起来,括号内的数据元素用逗号分隔开。下面是一些广义表的例子:
A =()
B =(e)
C =(a,(b,c,d))
D =(A,B,C)
E =(a,E)
F =(())

⒉广义表的性质


从上述广义表的定义和例子可以得到广义表的下列重要性质:

⑴广义表是一种多层次的数据结构。广义表的元素可以是单元素,也可以是子表,而子表的元素还可以是子表,…。

⑵广义表可以是递归的表。广义表的定义并没有限制元素的递归,即广义表也可以是其自身的子表。例如表E 就是一个递归的表。

⑶广义表可以为其他表所共享。例如,表A、表B、表C 是表D 的共享子表。在D中可以不必列出子表的值,而用子表的名称来引用。


广义表的上述特性对于它的使用价值和应用效果起到了很大的作用。

广义表可以看成是线性表的推广,线性表是广义表的特例。广义表的结构相当灵活,在某种前提下,它可以兼容线性表、数组、树和有向图等各种常用的数据结构。当二维数组的每行(或每列)作为子表处理时,二维数组即为一个广义表。另外,树和有向图也可以用广义表来表示。由于广义表不仅集中了线性表、数组、树和有向图等常见数据结构的特点,而且可有效地利用存储空间,因此在计算机的许多应用领域都有成功使用广义表的实例。

⒊广义表基本运算


广义表有两个重要的基本操作,即取头操作(Head)和取尾操作(Tail)。根据广义表的表头、表尾的定义可知,对于任意一个非空的列表,其表头可能是单元素也可能是列表,而表尾必为列表。例如:
Head(B)= e Tail(B)=()
Head(C)= a Tail(C)=((b,c,d))
Head(D)= A Tail(D)=(B,C)
Head(E)= a Tail(E)=(E)
Head(F)=() Tail(F)=()

此外,在广义表上可以定义与线性表类似的一些操作,如建立、插入、删除、拆开、连接、复制、遍历等。
CreateLists(ls):根据广义表的书写形式创建一个广义表ls。
IsEmpty(ls):若广义表ls 空,则返回True;否则返回False。
Length(ls):求广义表ls 的长度。
Depth(ls):求广义表ls 的深度。
Locate(ls,x):在广义表ls 中查找数据元素x。
Merge(ls1,ls2):以ls1 为头、ls2 为尾建立广义表。
CopyGList(ls1,ls2):复制广义表,即按ls1 建立广义表ls2。
Head(ls):返回广义表ls 的头部。
Tail(ls):返回广义表的尾部。
……

5.2广义表—广义表的存储

由于广义表中的数据元素可以具有不同的结构,因此难以用顺序的存储结构来表示。而链式的存储结构分配较为灵活,易于解决广义表的共享与递归问题,所以通常都采用链式的存储结构来存储广义表。在这种表示方式下,每个数据元素可用一个结点表示。

按结点形式的不同,广义表的链式存储结构又可以分为不同的两种存储方式。一种称为头尾表示法,另一种称为孩子兄弟表示法。

⒈头尾表示法


若广义表不空,则可分解成表头和表尾;反之,一对确定的表头和表尾可惟一地确定一个广义表。头尾表示法就是根据这一性质设计而成的一种存储方法。

由于广义表中的数据元素既可能是列表也可能是单元素,相应地在头尾表示法中结点的结构形式有两种:一种是表结点,用以表示列表;另一种是元素结点,用以表示单元素。

在表结点中应该包括一个指向表头的指针和指向表尾的指针;而在元素结点中应该包括所表示单元素的元素值。为了区分这两类结点,在结点中还要设置一个标志域,如果标志为1,则表示该结点为表结点;如果标志为0,则表示该结点为元素结点。其形式定义说明如下:
typedef enum {ATOM, LIST} Elemtag; /*ATOM=0:单元素;LIST=1:子表*/
typedef struct GLNode {
Elemtag tag; /*标志域,用于区分元素结点和表结点*/
union { /*元素结点和表结点的联合部分*/
datatype data; /*data 是元素结点的值域*/
struct {
struct GLNode *hp, *tp
}ptr; /*ptr 是表结点的指针域,ptr.hp 和ptr.tp 分别*/
/*指向表头和表尾*/
};
}*GList; /*广义表类型*/

头尾表示法的结点形式如图5.21 所示。

对于5.5.1 所列举的广义表A、B、C、D、E、F,若采用头尾表示法的存储方式,其存储结构如图5.22 所示。

从上述存储结构示例中可以看出,采用头尾表示法容易分清列表中单元素或子表所在的层次。例如,在广义表D 中,单元素a 和e 在同一层次上,而单元素b、c、d 在同一层次上且比a 和e 低一层,子表B 和C 在同一层次上。另外,最高层的表结点的个数即为广义表的长度。例如,在广义表D 的最高层有三个表结点,其广义表的长度为3。

⒉孩子兄弟表示法


广义表的另一种表示法称为孩子兄弟表示法。在孩子兄弟表示法中,也有两种结点形式:一种是有孩子结点,用以表示列表;另一种是无孩子结点,用以表示单元素。在有孩子结点中包括一个指向第一个孩子(长子)的指针和一个指向兄弟的指针;而在无孩子结点中包括一个指向兄弟的指针和该元素的元素值。为了能区分这两类结点,在结点中还要设置一个标志域。如果标志为1,则表示该结点为有孩子结点;如果标志为0,则表示该结点为无孩子结点。其形式定义说明如下:
typedef enum {ATOM, LIST} Elemtag; /*ATOM=0:单元素;LIST=1:子表*/
typedef struct GLENode {
Elemtag tag; /*标志域,用于区分元素结点和表结点*/
union { /*元素结点和表结点的联合部分*/
datatype data; /*元素结点的值域*/
struct GLENode *hp; /*表结点的表头指针*/
};
struct GLENode *tp; /*指向下一个结点*/
}*EGList; /*广义表类型*/
孩子兄弟表示法的结点形式如图5.23 所示。

对于5.5.1 节中所列举的广义表A、B、C、D、E、F,若采用孩子兄弟表示法的存储方式,其存储结构如图5.24 所示。

从图5.24 的存储结构示例中可以看出,采用孩子兄弟表示法时,表达式中的左括号“(”对应存储表示中的tag=1 的结点,且最高层结点的tp 域必为NULL。

5.3 广义表—广义表基本操作的实现

广义表 (五)