（）不属于线性的数据结构。

广义表是5.2节提到的线性表的推广。线性表中的元素仅限于原子项，即不可以再分，而广义表中的元素既可以是原子项，也可以是子表（即另一个线性表）。它是n≥0个元素a₁, a₂, …，a_n的有限序列，其中每一个a_i或者是原子，或者是一个子表。广义表通常记为LS=（a₁, a₂, …，a_n），其中LS为广义表的名字，n为广义表的长度，每一个a_i为广义表的元素。但在习惯中，一般用大写字母表示广义表，小写字母表示原子。

广义表一般表示为：

（1）用LS=（a₁， a₂, …，a_n）形式，其中每一个a_i为原子或广义表。

例如：A=（b,c）；B=（a，A）都是广义表。

（2）将广义表中所有子表写到原子形式，并利用圆括号嵌套。

例如：上面提到的广义表A、B可以描述为：

A （b,c）； B （a,A （b，c））

（3）将广义表用树和图来描述，一个广义表的深度指的是该广义表展开后所含括号的层数。例如，A=（b，c）的深度为1，B=（A，d）的深度为2，C=（f，B,h）的深度为3；如下图所示。

广义表的深度

由于广义表的元素类型不一定相同，因此，难以用顺序结构来存储表中的元素，通常采用链接存储方法来存储广义表中元素，并称之为广义链表。广义表需要两种结构的结点，一种是表结点，表示列表；一种是原子节点，表示原子。一个表结点可以由标志域、指示表头的指针域和指示表尾的指针域组成；而原子结点由标志域和值域组成，如下图所示。

广义表的结构

数据类型描述如下：

广义表的存储结构如下图所示。

广义表的存储结构

数据结构

根据数据元素之间关系的不同特性，通常有下列4类基本的逻辑结构，即集合结构、线性结构、树形结构、图形结构。

1）线性结构

线性表是最常用且最简单的一种数据结构。线性表中除第一个元素外，每个元素均只有一个直接前驱；除最后一个元素外，每个元素都只有一个直接后继。

栈是限定仅在表尾进行插入或删除操作的线性表，是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。

队列是一种先进先出（FIFO）的线性表，它只允许在表的一端进行插入，而在另一端删除元素。

2）树

树是n（n≥0）个互不相交的有限集，当n=0时称为空树。在一棵非空树中，有且仅有一个节点称为根节点；当n>1时，其余的节点可分为若干个不相交的集合，其中每一个集合本身又是一棵树，这些集合称为根节点的子树。

3）图

图是由两个集合V和E组成的二元组，记为G=（V, E），其中V是顶点的非空有限集合，E是图中边的有限集合。

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5