Week2 Using the Java Collection Libraries Lecture 2

1. Java为数据结构编程提供了哪些支持？

（1）Java 提供了丰富的数据结构类，通过 Java 集合框架（Java Collections Framework） 来实现，常见的包括：

Java 集合框架（Java Collections Framework，简称 JCF） 是一组 用于存储和操作数据 的类和接口的集合，提供了一种统一的方式来管理、存取和操作不同类型的数据结构。它为开发者提供了各种现成的、可复用的数据结构类

• 列表（List）：用于存储有序元素集合，如 ArrayList、LinkedList。

• 集合（Set）：用于存储不重复的元素，如 HashSet、TreeSet。

• 队列（Queue）：用于按先进先出（FIFO）顺序处理元素，如 LinkedList、PriorityQueue。

• 映射（Map）：用于存储键值对，如 HashMap、TreeMap。

• 栈（Stack）：处理元素时采用先进后出（LIFO）方式，如 Stack 类。

（2）Java 还提供了泛型支持，允许用户为数据结构中的元素定义类型，这提高了类型安全性和复用性。

2. 使用 Java 可以创建哪些类型的数据结构？

• 数组（Array）：固定大小的结构，用于存储相同类型的元素。

• 列表（List）：如 ArrayList、LinkedList，提供动态数组和链表。

• 栈（Stack）：可以使用 Stack 或 Deque 实现 LIFO 功能。

• 队列（Queue）：使用 Queue、LinkedList 或 PriorityQueue 实现 FIFO 功能。

• 集合（Set）：如 HashSet、TreeSet，用于存储唯一元素。

• 映射（Map）：如 HashMap、TreeMap，用于存储键值对。

• 树（Tree）：可以通过自定义代码或使用内置类如 TreeMap、TreeSet 来实现。

• 图（Graph）：可以使用 Map 来表示邻接列表，或者自己实现。

• 堆（Heap）：常使用优先队列实现堆数据结构。

3. 如何在 Java 中创建和访问数据结构？

在 Java 中，数据结构可以通过以下方式创建和访问：

（1） 创建数据结构：

• 示例：创建一个整数列表：

List<Integer> myList = new ArrayList<>();

• 示例：创建一个 HashMap：

Map<String, Integer> myMap = new HashMap<>();

（2）访问数据结构：

• ArrayList（列表）：

myList.add(10); // 添加元素
Integer value = myList.get(0); // 访问索引为 0 的元素

• HashMap（映射）：

myMap.put("key1", 100); // 添加键值对
Integer value = myMap.get("key1"); // 通过键访问值

Java 的 集合框架 提供了直观且高效的方法来访问、添加和修改数据结构。

4. 一些实际例子？

以下是 Java 数据结构的一些实际应用示例：

（1） 待办事项应用：可以使用 ArrayList 存储任务，动态地添加、删除和管理任务。

（2） 缓存系统：可以使用 HashMap 实现内存缓存，将数据存储为键值对。

（3） 优先级调度：可以使用 PriorityQueue 实现优先级调度系统，根据优先级处理任务。

（4） 图遍历：可以使用 Map 或 Set 来表示图，适用于社交网络应用，节点（人）通过边（友谊）连接。

（5） 排队模拟：可以使用 Queue 模拟客户服务或交通管理等场景，按 FIFO 顺序处理请求。

一、Overview of Data Structure Programming

1. 线性集合编程（Programming with Linear collections）

（1） 线性集合的种类：

• 列表（Lists）、集合（Sets）、袋（Bags）、映射（Maps）、栈（Stacks）、队列（Queues）、优先队列（Priority Queues）。

（2） 使用线性集合：

• 集合编程（Programming with collections）

• 数据的搜索与排序（Searching & Sorting Data）

• 实现线性集合（Implementing linear collections）

• 实现排序算法（Implementing sorting algorithms）

• 链式数据结构和“指针”概念（Linked data structures and “pointers”）

2. 分层集合编程（Programming with Hierarchical collections）

（1） 分层集合的种类：

• 树（Trees）、二叉树（Binary trees）、通用树（General trees）。

（2）使用树结构集合：structured collections

• 构建树结构（Building tree structures）

• 搜索树结构（Searching tree structures）

• 遍历树结构（Traversing tree structures）

（3） 实现树结构集合

（4） 实现线性集合：使用二叉搜索树（with binary search trees）

二、编程与库（Programming with Libraries）

1. 现代程序（尤其是 GUI 和网络）太复杂，不能从头开始编写：

必须重用他人编写的代码。

2. 库是为重用而设计的代码集合：

• Java有大量的标准库，例如 java.util、java.io 等，提供了各种实用的类和工具。

• 库是由包（Packages）和类（Classes）组成的。一个包可以包含多个相关的类，简化代码的组织和使用。

• 包（Package） 是类和其他类型（如接口、子包）的集合

• 类实现接口。一个类可以实现一个或多个接口，但它必须提供接口中声明的所有方法的具体实现。

（1）Libraries

• java.util：集合类和其他实用类。

Collection classes and other utility classes.

• java.io：输入输出类。

• javax.swing 和 java.awt：用于 GUI 程序的大型类库。

我们将在几乎所有程序中使用这些库。

• java.util 是一个包，它包含了像 ArrayList、HashSet、LinkedList 等类。

（2）使用库（Using Libraries）

使用库时，阅读文档以选择有用的库。

• 使用 import 语句导入必要的包/类，如

import java.util.*

import java.io.*

• 注意文档中描述的构造函数、方法和接口。

• 像使用程序中自有的类一样使用这些类。

• 构造函数（Constructors）用于创建实例（making instances）

• 方法（Methods）用于调用

• 接口（Interfaces）用于实现

三、Collections

1. 标准集合（“Standard” Collections）

• 常见的集合类型：

袋（Bag）、集合（Set）、映射（Map）、列表（List）、队列（Queue）、栈（Stack）、树（Tree）、图（Graph）。

• Bag：一个无序的集合，可能包含重复元素。

• Set：一个无序的集合，不允许重复元素。

• Map：一个存储键值对的集合。

• List：一个有序集合，可以通过索引位置访问元素。

• Queue：一个有限访问的集合，通常遵循 FIFO（先进先出）原则。

• Stack：一个遵循 LIFO（后进先出）原则的集合。

• Tree：一种层次化的集合，常用于存储有序数据。

• Graph：一个由节点和边组成的集合，用来表示对象之间的关系。

• 这些类型在数据结构化和组织方式、以及如何处理重复和访问方面有所不同。

• 元素的具体类型及其存储/操作方式是抽象化的。

2. Abstract Data Types

抽象数据类型（ADT） 是一种数据类型，它描述了数据结构的操作和行为，但并不涉及数据是如何实现的。简而言之，ADT 强调了 操作接口 和 行为规范，而不关心其内部的实现细节。

• ADT 用来定义一类数据对象的集合，并指定允许对该数据进行的操作

Set, Bag, Queue, List, Stack, Map, etc are Abstract Data Types (outcome of abstraction / encapsulation)

• 例如，Set ADT：

• 操作包括 add(value)、remove(value) 和 contains(value)。

• 新集合的初始状态：一个新的 Set 不包含任何元素。

• 元素添加与移除的条件：

集合包含某个值 当且仅当：该值已被添加并且没有被移除。

集合 不包含 某个值 当且仅当：该值从未被添加，或已被移除并且没有再添加回来。

行为指定了每个操作的预期结果，但没有涉及实现细节。

3. Java Collections library

Java 集合库定义了几个重要的接口：

• Collection：所有集合的最通用接口。

• List：表示有序集合（如 ArrayList、LinkedList）。

• Set：表示无序且没有重复元素的集合（如 HashSet、TreeSet）。

• Queue：表示有序集合，且有限制访问的集合（如 LinkedList）。

• Map：表示键值对的集合（如 HashMap、TreeMap）。

Collection 接口 作为 Java 中最通用的集合接口，类似于Bag。也就是说，Collection 接口的设计考虑了最一般的集合特性，适用于各种类型的集合（如 List、Set、Queue），其功能可以扩展到包含不同的集合类型和不同的操作。

Bag 表示一个无序的集合，允许重复元素

• 每个实现这些接口的类（例如 ArrayList、LinkedList、HashSet、HashMap）提供不同的内部实现，但都遵循接口指定的规则。

4. Java Interfaces and ADT’s

（1） 接口与 ADT 的关系：

Java 接口对应于抽象数据类型（ADT）。

抽象数据类型（ADT）是在抽象层面上定义的数据类型，指定了可以对该类型的对象执行的操作，以及该对象应该如何表现。

Java 接口指定了可以在特定类型的对象上调用的方法。它定义了方法的签名，包括：

• 方法的名称。

• 方法的参数（及其类型）。

• 方法的返回类型。

行为只在注释中给出，但在接口中并不能强制执行。举例来说，接口中的方法列出的是方法的签名，而没有方法的具体实现。

（2） Java 接口的主要特点：

• 没有构造函数：No constructors

接口不能被直接实例化：new Set()

• 没有字段：No fields

接口不能定义字段（即实例变量）。接口不指定数据是如何存储的。

• 没有方法体：No method bodies.

• 接口只定义了 方法签名，没有方法的具体实现。方法体（即方法的具体实现）留给实现该接口的类来完成。

（3） Set 接口示例：

public interface Set {
public void add(??? item); // 添加元素
public void remove(??? item); // 移除元素
public boolean contains(??? item); // 检查元素是否存在
}

四、Programming with Lists of Objects

1. List Interface in Java

• Java中的List接口扩展了 Collection<E>，其中 <E> 代表列表中元素的类型。

包含的方法有：

• add(E o) 用于添加元素。

• get(int index) 用于通过索引访问元素。

• contains(Object o) 用于检查某个元素是否存在于列表中。

• iterator() 用于遍历元素。

• List 接口允许有序集合，并通过索引进行访问。

以下是每张图片中涉及的知识点的详细阐述和总结：

2. Using Java Collection Interfaces（使用 Java 集合接口）

（1） 声明接口的变量、参数或字段：

• 在 Java 中，我们可以声明一个变量、参数或字段，使用集合接口类型来定义集合的类型。比如：

private List drawing; // a list of Shapes

• 这段代码声明了一个名为 drawing 的变量，它是 List 类型的，可以存储 Shape 类型的元素（例如不同的形状 Rectangle、Circle 等）。这里的 List 是一个接口，意味着 drawing 可以使用任何实现了 List 接口的类（例如 ArrayList 或 LinkedList）。

（2） 调用方法：

• 你可以通过该变量调用集合接口中定义的方法。例如：

drawing.add(new Rect(100, 100, 20, 30));

• 这行代码向 drawing 列表中添加一个新的 Rect 对象，Rect 是 Shape 类型的一个子类。调用 add() 方法将新的元素添加到列表中。

（3）问题：如何指定集合中元素的类型？

• 这其实是关于泛型的问题，集合接口本身并不指定集合元素的具体类型。我们可以通过泛型在声明时指定集合中元素的类型，例如 List<Shape> 表示一个只能存储 Shape 类型对象的列表。

3. Parameterized Types（参数化类型）

（1） 集合类型的结构和访问规则相同：

• 无论集合存储什么类型的元素（如 String、Person、Shape 或整数），集合的结构和访问规则（access discipline）是相同的。

• 例如，Set<String> 和 Set<Integer> 都是集合类型，它们都遵循相同的访问和操作规则，只不过存储的元素类型不同。

（2） 只需要一个接口来表示每种集合类型：

• 对于不同类型的集合，只需要一个集合接口（如 Set）即可。例如：

• 一个 Set 接口可以用来表示存储任何类型的元素的集合，具体元素类型是在使用该接口时指定的。

• Set<String> 是一个存储字符串的集合，而 Set<Person> 是一个存储 Person 对象的集合。

（3） 集合接口和类是参数化的，即可以通过泛型来指定集合的类型和集合中元素的类型。

4. Parameterized Types: Interfaces with Type Parameters（参数化类型：带类型参数的接口）

（1） 接口带类型参数：

• 接口可以有类型参数，如 Set<T>。T 是类型参数，表示集合中存储的元素类型。它没有具体指定元素的类型，可以在使用该接口时根据需要传递具体类型（如 Set<String> 或 Set<Person>）。

public interface Set<T> {
public void add(T item);
public void remove(T item);
public boolean contains(T item);
}

• 这样，T 表示一个占位符，具体的类型将在使用时指定。

List<T>、Set<T> 这些集合接口都使用类型参数 T 来表示集合中元素的类型。

（2）声明变量时指定集合元素的类型：

• 当声明一个集合变量时，我们不仅指定集合的类型（如 Set 或 List），还要指定集合元素的类型。例如：

private Set<Person> friends;
private List<Shape> drawing;

• 这里，friends 变量是一个 Set 类型的集合，它只存储 Person 类型的对象，而 drawing 变量是一个 List 类型的集合，它只存储 Shape 类型的对象。

5. Using the Java Collection Library（使用 Java 集合库）

（1） 接口不能直接实例化：

• 接口不能直接实例化，因为接口只是定义了方法的签名，并没有实现这些方法。例如，不能这样创建：

List<Shape> drawing = new List<Shape>(); // 错误，List 是接口，不能实例化

（2） 类实现接口并提供具体实现：

• Java 中的集合类（如 ArrayList、HashSet 等）实现了集合接口，提供了实际的功能实现。这些类提供了构造函数来创建实例，定义了方法体来执行集合操作。例如：

private List<Shape> drawing = new ArrayList<Shape>();
Set<Person> friends = new HashSet<Person>();

6. ArrayList

（1）ArrayList 是 Java 集合框架的一部分：

• ArrayList 是 Java 集合框架中的一个类，用于存储有序的元素。与传统数组不同，ArrayList 可以动态扩展大小。

• 使用 ArrayList 时，必须导入 java.util 包：part of the java.util package

import java.util.*;

（2）可以创建新的 ArrayList 对象：

• 当你创建一个新的 ArrayList 对象时，你不需要事先指定它的大小。你只需要指定集合元素的类型。例如：

private ArrayList<Shape> drawing = new ArrayList<Shape>();

• 这种方式类似于一个动态数组，不需要设置固定的大小，可以根据需要扩展。

infinitely stretchable array

3. 你不能使用 [] 角括号的数组访问方式（不像普通数组 array[i] 这样访问元素）。

• 示例（错误的写法）：

ArrayList<Integer> numbers = new ArrayList<>();
numbers.add(10);
System.out.println(numbers[0]); // ❌ 错误！ArrayList 不能用 []

必须使用 ArrayList 的方法来访问和修改元素，而不能直接用 []。

主要用的方法：

• add(value): 添加元素

• get(index): 获取元素

• set(index, value): 修改元素

int firstNumber = numbers.get(0); // ✅ 使用 get() 访问

System.out.println(firstNumber); // 输出: 10

7. Using ArrayList: Declaring

（1）声明数组和 ArrayList：

• 当使用传统数组时，必须指定数组的大小：

private static final int maxStudents = 1000;

private Student[] students = new Student[maxStudents];
private int count = 0;

• 这种方式需要事先知道数组的大小，而 ArrayList 则无需指定大小，且没有最大限制。

（2） 使用 ArrayList 代替数组：No maximum; no initial size; no explicit count

• 使用 ArrayList 时，数组的固定大小不再是问题，且可以灵活地增加元素。例如：

private ArrayList<Student> students = new ArrayList<Student>();

在 普通数组（Array）中，必须手动维护一个 count 变量来跟踪当前存储的元素数量。例如：

private static final int maxStudents = 1000;
private Student[] students = new Student[maxStudents];
private int count = 0; // 👈 手动维护当前存储的学生数量

public void addStudent(Student s) {
if (count < maxStudents) {
students[count] = s;
count++; // 👈 需要手动更新 count
}
}

8. Using ArrayList: Methods

Java ArrayList 的常用方法

1️⃣ size() ：返回 ArrayList 中的元素个数。

2️⃣ add(item)：向列表末尾添加元素。

3️⃣ add(index, item)：在指定索引 index 处插入 item，后续元素右移。

4️⃣ set(index, item)：替换指定索引 index 处的元素。

5️⃣ contains(item)：检查列表是否包含某个元素，返回 true 或 false。

6️⃣ get(index)：获取指定索引 index 处的元素。

7️⃣ remove(item)：删除 ArrayList 中第一个匹配 item 的元素。

8️⃣ remove(index)：删除 index 位置的元素，后续元素左移。

• 示例：

ArrayList<String> list = new ArrayList<>();
list.add("Alice");
list.add("Bob");
System.out.println(list.size()); // 输出: 2

list.add(1, "David");
System.out.println(list); // 输出: [Alice, David, Bob]

list.set(2, "Eve");
System.out.println(list); // 输出: [Alice, David, Eve]

System.out.println(list.contains("Alice")); // 输出: true

System.out.println(list.get(1)); // 输出: David

list.remove("David");
System.out.println(list); // 输出: [Alice, Eve]

list.remove(1);
System.out.println(list); // 输出: [Alice]

9️⃣ 遍历 ArrayList两种方式：

1. for 循环：

for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}

2. for-each 循环：

for (String name : list) {
System.out.println(name);
}

9. Using ArrayList (代码示例)

主要知识点：如何使用 ArrayList 存储 Student 对象

1️⃣ ArrayList<Student> 的声明

• 创建 ArrayList 来存储 Student 类型对象

private ArrayList<Student> students = new ArrayList<Student>();

2️⃣ 添加学生对象

• 两种方式：

Student s = new Student("Lindsay King", "300012345");
students.add(s);  // 直接添加对象

students.add(0, new Student(fscanner)); // 在索引 0 位置插入

3️⃣ 遍历 ArrayList<Student>

如果类没有重写 toString() 方法，System.out.println(obj) 只会打印对象的哈希码，而不是我们想要的内容。因此，我们需要 toString() 方法来定义对象的可读格式。

• for 循环

for (int i = 0; i < students.size(); i++) {
    System.out.println(students.get(i).toString());
}

• 增强 for-each 循环

for (Student st : students) {
    System.out.println(st.toString());
}

4️⃣ 检查是否包含某个对象

• 使用 contains() 判断是否有某个学生

if (students.contains(current)) {
    file.println(current);
    students.remove(current);
}

五、Q&A

1️⃣ Java 线性集合（Linear Collections）

• ArrayList

• LinkedList

• Vector（和 ArrayList 一样，Vector 也可以动态扩容）

2️⃣ 线性集合的常见操作

• 添加元素 (add())

• 访问元素 (get())

• 修改元素 (set())

• 删除元素 (remove())

3️⃣ Java 层次集合（Hierarchical Collections）

• TreeSet

• HashMap

4️⃣ 层次集合的常见操作

• 插入 (put())

• 查找 (get())

• 删除 (remove())

• 检查存在性 (containsKey() 或 containsValue())

5️⃣ 什么是软件库（Software Library）？

• 一组预定义的类和方法，提供通用功能（如 Java Standard Library）。

6️⃣ Java Package 是什么？

• 组织类的方式，类似于文件夹，避免类名冲突。

package myPackage;

7️⃣ Java 的 IO 库

• java.io

• java.nio

8️⃣ Java 的 GUI 库

• javax.swing

• java.awt

9️⃣ 导入 Java 包的语句

• 使用 import 关键字

import java.util.ArrayList;

六、Conclusions（总结）

1️⃣ 我们可以声明一个变量/字段/参数的类型为某个元素类型的集合

• 示例：

List<String> names = new ArrayList<>();

2️⃣ 可以创建合适的集合类

• 示例：

Set<Integer> numbers = new HashSet<>();

3️⃣ 如何选择合适的集合类？

• ArrayList 适合随机访问

• LinkedList 适合频繁插入/删除

• HashSet 适合去重存储

• HashMap 适合键值对存储