软件设计与数据结构

Chapter 10 Comparing, Sorting and Iterators

| 关于   «  2. 比较与排序   ::   目录   ::   4. 实验 10 双向链表  »

3. 迭代器

3.1. 学习目标

完成本模块后，学生将能够：

  • 描述迭代器（Iterator）的用途和使用方法

  • 使用 Iterator 和 Iterable 接口实现迭代器

  • 设计并开发使用迭代器和迭代器方法的算法

  • 使用 Scanner 进行文件输入输出

3.1.1. 建议阅读

Java 插曲 5 迭代器，选自 Data Structures and Abstractions with Java, 4th edition by Frank M. Carrano and Timothy Henry

3.2. 迭代器简介

跟着做并参与

下载视频对应的幻灯片。观看视频时在幻灯片上做笔记，自己练习画图！

IntroToIterators.pdf

3.3. 检查点 1

3.4. 使用 Iterable 接口进行编程

跟着做并参与

下载视频对应的幻灯片。观看视频时在幻灯片上做笔记，自己练习画图！

Iterable.pdf

3.5. 检查点 2

3.6. 使用迭代器进行编程

跟着做并参与

下载视频对应的幻灯片。观看视频时在幻灯片上做笔记，自己练习画图！

ProgrammingWithIterators.pdf

3.7. 检查点 3

3.8. 迭代器设计决策

跟着做并参与

下载视频对应的幻灯片。观看视频时在幻灯片上做笔记，自己练习画图！

IteratorsDesignConsiderations.pdf

澄清

作为链式结构内部嵌套类（而不是子类）的迭代器，比作为独立类的迭代器效率更高。

3.9. 内部迭代器

正如本节所讨论的，迭代器有多种不同的设计方法。下面是如何为 LList 实现内部迭代器类的一个示例。

提供一个公共方法，使迭代器对象可用：

/**
* Iterator method creates Iterator object
*
* @return new Iterator object
*/
public Iterator<T> iterator()
{
   return new LListIterator<T>();
}

包含一个内部 Iterator 类。这个版本不提供 remove 功能，因为在单链表中要移除当前结点，就得跟踪之前的结点，这是很复杂的。

private class LListIterator<A> implements Iterator<T>
{
     private Node next;
     private boolean newCurr;

     /**
     * Creates a new DLListIterator
     */
     public LListIterator()
     {
       next = firstNode;
       newCurr = false;
     }

     /**
     * Checks if there are more elements in the list
     *
     * @return true if there are more elements in the list
     */
     @Override
     public boolean hasNext()
     {
       return (next != null);
     }

     /**
     * Gets the next value in the list
     *
     * @return the next value
     * @throws NoSuchElementException
     *             if there are no nodes left in the list
     */
     @Override
     public T next()
     {
       if (next == null)
       {
         throw new NoSuchElementException("No nodes left in the list.");
       }
       T value = next.data;
       next = next.getNext();
       newCurr = true;
       return value;
     }
}

下面是一个确实提供了 remove 功能的内部 Iterator 类版本。为了带来不必要的副作用，最好只通过数据结构或迭代器二者之一来提供 remove 功能。

private class LListIterator<A> implements Iterator<T>
 {
     private Node prev;
     private Node curr;
     private Node next;
     private boolean newCurr;

     /**
     * Creates a new DLListIterator
     */
     public LListIterator()
     {
         prev = null;
         curr = null;
         next = firstNode;
         newCurr = false;
     }

     /**
     * Checks if there are more elements in the list
     *
     * @return true if there are more elements in the list
     */
     @Override
     public boolean hasNext()
     {
         return (next != null);
     }

     /**
     * Gets the next value in the list
     *
     * @return the next value
     * @throws NoSuchElementException
     *             if there are no nodes left in the list
     */
     @Override
     public T next()
     {
         prev = curr;
         curr = next;
         next = next.getNext();
         if (curr == null)
         {
             throw new NoSuchElementException("No nodes left in the list.");
         }
         newCurr = true;
         return curr.data;
     }

    /**
     * Removes the last object returned with next() from the list
     *
     * @throws IllegalStateException
     *             if next has not been called yet
     *             and if the element has already been removed
     */
     @Override
     public void remove()
     {
         if (next == firstNode)
         {
             throw new IllegalStateException(
                  "Next has not been called yet.");
         }
         else if (!newCurr)
         {
             throw new IllegalStateException(
                  "The Element has already been removed.");
         }
         else if (curr == firstNode) {
             firstNode = next;
             curr = null;
         } else {
             prev.setNext(curr.getNext());
             curr = prev;
              //this code that updates prev is not necessary
              //because next() must be called before another remove()
              //and that will update prev, saving this O(n) operation
              //prev = firstNode;
              //while ((prev != null) && (prev.getNext() != curr)){
              //    prev = prev.getNext();
              //}
         }
         numberOfEntries--;
         newCurr = false;
     }
 }

3.10. 编程实践：迭代器

3.11. Scanner 实现 Iterator<String>

java.io 包为从文本文件读取内容提供了丰富的类继承层次结构。创建 Scanner 类是为了简化文本输入，因此它比其他类更受青睐。Scanner 实现了 Iterable<String>，还提供了 next() 和 hasNext() 方法以及许多其他方法。

Scanner 对象提供的若干方法几乎涵盖了本课程中你需要的一切输入功能：

  • <scanner>.hasNext(); 如果此扫描器在其输入中还有另一个标记，则返回 true。

  • <scanner>.next(); 查找并返回此扫描器中的下一个完整标记（默认情况下，下一个由空白字符分隔的字符串，作为一个 String 对象，比如下一行或下一个以制表符分隔的单词）。如果没有更多可用的标记（即你已经到达输入的末尾），则会抛出 NoSuchElementException。

  • <scanner>.hasNextLine(); 如果此扫描器在其输入中还有另一行，则返回 true。

  • <scanner>.nextLine(); 查找并返回下一个完整行。如果没有更多可用的标记（即你已经到达输入的末尾），则会抛出 NoSuchElementException。

  • <scanner>.hasNext<PrimitiveType>(); <PrimitiveType> 可以换成 double、float、int 等等。如果此扫描器在其输入中还有另一个标记，并且它可以被解释为 <PrimitiveType> 类型的值，则返回 true。

  • <scanner>.next<PrimitiveType>(); <PrimitiveType> 可以换成 double、float、int 等等。该方法把输入中的下一个标记扫描为一个 <PrimitiveType>，并返回对应的 <PrimitiveType> 值。如果下一个标记与 <PrimitiveType> 不匹配，或者扫描到的值超出范围，它会抛出 InputMismatchException。如果没有更多可用的标记，它还会抛出 NoSuchElementException。

  • <scanner>.useDelimiter(String pattern); 默认情况下，空白字符（空格、制表符或换行字符）被用作把输入分隔成标记的定界符。该方法允许用户把定界字符设置成自己喜欢用于拆分输入的任何字符。逗号是另一种常用的定界符，因为表格或数据通常存储在所谓的 CSV（逗号分隔值）文件中。

  • <scanner>.close(); 关闭扫描器，以释放扫描器正在使用的系统资源。

要使用这些方法，通常你会一次扫描一行来处理输入，然后在该行中扫描所需要寻找的标记。

例如：

Scanner inStream = IOHelper.createScanner("input.txt");
// if NOT at the end of the stream, more input is available
if (inStream.hasNextLine())
{
   // Get an entire line
   String thisLine = inStream.nextLine();
   // Create a scanner to process the line
   Scanner line = new Scanner(thisLine);
   // Check for the next whitespace delimited int
   if (line.hasNextInt())
   {
      System.out.println(line.nextInt());
   }
}
inStream.close();

注意，在提取每个输入之前都会先检查它是否存在，以避免异常。

另外，如果你以前用其他语言编写过程序，请注意 Java 中的字符使用 unicode 编码，即一种 16 位字符编码。其他语言的程序员可能更熟悉 ASCII，即美国信息交换标准码，它是一种 7 位字符编码。幸运的是，unicode 中的前 128 个编码与整个 ASCII 字符集等价。因此对于美国用户来说，在逐字符读写时免费使用 ASCII 值不会出错，尽管这种方法并不能直接扩展到面向国际受众编写的程序。

Scanner 也可以用来处理一行数据中的标记。这些标记可以用空白字符或其他定界符分隔。例如，要处理使用空白字符分隔的命令行：

set counter 10

add counter 1

display counter

Scanner inStream = IOHelper.createScanner("input.txt");
// if NOT at the end of the stream, more input is available
if (inStream.hasNextLine())
{
   // Get an entire line
   String thisLine = inStream.nextLine();
   // Create a scanner to process the line
   Scanner line = new Scanner(thisLine);
   // Create an array to hold the tokens on the line
   String[] tokens = new String[MAX];
   int tokenCount;
   // Check for the next whitespace delimited int
   while (line.hasNext() && tokenCount < MAX)
   {
      tokens[tokenCount++] = line.next();
   }
   processLineOfData(tokens);
}
inStream.close();

为了处理用空白字符以外的字符定界的数据，需要使用 useDelimiter 方法，并带有一个正则表达式模式作为参数。例如，要处理以逗号为定界符的命令行，例如：

Shepard, G, Gr., 5'9"

Brooks, G, Jr., 5'10"

Amoore, F, Sr., 6'2"

这里需要把 Scanner 设置为使用逗号。因为逗号后面可能有数量不定、未被确定的空白字符，所以应该使用正则表达式 ",\s "。这个正则表达式模式匹配一个后面跟着 0 个或多个空白字符的逗号。注意，",\s+" 匹配后面跟着 1 个或多个空白字符的逗号。还要注意，", *" 会匹配由空格键产生的 0 个或多个空格，但它不会考虑到同样能产生空白字符的制表符或换行符，因此使用 ",\s" 是更好的做法。关于 java 正则表达式的更多信息，请访问 https://docs.oracle.com/javase/8/docs/api/java/util/regex/Pattern.html

Scanner inStream = IOHelper.createScanner("input.txt");
// if NOT at the end of the stream, more input is available
if (inStream.hasNextLine())
{
   // Get an entire line
   String thisLine = inStream.nextLine();
   // Create a scanner to process the line
   Scanner line = new Scanner(thisLine).useDelimiter(",\\s*");
   // Create an array to hold the tokens on the line
   String[] tokens = new String[MAX];
   int tokenCount;
   // Check for the next whitespace delimited int
   while (line.hasNext() && tokenCount < MAX)
   {
      tokens[tokenCount++] = line.next();
   }
   processLineOfData(tokens);
}
inStream.close();

   «  2. 比较与排序   ::   目录   ::   4. 实验 10 双向链表  »

© Copyright 2011-2025 by OpenDSA Project Contributors and distributed under an MIT license. 最后更新于 9月 30, 2026. Created using Sphinx 8.2.0.
关闭窗口