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

阅读数:6 2019 年 11 月 6 日 07:41

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

(链表:背包的实现)

用链表数据结构实现我们的 Bag API 只需要将 Stack 中的 push() 改名为 add(),并去掉 pop() 的实现即可,如算法 1.4 所示(也可以用相同的方法实现 Queue,但需要的代码更多)。在这份实现中,加粗部分的代码可以通过遍历链表使 StackQueueBag 变为可迭代的。对于 Stack,链表的访问顺序是后进先出;对于 Queue,链表的访问顺序是先进先出;对于 Bag,它正好也是后进先出的顺序,但顺序在这里并不重要。如算法 1.4 中加粗部分的代码所示,要在集合数据类型中实现迭代,第一步就是要添加下面这行代码,这样我们的代码才能引用 Java 的 Iterator 接口:

复制代码
import java.util.Iterator;

第二步是在类的声明中添加这行代码,它保证了类必然会提供一个 iterator() 方法:

复制代码
implements Iterable<Item>

iterator() 方法本身只是简单地从实现了 Iterator 接口的类中返回一个对象:

复制代码
public Iterator<Item> iterator()
{ return new ListIterator(); }

这段代码保证了类必然会实现方法hasNext()next()remove() 供用例的 foreach 语法使用。要实现这些方法,算法 1.4 中的嵌套类 ListIterator 维护了一个实例变量 current 来记录链表的当前结点。hasNext() 方法会检测 current 是否为 nullnext() 方法会保存当前元素的引用,将 current 变量指向链表中的下个结点并返回所保存的引用。

算法 1.4 背包

复制代码
import java.util.Iterator;
public class Bag<Item> implements Iterable<Item>
{
private Node first; // 链表的首结点
private class Node
{
Item item;
Node next;
}
public void add(Item item)
{ // 和 Stack 的 push() 方法完全相同
Node oldfirst = first;
first = new Node();
first.item = item;
first.next = oldfirst;
}
public Iterator<Item> iterator()
{ return new ListIterator(); }
private class ListIterator implements Iterator<Item>
{
private Node current = first;
public boolean hasNext()
{ return current != null; }
public void remove() { }
public Item next()
{
Item item = current.item;
current = current.next;
return item;
}
}
}

这份 Bag 的实现维护了一条链表,用于保存所有通过 add() 添加的元素。size()isEmpty() 方法的代码和 Stack 中的完全相同,因此在此处省略。迭代器会遍历链表并将当前结点保存在 current 变量中。我们可以将加粗的代码添加到算法 1.2 和算法 1.3 中使 StackQueue 变为可迭代的,因为它们背后的数据结构是相同的,只是 StackQueue 的链表访问顺序分别是后进先出和先进先出而已。

评论

发布