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

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

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

(链表:结点记录)

在面向对象编程中,实现链表并不困难。我们首先用一个嵌套类来定义结点的抽象数据类型:

复制代码
private class Node
{
Item item;
Node next;
}

一个 Node 对象含有两个实例变量,类型分别为 Item(参数类型)和 Node。我们会在需要使用 Node 类的类中定义它并将它标记为 private,因为它不是为用例准备的。和任意数据类型一样,我们通过new Node() 触发(无参数的)构造函数来创建一个Node 类型的对象。调用的结果是一个指向 Node 对象的引用,它的实例变量均被初始化为 nullItem 是一个占位符,表示我们希望用链表处理的任意数据类型(我们将会使用 Java 的泛型使之表示任意引用类型);Node 类型的实例变量显示了这种数据结构的链式本质。为了强调我们在组织数据时只使用了 Node 类,我们没有定义任何方法且会在代码中直接引用实例变量:如果 first 是一个指向某个 Node 对象的变量,我们可以使用 first.itemfirst.next 访问它的实例变量。这种类型的类有时也被称为记录。它们实现的不是抽象数据类型,因为我们会直接使用其实例变量。但是在我们的实现中,Node 和它的用例代码都会被封装在相同的类中且无法被该类的用例访问,所以我们仍然能够享受数据抽象的好处。

评论

发布