Java 复习笔记 - 集合进阶篇：数据结构

---

数据结构 概述

数据结构是一种组织和存储数据的方式，它描述了数据元素之间的相互关系以及数据元素的组织形式。数据结构基本概念包括数据、数据元素和数据项、数据对象、数据结构、逻辑结构和存储结构。数据是指能够被计算机识别、存储、计算（处理）的符号集合，而数据元素也称作节点，是数据的基本单位，最小单位是数据项。数据对象是具有相同特征的数据元素的集合，是数据的子集。

数据结构是计算机存储、组织数据的方式，它分为数据的逻辑结构和存储结构。逻辑结构是指从逻辑关系上描述数据，与数据的存储无关，且独立于语言。存储结构是指数据元素及其关系在计算机存储时如何表示，依赖于语言。根据数据的逻辑关系，可以将数据结构分为线性结构和非线性结构。线性结构包括集合结构、线性结构和双线性结构，这些结构中的元素存在一对一的相互关系。而非线性结构包括树形结构和图形结构，这些结构中的元素存在一对多或多对多的相互关系。

总之，数据结构是计算机中用于管理和处理数据的一种方法，它有助于提高数据处理效率和精度。

常见的数据结构

Java 中常见的数据结构主要有以下几种：

1. 数组（Array）：数组是一种线性表数据结构，可以存储同一类型的元素集合。在 Java 中，数组可以通过声明和初始化来创建。
2. 链表（LinkedList）：链表是一种线性表数据结构，可以存储不同类型的元素集合。在 Java 中，链表可以通过 LinkedList 类来实现。
3. 栈（Stack）：栈是一种后进先出（LIFO）的数据结构，可以存储不同类型的元素集合。在 Java 中，栈可以通过 Stack 类来实现。
4. 队列（Queue）：队列是一种先进先出（FIFO）的数据结构，可以存储不同类型的元素集合。在 Java 中，队列可以通过 Queue 接口和它的实现类（如 LinkedList）来实现。
5. 集合（Set）：集合是一种不允许重复元素的数据结构，可以存储不同类型的元素集合。在 Java 中，集合可以通过 Set 接口和它的实现类（如 HashSet）来实现。
6. 映射（Map）：映射是一种键值对（key-value pair）的数据结构，可以存储不同类型的元素集合。在 Java 中，映射可以通过 Map 接口和它的实现类（如 HashMap）来实现。
7. 树（Tree）：树是一种非线性的数据结构，可以存储不同类型的元素集合。在 Java 中，树可以通过 Tree 接口和它的实现类（如 BinaryTree）来实现。
8. 图（Graph）：图是一种非线性的数据结构，可以存储不同类型的元素集合。在 Java 中，图可以通过 Graph 接口和它的实现类（如 SimpleGraph）来实现。

示例

（一）数组（Array）

在Java中，数组是一种简单的数据结构，用于存储固定大小的相同类型的元素集合。以下是一个Java数组的示例：

public class ArrayExample {
    public static void main(String[] args) {
        // 声明一个包含5个整数的数组
        int[] numbers = new int[5];

        // 通过索引访问和修改数组元素
        numbers[0] = 10;
        numbers[1] = 20;
        numbers[2] = 30;
        numbers[3] = 40;
        numbers[4] = 50;

        // 打印数组中的元素
        for (int i = 0; i < numbers.length; i++) {
            System.out.println("Element at index " + i + " : " + numbers[i]);
        }

        // 声明并初始化一个字符串数组
        String[] words = {"Hello", "World", "Java", "Array", "Example"};

        // 使用增强for循环打印数组中的元素
        for (String word : words) {
            System.out.println(word);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

在这个例子中，我们首先声明了一个包含5个整数的数组numbers，然后通过索引访问和修改数组中的元素。接下来，我们使用一个for循环遍历数组并打印出每个元素。然后我们声明并初始化了一个字符串数组words，并使用增强for循环打印出数组中的元素。

（二）链表（LinkedList）

在Java中，链表是一种常见的数据结构，它是一系列节点的集合，每个节点包含两个部分：数据和指向下一个节点的引用。下面是一个简单的单向链表的示例：

public class LinkedList {
    
    // 链表节点类
    private static class Node {
        int data;
        Node next;

        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    }

    // 头节点
    private Node head;

    // 向链表添加节点
    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    // 打印链表
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedList linkedList = new LinkedList();
        linkedList.add(1);
        linkedList.add(2);
        linkedList.add(3);
        linkedList.add(4);
        linkedList.add(5);
        linkedList.printList(); // 输出：1 2 3 4 5 
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

上面的示例代码定义了一个简单的链表类LinkedList。它包含一个内部类Node，用于表示链表中的节点。每个节点包含一个整数值和一个指向下一个节点的引用。链表类有一个头节点head，它指向链表的第一个节点。add方法用于向链表末尾添加新节点，而printList方法用于打印链表的内容。main方法创建了一个LinkedList对象，向其添加了几个节点，然后打印出链表的内容。

（三）栈（Stack）

在Java中，栈是一种数据结构，它遵循LIFO（后进先出）原则。这意味着最后一个被添加到栈中的元素将是第一个被移除的元素。Java的java.util.Stack类提供了栈的实现。

以下是一个简单的Java程序，它演示了如何使用Stack类：

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        // 创建一个新的Stack实例
        Stack<Integer> stack = new Stack<>();

        // 使用push方法向栈中添加元素
        stack.push(1);
        stack.push(2);
        stack.push(3);
        System.out.println("当前栈: " + stack);

        // 使用peek方法查看栈顶元素，不移除
        int top = stack.peek();
        System.out.println("栈顶元素: " + top);
        System.out.println("执行peek操作后的栈: " + stack);

        // 使用pop方法移除栈顶元素
        top = stack.pop();
        System.out.println("被移除的元素: " + top);
        System.out.println("执行pop操作后的栈: " + stack);

        // 使用isEmpty方法检查栈是否为空
        boolean empty = stack.isEmpty();
        System.out.println("栈是否为空: " + empty);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

这个示例展示了如何使用push方法将元素添加到栈中，使用peek方法查看（但不移除）栈顶元素，使用pop方法移除栈顶元素，以及使用isEmpty方法检查栈是否为空。

（四）队列（Queue）

在Java中，队列（Queue）是一种特殊类型的线性表，新元素总是在队列的末端添加，而删除操作总是在队列的开始进行。这样，队列中的元素总是先进先出（FIFO）。

下面是一个简单的Java程序，演示了如何使用Java的内置Queue接口以及它的实现类LinkedList：

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        // 创建一个队列
        Queue<Integer> queue = new LinkedList<>();

        // 添加元素到队列
        for (int i = 1; i <= 5; i++) {
            queue.add(i);
        }

        // 显示队列的元素
        System.out.println("Elements in queue: " + queue);

        // 删除队列的头元素
        int removedElement = queue.remove();
        System.out.println("Removed element: " + removedElement);

        // 查看队列的头元素，但不删除
        int headElement = queue.peek();
        System.out.println("Head of queue: " + headElement);

        // 查看队列的大小
        int size = queue.size();
        System.out.println("Size of queue: " + size);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

在这个示例中，我们创建了一个整数类型的队列，并使用LinkedList实现。我们添加了一些元素，并显示了队列的内容。然后我们删除了队列的头元素，并再次显示了队列的内容。我们还查看了队列的头元素，但没有删除它，并查看了队列的大小。

这个示例只展示了Java的Queue接口的基本功能。在实际应用中，可能会使用更复杂的操作，例如优先队列（PriorityQueue）或者阻塞队列（BlockingQueue）等。

（五）集合（Set）

在Java中，Set是一种集合，它不允许包含重复元素，并且最多包含一个null元素。以下是使用Java中Set的示例：

import java.util.HashSet;
import java.util.Set;

public class SetExample {
    public static void main(String[] args) {
        // 创建一个新的Set对象
        Set<String> set = new HashSet<>();

        // 添加元素到Set中
        set.add("A");
        set.add("B");
        set.add("C");
        set.add("D");

        // 输出Set的大小
        System.out.println("Size of set: " + set.size());

        // 检查一个元素是否在Set中
        System.out.println("Contains A? " + set.contains("A"));

        // 遍历并打印Set中的所有元素
        for (String element : set) {
            System.out.println(element);
        }

        // 删除一个元素
        set.remove("B");

        // 打印删除后的Set
        System.out.println("After removing B: " + set);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

在这个例子中，创建了一个HashSet，这是Set接口的一种实现。然后向这个Set添加了一些字符串元素，并检查了一个元素是否存在于Set中。遍历并打印了Set中的所有元素，然后删除了一个元素并打印了删除后的Set。

（六）映射（Map）

在Java中，Map是一种数据结构，可以存储键值对，其中键是唯一的。Map的常用实现类包括HashMap、TreeMap和LinkedHashMap等。以下是使用Java中Map的示例：

import java.util.HashMap;
import java.util.Map;

public class MapExample {
    public static void main(String[] args) {
        // 创建一个新的Map对象
        Map<String, Integer> map = new HashMap<>();

        // 向Map中添加元素
        map.put("Alice", 25);
        map.put("Bob", 30);
        map.put("Charlie", 35);

        // 获取Map中的元素
        int age = map.get("Bob");
        System.out.println("Bob's age is " + age);

        // 检查Map中是否包含某个键
        boolean containsKey = map.containsKey("Charlie");
        System.out.println("Map contains Charlie's key: " + containsKey);

        // 遍历Map中的所有键值对
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            String name = entry.getKey();
            int age = entry.getValue();
            System.out.println(name + " is " + age + " years old.");
        }

        // 删除Map中的元素
        map.remove("Alice");
        System.out.println("After removing Alice: " + map);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

在这个示例中，使用了一个HashMap来存储人名和对应的年龄。向Map中添加了一些元素，并使用get方法获取了其中一个元素的值。还使用containsKey方法检查了Map中是否包含某个键，并使用entrySet方法遍历了Map中的所有键值对。最后，使用remove方法删除了Map中的一个元素。

（七）树（Tree）

在Java中，树是一种非线性的数据结构，它用于表示具有层次关系的数据。每个树都由一个根节点和零个或多个子树组成，每个子树也是一个树。以下是一个简单的Java示例，演示了如何定义一个基本的树结构：

// 定义一个树结构节点
class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    // 构造方法
    TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

// 定义一个二叉树
public class BinaryTree {
    TreeNode root;

    // 构造方法
    BinaryTree(int value) {
        root = new TreeNode(value);
    }

    // 为了简单起见，这个例子中我们将只打印树的根节点值
    public void printRootValue() {
        System.out.println("Root Value: " + root.value);
    }

    public static void main(String[] args) {
        // 创建一个新的二叉树
        BinaryTree tree = new BinaryTree(1);

        // 打印根节点的值
        tree.printRootValue();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

在这个例子中，创建了一个二叉树，也就是说每个节点最多有两个子节点（可能为零个，即该节点为叶子节点）。每个节点有一个值，以及指向其左右子节点的引用。还定义了一个方法来打印树的根节点的值。当然，实际使用中，可能需要更多的方法来操作树，比如插入新节点、删除节点、搜索值等等。

（八）图（Graph）

在Java中，图（Graph）是一种常见的数据结构，用于表示对象之间的关系。下面是一个简单的示例，演示了如何使用Java实现一个图数据结构：

首先，需要定义图的基本元素：顶点和边。

1. 定义顶点类 Vertex：

public class Vertex {
    private String label;
    private int index;

    public Vertex(String label, int index) {
        this.label = label;
        this.index = index;
    }

    public String getLabel() {
        return label;
    }

    public int getIndex() {
        return index;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2. 定义边类 Edge：

public class Edge {
    private Vertex from;
    private Vertex to;
    private int weight;

    public Edge(Vertex from, Vertex to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
    }

    public Vertex getFrom() {
        return from;
    }

    public Vertex getTo() {
        return to;
    }

    public int getWeight() {
        return weight;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

接下来，定义一个图类 Graph，并在其中实现图的基本操作：添加顶点、添加边、打印图等。

3. 定义图类 Graph：

import java.util.*;

public class Graph {
    private List<Vertex> vertices;
    private List<Edge> edges;

    public Graph() {
        vertices = new ArrayList<>();
        edges = new ArrayList<>();
    }

    public void addVertex(Vertex vertex) {
        vertices.add(vertex);
    }

    public void addEdge(Edge edge) {
        edges.add(edge);
    }

    public void printGraph() {
        System.out.println("Vertices:");
        for (Vertex vertex : vertices) {
            System.out.println("Label: " + vertex.getLabel() + ", Index: " + vertex.getIndex());
        }
        System.out.println("Edges:");
        for (Edge edge : edges) {
            System.out.println("From: " + edge.getFrom().getLabel() + ", To: " + edge.getTo().getLabel() + ", Weight: " + edge.getWeight());
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

现在，可以创建一个图并对其进行操作：

4. 主类 Main：

public class Main {
    public static void main(String[] args) {
        Graph graph = new Graph();
        Vertex v1 = new Vertex("A", 0);
        Vertex v2 = new Vertex("B", 1);
        Vertex v3 = new Vertex("C", 2);
        graph.addVertex(v1);
        graph.addVertex(v2);
        graph.addVertex(v3);
        graph.addEdge(new Edge(v1, v2, 1));
        graph.addEdge(new Edge(v2, v3, 2));
        graph.addEdge(new Edge(v3, v1, 3));
        graph.printGraph();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

在这个例子中，创建了一个简单的无向图，其中包含三个节点A、B和C，以及三条边连接它们。边的权重分别表示从A到B的距离为1，从B到C的距离为2，以及从C到A的距离为3。这些权重可以解释为任意两个节点之间的距离，例如，节点A和节点B之间的距离为1，节点B和节点C之间的距离为2，以此类推。

为了完整地表示这个图，可以使用邻接矩阵来表示它。邻接矩阵是一个二维数组，其中行和列都表示图中的节点，矩阵中的元素表示两个节点之间是否有边相连，以及边的权重。在这个例子中，邻接矩阵可以如下所示：

A B C
A 0 1 3
B 1 0 2
C 3 2 0
1
2
3
4

其中第一行第二列的元素为1，表示从A到B有一条权重为1的边；第二行第三列的元素为2，表示从B到C有一条权重为2的边；以此类推。

除了邻接矩阵之外，还可以使用邻接列表来表示图。邻接列表是一个数组，其中每个元素都表示一个节点及其相邻的节点和边。例如，对于上面的图，邻接列表可以如下所示：

A: B(1) C(3)
B: A(1) C(2)
C: A(3) B(2)
1
2
3

其中第一行的第一个元素A表示起点节点，后面的冒号后跟着它的相邻节点和相应的边的权重。例如，从A到B有一条权重为1的边，从A到C有一条权重为3的边。以此类推，对于其他节点也是如此。