接着讲递归结构

人生代码

共 1794字,需浏览 4分钟

 ·

2021-02-08 14:23

接着讲递归结构

递归(递归定义的)数据结构是在部分中复制自身的结构。

我们刚刚见过在上面的公司结构的例子。

A公司部门是:

要么是一群人。

或者一个带有部门的对象。

web开发人员还有更著名的例子:HTML和XML文档。

在HTML文档中,一个HTML标签可能包含以下列表:

文本块。

html注释。

其他html标签(可能包含文本片段/注释或其他标签等)。

这又是一个递归定义。

为了更好地理解,我们将介绍另一种名为“链表”的递归结构,在某些情况下,它可能是数组的更好选择。

链表

想象一下,我们想存储一个有序的对象列表。

自然的选择是一个数组:

let arr = [obj1, obj2, obj3];

但是数组有一个问题。“删除元素”和“插入元素”操作代价很高。例如,arr.unshift(obj)操作必须对所有元素重新编号,以便为新的obj腾出空间,如果数组很大,则需要花费时间。与arr.shift()相同。

只有那些不需要大规模重编号的结构修改是在数组末尾操作的:arr.push/pop。数组对于大的队列来说很慢,当我们需要从一开始就处理时。

另外,如果我们真的需要快速插入/删除,我们可以选择另一种称为链表的数据结构。

链表元素被递归定义为一个对象:

值。

引用下一个链表元素的next属性,如果结束,则为null。

let list = {
  value1,
  next: {
    value2,
    next: {
      value3,
      next: {
        value4,
        nextnull
      }
    }
  }
};

列表的图示:

创建的另一个代码:

let list = { value1 };
list.next = { value2 };
list.next.next = { value3 };
list.next.next.next = { value4 };
list.next.next.next.next = null;

在这里我们可以更清楚地看到有多个对象,每个对象都有值,下一个对象指向邻居。list变量是链表中的第一个对象,因此跟随它的next指针可以到达任何元素。

这个列表可以很容易地被分割成多个部分,然后再连接回来:

let secondList = list.next.next;
list.next.next = null;

加入:

list.next.next = secondList;

当然,我们可以在任何地方插入或删除物品。

例如,要添加一个新值,我们需要更新列表的头:

let list = { value1 };
list.next = { value2 };
list.next.next = { value3 };
list.next.next.next = { value4 };

// prepend the new value to the list
list = { value"new item"next: list };

要从中间删除一个值,更改前一个值的下一个:

list.next = list.next.next;

我们列了清单。下一个跳过1到值2。值1现在被排除在链之外。如果它没有存储在其他地方,它将自动从内存中删除。

与数组不同的是,没有质量重编号,我们可以很容易地重新排列元素。

当然,列表并不总是比数组好。否则,每个人都会只使用列表。

主要的缺点是我们不能简单地按编号访问元素。在数组中,arr[n]是一个直接引用。但是在列表中,我们需要从第一项开始,然后再走N次,才能得到第N个元素。

但我们并不总是需要这样的操作。例如,当我们需要队列甚至deque时——这种有序结构必须允许非常快地从两端添加/删除元素,但不需要访问其中间部分。

列表可以增强:

我们可以添加属性prev来引用之前的元素,方便向后移动。

我们还可以添加一个名为tail的变量来引用列表的最后一个元素(并在从末尾添加/删除元素时更新它)。

数据结构可以根据我们的需要而变化。


浏览 17
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报