CS61B 课程笔记（Lecture 11 Libraries, Abstract Classes, Packages）

Java 库和包

Java 提供了许多内置的库和抽象数据类型（ADT），这些工具可以简化编程工作。java.util 库中包含了几个重要的 ADT：

  • List（列表）：有序的元素集合，常见实现是 ArrayList。
  • Set（集合）：无序且元素唯一的集合，常见实现是 HashSet。
  • Map（映射）：键值对的集合，常见实现是 HashMap。
  • List接口：不仅有ArrayList实现，还可以通过LinkedList实现，这两者在内部存储和访问方式上有显著不同。
    • ArrayList基于动态数组，优点是随机访问快，缺点是插入删除中间元素时性能差。
    • LinkedList基于双向链表，优点是插入删除操作快，缺点是随机访问性能差。
  • Set接口：常见的实现有HashSet和TreeSet。
    • HashSet基于哈希表，无序且唯一，效率高。
    • TreeSet基于红黑树，元素有序，适合需要排序的数据。
  • Map接口：HashMap和TreeMap是最常见的两种实现。
    • HashMap提供无序但高效的键值映射。
    • TreeMap实现有序映射，基于键的自然顺序或自定义比较器。

示例练习：

  1. 从文件中读取单词
    该方法从文件中读取单词并将其存储到列表中。

    1
    2
    3
    4
    5
    6
    7
    8
    public static List<String> getWords(String inputFileName) {
        List<String> lst = new ArrayList<>();
        In in = new In(inputFileName);
        while (!in.isEmpty()) {
            lst.add(in.readString()); // 可以选择先清理字符串
        }
        return lst;
    }

  2. 统计唯一单词数
    该方法统计列表中出现的唯一单词的数量。

    1
    2
    3
    4
    5
    6
    7
    public static int countUniqueWords(List<String> words) {
        Set<String> ss = new HashSet<>();
        for (String s : words) {
            ss.add(s);
        }
        return ss.size();
    }

  3. 收集单词出现次数
    该方法统计每个单词在列表中出现的次数。

    1
    2
    3
    4
    5
    6
    7
    public static Map<String, Integer> collectWordCount(List<String> words) {
        Map<String, Integer> counts = new HashMap<>();
        for (String word : words) {
            counts.put(word, counts.getOrDefault(word, 0) + 1);
        }
        return counts;
    }

抽象类与接口的比较

  • 接口（Interface）：定义抽象方法（例如 Deque 接口）。所有方法默认都是 public 和 abstract 的。
    • 示例：Deque 接口由 ArrayDeque 和 LinkedListDeque 实现。
  • 抽象类（Abstract Class）：可以包含抽象方法和具体方法，变量也可以是任何类型。抽象类介于接口和具体类之间，提供了更多灵活性。
    • 特点：
      • 方法可以是 public 或 private。
      • 可以包含任何类型的变量。
      • 抽象类不能被实例化。
      • 默认情况下，方法是具体的，除非被声明为 abstract。
      • 每个类只能继承一个抽象类。

包（Packages）

  • 包（Package） 提供了类的规范化名称，以避免命名冲突。命名通常使用反向域名，如 ug.joshh.animal。

    1
    ug.joshh.animal.Dog d = new ug.joshh.animal.Dog();

    为了避免每次使用类时都输入完整包名，Java 允许使用 import 来导入包：

    1
    import ug.joshh.animal;