JavaScript数据结构之广义表的定义与表示方法详解

什么是广义表

广义表是一种包含了无数元素的数据结构，可以是元素或者嵌套的子表。广义表可以表示为：

$\quad\quad\quad GL = (a_0,a_1,...,a_n)$

其中$a_i$可以是元素或者一个子表，如果$a_i$为一个子表，那么$a_i$本身也是一个广义表。广义表中，第一个元素$a_0$表示广义表的类型，对于普通广义表来说，$a_0$为常量L。一个普通广义表可以表示为：

$\quad\quad\quad L = (a_0,a_1,...,a_n)$

$a_0$为常量L，$a_1$到$a_n$可以是元素或者嵌套的广义表。

广义表的表示方法

广义表有两种常见的表示方法：线性存储和二叉链表。

线性存储

线性存储方式是将广义表中的元素按照某种先后次序依次存储在一维数组中。元素与元素之间可以用逗号隔开，元素与子表之间可以用括号隔开。例如，该广义表：

$\quad\quad\quad L = (1,(2,3),4,(5,6,(7,8)))$

可以用线性存储表示为：

$\quad\quad\quad L = [1,\text{'('},2,3,\text{')'},4,\text{'('},5,6,\text{'('},7,8,\text{')'},\text{')'}]$

二叉链表

二叉链表是将广义表中的每个元素和含有嵌套广义表的元素表示为一个二叉树的结点，使用嵌套子树来表示子表。例如，该广义表：

$\quad\quad\quad L = (1,(2,3),4,(5,6,(7,8)))$

可以用二叉链表表示为：

L
├─1
├─sublist
│    ├─2
│    └─3
├─4
└─sublist
     ├─5
     ├─6
     └─sublist
          ├─7
          └─8

广义表的操作

由于广义表中的元素分为常规元素和嵌套的子表，因此一些操作定义成递归方式更合适。

求广义表长度

广义表长度可以递归表示为：如果广义表为空，长度为0，否则长度为广义表第一个元素长度加上剩下元素的长度。递归代码如下：

function glen(gl) {
  if (!gl.length) {
    return 0;
  } else if (typeof gl[0] !== 'object') {
    return 1 + glen(gl.slice(1));
  } else {
    return glen(gl[0]) + glen(gl.slice(1));
  }
}

取广义表的第$i$个元素

获取广义表的第$i$个元素也是递归的实现：如果$i=1$，则返回广义表的第一个元素，否则就是取剩下的广义表的第$i-1$个元素。递归代码如下：

function getgl(gl, i) {
  if (i === 1) {
    return gl[0];
  } else {
    let rest = gl.slice(1);
    if (typeof gl[0] === 'object') {
      rest = gl[0].concat(rest);
    }
    return getgl(rest, i - 1);
  }
}

示例说明

示例1：求广义表长度

假设我们有以下广义表：

$\quad\quad\quad L = (1,(2,3),4,(5,6,(7,8)))$

我们可以使用以上提到的glen函数来求取广义表L的长度：

let L = [1, [2, 3], 4, [5, 6, [7, 8]]];
let len = glen(L);
console.log(len); // output: 8

因此广义表L的长度为8。

示例2：取广义表的第$i$个元素

假设我们有以下广义表：

$\quad\quad\quad L = (1,(2,3),\text{'hello'},(5,6,(7,8)))$

现在我们想要取$L$的第4个元素，也就是字符串'hello'：

let L = [1, [2, 3], 'hello', [5, 6, [7, 8]]];
let fourth = getgl(L, 4);
console.log(fourth); // output: hello

因此，广义表L的第4个元素为字符串'hello'。