算法(4th ed)(131):基础——背包、队列和栈 5.3.2

阅读数:9 2019 年 11 月 6 日 07:35

算法(4th ed)(131):基础——背包、队列和栈 5.3.2

(链表:构造链表)

现在,根据递归定义,我们只需要一个 Node 类型的变量就能表示一条链表,只要保证它的值是 null 或者指向另一个 Node 对象且该对象的 next 域指向了另一条链表即可。例如,要构造一条含有元素tobeor 的链表,我们首先为每个元素创造一个结点:

复制代码
Node first = new Node();
Node second = new Node();
Node third = new Node();

并将每个结点的 item 域设为所需的值(简单起见,我们假设在这些例子中 ItemString):

复制代码
first.item = "to";
second.item = "be";
third.item = "or";

然后设置 next 域来构造链表:

复制代码
first.next = second;
second.next = third;

(注意:third.next 仍然是 null,即对象创建时它被初始化的值。)结果是,third 是一条链表(它是一个结点的引用,该结点指向 null,即一个空链表),second 也是一条链表(它是一个结点的引用,且该结点含有一个指向 third 的引用,而 third 是一条链表),first 也是一条链表(它是一个结点的引用,且该结点含有一个指向 second 的引用,而 second 是一条链表)。图 1.3.5 所示的代码以不同的顺序完成了这些赋值语句。

算法(4th ed)(131):基础——背包、队列和栈 5.3.2

图 1.3.5 用链接构造一条链表

链表表示的是一列元素。在我们刚刚考察过的例子中,first 表示的序列是 tobeor。我们也可以用一个数组来表示一列元素。例如,可以用以下数组表示同一列字符串:

复制代码
String[] s = { "to", "be", "or" };

不同之处在于,在链表中向序列插入元素或是从序列中删除元素都更方便。下面,我们来学习完成这些任务的代码。

在追踪使用链表和其他链式结构的代码时,我们会使用可视化表示方法:

  • 用长方形表示对象;
  • 将实例变量的值写在长方形中;
  • 用指向被引用对象的箭头表示引用关系。

这种表示方式抓住了链表的关键特性。方便起见,我们用术语链接表示对结点的引用。简单起见,当元素的值为字符串时(如我们的例子所示),我们会将字符串写在长方形之内,而非使用 1.2 节中所讨论的更准确的方式表示字符串对象和字符数组。这种可视化的表示方式使我们能够将注意力集中在链表上。

评论

发布