图源:吟游诗人-狼娘 月巴小鹅 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]