数据结构-广义表详解（类C语言版）

广义表的概念

定义

表头

表尾

例

广义表的性质

广义表与线性表的区别

广义表的存储结构

头尾链表的存储结构

扩展线性链表的存储结构

广义表的基本运算

例

广义表的概念

定义

广义表通常记作：LS = (a1, a2, ..., an)

其中：LS为表名，n为表的长度，每一个ai为表的元素。

习惯上，一般用大写字母表示广义表，小写字母表示原子。

表头

若LS非空（n≥1），则其第一个元素a1就是表头。

记作head(LS) = a1。

注：表头可以是原子，也可以是子表。

表尾

除表头之外的其他元素组成的表。

记作tail(LS) = (a2, ..., an)。

注：表尾不是最后一个元素，而是一个字表。

例

广义表的性质

（1）广义表中的数据元素有相对次序；一个直接前驱和一个直接后继。

（2）广义表的长度定义为最外层所包含元素的个数；

如：C = (a, (b, c))是长度为2的广义表。

（3）广义表的深度定义为该广义表展开后所含括号的重数；

A = (b, c)的深度为1，B = (A, d)的深度为2，C = (f, B, h) 的深度为3.

注意：“原子”的深度为0；“空表”的深度为1。

（4）广义表可以为其他广义表共享；如：广义表B就共享表A。在B中不必列出A的值，而是通过名称来引用，B = (A)。

（5）广义表可以是一个递归的表。如：F = (a, F) = (a, (a, (a, ...)))

注意：递归表的深度是无穷值，长度是有限值。

（6）广义表是多层次结构，广义表的元素可以是单元素，也可以是字表，而字表的元素还可以是字表， ...。可以用图形象地表示。

例：D = (E, F) 其中：E = (a, (b, c)) F = (d, (e))

广义表与线性表的区别

广义表可以看成是线性表的推广，线性表是广义表的特例。

广义表的结构相当灵活，在某种前提下，它可以兼容线性表、数组、树和有向图等各种常用的数据结构。

当二维数组的每行（或每列）作为字表处理时，二维数组即为一个广义表。

另外，树和有向图也可以用广义表来表示。

由于广义表不仅集中了线性表、数组、树和有向图等常见数据结构的特点，而且可有效地利用存储空间，因此在计算机的许多应用领域都有成功使用广义表的实例。

广义表的存储结构

头尾链表的存储结构

// －－－－－广义表的头尾链表存储表示 －－－－－
typedef enum{ATOM, LIST} ElemTag; //ATOM==O: 原子； LIST==1: 子表
typedef struct GLNode 
{
    ElemTag tag;     // 公共部分 ， 用于区分原子结点和表结点
    union            // 原子结点和表结点的联合部分
    {
        AtomType atom; //atom是原子结点的值域，AtomType由用户定义
        struct{struct GLNode *hp, *tp; } ptr; 
            //ptr是表结点的指针域，ptr.hp和ptr.tp分别指向表头和表尾
    };
} *GList;   // 广义表类型

扩展线性链表的存储结构