首页 / 软件开发 / 数据结构与算法 / 数据结构教程 第二十课 广义表

广义表是线性表的推广，其表中的元素可以是另一个广义表,或其自身.

广义表的定义:

ADT GList{

数据对象:D={i=1,2,...,n>=0;ei（-AtomSet或ei（-GList,

AtomSet为某个数据对象}

数据关系:R1={<ei-1,ei>|ei-1,ei（-D,2=<i<=n}

基本操作:

InitGlist（&L）;

操作结果:创建空的广义表L

CreateGList（&L,S）;

初始条件:S是广义表的书写形式串

操作结果:由S创建广义表L

DestroyGlist（&L）;

初始条件:广义表L存在

操作结果:销毁广义表L

CopyGlist（&T,L）;

初始条件:广义表L存在

操作结果:由广义表L复制得到广义表T

GListLength（L）;

初始条件:广义表L存在

操作结果:求广义表L的长度,即元素个数

GListDepth（L）;

初始条件:广义表L存在

操作结果:求广义表L的深度

GlistEmpty（L）;

初始条件:广义表L存在

操作结果:判断广义表L是否为空

GetHead（L）;

初始条件:广义表L存在

操作结果:取广义表L的头

GetTail（L）;

初始条件:广义表L存在

操作结果:取广义表L的尾

InsertFirst_GL（&L,e）;

初始条件:广义表L存在

操作结果:插入元素e作为广义表L的第一元素

DeleteFirst_GL（&L,&e）;

初始条件:广义表L存在

操作结果:删除广义表L的第一元素,并用e返回其值

Traverse_GL（L,Visit（））;

初始条件:广义表L存在

操作结果:遍历广义表L,用函数Visit处理每个元素

}ADT GList

广义表一般记作:LS=（a1,a2,...,an）

其中LS是广义表的名称,n是它的长度,ai可以是单个元素也可是广义表,分别称为原子和子表,当广义表非空时,称第一个元素a1为LS的表头称其余元素组成的广义表为表尾.

广义表的头尾链表存储表示

typedef emnu{ATOM,LIST} ElemTag;

typedef struct GLNode{

ElemTag tag;

union{

AtomType atom;

struct{struct GLNode *hp,*tp;}ptr;

}

}

有A、B、C、D、E五个广义表的描述如下：

A=（） A是一个空表,它的长度为零

B=（e） 列表B只有一个原子e,B的长度为1.

C=（a,（b,c,d）） 列表C的长度为2,两个元素分别为原子a和子表（b,c,d）

D=（A,B,C） 列表D的长度为3,三个元素都是列表,显然,将子表的值代入后,则有D=（（）,（e）,（a,（b,c,d）））

E=（a,E） 这是一个递归的表,它的长度为2,E相当于一个无限的列表E=（a,（a,（a,...）））

上述五个广义表用以上的存储结构的存储映像如下: