图源:@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。