深入理解数据结构与算法系列：广义表详解(第二十六讲)

【408数据结构与算法】—广义表（二十六）

一、广义表

• 广义表又称列表Lists是n>=0个元素a0,a1,…an-1的哟选序列，其中每一个ai或者是原子，或者是一个广义表
• 广义表通常记作：LS=（a1,a2,…an）
  其中：LS为表名，n为表的长度，每一个ai为表的元素。习惯上，一般用大写字母表示广义表，小写字母表示原子。



• 
  



• 
  



• 
  

二、广义表的相对性质

1. 广义表中的数据元素有相对次序，一个直接前趋和一个直接后继
2. 广义表的长度定义为最外层所包含的元素的个数，如：​​C=（a,(b,c））​​是长度为2的广义表
3. 广义表的深度定义为该广义表展开后所包含括号的重数
4. 广义表可以为其他广义表共享，如：广义表B就共享表A。在B中不必列出A的值，而是通过名称来引用，B=（A）
5. 广义表也可以是一个递归的表，注意：递归表的深度是无穷的值，长度是有限的值。如​​F=(a,F）=(a,(a,(a,……)))​​
6. 广义表是多层次的结构，广义表的元素可以是单元素，也可以是子表，而子表的元素还可以是子表

广义表与线性表的区别？

1. 广义表是线性表的推广，是由0个或多个单元素或子表组成的有限序列。
2. 广义表与线性表的区别在于：线性表的元素都是结构上不可分的单元素，而广义表的元素既可以是单元素，也可以是有结构的表。
3. 广义表的长度是指广义表中元素的个数。广义表的深度是指广义表展开后所含的括号的最大层数。
4. 非空广义表的第一个元素称为表头，他可以是一个单元素，也可以是一个子表；除表头元素之外，由其余元素所构成的表称为表尾，非空广义表的表尾必定是一个表。

三、广义表的基本运算

求表头GetHead（L）： 非空广义表的第一个元素，可以是一个单一的元素也可以是一个子表

求表尾GetTail（L）：非空广义表除去表头元素以外其他元素所构成的表，表尾一定是一个表。

四、广义表的存储结构

由于广义表中的元素本身又可以具有结构，它是一种带有层次的非线性结构，因此难以用顺序存储结构表示，通常采用链式存储结构。

若广义表不为空，则可分解为表头和表尾两部分。反之，一对确定的表头和表尾可唯一确定一个广义表。

广义表中的元素可以是原子也可以是子表，针对原子和子表可以分别设计不同的节点结构。表节点有标志域、指示表头的指针域和指示表尾的指针域；而原子只有标志域和值域。

例如广义表​​LS=(a,(b,c,d))​​,其链式存储结构如图所示：