算法与数据结构回顾 – 广义表

This article is also available in the following languages: English。

图源：吟游诗人-狼娘 月巴小鹅 111776313

简述

广义表是线性表的一种推广。线性表要求表中元素拥有统一的类型，而广义表无此限制。需要注意的是，广义表和线性表长度一般认为是有限的，但广义表的深度可以是无限的（即递归表）。

广义表是一种数据结构。对广义表的常见操作包括：

• 创建
• 从字符串形式创建
• 销毁
• 复制
• 取表头
• 取表尾
• 判空
• 求长度
• 求深度
• 从表头插入
• 从表头删除
• 遍历

广义表是Lisp语言的基本数据结构。后文以Common Lisp和C++给出各基本操作的示例。

名词注解

长度

指广义表中的元素个数。举例如下：

例一

(a, b)

该表中共有两个元素：原子项a，原子项b。因而该表的长度为2。

例二

(a, (b, c))

该表中共有两个元素：原子项a，广义表(b, c)。因而该表的长度为2。

深度

指广义表中子表的嵌套层数。举例如下：

例一

(a, b)

该表中没有子表，因而该表的深度为1。

例二

(a, (b, c))

该表中嵌套了一个无嵌套的子表，因而该表的深度为2。

例三

((a, b), (c, d))

该表中嵌套了两个无嵌套的子表，因而该表的深度为2。

例四

(a, (b, (c, d)))

该表中嵌套了1个子表，子表中嵌套了1个无嵌套的子表，因而该表的深度为3。

可理解为广义表字符串形式中括号的层数。

子表

嵌套在广义表中的广义表叫做该广义表的字表。例如：

(a, (b, c))

称(b, c)是(a, (b, c))的字表。

原子项

不可作为广义表再分的元素。例如：

(1, (a, b))

上表中1不是广义表，对广义表来说不可再分，因此是原子项。

上表中(a, b)是广义表，可以被分割为(a)与(b)，因此不是原子项。

字符串形式（书写形式）

一种广义表的序列化方法。即将广义表写成由括号、原子项的值、（逗号）等组成的字符串。例如：

(1 2 (A B))

与

(1, 2, (A, B))

都是常见的广义表的书写形式。

Lisp 中的实现

使用SBCL Lisp环境。

创建

使用cons函数可以创建列表。例如创建一个只包含数字1（表头为原子项整数1，表尾为空）的列表：

(cons 1 nil)

或者：

(list 1)

也可以根据已有的表头和表尾创建列表：

(cons 1 '(2 5))

也可以使用符号。

(cons 'a '(b 2))

设置变量X为列表(1 A B)，作为接下来的示例：

(let ((x (cons 1 '(a b)))) (prin1 x))

输出为：

(1 A B)

复制

可以理解为变量传值。

(let ((x (cons 1 '(a b))))
     (let ((y x))
          (prin1 y)))

输出为：

(1 A B)

取表头

使用car函数。

(let ((x (cons 1 '(a b)))) (car x))

输出为：

1

此时输出为原子项。

取表尾

使用cdr函数。

(let ((x (cons 1 '(a b)))) (cdr x))

输出为：

(A B)

此时输出为广义表。

求长度

使用length函数。

例一

有广义表(1 A B)，求长度。

(length '(1 A B))

得到结果为3。

例二

有广义表(1 (A B))，求长度。

(length '(1 (A B)))

得到结果为2。

判空

广义表的长度为0即为空。

(if (= (length '()) 1) t nil)

得到结果为NIL。

从表头插入

反复应用函数cons可以实现从表头将数据插入广义表。

(let ((x (cons 1 '(A B))))
     (setf x (cons 3 (cons 2 x)))
     (prin1 x))

输出为：

(3 2 1 A B)

从表头删除

反复应用函数cdr可以实现从表头删除数据。

(let ((x (cons 1 '(a b))))
     (setf x (cdr (cdr x)))
     (prin1 x))

输出为：

(B)

求深度

基本思路：递归求解。

• 定义函数list-depth，接受变量list作为参数
• 判断list是否为广义表，不是则直接返回0
• 若list是广义表，则：
  • 对该广义表中的每一个元素调用list-depth，使用mapcar实现这一操作。返回值组成一张广义表。
  • 取该广义表的最大值。
  • （赋初始值，可选项）
  • 将已有的最大深度值 +1。

(defun list-depth (list)
    (if (listp list)
        (+ 1 (reduce #'max (mapcar #'list-depth list)
            :initial-value 0))
        0)
)

调用：

(list-depth '(1 (2 3)))

输出为：

2

C++ 实现

由于广义表的特性，其很难使用顺序结构进行存储。因此广义表多建立在链式存储的结构之上。

讨论只含有两种可能结点的广义表：

• int类型的原子项结点
• 由int类型构成的广义表结点；此时相当于该结点是指向子表头结点的指针

因此可以设计“表结构”和“结点结构”。“表结构”中保存该表的头结点指针，及表的长度。当表为空表时，其头结点指针为nullptr。“结点结构”存储了具体的数据。具体存储结构如下：

#define ElementType int

typedef struct Node
{
    bool type;
    Node *next;
    union
    {
        ElementType atom;
        Node *nodePointer;
    }
    data;
};

typedef struct List
{
    int length;
    Node *head;
};

其中，Node.type指明了结点的类型：为false时代表该结点是原子项结点，为true时代表该结点为子表结点。

创建

把表和各结点都放在堆里。

List::List(): length(0), head(nullptr)
{

}

List demo = new List();

销毁

List::~List()
{
    delete *head;
}

判空

利用“表结构”中的length即可。

bool List::CheckEmpty()
{
    if (this->length == 0) {
        return true;
    }
    return false;
}

求长度

同上。

demo.length;

[TODO]