广义表的定义及用法

网上有关“广义表的定义及用法”话题很是火热，小编也是针对广义表的定义及用法寻找了一些与之相关的一些信息进行分析，如果能碰巧解决你现在面临的问题，希望能够帮助到您。

广义表（Lists，又称列表） 是线性表的推广。线性表定义为n>=0个元素a1,a2,a3,…,an的有限序列。线性表的元素仅限于原子项，原子是作为结构上不可分割的成分，它可以是一个数或一个结构，若放松对表元素的这种限制，容许它们具有其自身结构，这样就产生了广义表的概念。

广义表是n (n>=0)个元素a1,a2,a3,…,an的有限序列，其中ai或者是原子项，或者是一个广义表。通常记作LS=（a1,a2,a3,…,an)。LS是广义表的名字，n为它的长度。若ai是广义表，则称它为LS的子表。

抽象数据类型广义表的定义如下：

ADT Glist

{

数据对象：D={ei | i=1,2,..,n;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( &T,L);

初始条件：广义表L存在。

操作结果：取广义表L的尾。

InsertFirst_GL(&L,e);

初始条件：广义表L存在。

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

DeleteFirst_GL(&L,&e);

初始条件：广义表L存在。

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

Traverse_GL (L,visit());

初始条件：广义表L存在。

操作结果：遍历广义表L，用函数visit处理每个元素。

｝

通常用圆括号将广义表括起来，用逗号分隔其中的元素。为了区别原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。若广义表LS（n>=1)非空，则a1是LS的表头，其余元素组成的表(a2,…an)称为LS的表尾。

显然广义表是递归定义的，这是因为在定义广义表时又用到了广义表的概念。广义表的例子如下：

（1）A=（）——A是一个空表，其长度为零。

（2）B=（e）——表B只有一个原子e，B的长度为1。

（3）C=（a,(b,c,d))——表C的长度为2，两个元素分别

为原子a和子表(b,c,d)。

（4）D=（A，B，C）——表D的长度为3，三个元素

都是广义表。显然，将子表的值代入后，

则有D=(( ),(e),(a,(b,c,d)))。

（5）E=（E）——这是一个递归的表，它的长度为2，E相当于一个无限的广义表E=(a,(a,(a,(a,…)))).

从上述定义和例子可推出广义表的三个重要结论：

（1）广义表的元素可以是子表，而子表的元素还可以是子表，。由此，广义表是一个多层次的结构，可以用图形象地表示。P108

（2）广义表可为其它表所共享。例如在上述例（4）中，广义表A，B，C为D的子表，则在D中可以不必列出子表的值，而是通过子表的名称来引用。

（3）广义表的递归性。

综上所述，广义表不仅是线性表的推广，也是树的推广。

由表头、表尾的定义可知：任何一个非空广义表其表头可能是原子，也可能是列表，而其表尾必定是列表。

gethead(B)=egettail(B)=()

gethead(D)=Agettail(D)=(B,C)

由于（B，C）为非空广义表，则可继续分解得到：

gethead(B,C)=Bgettail(B,C)=(C)

注意广义表（）和( ( ) )不同。前者是长度为0的空表，

对其不能做求表头的和表尾的运算；而后者是长度为1的非空表（只不过该表中唯一的一个元素是空表）。对其可进行分解，得到表头和表尾均为空表（）。

广义表的存储结构

由于广义表(a1,a2,a3,…an)中的数据元素可以具有不同的结构，（或是原子，或是广义表），因此，难以用顺序存储结构表示，通常 采用链式存储结构 ，每个数据元素可用一个结点表示。

由于广义表中有两种数据元素，原子或广义表，因此，需要两种结构的结点：一种是表结点，用以表示列表；一种是原子结点，用以表示原子。

若列表不空，则可分解成表头和表尾；反之，一对确定的表头和表尾可唯一确定列表。由此，一个表结点可由三个域组成：标志域、指示表头的指针域和指示表尾的指针域；而原子结点只需两个域：标志域和值域。

1、仅有表结点由三个域组成：

标志域、指示表头的指针域和指示表尾的指针域；而原子域只需两个域：标志域和值域。

头尾链表存储表示

[cpp] view plain copy

typedefenum{ATOM,LIST?}?ElemTag;//ATOM==0:表示原子,LIST==1:表示子表

typedefstructGLNode?{

ElemTagtag;//公共部分，用以区分原子部分和表结点

union{//原子部分和表结点的联合部分

AtomTypeatom;//atom是原子结点的值域,AtomType由用户定义

struct{structGLNode?*hp,?*tp;}?ptr;

//?ptr是表结点的指针域,ptr.hp?和ptr.tp分别指向表头和表尾

};

}?*Glist;//广义表类型

示例如图：

这种存储结构的三个特点：

1。除空表的表头指针为空外，对任何非空列表，其表头指针均指向一个表结点，且该结点中的hp域指示列表表头，tp域指向列表表尾（除非表尾为空，则指针为空，否则必为表结点）；

2。容易分清列表中原子和子表所在层次。如在列表D中，原子e和a在同一层次上，而b、c和d在同一层次且比e和a低一层，B和C是同一层的子表；

3。最高层的表结点个数即为列表的长度。

2、表结点和原子结点均由三个域组成： 标志域、指示表头的指针域和指示表尾的指针域；原子结点的三个域为：标志域、值域和指示表尾的指针域。

其类型定义如下：

扩展线性链表存储表示

[cpp] view plain copy

Typedefenum{ATOM,LIST}?ElemTag;

//ATOM==0:表示原子,LIST==1:表示子表

TypedefstructGLNode?{

ElemTagtag;//公共部分，用以区分原子部分和表结点

union{//原子部分和表结点的联合部分

AtomTypeatom;//原子结点的值域

structGLNode*hp;//表结点的表头指针

};

structGLNode*tp;

//相当于线性链表的next，指向下一个元素结点

}?*Glist;//广义表类型Glist?是一种扩展的线性链表

示例如图：

数据类型是和数据结构密切相关的一个概念。它最早出现在高级程序设计语言中，用以刻划程序中操作对象的特性。在用高级语言编写的程序中，每个变量、常量或表达式都有一个它所属的确定的数据类型。类型显式地或隐含地规定了在程序执行期间变量或表达式所有可能的取值范围，以及在这些值上允许进行的操作。因此，数据类型(Data Type)是一个值的集合和定义在这个值集上的一组操作的总称。

在高级程序设计语言中，数据类型可分为两类：一类是原子类型，另一类则是结构类型。原子类型的值是不可分解的。如C语言中整型、字符型、浮点型、双精度型等基本类型，分别用保留字int、char、float、double标识。而结构类型的值是由若干成分按某种结构组成的，因此是可分解的，并且它的成分可以是非结构的，也可以是结构的。例如，数组的值由若干分量组成，每个分量可以是整数，也可以是数组等。在某种意义上，数据结构可以看成是“一组具有相同结构的值”，而数据类型则可被看成是由一种数据结构和定义在其上的一组操作所组成的。

抽象数据类型

抽象数据类型(Abstruct Data Type，简称ADT)是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。

抽象数据类型和数据类型实质上是一个概念。例如，各种计算机都拥有的整数类型就是一个抽象数据类型，尽管它们在不同处理器上的实现方法可以不同，但由于其定义的数学特性相同，在用户看来都是相同的。因此，“抽象”的意义在于数据类型的数学抽象特性。

但在另一方面，抽象数据类型的范畴更广，它不再局限于前述各处理器中已定义并实现的数据类型，还包括用户在设计软件系统时自己定义的数据类型。为了提高软件的重用性，在近代程序设计方 法学 中，要求在构成软件系统的每个相对独立的模块上，定义一组数据和施于这些数据上的一组操作，并在模块的内部给出这些数据的表示及其操作的细节，而在模块的外部使用的只是抽象的数据及抽象的操作。这也就是面向对象的程序设计方法。

抽象数据类型的定义可以由一种数据结构和定义在其上的一组操作组成，而数据结构又包括数据元素及元素间的关系，因此抽象数据类型一般可以由元素、关系及操作三种要素来定义。

抽象数据类型的特征是使用与实现相分离，实行封装和信息隐蔽。就是说，在抽象数据类型设计时，把类型的定义与其实现分离开来。

关于“广义表的定义及用法”这个话题的介绍，今天小编就给大家分享完了，如果对你有所帮助请保持对本站的关注！