详解广义表长度与深度计算方法

一、 广义表的表示

广义表是一种递归定义的表，它的形式可以用如下方式表示：

• 空表：()。
• 普通表：包含元素的线性表，如 (a, b, c)。
• 嵌套表：可以包含子表，如 (a, (b, c), d)。

二、 广义表的长度

长度（Length）是指广义表的第一层元素个数。

计算方法

• 对于空表 ()，长度为 0。
• 对于非空广义表，其长度是第一层中的直接元素个数，不包括递归子表内部的元素个数。

例如：

1. (a, b, c) 的长度是 3（包含 3 个直接元素）。
2. (a, (b, c), d) 的长度是 3（第一层有 a、(b, c) 和 d 三个元素）。
3. () 的长度是 0。

三、 广义表的深度

深度（Depth）是指广义表的最大嵌套层数。

计算方法

• 对于空表 ()，深度为 1。
• 对于普通表（无嵌套子表），深度为 1。
• 对于嵌套表，其深度为子表的最大深度加 1。

递归规则

1. 如果广义表为空，则深度为 1。
2. 如果广义表中包含子表，则需要计算所有子表的深度，取其中的最大值，加上 1。

例如：

1. (a, b, c) 的深度是 1（没有嵌套层）。
2. (a, (b, c), d) 的深度是 2（(b, c) 是第一层中的子表，其深度为 1，整体深度为 2）。
3. (a, (b, (c, d), e), f) 的深度是 3（最深的子表是 (c, d)，深度为 2，加上第一层为 3）。

四、 举例说明

例 1：广义表 L = (a, (b, c), d, (e, (f, g)))

• 长度：第一层元素为 a、(b, c)、d 和 (e, (f, g))，共 4 个，长度为 4。
• 深度：
  • 第一层：a、d 深度为 1。
  • 子表 (b, c) 深度为 1。
  • 子表 (e, (f, g)) 深度为 2（(f, g) 的深度为 1，加 1）。
  • 总深度为 3。

例 2：广义表 L = ()

• 长度：空表长度为 0。
• 深度：空表深度为 1。

例 3：广义表 L = (a, (b, (c, (d))))

• 长度：第一层有 a 和 (b, (c, (d)))，共 2 个，长度为 2。
• 深度：
  • (b, (c, (d))) 是子表。
  • (c, (d)) 是其子表，深度为 2。
  • (d) 深度为 1。
  • 总深度为 4。

五、 步骤总结

长度计算

1. 从左到右，统计广义表第一层的元素个数（包括原子和子表）。
2. 不需要进入子表。

深度计算

1. 遇到子表时，递归计算子表的深度。
2. 取所有子表深度的最大值，加上 1。