【WIP】算法与数据结构回顾 - 广义表

【WIP】算法与数据结构回顾 - 广义表

图源:@Rella 《glow》 91882132

简述

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

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

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

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

名词注解

长度

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

例一

1
(a, b)

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

例二

1
(a, (b, c))

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

深度

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

例一

1
(a, b)

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

例二

1
(a, (b, c))

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

例三

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

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

例四

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

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

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

子表

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

1
(a, (b, c))

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

原子项

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

1
(1, (a, b))

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

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

字符串形式(书写形式)

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

1
(1 2 (A B))

1
(1, 2, (A, B))

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

Lisp 中的实现

使用 SBCL Lisp 环境。

创建

使用 cons 函数可以创建列表。例如创建一个只包含数字 1(表头为原子项整数 1,表尾为空)的列表:

1
(cons 1 nil)

或者:

1
(list 1)

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

1
(cons 1 '(2 5))

也可以使用符号。

1
(cons 'a '(b 2))

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

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

输出为:

1
(1 A B)

复制

可以理解为变量传值。

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

输出为:

1
(1 A B)

取表头

使用 car 函数。

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

输出为:

1
1

此时输出为原子项。

取表尾

使用 cdr 函数。

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

输出为:

1
(A B)

此时输出为广义表。

求长度

使用 length 函数。

例一

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

1
(length '(1 A B))

得到结果为 3。

例二

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

1
(length '(1 (A B)))

得到结果为 2。

判空

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

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

得到结果为NIL

从表头插入

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

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

输出为:

1
(3 2 1 A B)

从表头删除

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

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

输出为:

1
(B)

求深度

基本思路:递归求解。

  • 定义函数 list-depth,接受变量list 作为参数
  • 判断 list 是否为广义表,不是则直接返回 0
  • list 是广义表,则:
    • 对该广义表中的每一个元素调用 list-depth,使用mapcar 实现这一操作。返回值组成一张广义表。
    • 取该广义表的最大值。
    • (赋初始值,可选项)
    • 将已有的最大深度值 +1。
1
2
3
4
5
6
(defun list-depth (list)
(if (listp list)
(+ 1 (reduce #'max (mapcar #'list-depth list)
:initial-value 0))
0)
)

调用:

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

输出为:

1
2

存储结构

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

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

  • int(32)类型的原子项结点
  • 由 int(32)类型构成的广义表结点

因此可以设计存储结构如下:

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

C - C++ 实现

数据结构定义

设置“表结构”和“结点结构”。“表结构”中保存该表的头结点指针,及表的长度。当表为空表时,其头结点指针为nullptr

按一般考核要求,显式设置类型别名,不使用对象,不使用未经允许的 STL 模板,不使用类型推导,忽略常量标识和异常处理等内容等(“C-styled C++”)。如有需求可自行按照逻辑改写。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef struct Node
{
bool type;
Node *next;
union
{
ElementType atom;
Node *nodePointer;
}
nodeContent;
}
NodeType;

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

随后逐一实现基本方法。

创建

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

1
2
3
4
5
void construct_list(ListType **gList)
{
*gList = new ListType{0, nullptr};
return;
}

销毁

1
2
3
4
5
void destroy_list(ListType **gList)
{
delete *gList;
return;
}

判空

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

1
2
3
4
5
6
7
bool check_list_empty(ListType *gList)
{
if (gList->length == 0) {
return true;
}
return false;
}

求长度

同上。

1
2
3
4
int get_list_length(ListType *gList)
{
return gList->length;
}

【WIP】算法与数据结构回顾 - 广义表

https://www.zhouweitong.site/post/031-algorithm-generalized-list/

作者

ObjectNotFound

发布于

2021-10-29

更新于

2022-01-25

许可协议

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×