Java数据结构

13 Java 数据结构

数据结构分为两种：线性结构、非线性结构

线性结构：

• 最常用的数据结构。数据元素间存在一对一线性关系。

• 线性结构有 2 种不同的存储结构：顺序储存结构，链式储存结构

  顺序存储结构中元素存储在连续的内存空间中。

  链式储存结构中元素储存在非连续的空间中，元素节点中存放数据元素及相邻元素的地址信息

• 常见的线性结构有：数组、队列、链表、栈等

非线性结构：

• 非线性结构包括：二维数组、多维数组、广义表、树结构、图结构

13.1 集合的框架体系

Java 提供了一系列集合容器，以方便程序员动态保存元素。并提供了一系列方便的操作对象的方法。

Java 集合主要分为两组：单列集合（Collection）、双列集合（Map）

（集合体系图_13.1）

• Collection 接口（单列集合）：可以存放多个元素。每个元素可以是 Object

  Collection 接口有两个重要子接口：List（有序集合）和 Set（无序集合）

• Map 接口（双列集合）：用于保存具有映射关系的数据：key - value（双列元素）

  key 和 value 可以是任何类型的引用数据类型。其中 key 不能重复，value 可以重复

  key 和 value 存在单一对应关系。通过特定的 key 一定能找到指定的 value

13.2 单列集合接口 Collection

public interface Collection<E> extends Lterable<E>

Collection 实现子类可以存放多个元素。每个元素可以是 Object

有些 Collection 实现子类能存放重复的元素，有些不能

有些 Collection 实现子类是有序的（List） ，有些不是（Set）

Collection 接口没有直接的实现子类，都是通过其子接口实现的

常用方法：

• add：添加单个元素

  ArrayList list = new ArrayList();
  list.add("哈哈啊");
  list.add(10);				// 相当于List.add(new Integer(10));
  list.add(true);				// 同上

• remove：删除单个元素

  list.remove(0)				// 删除编号 0 的元素。上例中会删除 "哈哈啊"
  list.remove((Integer)10);	// 删除上例的 10 要这样写

• contains：检查元素是否存在

• size：获取元素个数

• isEmpty：判断是否为空

• clear：清空

• addAll：添加多个元素

  ArrayList list2 = new ArrayList();
  list2.add(111);
  list2.add("idea");
  list.addAll(list2);			// 这里可以输入所有实现了 Collection 接口的集合

• containsAll：检查多个元素是否存在

  list.contaionsAll(list2);	// 同上，放一个实现了 Collection 接口的集合

• removeAll：删除多个元素

  list.removeAll(list2);		// 同上

• Iterator iterator()：返回指向集合开始位置的迭代器

13.2.1 迭代器 Iterator

Iterator 对象称为迭代器，主要用于遍历 Collection 集合中的元素。

Collection 继承的 Iterable 接口中，提供了 iterator() 方法，会返回一个新的迭代器。

Iterator 对象仅用于遍历集合，本身不存放元素

IDEA 中，迭代器 while 循环的模板快捷键：itit

常用方法：

• boolean hasNext()：该方法判断是否有下一个元素。
• T next()：该方法会将指针下移，然后返回下移后的位置上的元素

用迭代器遍历元素：

Collection<Object> c = new LinkedList<>();
Iterator<Object> iterator = c.iterator();		// [1]
while (iterator.hasNext()){						// [2]
	Object obj = iterator.next();				// [3]
	System.out.println(obj);
}

1. 获取迭代器

2. 判断有无下一元素

3. 将迭代器后移，并返回那个后移位置上的元素

   while 循环结束后，指针指向最后元素的位置。再次 next() 会报错。如果需要再使用，需要重置迭代器。

   iterator = list.iterator();				// 重置了迭代器

for each（增强 for 循环）：

for each 的语法与 for 循环相似，但是可以遍历 Collection 和 数组 中的元素

IDEA 中，增强 for 循环的模板快捷键：I

for (Object o : list){
	...
}

• for each 可在 Collection 集合中使用。
• for each 的底层在本质上也是 Iterator。可以理解为简化版本的迭代器遍历。

13.3 有序集合接口 List

public interface List<E> extends Collection<E>

List 是 Collection 接口的子类接口

List 是有序（添加顺序和取出顺序一致）的，可重复的

List 中的每个元素都有其对应的顺序索引（从 0 开始编号）

常用方法：

• add(int, obj)：在 int 位置插入 obj 元素。返回 true

  add(obj)：在末尾插入 obj。返回 true

  list.add(111);
  list.add(0, 110);						// 在第 1 个位置插入数字 110

  addElement(obj)：在末尾插入 obj。无返回值。你说要这方法有啥用？名字还长一截

• addAll(int, collection)：在 int 位置插入 collection 中的所有元素

• get(int)：返回 int 位置的元素

• indexOf(obj)：返回 obj 首次出现时的位置

• lastIndexOf(obj)：返回 obj 最后一次出现时的位置

• remove(int)：移除 int 位置的元素，并返回那个被移除的元素

• set(int, obj)：设置 int 位置的元素为 obj。相当于替换。返回那个被替换元素的下标

  setElement(obj, int)：设置 int 位置的元素为 obj。无返回值

• subList(int1, int2)：返回 [int1, int2) 范围的元素构成的子集合

13.3.1 可变数组 ArrayList

public class ArrayList<E> extends AbstractList<E>
     implements List<E>, RandomAccess, Cloneable, java.io.Serializable

ArrayList 是 List 的实现子类。其底层由数组来实现存储。

ArrayList 可以存放 null

ArrayList 的源码：

1. ArrayList 中维护了一个 Object 类型的数组 elementData。该数组就是用来存放元素的数组

   transient Object[] elementData;

2. 创建 ArrayList 对象时，如果使用无参构造器，则 elementData[] 初始容量为 0

   private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
   
   public ArrayList() {
       this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
   }

3. 如果使用指定大小构造器，则初始容量为指定大小。

   private static final Object[] EMPTY_ELEMENTDATA = {};
   
   public ArrayList(int initialCapacity) {
       if (initialCapacity > 0) {
           this.elementData = new Object[initialCapacity];
       } else if (initialCapacity == 0) {
   	/* 这个场合，与默认构造器的不同之处在于
   		扩容时，该 0 容量变为 1，而默认构造器会变为 10 */
           this.elementData = EMPTY_ELEMENTDATA;
       } else {
           throw new IllegalArgumentException(...);
       }
   }

4. 扩容的场合：

   如果是 无参构造器生成的初始 0 长度的 elementData，则将其容量置为 10。

   否则容量扩容为 1.5 倍。

   /* 扩容方法，传入的参数 minCapacity 是容器现有元素数量 + 1 的值
   	如果是无参构造器生成的默认数组，此时传入固定值 10 */
   private void grow(int minCapacity) {
       int oldCapacity = elementData.length;
       /* 计算新的容量（旧容量的 1.5 倍）
       	此处 >> 为位运算符，等同于 newC = oldC + oldC / 2; */
       int newCapacity = oldCapacity + (oldCapacity >> 1);
       /* 这里如果原容量是特殊值（1 或 0），容量会变为那个 minCapacity 的值 */
       if (newCapacity - minCapacity < 0)
           newCapacity = minCapacity;
       if (newCapacity - MAX_ARRAY_SIZE > 0)
           newCapacity = hugeCapacity(minCapacity);
       elementData = Arrays.copyOf(elementData, newCapacity);
   }

13.3.2 可变数组 Vector

public class Vector<E>
    extends AbstractList<E>
    implements List<E>, RandomAccess, Cloneable, java.io.Serializable

Vector 是 List 的实现子类。其底层由数组来实现存储

Vector 与 ArrayList 基本等同。ArrayList 效率更高，Vector 线程安全。

在开发中，需要考虑线程安全时，建议使用 Vector ，而非 ArrayList。

Vector 的源码：

1. 底层维护了一个 Object 类型的数组 elementData。用以存放元素

   protected Object[] elementData;

2. 使用无参构造器创建对象时，默认大小是 10

   使用有参构造器的场合，默认是那个指定大小（initialCapaticy）

   也能在构造器中指定那个扩容的增长速度（capacityIncrement）

   public Vector() {
       this(10);
   }
   
   public Vector(int initialCapacity) {
       this(initialCapacity, 0);
   }
   
   public Vector(int initialCapacity, int capacityIncrement) {
       super();
       if (initialCapacity < 0)
           throw new IllegalArgumentException(...);
       this.elementData = new Object[initialCapacity];
       this.capacityIncrement = capacityIncrement;
   }

3. 扩容的场合，容量变成 2 倍

   使用有参构造器改变了 capacityIncrement 的场合，增量是那个指定数值

   private void grow(int minCapacity) {
       int oldCapacity = elementData.length;
       /* 计算新的容量（按照指定的增速扩容）
       	那个指定无效或未指定时，容量变为 2 倍 */
       int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                        capacityIncrement : oldCapacity);
       if (newCapacity - minCapacity < 0)
           newCapacity = minCapacity;
       if (newCapacity - MAX_ARRAY_SIZE > 0)
           newCapacity = hugeCapacity(minCapacity);
       elementData = Arrays.copyOf(elementData, newCapacity);
   }

13.3.3 链表 LinkedList

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList 是 List 的实现子类，底层以链表形式存储元素。

链表是一种非线性结构：其以节点方式存储，节点间在内存上的位置不连续。

链表是有序的列表。单向链表每个节点包含 data 域和 next 域。那些 next 域指向下一节点的位置。

双向链表在单向链表的基础上，每个节点加入 prev 区域以指示其前方节点。这样，就能实现双向查找。双向链表可以不依靠辅助节点而实现自我删除。

LinkedList 底层实现了 双向链表 和 双端队列 特点。

LinkedList 可以添加 null，可添加重复元素。但没有实现同步，因此线程不安全。

常用方法：

• void addLast(E e)：尾插一个新的元素

  LinkedList 的 add 方法即调用该方法

• void addFirst(E e)：头插一个新的元素

• E removeLast()：移除并返回尾部元素。为空时报错

  E poll()：移除并返回尾部元素。为空时返回 null

  E removeFirst()：移除并返回头部元素。为空时报错

• E getLast()：仅返回尾部元素。为空时报错

  E peek()：返回尾部元素。为空时返回 null

  E element()：返回头部元素。为空时返回 null

  E getFirst()

LinkedList 的源码

1. LinkedList 只有默认构造器和一个拷贝构造器

   public LinkedList() {
   }
   
   public LinkedList(Collection<? extends E> c) {
       this();
       addAll(c);
   }

2. LinkedList 底层维护了一个 双向链表

   两个属性 first、last 分别指向 首节点 和 尾节点

   每个节点（Node 对象），里面又维护了 prev、next、item 属性。

   其中通过 prev 指向前一个节点，通过 next 指向后一个节点。最终实现双向链表。

   transient Node<E> first;
   transient Node<E> last;
   
   private static class Node<E> {
       E item;
       Node<E> next;
       Node<E> prev;
   
       Node(Node<E> prev, E element, Node<E> next) {
           this.item = element;
           this.next = next;
           this.prev = prev;
       }
   }

3. LinkedList 不需要扩容。其增删元素时只要改变节点的指向即可。

   也因此，其添加、删除元素效率比数组更高

ArrayList 和 LinkedList 的比较：

	底层结构	增删效率	改查效率
ArrayList	可变数组	低（数组扩容）	高
LinkedList	双向链表	高（链表追加）	低

应该根据实际情况来选择使用的集合：

• 如果改查操作多，选择 ArrayList。一般来说，在程序中，80% - 90% 都是查询。大部分情况下，选择 ArrayList。
• 如果增删操作多，选择 LinkedList

13.3.4 稀疏数组

二维数组的很多值是默认值 0，因此记录了很多没有意义的数据。因此，可以使用稀疏数组。

稀疏数组的处理方法：

1. 记录数组共有几行几列，有多少个不同的值
2. 把具有不同值的元素的行列及值记录在一个小规模数组中，从而缩小程序规模

二维数组转换为稀疏数组：

下面用 ArrayList 模拟一个稀疏数组。

二维数组：

int[][] map = {{0, 2, 0, 0, 0, 0 ,0 , 0},
              {0, 0, 3, 0, 0, 0, 0, -1},
              {15, 0, 0, 0, 0, 4, 0, 0},
              {0, 2, 0, 0, 0, 0, 0, 0},
              {0, 0, 0, 0, 0, 0, 0, 0},
              {0, 0, 0, 0, 0, 0, 0, 1},
              {0, 0, 0, 0, 0, 0, 0, 0}};

遍历原始的二维数组，得到有效数据的个数 sum，并将二维数组的有效数据存入稀疏数组

List<int[]> sparseArray = new ArrayList();

sparseArray.add(new int[]{map.length, map[0].length, 0});	//

for (int y = 0; y < map.length; y++) {
    for (int x = 0; x < map[0].length; x++) {
        if (map[y][x] != 0) {
            sparseArray.add(new int[]{y, x, map[y][x]});
            sparseArray.get(0)[2]++;
        }
    }
}

稀疏数组转化为二维数组：

读取稀疏数组的每一行，按照其第一行数据，创建原始的二维数组。

读取后几行数据，将值赋给二维数组

13.3.5 栈 Stack

public class Stack<E> extends Vector<E>

Stack 是 Vector 的子类。以数组模拟了栈的数据结构。

栈是一个先入后出的有序列表。其元素之插入删除只能在该线性表的同一端进行。

其允许增删的一端称为栈顶，另一端即为栈底。

最先放入的元素位于栈底，最后放入的元素位于栈顶。

放入元素称为入栈（push），取出元素称为出栈（pop）

• 子程序的调用
• 处理递归调用
• 表达式的转换与求值
• 二叉树的遍历
• 图形的深度优先搜索法

常用方法：

• E push(E item)：将元素 item 压入栈。返回值是 item 自己

• E pop()：让栈顶元素出栈

• E peek()：仅获取栈顶元素

• int search(Object o)：查找该元素最后出现的位置。

  栈底为 1，栈顶为 size()，不存在返回 -1

13.3.5.1 栈模拟计算器

使用栈结构完成对计算器的实现

要进行计算，需要获得表达式。

表达式分为三种：

• 中缀表达式：

  中缀表达式即生活中常见的运算表达式。比如：(3 + 4) * 5 - 6

  中缀表达式是人最熟悉的。但是对于计算机来说却不好操作。因此，计算时常将其转化为其他表达式进行操作。

• 前缀表达式：

  前缀表达式（波兰表达式）是一种没有括号的表达式。其将运算符写在前面，操作数写在后面

  (3 + 4) * 5 - 6 的前缀表达式为： + 3 * 4 - 5 6

  (1 + 2) * (3 + 4) 的前缀表达式为：* + 1 2 + 3 4

  前缀表达式的计算机求值：

  • 从右向左扫描表达式
  • 将数字压入堆栈
  • 遇到运算符的场合，对数字栈顶元素与次顶元素进行计算，并把那个结果入栈
  • 重复该操作，最终数字栈的唯一剩余数字即为运算结果

• 后缀表达式：

  后缀表达式（逆波兰表达式）与前缀表达式相似。但其运算符位于操作数之后

  (3 + 4) * 5 - 6 的后缀表达式为： 3 4 + 5 * 6 -

  (1 + 2) * (3 + 4) 的后缀表达式为：1 2 + 3 4 + *

  后缀表达式的计算机求值：

  • 从左向右扫描表达式
  • 将数字压入堆栈
  • 遇到运算符的场合，对数字栈顶元素与次顶元素进行计算，并把那个结果入栈
  • 重复该操作，最终数字栈的唯一剩余数字即为运算结果

对于人类来说，中缀表达式最为熟悉。但对于计算机来说，前缀、后缀表达式更容易识别。

我们可以将中缀表达式转化为后缀表达式，再进行运算。

中缀表达式转换为后缀表达式：

1. 初始化两个栈：运算符栈 operator_stack、表达式栈 formula_stack

2. 从左到右扫描中缀表达式

3. 遇到操作数时，将其压入表达式栈 formula_stack

4. 遇到运算符时，比较其与 operator_stack 栈顶运算符的优先级。

   • operator_stack 为空，或栈顶为 ( 的场合，让运算符入栈
   • 优先级高于栈顶运算符的场合，让其入栈
   • 优先级低于或等于栈顶运算符的场合，将那个堆顶运算符弹出并压入 formula_stack。之后，重复该步骤。

5. 遇到括号时：

   • 遇到 ( 时，压入 operator_stack
   • 遇到 ) 时，直到遇到 ( 前，依次弹出 operator_stack 堆顶的运算符，并压入 formula_stack。之后将这一对括号丢弃。

6. 到达表达式最右边时，依次弹出 operator_stack 堆顶的运算符，压入 formula_stack。

7. 此时，formula_stack 即为后缀表达式。

   使用 Java 的 toArray 方法将其转为数组。或将其依次弹出，并逆序输出。

计算器的实现：

class Calculator {
    private static final Map<Character, Integer> priority = new HashMap<>();

    static {
        priority.put('+', 1);
        priority.put('-', 1);
        priority.put('*', 2);
        priority.put('/', 2);
        priority.put('×', 2);
        priority.put('÷', 2);
        priority.put('(', -100);
        priority.put(')', -10);
    }

    public static double calculate(String formula) {
        String[] ss = formula.split(" ");
        Stack<String> operator_stack = new Stack<>();
        Stack<String> formula_stack = new Stack<>();
        for (String s : ss) {
            if (s.matches("\\d+([.]\\d+)?")) {
                formula_stack.push(s);
                continue;
            } else if (operator_stack.empty() || s.equals("(")) {
                operator_stack.push(s);
                continue;
            }
            String temp = operator_stack.peek();
            while (priority.get(s.charAt(0)) <= priority.get(temp.charAt(0))) {
                formula_stack.push(operator_stack.pop());
                if (operator_stack.empty()) break;
                temp = operator_stack.peek();
            }
            if (s.equals(")")) {
                operator_stack.pop();
            } else operator_stack.push(s);

        }
        while (!operator_stack.empty()) {
            formula_stack.push(operator_stack.pop());
        }
        return anti_Poland(String.join(" ", formula_stack.toArray(new String[]{})));
    }

    private static double anti_Poland(String formula) {
        String[] ss = formula.split(" ");
        Stack<Double> ns = new Stack<>();
        for (String s : ss) {
            try {
                double num = Double.parseDouble(s);
                ns.push(num);
            } catch (Exception e) {
                switch (s) {
                    case "+":
                        ns.push(ns.pop() + ns.pop());
                        break;
                    case "*":
                    case "×":
                        ns.push(ns.pop() * ns.pop());
                        break;
                    case "/":
                    case "÷":
                        ns.push(1 / ns.pop() * ns.pop());
                        break;
                    case "-":
                        ns.push(-ns.pop() + ns.pop());
                        break;
                    default:
                        throw new RuntimeException("Illegal operator");
                }
            }
        }
        return ns.pop();
    }
}

13.3.6 跳表 SkipList

跳表是一种特殊的链表。普通的链表虽然添加、删除节点的速度很快（O(1)），但是要查找节点却很慢（O(n)）。跳表是一个多层次的链表，其在链表的基础上增加了多级索引，实现了 O(㏒n) 的查找速度。

跳表将原本数据层的数据按照一定间隔抽取节点形成索引层，之后再从索引层抽取节点形成第二级索引，以此类推形成多层索引。

跳表的查询速度得到了优化，但占用空间更大。本质上是一种空间换时间的做法。

查询

从最稀疏的索引层（最上层）开始，确定那个待查找数据所在的范围，逐层向下并确定范围，直至数据层。

增删

删除元素时，如果那个元素是索引元素，那些索引也会被删除。同时，如果只向数据层中增加元素，可能使索引间隔过大，从而降低查找效率。如果在增加元素时还能保持索引数量的动态平衡，就能防止跳表退化，保持跳表效率。

跳表给出的解决方案是：在增加元素时产生一个随机值，让这个随机值决定该新节点是否成为索引节点，以及成为几级索引节点。

实现跳表

class Skiplist {
    private final int level;					// 该跳表的合计层数，包括数据层和索引层
    private final Random seed;					// 随机数种子
    private final Node root;					// 链表开头
    private final Node end;						// 链表结尾

    private static class Node {					// 链表节点类
        int val;				// 值
        int count;				// 储存的值的数量
        Node[] next;			// 指向的下一节点
        Node[] prev;			// 指向的上一节点
        						// 需要指出的是：next 和 prev 的长度指示了节点所在的最高层级
        						// 长度为 1 时仅处在数据层，2 时也位于一级索引，以此类推
        						// 也就是说，next 和 prev 里，下标 0 的位置位于数据层，1 位于一级索引层

        /* 三个参数是：值 val，节点的层级 rand，节点储存值的数量 count */
        Node(int val, int rand, int count) {
            this.val = val;
            this.count = count;
            next = new Node[rand];
            prev = new Node[rand];
        }
    }

    /* 构造器 */
    public Skiplist() {
        this(4);
    }
	
    /* 有参构造器。输入的值是索引层数量。该值至少应为 1 */
    public Skiplist(int level) {
        if (level < 1 || level > 30)
            throw new RuntimeException(level == 0 ?
                    "Why not choose a LinkedList?" :
                    "SkipList level out of range: given " + level + " out of range [1, 30]");
        this.level = level + 1;
        this.seed = new Random(System.currentTimeMillis());
        root = new Node(Integer.MIN_VALUE, this.level, 0);
        end = new Node(Integer.MAX_VALUE, this.level, 0);
        for (int n = 0; n < this.level; n++) {
            root.next[n] = end;
            end.prev[n] = root;
        }
    }
	
    /* 查询一个值是否存在 */
    public boolean search(int target) {
        Node find = position(target);
        return find.val == target && find.count > 0;
    }
	
    /* 搜索一个值的位置。不存在时会返回数据层中前一个节点的位置 */
    private Node position(int target) {
        Node see = root;
        while (true) {
            if (see.val == target) return see;
            for (int n = see.next.length - 1; ; n--) {
                if (n < 0) return see;
                else if (see.next[n].val <= target) {
                    see = see.next[n];
                    break;
                }
            }
        }
    }
	
    /* 添加一个值 */
    public void add(int num) {
        Node pos = position(num);
        if (pos.val == num) {		// 如果这个节点已经建立，就仅使该节点计数增加
            pos.count++;
            return;
        }
        int rand = 1 + level - Integer.toBinaryString(seed.nextInt(1 << level)).length();
        			// level 的值等于总层数。seed 是一个随机数种子，nextInt(int n) 方法返回 [0, n) 的数值
        			// Integer.toBinaryString(int n) 方法是将一个数字转化成二进制表示的字符串
        			// seed.nextInt(1 << level) 保证了返回值的二进制长度在 [1, level] 之间，并且概率合意
        Node add = new Node(num, rand, 1);
        for (int t = 0; t < rand; ) {			// 将新节点添加到链表中。
            for (; t < pos.next.length && t < rand; t++) {
                Node next = pos.next[t];
                add.next[t] = next;
                next.prev[t] = add;
                pos.next[t] = add;
                add.prev[t] = pos;
            }
            pos = pos.prev[pos.prev.length - 1];
        }
    }
	
    /* 删除节点（的值） */
    public boolean erase(int num) {
        Node pos = position(num);
        if (pos.val == num && pos.count > 0) {
            pos.count--;
            return true;
        } else return false;
    }
}

13.4 队列接口 Queue

public interface Queue<E> extends Collection<E>

Queue 是 Collection 的子接口

Queue 的实现子类都是队列式集合。队列是一个有序列表，可以用数组或链表来实现

队列遵循先入先出的原则。队列中元素是以添加顺序取出的。

向队列中增加元素称为入列（push），取出元素称为出列（pop）

常用方法：

• add(E e)：添加元素。队列满的场合抛出异常

  put(E e)：添加元素。队列满的场合可能阻塞

  boolean offer(E e)：添加元素。队列满的场合返回 false

• E remove()：移除并返回队列头部元素。队列空的场合抛出异常

  E poll()：移除并返回队列头部元素

  E take()：移除并返回队列头部元素。队列空的场合可能阻塞

• E peek()：仅返回队列头部元素。为空时返回 null

  E element()：仅返回队列头部元素。为空时抛出异常

13.4.1 优先级队列 PriorityQueue

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable

PriorityQueue 是一个无界优先级队列。底层以数组储存元素。

无界队列：即没有范围限制的队列。

PriorityQueue 不允许 null 元素，也不允许不可比较的元素。

PriorityQueue 中的元素以自然顺序，或传入的比较器决定的顺序排序。其中的最小元素位于队头，最大元素位于队尾。

以迭代器遍历时，会按照原本的放入顺序获取元素。PriorityQueue 的源码：

1. 底层维护了一个 Object 类型的数组 queue。用以存放元素

   另维护了一个比较器 comparator，用以比较元素

   transient Object[] queue;
   private final Comparator<? super E> comparator;

2. 默认构造器初始容量为 11，比较器为 null

   也能指定初始容量，或传入比较器

   public PriorityQueue() {
       this(DEFAULT_INITIAL_CAPACITY, null);
   }
   
   public PriorityQueue(int initialCapacity) {
       this(initialCapacity, null);
   }
   
   public PriorityQueue(Comparator<? super E> comparator) {
       this(DEFAULT_INITIAL_CAPACITY, comparator);
   }
   
   public PriorityQueue(int initialCapacity,
                        Comparator<? super E> comparator) {
       if (initialCapacity < 1)
           throw new IllegalArgumentException();
       this.queue = new Object[initialCapacity];
       this.comparator = comparator;
   }

3. 放入时依靠比较器 comparator 进行排序。

   那个比较器为 null 的场合，每次放入元素会按元素自身的自然顺序进行排序。

   不能排序的场合会抛出异常。

4. 扩容时，容量小于 64 的场合容量变为 2 倍 + 2。否则那个容量变为 1.5 倍

   private void grow(int minCapacity) {
           int oldCapacity = queue.length;
           int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                            (oldCapacity + 2) :
                                            (oldCapacity >> 1));
           if (newCapacity - MAX_ARRAY_SIZE > 0)
               newCapacity = hugeCapacity(minCapacity);
           queue = Arrays.copyOf(queue, newCapacity);
       }

13.4.2 阻塞队列接口 BlockingQueue

public interface BlockingQueue<E> extends Queue<E>

BlockingQueue 是一个接口，其实现子类都是阻塞队列。

阻塞队列：

• 元素入列时，那个队列已满的场合，会进行等待。直到有元素出列后，元素数量未超过队列总数时，解除阻塞状态，进而继续入列。
• 元素出列时，如果队列为空，则会进行等待。直到有元素入列时，解除阻塞状态，进而继续出列。
• 阻塞队列能防止容器溢出。只要是阻塞队列，就是线程安全的队列。
• 阻塞队列不接受 null 元素

BlockingQueue 的常用实现子类有：

• ArrayBlockingQueue：底层以数组存放元素的有界阻塞队列
• LinkedBlockingQueue：底层以链表存放元素的可选边界的阻塞队列
• PriorityBlockingQueue：无界阻塞队列，与 PriorityQueue 排序方式相同

常用方法：

实际上，其常用方法能分为几类：

	抛出异常	特殊值	阻塞	等待
插入	add(e)	offer(e)	put(e)	offer(e, time, unit)
删除	remove()	poll()	take()	take(time, unit)
查找	element()	peek()	-	-

13.5 双列集合接口 Map

public interface Map<K,V>

以下关于 Map 接口的描述，适用于 JDK 8 的环境

Map 与 Collection 并列存在，用于保存具有映射关系的数据：key - value（双列元素）

Map 的 key 和 value 可以是任何类型的引用数据类型，也能存入 null。

Map 的 key 不允许重复，value 可以重复。key 和 value 存在单一对应关系。通过特定的 key 一定能找到指定的 value。

一组 k - v 会被封装到一个 Entry 对象中。Entry 是一个内部接口。Map 的实现子类中都包含一个实现这个接口的内部类。

interface Entry<K,V> {
	K getKey();
	V getValue();
    ...
}

如果添加相同的 key，会覆盖原先的 key -value。等同于修改（key 不会替换，value 会被替换）

常用方法：

• put()：添加。已存在的场合，实行替换。（key 不替换，value 替换）

• remove()：根据键删除映射关系

• get()：根据键获取值

• size()：元素个数

• isEmpty()：判断个数是否为 0

• clear()：清空

• containsKey()：查找键是否存在

• Set<K> keySet()：获取所有 键 构成的集合

  Set<Map.Entry<K,V>> entrySet()：获取所有 Entry 构成的集合

  Collection<V> values()：获取所有 值 构成的集合

Map 接口遍历元素：

• 方法一：利用 Set<K> keySet() 方法

  先得到所有 keys，再遍历 keys，根据每个 key 获得 value：

  Set keyset = map.keySet();
  for (Object o : keyset) {
  	System.out.println(o + " = " + map.get(o));
  }

• 方法二：利用 Set<V> values() 方法

  直接把所有 values 取出，之后遍历 values

  Collection values = map.values();
  for (Object value : values) {
  	System.out.println(value);
  }

• 方法三：利用 Set<Map.Entry<K,V>> entrySet() 方法

  通过获取 entrySet 来获取 k - v

  Set<Map.Entry> entrySet = map.entrySet();
  for (Map.Entry e : entrySet) {
  	System.out.println(e.getKey() + " - " + e.getValue());
  }

13.5.1 散列表 HashMap

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable

HashMap 是 Map 接口使用频率最高的实现类。是根据关键码值（key value）而进行直接访问的数据结构。通过将关键码值映射到表中一个位置来访问记录，以加快查找速度。

那个映射函数叫做散列函数，存放记录的数组叫做散列表（哈希表）

HashMap 是以 k - v 对得到方式来存储数据。一组数据会被封装到一个 Node 对象中。

static class Node<K,V> implements Map.Entry<K,V> {
 final int hash;
 final K key;
 V value;
 Node<K,V> next;

 ...
}

JDK 7 前，HashMap 底层是 数组 + 链表。JDK 8 后，底层是 数组 + 链表 + 红黑树。HashMap 不保证映射的顺序。

HashMap 没有实现同步（没有 synchronized），是线程不安全的

HashMap 的源码：

1. HashMap 底层维护了 Node 类型的数组 table。默认为 null

   transient Node<K,V>[] table;

   另外，还有集合 values、keySet、enrtySet。这些集合能帮助程序员进行遍历

   transient Set<K>				keySet;
   transient Collection<V>			values;
   transient Set<Map.Entry<K,V>>	entrySet;

2. 创建对象时，默认构造器将加载因子（loadfactor）初始化为 0.75。

   也能指定那些初始容量和加载因子。

   默认构造器第一次添加元素的场合，table 扩容为 16，临界值为 16 * 0.75 = 12。

   static final float DEFAULT_LOAD_FACTOR = 0.75f;
   static final int MAXIMUM_CAPACITY = 1 << 30;
   
   
   public HashMap() {
       this.loadFactor = DEFAULT_LOAD_FACTOR;					// 这个默认构造的场合，其他参数都是默认值
   }
   
   public HashMap(int initialCapacity) {
       this(initialCapacity, DEFAULT_LOAD_FACTOR);
   }
   
   public HashMap(int initialCapacity, float loadFactor) {
       if (initialCapacity < 0)
           throw new IllegalArgumentException(...);
       if (initialCapacity > MAXIMUM_CAPACITY)
           initialCapacity = MAXIMUM_CAPACITY;
       if (loadFactor <= 0 || Float.isNaN(loadFactor))
           throw new IllegalArgumentException(...);
       this.loadFactor = loadFactor;
       this.threshold = tableSizeFor(initialCapacity);
   }

3. 添加时容量不够的场合，需要扩容。

   默认构造器第一次添加元素的场合，table 扩容为 16，临界值为 16 * 0.75 = 12。

   扩容的场合，容量变为 2 倍。临界值相应变化。

   临界值不会超过那个指定的 MAXIMUM_CAPACITY（1 << 30），否则变成 Integer.MAX_VALUE。

   JDK 8 中，如果一条链表的元素个数超过 TREEIFY_THRESHOLD（默认是 8），并且 table 的大小 >= MIN_TREEIFY_CAPACITY（默认 64），会进行树化。

   剪枝：红黑树的元素减少到一定程度，会被重新转化为 链表

   static final int MAXIMUM_CAPACITY = 1 << 30;
   static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
   
   final Node<K,V>[] resize() {
       Node<K,V>[] oldTab = table;								// <- 旧的数据数组 table
       int oldCap = (oldTab == null) ? 0 : oldTab.length;		// <- 旧的 table 的容量
       int oldThr = threshold;									// <- 旧的临界值
       int newCap, newThr = 0;									// <- 新的容量、临界值
       
       /* 旧的数组不为空时，
       	如果容量已达指定的 MAXIMUM_CAPACITY，则不扩容
       	否则扩容为 2 倍容量，临界值也变为 2 倍 */
       if (oldCap > 0) {
           newCap = oldCap << 1;
           if (oldCap >= MAXIMUM_CAPACITY) {
               threshold = Integer.MAX_VALUE;
               return oldTab;
           }
           else if (newCap < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
               newThr = oldThr << 1;
       }
       /* 旧的数组为空，但临界值已被指定（原因是：指定构造器传入初始容量为 0） */
       else if (oldThr > 0)
           newCap = oldThr;
       /* 旧的数组为空，临界值为 0（原因是：使用默认构造器）
       	默认构造器初始化容量为 16，默认临界因子为 0.75f */
       else {
           newCap = DEFAULT_INITIAL_CAPACITY;
           newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
       }
       
       /* 到这里，newThr（新临界值）为 0 的原因可能是：
       	1. 旧容量小于那个最小容量（16）
       	2. 扩容后容量大于那个最大容量
       	3. 旧的临界值为 0 或 Integer.MIN_VALUE
       	4. 构造器传入初始容量为 0 */
       if (newThr == 0) {
           /* 按照 新容量 * 临界因子 的方法计算临界值。临界值不会超过一个指定的最大值 */
           float ft = (float)newCap * loadFactor;
           newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                     (int)ft : Integer.MAX_VALUE);
       }
       threshold = newThr;
       
       /* 确定了容量和临界值，下面把旧数组元素移至新数组。
       	那个移动的场合，会以新容量重新计算所有元素的下标位置 */
       Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
       table = newTab;
       if (oldTab != null) {
           for (int j = 0; j < oldCap; ++j) {
               Node<K,V> e;
               if ((e = oldTab[j]) != null) {
                   oldTab[j] = null;
                   if (e.next == null)
                       newTab[e.hash & (newCap - 1)] = e;
                   else if (e instanceof TreeNode)
                       ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                   else {
                       Node<K,V> loHead = null, loTail = null;
                       Node<K,V> hiHead = null, hiTail = null;
                       Node<K,V> next;
                       do {
                           next = e.next;
                           if ((e.hash & oldCap) == 0) {
                               if (loTail == null)
                                   loHead = e;
                               else
                                   loTail.next = e;
                               loTail = e;
                           }
                           else {
                               if (hiTail == null)
                                   hiHead = e;
                               else
                                   hiTail.next = e;
                               hiTail = e;
                           }
                       } while ((e = next) != null);
                       if (loTail != null) {
                           loTail.next = null;
                           newTab[j] = loHead;
                       }
                       if (hiTail != null) {
                           hiTail.next = null;
                           newTab[j + oldCap] = hiHead;
                       }
                   }
               }
           }
       }
       return newTab;
   }

4. 添加 k - v 时，通过 key 的哈希值得到其在 table 的索引，判断索引位置是否被占用。

   未占用的场合，直接添加。

   占用的场合，判断其 key 是否相等。相等的场合，替换 value。否则，按照 树 或 链表 的方式处理。

   public V put(K key, V value) {
       return putVal(hash(key), key, value, false, true);
   }
   
   
   /* 会先对放入元素的哈希值进行一次计算，得到一个数字：hash */
   static final int hash(Object key) {
       int h = key.hashCode();
       return (key == null) ? 0 : (h ^ (h >>> 16));	// 位运算符：>>> 无符号右移
   }
   
   
   /* put 方法会调用该 putVal 方法。
   	那些传入值是：	hash、	key、	value、			false、				true */
   final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
       Node<K,V>[] tab = table; 		// <- 是那个存放数据的 table 数组
       int n;							// <- 是 table.length
       
       /* 如果原先的 table 为空，则对其重新分配空间 */
       if (tab == null || (n = tab.length) == 0) {
           tab = resize();
           n = tab.length;
       }
       
       /* 用方才计算的 hash 数，得到要放入元素的下标值 i
       	n - 1 是数据数组的最大下标，(n - 1) & hash 必定不大于 n - 1 */
       int i = (n - 1) & hash;			// 位运算符：& 按位与
       Node<K,V> p = tab[i];			// 得到 table 中，位于那个插入位置的元素
       
       
       /* 倘若该位置为空，则直接放入 */
       if (p == null) {
           tab[i] = newNode(hash, key, value, null);
       }
       /* 该位置不为空，意味着可能添加了重复元素 */
       else {
           Node<K,V> e; 			// <- 被发现重复的那个 Node。无重复时结果为 null。这个 Node 的 value 会被替换。
           K k = p.key;			// <- 当前取出进行比较的 key 值
           
           /* 为了验证其是否重复，这里要进行如下比较：
           	1. 比较两者的 hash 数。不同的场合是不同元素
           	2. 使用 == 和 equals 两种方法比较 key。不同的场合是不同元素 
           	如果是相同元素，则该节点的值会被替换 */
           if (p.hash == hash && (k  == key || (key != null && key.equals(k)))) {
               e = p;
           }
           
           /* 此处节点结构是 树 的场合，还需遍历比较树的每个节点 */
           else if (p instanceof TreeNode)
               e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
           
           /* 此处节点结构是 链表 的场合，还需遍历比较每个链表节点 */
           else {
               for (int binCount = 0; ; ++binCount) {
                   e = p.next;
                   /* e == null 意味着遍历结束，全部不同。这样，在此处添加那个新的 Node */
                   if (e == null) {
                       p.next = newNode(hash, key, value, null);
                       if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                           treeifyBin(tab, hash);
                       break;
                   }
                   /* 故技重施，如果发现相同，则替换那个新元素 */
                   if (e.hash == hash &&
                       ((k = e.key) == key || (key != null && key.equals(k)))) {
                       break;
                   }
                   p = e;
               }
           }
           
           /* 经历上述比较后，e != null 意味着有元素要被替换了 */
           if (e != null) {
               V oldValue = e.value;
               /* 传入的参数 onluIfAbsent == false，所以此处一定是 true */
               if (!onlyIfAbsent || oldValue == null)
                   e.value = value;
               afterNodeAccess(e);		// <- HashMap 中，该方法为空实现。
               return oldValue;
           }
       }
       ++modCount;
       
       /* 如果到达这里，说明添加了元素（而非替换），要查看大小是否超过临界值 */
       if (++size > threshold)
           resize();
       afterNodeInsertion(evict);		// <- HashMap 中，该方法为空实现。
       return null;
   }
   
   
   /* 上面提到的一些空实现的方法 */
   void afterNodeAccess(Node<K,V> p) { }
   void afterNodeInsertion(boolean evict) { }
   void afterNodeRemoval(Node<K,V> p) { }

13.5.2 散列表 Hashtable

public class Hashtable<K,V>
    extends Dictionary<K,V>
    implements Map<K,V>, Cloneable, java.io.Serializable

Hashtable 和 HashMap 基本一致，但Hashtable 是线程安全的 。但也因为如此，Hashtable 的效率低下。

Hashtable 与 HashMap 的比较：

	版本	线程安全（同步）	效率	是否允许 null值
Hashtable	1.0	安全	较低	不允许
HashMap	1.2	不安全	高	允许

• Hashtable 底层也是有数组，默认构造器的初始容量为 11。临界值是 11 * 0.75 = 8。

• 扩容大致如下：

  int newCapacity = (oldCapacity << 1) + 1;			//即，原容量 * 2 + 1

• Hashtable 不会树化

13.5.3 红黑树 TreeMap

public class TreeMap<K,V>
    extends AbstractMap<K,V>
    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

TreeMap 实现了 Map 接口。底层使用 红黑树 存储数据。

相较数组（访问快，检索、插入慢）和链表（插入快，检索、访问慢），树形数据结构（如二叉排序树）在保证数据检索速度的同时，也能保证数据插入、删除、修改的速度

——见 [[14.1.4.1 平衡二叉树]](https://i-melody.github.io/2022/06/02/Java/入门阶段/14 树/#14-1-4-1-平衡二叉树)

TreeMap 的源码：

1. TreeMap 底层维护了一个二叉树，以及一个比较器

   private final Comparator<? super K> comparator;
   
   private transient Entry<K,V> root;

2. 创建对象时，能采用无参构造，也能指定比较器完成构造

   那个无参构造的场合，比较器为空。

   public TreeMap() {
       comparator = null;
   }
   
   public TreeMap(Comparator<? super K> comparator) {
       this.comparator = comparator;
   }

   比较器如果为空，则要求传入的 key 必须是 Comparable 接口的实现子类，否则无法进行比较。

   final int compare(Object k1, Object k2) {
       return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
           : comparator.compare((K)k1, (K)k2);
   }

3. 添加时，通过比较器确定那个添加位置。

   public V put(K key, V value) {
       Entry<K,V> t = root;	// <- 树的根节点
       
       /* 二叉树为空的场合，创建根节点，将数据放入 */
       if (t == null) {
           compare(key, key);
           root = new Entry<>(key, value, null);
           size = 1;
           modCount++;
           return null;
       }
       
       int cmp;				// <- 临时值，存放比较结果
       Entry<K,V> parent;		// <- 临时值，存放父节点
       Comparator<? super K> cpr = comparator;		// <- 比较器
       
       /* 有比较器的场合，按照这个方法进行比较 */
       if (cpr != null) {
           do {
               parent = t;
               cmp = cpr.compare(key, t.key);
               if (cmp < 0)
                   t = t.left;
               else if (cmp > 0)
                   t = t.right;
               else
                   return t.setValue(value);
           } while (t != null);
       }
       
       /* 比较器为空的场合，按照这个方法进行比较 */
       else {
           if (key == null) {
               throw new NullPointerException();
           }
           Comparable<? super K> k = (Comparable<? super K>) key;
           do {
               parent = t;
               cmp = k.compareTo(t.key);
               if (cmp < 0)
                   t = t.left;
               else if (cmp > 0)
                   t = t.right;
               else
                   return t.setValue(value);
           } while (t != null);
       }
       
       /* 将数据节点放到正确的路径下 */
       Entry<K,V> e = new Entry<>(key, value, parent);
       if (cmp < 0)
           parent.left = e;
       else
           parent.right = e;
       
       /* 此处会试着将该树转换成完全二叉树 */
       fixAfterInsertion(e);
       size++;
       modCount++;
       return null;
   }

4. 添加的最后，会试着将该树转换成完全二叉树

   private void fixAfterInsertion(Entry<K,V> x) {
       x.color = RED;
   
       while (x != null && x != root && x.parent.color == RED) {
           if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
               Entry<K,V> y = rightOf(parentOf(parentOf(x)));
               if (colorOf(y) == RED) {
                   setColor(parentOf(x), BLACK);
                   setColor(y, BLACK);
                   setColor(parentOf(parentOf(x)), RED);
                   x = parentOf(parentOf(x));
               } else {
                   if (x == rightOf(parentOf(x))) {
                       x = parentOf(x);
                       rotateLeft(x);
                   }
                   setColor(parentOf(x), BLACK);
                   setColor(parentOf(parentOf(x)), RED);
                   rotateRight(parentOf(parentOf(x)));
               }
           } else {
               Entry<K,V> y = leftOf(parentOf(parentOf(x)));
               if (colorOf(y) == RED) {
                   setColor(parentOf(x), BLACK);
                   setColor(y, BLACK);
                   setColor(parentOf(parentOf(x)), RED);
                   x = parentOf(parentOf(x));
               } else {
                   if (x == leftOf(parentOf(x))) {
                       x = parentOf(x);
                       rotateRight(x);
                   }
                   setColor(parentOf(x), BLACK);
                   setColor(parentOf(parentOf(x)), RED);
                   rotateLeft(parentOf(parentOf(x)));
               }
           }
       }
       root.color = BLACK;
   }

13.5.4 Properties

Properties 继承自 Hashtable 并实现了 Map 接口。也使用键值对的方式保存数据

Properties 使用特点与 Hashtable 相似

Properties 还可以用于 xxx.properties 文件中，加载数据到 Properties 对象，进行读取和修改

xxx.properties 文件常作为配置文件

public class Properties extends Hashtable<Object,Object>

——关于这些，详见 [[17 IO流 ]](https://i-melody.github.io/2022/01/06/Java/入门阶段/17 IO流/)

• String getProperty(String key) ：输入一个 String 类型的 key，返回一个 String 的 value

  public String getProperty(String key) {
  Object oval = super.get(key);
  String sval = (oval instanceof String) ? (String)oval : null;
  return ((sval == null) && (defaults != null)) ? defaults.getProperty(key) : sval;
  }

13.6 无序集合接口 Set

Set 是 Collection 接口的子类接口。

Set 接口的特点是无序（添加和取出顺序不一致，其取出顺序由某个算法决定），没有索引

不允许重复元素。故而，最多包含一个 null

public interface Set<E> extends Collection<E>

13.6.1 HashSet

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

HashSet 实现了 Set 接口。底层实际上使用 HashMap 来存储数据。身在 Collection 心在 Map

HashSet 是无序的。其实际顺序取决于计算得到的 hash 值

HashSet 的源码

1. HashSet 底层是 HashMap。

   private transient HashMap<E,Object> map;

2. 实例化也和 HashMap 相同

   public HashSet() {
       map = new HashMap<>();
   }
   
   public HashSet(int initialCapacity) {
       map = new HashMap<>(initialCapacity);
   }
   
   public HashSet(int initialCapacity, float loadFactor) {
       map = new HashMap<>(initialCapacity, loadFactor);
   }

3. 添加一个元素时调用 HashMap 的方法

   public boolean add(E e) {
       return map.put(e, PRESENT)==null;
   }

13.6.2 LinkedHashSet

LinkedHashSet 是 HashSet 的子类

LinkedHashSet 底层是一个 LinkedHashMap，维护了一个数组 + 双向链表。有其父必有其子

LinkedHashSet 根据元素的 hashCode 值来决定元素的存储位置。同时，使用链表维护元素的次序。这使得元素看起来是以插入顺序保存的，并得以按照放入顺序取出

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

LinkedHashSet 的源码：

1. 在类 HashSet 中，存在一个默认访问范围的构造器。该构造器不同于其他构造器，会让实例维护一个 LinkedHashMap

   HashSet(int initialCapacity, float loadFactor, boolean dummy) {
       map = new LinkedHashMap<>(initialCapacity, loadFactor);
   }

   LinkedHashSet 的构造器即调用了该父类构造器

   public LinkedHashSet(int initialCapacity, float loadFactor) {
       super(initialCapacity, loadFactor, true);
   }
   
   public LinkedHashSet(int initialCapacity) {
       super(initialCapacity, .75f, true);
   }
   
   public LinkedHashSet() {
       super(16, .75f, true);
   }

13.6.3 TreeSet

public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable

TreeSet 实现了 Set 接口，其底层是一个 TreeMap。好家伙，原来 Set 全家都是卧底

调用无参构造器创建 TreeSet 时，默认是无序排列。也能在构造时传入一个比较器。有比较器的场合，比较器返回 0 时，不发生替换

不传入比较器的场合，使用的是传入对象自带的比较器。所以，这个场合，传入的 key 对象必须是 Comparable 接口的实现子类

13.7 集合的选择

在开发中，选择什么集合实现类，主要取决于业务操作特点，然后根据集合实现类特性进行分析选择。

判断存储的类型（一组对象 [单列]，或一组键值对 [双列]）

• 一组对象：Collection 接口
  • 允许重复：List
    • 增删多：LinkedList （双向链表）
    • 改查多：ArrayList （Object[] 数组）
  • 不允许重复：Set
    • 无序：HashSet （数组 + 链表 + 红黑树，底层是 HashMap）
    • 排序：TreeSet
    • 顺序一致：LinkedHashSet （数组 + 双向链表，底层是 LinkedHashMap）
• 一组键值对：Map
  • 键无序：HashMap （数组 + 链表 + 红黑树 [ JDK 8 以后 ] ）
  • 键排序：TreeMap
  • 键顺序一致：LinkedHashMap （底层是 HashMap）
  • 读取文件：Properties

13.8 工具类 Collections

Collections 工具类是一个操作 Set、List、Map 等集合的工具类

其中提供了一系列静态方法，对集合元素进行 排序、查询和修改等操作

常用方法：

排序：

• reverse(List)：反转 List 中元素的排序
• shuffle(List)：对 List 中元素进行随机排序
• sort(List)：根据元素的自然顺序对指定 List 集合元素升序排列
• reverse(List, Comparator)：根据指定 Comparator 对 List 排序
• swap(List, int, int)：将两处元素位置互换

查找、替换：

• Object max(Collection)：根据元素的自然排序，返回集合中最大的元素

• Object max(Collection, Comparator)：根据比较器，返回最大元素

• Object min(Collection)：根据元素的自然排序，返回最小元素

• Object min(Collection, Comparator)：根据比较器，返回最小元素

• int frequency(Collection, Object)：返回集合中指定元素的出现次数

• void copy(List dest, List src)：将 src 的内容复制到 dest 中

  这个场合，要保证 dest 的大小不小于 src。所以，可能需要先给 dest 赋值

• boolean replaceAll(List list, Object oldVal, Object newVal)：用 newVal 替换所有 oldVal 值

13.9 JUnit

一个类有多个功能代码需要测试，为了测试，就要写入 main 方法中

如果有多个功能代码测试，需要反复撤销，过程繁琐

JUnit 是一个 Java 语言单元测试框架

多数 Java 开发环境都已集成了 JUnit 作为单元测试工具

使用方法

……总的来讲，方法就是加入 @Test，然后 alt + enter 引入 JUnit 5，最后运行

14 树

什么是树？

	结构严格派 唯一父节点和复数子节点	结构中立派 有前驱和后继关系就行	结构自由派 能存放内容就行
类型严格派 是一种数据结构	二叉树是树	链表也是树	栈也是树
类型中立派 和编程有关就行	包也是树	语句肯定是树	标识符都是树
类型自由派 和程序员有关就行	wifi 当然是树	衣服拉链也是树	馄饨也是树！

14.1 二叉树：

（树结构图_14.1）

• **二叉树：**树有多种。每个节点最多只能有 2 个子节点的一种树的形式称为二叉树

  二叉树的子节点分为 左节点 和 右节点。

• **满二叉树：**二叉树的 所有叶节点 都在 最后一层，且节点总数是 2n - 1

• **完全二叉树：**二叉树的 所有叶节点 都在 最后一层 和 倒数第二层，且最后一层的叶节点在左侧连续、倒数第二层的叶节点在右侧连续

二叉树的遍历：

• **前序遍历：**先输出父节点，再遍历左子树和右子树。

  自根节点起。先输出当前节点。再递归前序遍历左节点。那之后，递归前序遍历右节点。

  public static class Node {					// 节点类
      int val;
      Node left;
      Node right;
  }
  
  public static String traverse(Node root) {
      StringBuilder sb = new StringBuilder();
      traverse(root, sb);
      return sb.toString();
  }
  
  private static void traverse(Node root, StringBuilder sb) {
      if (root == null) return;
      sb.append(root.val).append(" ");		// 先输出父节点
      traverse(root.left, sb);				// 再遍历左子树
      traverse(root.right, sb);				// 再遍历右子树
  }

• **中序遍历：**先遍历左子树，再输出父节点，再遍历右子树。

• **后序遍历：**先遍历左子树，再遍历右子树，再输出父节点。

14.1.1 顺序存储二叉树

从数据存储来看，数组与树可以相互转换。数组可以转换成树，树也能转换成数组。

顺序存储二叉树通常只考虑完全二叉树。将数组转换成树后，将可以进行前序、中序、后序遍历。

顺序存储二叉树的例子：

int[] array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

该 array 的顺序存储二叉树为：

0
1
3
2
5
4
6
7
8
9
10

顺序存储二叉树的转换：

• 数组下标为 0 的元素放在根节点。

• 对于数组下标为 n 的元素，其左子节点的数组下标为 2 × n + 1、右子节点的数组下标为 2 × n + 2、父节点的数组下标为 (n - 1) / 2

  可以发现，所有左节点都是奇数下标，右节点都是偶数下标

public static Node toTree(int[] array) {
    Node root = new Node(array[0]);
    List<Node> list = new ArrayList<Node>();
    list.add(root);									// 数组下标为 0 的元素放在根节点。
    for (int i = 1; i < array.length; i++) {		// 按照前述方法，创建每个元素节点，并放在对应父节点下
        Node temp = new Node(array[i]);
        list.add(temp);
        Node parent = list.get((i - 1) / 2);
        if (i % 2 == 0) parent.right = temp;
        else parent.left = temp;
    }
    return root;
}

public static class Node {
    public int val;
    public Node left;
    public Node right;
    
    public Node(int val) {
        this.val = val;
    }
}

以上是一种显式的转换。也可以直接将数组视为抽象的顺序存储二叉树。

如：堆。——见 [[5.4.8 堆排序]](https://i-melody.github.io/2021/11/27/Java/入门阶段/5 数组、排序和查找/#5-4-8-堆排序)

14.1.2 线索化二叉树

含有 n 各节点的二叉链表中，有 n + 1 个空指针域。利用这些空指针域，存放指向节点在某种遍历次序下的前驱和后继节点的指针，这种附加的指针称为 线索。加上了线索的二叉链表称为 线索链表，相应二叉树称为 线索二叉树。

线索二叉树可分为：前序线索二叉树、中序线索二叉树、后续线索二叉树。

线索化二叉树后，那些左节点和右节点既可能指向 自身的子树，也可能指向自身的 前驱 / 后继 节点。因此，需要添加一组标记，以记录线索的种类。

这个遍历的场合，不能再使用递归方式遍历，而是改为线性方式遍历即可。

14.1.3 赫夫曼树

给定 n 个权值作为 n 个叶节点，构造一棵二叉树。若该树的带权路径长度（WPL）最小，则称其为 最优二叉树（赫夫曼树、哈夫曼树、霍夫曼树）

• 节点的带权路径长度：该节点的权 × 节点路径长度

• 树的带权路径长度：所有的叶结点的带权路径长度之和

  赫夫曼树中，一定是权值较大的节点距离根更近。

赫夫曼树的例子：

NaN
NaN
14
NaN
5
NaN
1
2
NaN
16
20

生成赫夫曼树：

1. 对数据进行排序。每个数据都可以创建一个节点
2. 取出权值最小的两颗二叉树，合并为一棵新的二叉树。该二叉树权值是两棵子树的权值之和
3. 将数据再次排序，重复合并步骤，直至剩余唯一的树，即为赫夫曼树

赫夫曼编码：

赫夫曼编码是一种编码方式，是一种程序算法。赫夫曼编码是赫夫曼树在电讯通信中的经典应用之一。

赫夫曼编码广泛应用于数据文件压缩，其压缩率在 20% ~ 90% 间

赫夫曼编码是可变字长编码的一种。是老赫在 1952 年提出的编码方法，称为 “最佳编码”

赫夫曼编码是无损处理方案。由于赫夫曼编码是按字节处理数据，因此可以处理所有文件

编码方式有三种：

• 定长编码：

  如 ASCII 码，其每个字符占用长度为固定 8 字节

• 变长编码：

  对字符进行统计，按照各个字符出现的次数进行编码。出现次数越多，编码越小。

  字符的编码不能是其他字符编码的前缀，这样的编码叫做前缀编码（消除二义性）。

• 赫夫曼编码：

  按照字符的出现次数，构建赫夫曼树。之后，按照赫夫曼树结构，给字符规定编码。向左的路径记为 0，向右记为 1。

  这样得到的编码，一定是前缀编码。因为那些字符节点都是叶节点。赫夫曼行啊赫夫曼！

  之后，用规定的编码将指定字符串转化为字节数组。最后，传递字符数组即可。

实现赫夫曼编码：

——见本章附录：[F1 实现赫夫曼编码/解码]

注意事项：

• 压缩已经过压缩处理的文件，那个压缩率会变低
• 如果一个文件中重复的数据很少，压缩效果也会不明显

14.1.4 二叉排序树

二叉排序树（BST，Binary Sort Tree）：对于任何一个非叶节点，其左节点小于等于当前节点，右节点大于等于当前节点

二叉排序树的例子：

10
8
4
2
1
6
9
15
12
23

二叉排序树删除节点：

• 删除叶节点的场合，将那个父节点的对应连接置空即可。

• 删除有唯一子节点的节点场合，让那个父节点的对应连接改为指向子树即可。

• 删除有两个子节点的节点的场合，将该节点置为正无穷或负无穷。

  之后维护该二叉排序树，直到该节点成为叶节点时，删除该节点即可。

14.1.4.1 平衡二叉树

二叉排序树可能形成一些奇怪的形状（如左子树全部为空），这样就不能发挥树形结构的比较优势。

平衡二叉树（AVL 树）：也叫平衡二叉搜索树。非空时，其任意节点左右两个子树的高度差不超过 1，且左右子树也都是平衡二叉树。

平衡二叉树的实现方法有：红黑树、AVL、替罪羊树、Treap、伸展树等

平衡二叉树的左旋转：

• 创建一个新节点。该节点的值等于根节点值
• 使该新节点的左子树指向当前根节点的左子树。使该节点的右子树指向当前根节点右子树的左子树
• 使当前根节点的右子树的左子树指向该新节点
• 使当前根节点的右子树成为新的根节点。旧的根节点被废弃

简单的说，就是让根节点的右子树指向右子树的左子树。而右子树的左子树指向根节点。

合理性在于，根节点（root）的右子树（right）上的所有值都大于 root；而 right 的所有左子树的值，以及 root 所有左子树的值也一定小于 right 值

平衡二叉树的右旋转：

还不是一样？

平衡二叉树的双旋转：

符合进行右旋转的条件（右子树高度 > 左子树高度 + 1）时，如果那个左子树的右子树高度高于其左子树高度，需要先对左子树进行左旋转。以此类推。

实现平衡二叉树：

——见本章附录：[F2 实现平衡二叉树]

14.1.5 线段树

线段树（Segment Tree）是一棵二叉树。其每个节点表示一个闭区间，父节点的区间内包含所有子节点的区间。

• 对于每个非叶节点，将其区间平均划分成两个子区间。左节点指向其中较小区间，右节点指向那个较大区间

  换言之，对于非叶节点 [L, R]，其左子节点是 [L, (L + R) / 2]，右子节点是 [((L + R) / 2) + 1, R]

• 对于每个叶节点，其区间仅包含一个元素。即，其区间的左界等于右界。

线段树的例子：

在区间 [1, 9] 中，记录 [2, 9] 的样子

[1,9]
[1,5]
[6,9]
[1,3]
[4,5]
[6,7]
[8,9]
[1,2]
[3,3]
[4,4]
[5,5]
[6,6]
[7,7]
[8,8]
[9,9]
[1,1]
[2,2]

线段树是近似的完全二叉树。有时，线段树的节点是随着线段树的更新逐渐建立的，此时线段树不处于完全二叉树的状态。

线段树的更新：

标记区间时，按照 广度优先搜索 的思想，从根节点开始遍历区间。

——广度优先搜索，见本章 [14.3.2 广度优先搜索 BFS]

比如，添加区间 [START, END] 时：

• 如果一个节点的区间内所有元素都被标记，则标记这个节点

  对于区间 [L, R]，如果 L >= STRAT 且 R <= END，则标记该节点

• 如果一个节点的区间内部分元素被标记，则继续遍历其左右节点

  对于区间 [L, R]，MID = (L + R) / 2

  如果 MID >= L，则需要遍历其左节点。如果 MID < R，则需要遍历其右节点

标记节点时，只需在该节点添加懒标记，而不必对所有子节点进行标记。

懒标记：

使用懒标记，可以只更新到满足条件的区间，而不必对所有子区间一一更新。此后再次遍历到该节点时，再对懒标记进行下推

上述例子中，记录区间 [2, 7] 时，仅更新了 [2, 2]、[3, 3]、[4, 5]、[6, 9] 这些节点。

以节点 [6, 9] 为例，该区间上被添加了懒标记，代表该区间及所有子区间都被记录了一次。下次遍历到这个节点时，懒标记被下推给子节点 [6, 7]、[8, 9]

线段树的查询：

一个区间的元素和，等于 其子区间各自元素和 的合计值

一个区间中的最大值，等于 其子区间各自最大值 中的较大值

14.2 多路查找树

二叉树虽然效率较高，但需要加载到内存中。节点过多时就可能出现问题。

如：需要进行多次 I / O 操作，导致构建速度慢；造成二叉树高度很大，降低操作速度。

每个节点可以拥有更多数据项和更多子节点的树，就是多叉树（multiway tree）。

多叉树通过重新组织节点，能减少树的高度，能对二叉树进行优化。

名词解释：

• 节点的度：节点的子节点数量
• 树的度 / 阶：树中所有节点的度的最大值

14.2.1 2-3 树

2-3 树是最简单的 B 树结构。其具有如下特点：

• 所有叶节点都在同一层。节点包含不超过 2 个值。

• 有两个子节点的节点叫 二节点。二节点要么没有子节点，要么有两个子节点。

  有三个子节点的节点叫 三节点。三节点要么没有子节点，要么有三个子节点。

• 2-3 树是由 二节点 和 三节点 构成的树。其节点仍遵循二叉排序树的规则。

  对于二节点：其左子树的值需小于当前节点、右子树的值需大于当前节点

  对于三节点：其左子树的值小于当前节点的最小值，中子树的值需介于当前节点的两个值之间，右子树的值大于当前节点的最大值

2-3 树的例子：

10
6
1, 3
7
15, 20
11, 12
19
22, 32

构建 2-3 树：

• 插入节点时，如果不能满足条件，即需要拆分。

  拆分时先拆上层。上层满时，才拆本层。拆分后仍要满足规则

2-3-4 树：

还不是一样？

14.2.2 B 树

B 树（b-tree，balance tree）。2-3 树与 2-3-4 树都是 B 树的种类。

30, 60
P1 - P2 - P3
10, 20
P1 - P2 - P3
40, 50
. - P2 - P3
70, 80
P1 - P2 - P3
3, 6
12, 13
23, 24

41, 48
55, 57
61, 62
73, 74
84, 86

B 树具有如下特点：

• 树树我啊，所有叶节点都在同一层呢。

• 搜索时，从根节点起，对当前节点内的关键字（有序）进行二分查找。

  命中则结束。否则，进入那个对应范围的子节点。那个命中可能发生在叶节点，也可能在非叶节点。

  如果当前节点为空，则表示没有找到。

• B 树的关键字集合分布在整棵树中，非叶节点和叶节点都存放数据

• B 树的搜索性能等价于在关键字全集内进行二分查找

B+ 树：

B+ 树是 B 树的变体。

使用链表存储数据时，查找数据缓慢。因此将链表数据分为若干段，将每段的索引节点保存为树。

数据链表












0
4
9
12
13
17
23
24
25
32
38
39
40
41
48
52
55
57
61
62
66
73
74
79
84
86
87
0, 32, 61
A - B - C
0, 12, 23
A - B - C
32, 40, 52
A - B - C
61, 73, 84
A - B - C

B+ 树具有如下特点：

• B+ 树的关键字都出现在叶节点的链表中，链表中数据是有序的。

  非叶节点只相当于叶节点的索引（稀疏索引），叶节点相当于是存储数据的数据层（稠密索引）。

• B+ 树的命中只可能发生在叶节点。

• B+ 树的搜索性能也等价于在关键字全集内进行二分查找

• B+ 树更适合文件索引系统

B* 树：

B* 树是 B+ 树的变体，其在非根、非叶节点间加入了兄弟指针。

索引相连
数据链表












0, 12, 23
A - B - C
32, 40, 52
A - B - C
61, 73, 84
A - B - C
0
4
9
12
13
17
23
24
25
32
38
39
40
41
48
52
55
57
61
62
66
73
74
79
84
86
87
0, 32, 61
A - B - C

B* 树具有以下特点：

• B* 树定义了非叶子节点关键字个数至少为 (2 / 3) * M。其块的最低使用率为 2 / 3，而 B+ 树最低使用率为 1 / 2
• B* 树分配新节点的概率更低，空间使用率更高

14.2.3 前缀树

前缀树（字典树、单词查找树、键树），是一种多路查找树。利用元素的公共前缀来减少查询时间。

下面是一个存储了数个单词（a、act、art、cat、can、cant、roin）的前缀树：

a
c
r
c
r
t
t
a
t
n
t
o
i
n

前缀树具有如下特点：

• 根节点不包含字符，除根节点外每一个节点包含一个字符。

• 节点的路径即为一条存储字符串。特别的，根节点表示空字符串

  每个节点持有一个计数器，计算该节点处存储的字符串数量。

• 所有的子节点都与父节点具有相同前缀。

• 在前缀树中，查询字符串的时间复杂度为 O(L)，其中 L 为字符串长度

实现前缀树：

class TrimTree {
    /* 节点类 */
    private static class Node {
        Map<Character, Node> next = null;
        int count = 0;
        Node() {
            this.next = new HashMap<>();
            this.count = 0;
        }
    }

    private Node root = null;		// 根节点

    /* 构造器 */
    public TrimTree(String... strings) {
        this.root = new Node();
        for (String s : strings) add(s);
    }
	
    /* 添加字符串 */
    public void add(String s) {
        Node p = root;
        for (char c : s.toCharArray()) {
            if (!p.next.containsKey(c)) p.next.put(c, new Node());
            p = p.next.get(c);
        }
        p.count++;
    }
	
    /* 查找字符串 */
    public int search(String s) {
        Node p = root;
        for (char c : s.toCharArray()) {
            if (!p.next.containsKey(c)) return 0;
            p = p.next.get(c);
        }
        return p.count;
    }
}

14.3 图

线性表局限于一个直接前驱和一个直接后继的关系。

树可能有数个直接后继，但只能有一个直接前驱（父节点）

当需要表示多对多关系时，就需要 图

图是一种数据结构。每个节点可以有零个或多个相邻元素。

两个节点间的连接称为 边（edge），节点也被称为 顶点（vertex）

图的分类：

• 按照 顶点间的连接有无方向 分为：有向图、无向图
• 按照 是否带权 分为：带权图（网）、非带权图
• 按照 表示方式 分为：二维数组表示（邻接矩阵）、链表表示（邻接表）

图的表示方式：

一组连接的节点：

1
0
2
3
4

邻接矩阵：

   0  1  2  3  4
0 ┌0, 1, 1, 1, 1┐
1 |1, 0, 1, 0, 0|
2 |1, 1, 0, 0, 0|
3 |1, 0, 0, 0, 0|
4 └1, 0, 0, 0, 0┘-

其中，(0, 1) == 1 表示 节点 0 与 节点 1 相连

邻接矩阵为每个顶点都分配了 n 个边的空间。这样，造成了空间的损失

邻接表：

0 [1]→[2]→[3]→[4]→
1 [0]→[2]→
2 [0]→[1]→
3 [0]→
4 [0]→-

邻接表为每个节点创建一个链表，链表中是与其相连的节点。邻接表由 数组 + 链表 组成

邻接表只关心存在的边，不关心不存在的边，因此没有空间浪费

14.3.1 深度优先搜索 DFS

深度优先搜索（Depth First Search），其策略是优先纵向挖掘深入，而不是对一个节点的所有节点先进行横向访问。

从初始访问节点出发，首先访问其第一个相邻节点。之后，从那个访问节点出发，递归访问第一个相邻节点。直到一个节点的路径完全访问结束后，才访问第二个节点。

步骤：

• 访问初始节点 s，标记其为已访问
• 从 s 的第一个相邻节点起，以递归方式对其进行深度优先搜索。
• 当前节点没有可访问的相邻节点时，就完成了对一条路径访问。此时才返回上一级，继续搜索下一节点。

14.3.2 广度优先搜索 BFS

广度优先搜索（Broad First Search），其策略是优先横向访问所有相邻节点，而不是对一条路径进行纵向挖掘。

从初始访问节点出发，记录所有相邻节点。之后，访问先前记录节点，并记录所有相邻节点。直到没有能访问的节点为止，就完成了对所有连接节点的搜索。

步骤：

• 记录初始节点 s
• 访问上一次记录的节点，将其标记为已访问。将那些节点的所有可访问的相邻节点记录。
• 重复上一步，直到没有可访问的节点时，就完成了对所有连接节点的访问。

附录

F1 实现赫夫曼编码/解码

/* 压缩数据包 */
class DataBox {
    public byte[] data;				// 压缩信息主体
    public Map<Byte, String> key;	// 赫夫曼表
    public int step;				// 补位数
}


class Huff {
    /* 将数据压缩，返回一个压缩包 */
    public static DataBox huff(byte[] data) {
        DataBox dataBox = new DataBox();
        dataBox.key = getHuffMap(data);						// 在压缩包内记录编码表
        dataBox.data = toHuff(data, dataBox);				// 在压缩包内记录压缩后数据，也会记录补位数
        return dataBox;
    }
	
    /* 根据要压缩的数据，计算那个赫夫曼表 */
    private static Map<Byte, String> getHuffMap(byte[] val) {
        if (val == null || val.length == 0) return new HashMap<>();
        Map<Byte, Node> huff = new HashMap<>();
        for (byte c : val) {								// 记录每个字符出现的次数
            if (huff.containsKey(c)) huff.get(c).times++;
            else huff.put(c, new Node(c, 1));
        }
        PriorityQueue<Node> pq = new PriorityQueue<>(huff.values());
        while (pq.size() > 1) {								// 生成赫夫曼树
            Node temp = new Node(pq.remove(), pq.remove());
            pq.add(temp);
        }
        Map<Byte, String> ret = new HashMap<>();
        update(ret, pq.remove(), "");						// 根据那个赫夫曼树，生成赫夫曼编码
        if (ret.size() == 1) ret.put(val[0], "0");			// 特别地，只有唯一字符从场合这样处理
        return ret;
    }
	
    /* 根据赫夫曼表，将数据压缩 */
    private static byte[] toHuff(byte[] val, DataBox d) {
        StringBuilder sb = new StringBuilder();
        for (byte c : val) {								// 得到压缩后的 bit 字符串
            sb.append(d.key.get(c));
        }
        byte[] ret = new byte[(sb.length() + 7) / 8];		// 压缩后的数据放在 byte 数组中
        d.step = sb.length() % 8;							// 记录那个补位数
        for (int i = 0; i < ret.length; i ++) {
            if (i >= ret.length - 1 && d.step != 0) {		// 最后一位可能有补位。那个场合，让有效数字在最左侧
                ret[i] = (byte) (Integer.parseInt(sb.substring(8 * i), 2) << (8 - d.step));
            } else ret[i] = (byte) Integer.parseInt(sb.substring(8 * i, 8 * i + 8), 2);
        }
        return ret;
    }
	
    /* 该方法能遍历赫夫曼树，以获取赫夫曼表 */
    private static void update(Map<Byte, String> ss, Node root, String s) {
        if (root == null) return;
        else if (root.right == null && root.left == null) {
            ss.put(root.val, s);									// 是叶节点的场合，记录这个编码值
        }
        if (root.left != null) update(ss, root.left, s + "0");		// 向左路径记为 0
        if (root.right != null) update(ss, root.right, s + "1");	// 向右路径记为 1
    }
    
    /* 解压压缩包 */
    public static byte[] antiHuff(DataBox d) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < d.data.length; i++) {					// 获取那个压缩数据的编码
            String temp = null;
            if (i >= d.data.length - 1 && d.step != 0) sb.append((temp = Integer.toBinaryString(d.data[i] | 256)), temp.length() - 8, temp.length() - 8 + d.step);				// 遍历到最后，要处理那个补位
            else sb.append((temp = Integer.toBinaryString(d.data[i] | 256)).substring(temp.length() - 8));
        }
        Map<String, Byte> anti = new HashMap<>();
        for (Byte aByte : d.key.keySet()) {							// 将编码表转化为解码表
            anti.put(d.key.get(aByte), aByte);
        }
        List<Byte> ret = new ArrayList<>();
        StringBuilder s = new StringBuilder();
        for (int i = 0; i < sb.length(); i++) {						// 按照解码表，把压缩编码转化为未解压编码
            s.append(sb.charAt(i));
            if (anti.containsKey(s.toString())) {
                ret.add(anti.get(s.toString()));
                s = new StringBuilder();
            }
        }
        byte[] bt = new byte[ret.size()];							// 将 Byte 数组转化为 byte 数组
        for (int i = 0; i < bt.length; i++) {
            bt[i] = ret.get(i);
        }
        return bt;
    }

	/* 节点类，是构建赫夫曼树时用到的类 */
    static class Node implements Comparable<Node> {
        public byte val;			// 代表的 byte 值
        public int times;			// 出现的次数
        public Node left;
        public Node right;

        public Node(Node l, Node r) {
            this.left = l;
            this.right = r;
            this.times = l.times + r.times;
        }

        public Node(byte val, int pow) {
            this.val = val;
            this.times = pow;
        }


        public Node(byte val) {
            this.val = val;
            this.times = 0;
        }

        @Override
        public int compareTo(Node o) {
            return this.times - o.times;
        }
    }
}

F2 实现平衡二叉树

class AVL{
    public Node root = null;				// 根节点
    
    /* 添加一个值（添加一个节点）
    	val：要添加的值 */
    public void add(int val) {
        Node toAdd = new Node(val);
        if (root == null) root = toAdd;
        else {
            Node par = root;
            Node temp = root;
            while (temp != null) {			// 确定其插入位置
                par = temp;
                if (val > temp.val) {
                    temp = temp.right;
                    toAdd.way = true;
                } else {
                    temp = temp.left;
                    toAdd.way = false;
                }
            }
            if (toAdd.way) {				// 将其插入到指定位置
                par.right = toAdd;
                par.right.parent = par;
            } else {
                par.left = toAdd;
                par.left.parent = par;
            }
            while (true) {					// 维护该平衡二叉树
                par = toAVL(par);
                if (par.parent == null) {
                    root = par;
                    break;
                } else {
                    if (par.way) par.parent.right = par;
                    else par.parent.left = par;
                    par = par.parent;
                }
            }
        }
    }
	
    /* 维护平衡二叉树
    	root: 待检查节点 */
    private static Node toAVL(Node root) {
        if (root == null) return null;
        int gap = root.rightHeight() - root.leftHeight();
        if (Math.abs(gap) > 1) {			// |gap| > 1 时，需要旋转
            if (gap > 0) {					// gap > 0 需要左旋，否则右旋
                if (root.right.leftHeight() > root.right.rightHeight()) root.right = roll(root.right, true);
                return roll(root, false);
            } else {
                if (root.left.rightHeight() > root.left.leftHeight()) root.left = roll(root.left, false);
                return roll(root, true);
            }
        } else return root;
    }

    /* 对该节点进行旋转。
    	root：待旋转节点
    	dirR：true 的场合右旋，否则左旋 */
    private static Node roll(Node root, boolean dirR) {
        Node temp = null;
        if (dirR) {
            temp = root.left;
            root.left = temp.right;
            if (temp.right != null) {
                temp.right.way = false;
                temp.right.parent = root;
            }
            temp.right = root;
        } else {
            temp = root.right;
            root.right = temp.left;
            if (temp.left != null) {
                temp.left.way = true;
                temp.left.parent = root;
            }
            temp.left = root;
        }
        temp.way = root.way;
        temp.parent = root.parent;
        root.way = dirR;
        root.parent = temp;
        return temp;
    }
    
    /* 一个展示树的方法。供 debug 用 */
    public static void show(Node root) {
        LinkedList<Node> a = new LinkedList<>();
        LinkedList<Node> b = new LinkedList<>();
        a.add(root);
        while (!a.isEmpty()) {
            Node temp = a.removeFirst();
            System.out.print(temp.val + " ");
            if (temp.left != null) b.add(temp.left);
            if (temp.right != null) b.add(temp.right);
            if (a.isEmpty()) {
                System.out.println();
                a = b;
                b = new LinkedList<>();
            }
        }
        System.out.println("共 " + count(root) + " 个节点");
    }
    
    /* 一个清点树中节点的方法 */
    public static int count(Node root) {
        if (root == null) return 0;
        return 1 + count(root.left) + count(root.right);
    }

    public static class Node {
        public int val;				// 值
        public Node left;			// 左节点
        public Node right;			// 右节点
        public Node parent;			// 父节点
        boolean way = false;        // false：该节点是左节点；true：是右节点

        public Node(int val) {
            this.val = val;
        }

        public int leftHeight() {	// 左子树高度
            return (left == null ? 0 : left.height());
        }

        public int rightHeight() {	// 右子树高度
            return (right == null ? 0 : right.height());
        }

        public int height() {		// 该节点树高度
            return Math.max(leftHeight(), rightHeight()) + 1;
        }
    }
}

16 多线程

16.1 线程的概念

对于一般程序而言，其结构大都可以分为一个入口、一个出口、一个顺次执行的语句序列。这样的语句结构称为进程，它是程序的一次动态执行，对应了代码加载、执行至完毕的全过程。

进程即是程序在处理机中的一次运行。在这样一个结构中不仅包含程序代码，也包括了系统资源的概念。

在单 CPU 计算机内部，微观上讲，同一时间只能有一个线程运行。实现多线程即从宏观上使多个作业同时执行。

程序：为完成特定任务，用某种语言编写的一组指令的集合。

进程：运行中的程序。当你运行一个程序，系统就会为该进程分配空间。进程是程序的一次执行过程。是一个动态过程：有其自身产生、存在、消亡的过程。

线程：由进程创建的，进程的一个实体。一个进程可以有多个线程。

单线程：同一时刻，只允许执行一个线程。

多线程：同一时刻，可以执行多个线程。

并发：同一时刻，多个任务交替执行，造成一种貌似并行的状态。单核 CPU 实现的多任务就是并发。

并行：同一时刻，多个任务同时进行。多核 CPU 可以实现并行。

16.1.1 线程的结构

在 Java 中，线程由以下 3 部分组成：

• 虚拟 CPU：封装在 java.lang.Thread 类中，控制着整个线程的运行
• 执行的代码：传递给 Thread 类，由其控制按序执行
• 处理的数据：传递给 Thread 类，是在代码执行过程中需要处理的数据

16.1.2 线程的状态

Java 的线程是通过包 java.lang 中定义的类 Thread 来实现的。当生成了一个 Thread 类后就产生了一个线程。通过该对象实例，可以启动线程、终止线程，或暂时挂起线程

线程共有 4 种状态：新建（New）、可运行（Runnable）、死亡（Dead）、阻塞（Blocked）

• 新建（New）：

  线程对象刚刚创建，还未启动（New）。此时还处于不可运行状态，但已有了相应内存空间及其他资源

• 可运行（Runnable）：

  此时线程已经启动，处于线程的 run() 方法中。这种情况下线程可能正在运行；也可能没有运行，但只要 CPU 空闲就会立刻运行。

  可以运行但没在运行的线程都排在一个队列中，这个队列称为就绪队列。

  可运行状态下，运行中的线程处于运行状态（Running），未运行线程处于就绪状态（Ready）。

  调用 start() 方法可以让线程进入可运行状态。

• 死亡（Dead）：

  线程死亡（Terminated）的原因有两个：一是 run() 方法最后一个语句执行完毕，二是线程遇到异常退出

• 阻塞（Blocked）：

  一个正常运行的线程因为特殊原因被暂停执行，就进入阻塞状态（Blocked）。

  阻塞时线程不能进入就绪对流排队，必须等到引起阻塞的原因消除，才能重新进入队列排队。

  引起阻塞的方法很多，sleep() 和 wait() 是两个常用的阻塞方法

• 中断线程：

  • void interrupt()：向一个线程发送一个中断请求，并把该线程的 interruptd 状态变为 true。

    中断阻塞线程的场合，会抛出 InterruptException 异常

  • static boolean interrupted()：检测当前线程是否被中断，并重置状态 interrupted 的值。

    连续调用该方法的场合，第二次调用会返回 false

  • boolean isInterrupted()：检测当前线程是否中断。不改变 interrupted 的值

16.2 线程的使用

在 Java 中线程使用有两种方法：

1. 继承 Thread 类，重写 run 方法

   public class Thread implements Runnable		//可见 Thread 也是实现了 Runable 接口

2. 实现 Runable 接口，重写 run 方法

16.2.1 继承 Thread 类

Thread 类是 Java 用于表示线程的类。那么，一个类被定义为其子类，则该类也能用来表示线程

public static void main(String[] args) {
 Type type = new Type();
 type.start();								//开始线程
 											//如果用 run 方法，则还是停留在主线程
 											//  那样，相当于 串行。执行完毕才继续
}
class Type extends Thread {						//先继承 Thread 类
 int i = 0;
 @Override
 public void run() {
     while (true) {
         System.out.println(i);
         try {
             Thread.sleep(100);				//休眠 100 毫秒
         } catch (InterruptedException e) {
             e.printStackTrace();
         }
         if (i++ == 10) {					//i = 10 时停止循环
             break;
         }
     }
 }
}

关于 start() 方法

public synchronized void start() {
	...
    start0();
}

private native void start0();					//start0 是 native。即，底层方法

1. start() 方法调用了一个 start0() 底层方法
2. start0() 是本地方法，由 JVM 调用，底层是 c/c++ 实现
3. 真正的多线程效果，是 start0()，而不是 run()
4. start() 方法调用 start0() 方法后，该线程不一定会立刻执行，只是将线程变成了可运行状态。具体何时运行，由 CPU 统一调度

16.2.2 实现 Runable 接口

Runnable 是 Java 用以实现线程的接口。从根本上将，任何实现线程的类都必须实现该接口。

public static void main(String[] args) {
 Runnable type = new Type();					//Runable 没有 start()方法
 Thread thread = new Thread(type);				//所以，这里使用了 静态代理
 thread.start();
}
class Type implements Runnable {				//这部分和 Thread 相似
 @Override
 public void run() {
     int i = 0;
     while (true){
         System.out.println(i << i);
         try {
             Thread.sleep(100);
         } catch (InterruptedException e) {
             e.printStackTrace();
         }
         if (++i > 15){
             break;
         }
     }
 }
}

关于 静态代理

class Thread implements Runable {}
	...	
	private Runnable target;
	...
 public Thread(Runnable target) {	//构造器
     init(null, target, "Thread-" + nextThreadNum(), 0);
     								//这句话可以先理解为 this.target = target;
 }
	...
 public void run() {
     if (target != null) {
         target.run();
     }
 }
	...
}

相当于，先创建了一个新线程，然后在新线程中调用 run 方法

16.2.3 继承 Thread 和 实现 Runable 的区别

1. 从 Java 设计来看，两者本质上没有区别。Thread 类本身就实现了 Runable 接口
2. 实现 Runable 接口的方式更加适合多个线程共享一个资源的情况，且避免了单继承的限制。建议使用。

16.2.4 线程中止

1. 当线程结束后，会自动退出

2. 还可以通过使用变量来控制 run 方法退出的方式来停止线程，即 通知方式。

   public void run() {
    while (active) {					//这个场合，只要外部控制 active 即可
        try {
            Thread.sleep(1);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        move();
    }
   }

16.2.5 线程常用方法

• setName(name)：设置线程名称，使之与参数 name 相同

• getName()：返回线程名称

• start()：线程开始执行。JVM 调用 start0 方法

  该方法会创建新的线程，新线程调用 run。

• run()：到下面玩跑步

  就是简单的方法调用，不会产生新线程。

• setPriority(int priority)：更改线程优先级

  getPriority()：获取线程优先级

  priority 范围：

  • MAX_PRIORITY：最高优先级（10）
  • MIN_PRIORITY：最低优先级（1）
  • NORM_PRIORITY：不高不低，真是好极了的优先级（5）

  每个线程都有一个优先级。Java 线程调度采用如下优先级策略：

  • 优先级高的先执行，优先级低的后执行
  • 每个线程创建时会被自动分配一个优先级。默认的场合，继承父类优先级
  • 任务紧急的线程，优先级较高
  • 同优先级线程按 “先进先出” 原则调度

• sleep(int millsecond)：让线程休眠指定的时间

  该方法是 Thread 类的静态方法，可以直接调用

• interrupt()：中断线程（不是 中止）

• yield()：线程的礼让。让出 CPU 让其他线程执行。因为礼让的时间不确定，所以不一定礼让成功。

  本质是 RUNNING 切换为 READY，即让当前线程放弃执行权

• wait()：导致当前线程等待

  直到其他线程调用此对象的 notify() 方法或 notifyAll() 方法才能唤醒此线程

  notify()、notifyAll()：唤醒因 wait() 阻塞的线程。

  这些方法（wait()、notify()、notifyAll()）只能在 synchrnized 方法或代码块中调用

• join()：线程的插队。插队的线程一旦插入成功，则必定先执行完插队线程的所有任务

  将导致其他线程的等待，直到 join() 方法的线程结束

  join(long timeout)：join，但是时间到后也能结束其他线程的等待

• isAlive()：测试当前线程是否在活动

• Thread.currentThread()：引用当前运行中的线程

16.2.6 用户线程和守护线程

• 用户线程：也叫工作线程。当线程任务执行完毕或通知方式结束

• 守护线程：一般是为工作线程服务的。当所有线程结束，守护线程自动结束

  常见的守护线程：垃圾回收机制

  Thread thraed = new Thread(bullet);
  thread.setDeamon(true);							//这样，子线程被设置为主线程的守护线程
  thread.start();

16.2.7 线程的生命周期

线程的状态有

• NEW：尚未启动

• RUNNABLE：在 JVM 中执行的线程

  可细分为 READY 和 RUNNING

• BLOCKED：被阻塞等待监视器锁定的线程

• WAITING：正等待另一个线程执行特定动作的线程

• TIMED_WAITING：正等待另一个线程执行特定动作达到等待时间的线程

• TERMINATED：已退出的线程

有一张重要的图，去 这里 查看吧

16.3 线程的互斥

在多线程编程，一些敏感数据不允许被多个线程同时访问。此时就用同步访问技术，保证数据在任意时刻，最多有一个线程同时访问，以保证数据的完整性。

也可以这样理解：线程同步，即当有一个线程对内存进行操作时，其他线程都不能对这个内存地址进行操作（被阻塞），直到该线程完成操作，再让下一线程进行操作。

16.3.1 互斥锁

在 Java 语言中，引入了 “对象互斥锁” 的概念，也称为监视器，来保证共享数据操作的完整性

每个对象都对应一个可称为 “互斥锁” 的标记，这个标记用来保证在任一时刻都只能有一个线程访问对象。

Java 语言中，有 2 种方式实现互斥锁：

• 用关键字 volatile 声明一个共享数据（变量）。一般很少使用该关键字
• 用关键字 synchronized 声明共享数据的一个方法或一个代码

同步的局限性：导致程序的执行效率要降低。

非静态的对象，同步方法的锁可以是 this，也可以是其他对象（要求是同一对象）

静态对象，同步方法的锁为当前类本身

1. 同步代码块

   synchronized (对象) {		//得到对象的锁，才能操作同步代码
   	需要被同步代码;
   }

   在第一个线程持有锁定标记时，如果另一个线程企图执行该代码块语句，将从对象中索取锁定标记。

   因为此时该标记不可得，古该线程不能继续执行，而是加入等待队列。

   程序运行完 synchronized 代码块后，锁定标记会被自动返还。即使该同步代码块执行过程中抛出异常也是如此。一个线程多次调用该同步代码块的场合，也会在最外层执行完毕后正确返还。

2. 放在方法声明中，表示整个方法为同步方法

   因为 synchronized 语句的参数必须是 this，因此允许下面这种简洁的写法：

   public synchronized void method(){
   	代码;
   }

16.3.2 线程死锁

多个线程都占用了对方的资源，不肯相让，就导致了死锁。编程时要避免死锁的产生。

• 以下操作会释放锁

  1. 当前线程的同步方法、同步代码块执行结束。
  2. 当前线程在同步方法、同步代码块中遇到 break、return
  3. 当前线程在同步方法、同步代码块中出现了未处理的 Error
  4. 当前线程在同步方法、同步代码块中执行了 wait() 方法，当前线程暂停，并释放锁

• 以下操作不会释放锁

  1. 执行同步方法、同步代码块时，程序调用 Thread.sleep() 或 Thread.yield() 方法暂停当前线程的执行，不会释放锁

  2. 线程执行同步代码块时，其他线程调用了该线程的 suspend() 方法将该线程挂起，该线程不会释放锁

     所以，应尽量避免使用 suspend() 和 resume() 来控制线程

16.4 线程的同步

Java 中，可以使用 wait()、notify()、notifyAll() 来协调线程间的运行速度关系。这些方法都被定义在 java.lang.Object 中

Java 中的每个对象实例都有两个线程队列和它相连。一个用以实现等待锁定标志的线程，另一个用来实现 wait() 和 notify() 的交互机制

• wait()：让当前线程释放所有其持有的 “对象互斥锁”，进入等待队列

• notify()、notifyAll()：唤醒一个或所有在等待队列中等待的线程，并将他们移入同一个等待 “对象互斥锁” 的队列。

  执行这些方法时如果没有等待中的线程，则其不会生效，也不会被保留到以后再生效

synchronized (key) {
    if (key.value == 0) key.wait();
    key.value--;
}
synchronized (key) {
    key.value++;
    key.nitifyAll();
}

因为调用这些方法时必须持有对象的 “对象互斥锁”，所以上述方法只能在 synhronized 方法或代码块中执行。

17 IO流

17.1 文件

文件就是保存数据的地方。

文件流：文件 在 程序 中是以 流 的形式来操作的。

流：数据在数据源（文件）和程序（内存）之间经历的路径

输入流：数据从数据源到程序的路径

输出流：数据从程序到数据源的路径

17.1.1 常用的文件操作

Java 提供了 File 类，用于处理文件相关的操作

1. 创建文件对象相关构造器和方法

   • new File(String pathname)：根据路径创建一个 File 对象

     String path1 = "d:/test.jpg";
     String path2 = "d:\\test.jpg";
     File file1 = new File(path1);
     File file2 = new File(path2);			//此时只是在内存中产生了一个对象

   • new File(File parent, String child)：根据父目录文件 + 子路径构建

     File parentFile1 = new File("d:\\");
     String fileName1 = "test.txt";
     File file3 = new File(parentFile1, fileName1);

   • new File(String parent, String child)：根据父路径 + 子路径构建

   • creatNewFile()：创建新文件

     try {
      file.createNewFile();				//这个场合，内存对象才写入磁盘
     } catch (IOException e) {
      e.printStackTrace();
     }

2. 获取文件相关信息

   • getName()：获取名称

   • getAbsolutePath()：获取文件绝对路径

   • getParent()：获取文件父级目录

   • long length()：获取文件大小（字节）

   • exists()：文件是否存在

   • isFile()：是不是一个文件

   • isDirectory()：是不是一个目录

   • isAbsolute()：是不是绝对路径

   • canRead()：是否可读

     canWirte()：是否可写

   • long lastModified()：最后修改时间

   • String[] list()：列出符合模式的文件名

3. 目录的操作和文件删除

   • mkdir：创建一级目录
   • mkdirs：创建多级目录
   • delete：删除空目录或文件
   • boolean renameTo(File newName)：更改文件名

   其实目录（在内存看来）就是特殊的文件

注意事项：

• File 类可以获取文件的各种相关属性，可以对其进行改名，甚至删除。但除了文件名外的属性没有修改方法
• File 类可以用来描述一个目录，但不能改变目录名，也不能删除目录

17.2 IO流

1. I / O 是 Input / Output 的缩写。IO 技术是非常实用的技术，用于处理数据传输。如 读 / 写 文件，网络通讯等。
2. Java 程序中，对于数据的 输入 / 输出 操作以 “流（stream）”的方式进行
3. java.io 包下提供了各种 “流” 类和接口，用以获取不同种类的数据，并通过方法输入或输出数据
4. 输入（input）：读取外部数据（磁盘、光盘、网络数据等）到程序（内存）中
5. 输出（output）：将程序（内存）数据输出到外部存储

17.2.1 IO流的分类

• 按操作数据单位不同分为：

  • 字节流（8 bit）：二进制文件用该方法，能确保文件无损
  • 字符流（按照字符，字符的字节数由编码决定）：文本文件，效率更高

• 按数据流的流向不同分为：

  • 输入流：读取外部数据（磁盘、光盘、网络数据等）到程序（内存）中
  • 输出流：将程序（内存）数据输出到外部存储

• 按流的角色不同分为：

  • 节点流
  • 处理流 / 包装流

  Σ(っ °Д °;)っ	字节流	字符流
  输入流	InputStream	Reader
  输出流	OutputStream	Writer

Java 的 IO流 总共涉及 40多个类，实际上都是上述 4 类的抽象基类派生的

由这 4 个类派生的子类名称都是以其父类名作为子类名后缀

17.2.2 IO流 常用类

17.2.2.1 FileInputStream：文件字节输入流

• 构造器：

  new FileInputStream(File file);				//通过一个 File 的路径指定创建
  new FileInputStream(String path);			//通过一个路径指定创建
  new FileInputStream(FileDescriptor fdObj);	//通过文件描述符创建

• 方法：

  • available()：返回目前可以从流中读取的字节数

    实际操作时，读取的字节数可能大于这个返回值

  • close()：关闭文件输入流，释放资源

  • finalize()：确保在不引用文件输入流时调用其 close() 方法

  • getChannel()：返回与此流有关的唯一的 FileChannel 对象

  • getFD()：返回描述符

  • read()：从该输入流中读取一个数据字节

    如果没有输入可用，该方法会被阻止。返回 -1 的场合，说明到达文件的末尾。

    File file = new File("d:\\test");
    FileInputStream fileInputStream = null;
    int read;
    try {
     fileInputStream = new FileInputStream(file);
     while ((read = fileInputStream.read()) != -1){
         System.out.print((char) read);
     }
    } catch (IOException e) {
     e.printStackTrace();
    } finally {
     try {
         fileInputStream.close();
     } catch (IOException e) {
         e.printStackTrace();
     }
    }										//真 TM 复杂。throw 了算了

    这个场合，效率较低

    read(byte[] b)：从该输入流中把最多 b.length 个字节的数据读入一个 byte 数组

    读取正常的场合，返回实际读取的字节数。

    ...
    byte[] b = new byte[8];					//一次读取 8 字节
    try {
     fileInputStream = new FileInputStream(file);
     while ((read = fileInputStream.read(b)) != -1){
         System.out.print(new String(b, 0, read));
         								//这一句看不懂请看[12.2 - 4]
     }
    catch 
    ...
    finally
    ...

    read(byte[] b, int off, int len)：从该输入流中读取 len 字节数据，从数组下标 off 处起写入

  • skip(long n)：从该输入流中跳过并去丢弃 n 个字节的数据

  • mark(int markArea)：标记数据量的当前位置，并划出一个缓冲区。缓冲区大小至少为 markArea

    reset()：将输入流重新定位到对此流最后调用 mark() 方法时的位置

    markSupported()：测试数据流是否支持 mark() 和 reset() 操作

17.2.2.2 FileOutputStream：文件字节输出流

• 构造器：

  new FileOutputStream(File file);			//通过一个 File 的路径指定创建
  new FileOutputStream(File file, boolean append);			
  							//append = false，写入采用 覆盖原文件 方式
  							//append = true 的场合，写入采用 末尾追加 方式
  new FileOutputStream(String path);			//通过一个路径指定创建
  new FileOutputStream(String path, boolean append);			
  new FileOutputStream(FileDescriptor fdObj);	//通过文件描述符创建

• 方法：

  • close()：关闭文件输入流，释放资源

  • flush()：刷新此输出流并强制写出所有缓冲的输出字节

  • finalize()：确保在不引用文件输入流时调用其 close() 方法

  • getChannel()：返回与此流有关的唯一的 FileChannel 对象

  • getFD()：返回描述符

  • write(byte[] b)：将 b.length 个字节从指定 byte 数组写入此文件输出流

    File file = new File("d:\\test1");
    FileOutputStream fileOutputStream = null;
    try {
     fileOutputStream = new FileOutputStream(file);
     									//此时，若文件不存在会被创建
     fileOutputStream.write('a');
     String str = "Melody";
     fileOutputStream.write(str.getBytes());
    } 
    catch
    ...
    finally
    ...

    write(byte[] b， int off, int len)：将指定 byte 数组中下标 off 开始的 len 个字节写入此文件输出流

    write(int b)：将指定字节写入此文件输出流

17.2.2.3 FileReader：文件字符输入流

与其他程序设计语言使用 ASCII 码不同，Java 使用 Unicode 码表示字符串和字符。ASCII 码的字符占用 1 字节，可以认为一个字符就是一个字节。但 Unicode 码用 2 字节表示 1 个字符，此时字符流和字节流就不相同。

• 构造器：

  new FileRaeder(File file);
  new FileRaeder(String string);

• 方法：

  • read()：读取单个字符。
  • read(char[])：批量读取多个字符到数组。

17.2.2.3 FileWriter：文件字符输出流

• 构造器：

  new FileWriter(File path);
  new FileWriter(String path2);
  new FileWriter(File path3, boolean append);
  new FileWriter(String path4, boolean append);

• 方法：

  • write(int)：写入单个字符
  • write(char[])：写入指定数组
  • write(char[], off, len)：写入指定数组的指定部分
  • write(string)：写入字符串
  • write(string, off, len)：写入字符串的指定部分
  • flush()：刷新该流的缓冲。如果没有执行，内容就不会写入文件
  • close()：等于 flush() + 关闭

  注意！FileWriter 使用后，必须关闭（close）或刷新（flush），否则无法真正写入

17.2.2.4 转换流 InputStreamReader 和 OutputStreamWriter

1. InputStreamReader 是 Reader 的子类。可以把 InputStream（字节流）转换成 Reader（字符流）
2. OutputStreamWriter 是 Writer 的子类。可以把 OutputStream（字节流）转换成 Writer（字符流）
3. 处理纯文本数据时，如果使用字符流效率更高，并能有效解决中文问题，建议将字节流转换成字符流。
4. 可以在使用时指定编码格式（UTF -8、GBK 等）

• 构造器

  InputStreamReader isr = new InputStreamReader(fileInputStream, "UTF-8");
  										//传入 字节流 和 编码类型
  BufferedReader br = new Bufferedreader(isr);
  										//用另一个处理流包装

17.2.3 节点流和处理流

1. 节点流：从一个特定数据源读写数据。
2. 处理流（包装流）：是 “连接” 在已存在的流（节点流或处理流）上，为程序提供更强大的读写功能。

节点流和处理流的区别和联系

1. 节点流是 底层流 / 低级流。直接和数据源相接。
2. 处理流（包装流）包装节点流，既可以消除不同节点流的实现差异，也可以提供更方便的方法完成输入输出
3. 处理流对节点流进行包装，使用了修饰器设计模式。不会直接与数据源相连
4. 处理流的功能主要体现在
   • 性能的提高：以增加缓冲的方式提高输入输出的效率
   • 操作的便捷：处理流可能提供了一系列便捷方法来一次性输入大量数据，使用更加灵活方便
5. 关闭时关闭外层流即可

17.2.3.1 缓冲区流

缓冲区流是一种包装流。缓冲区字节流有 BufferedInputStream 和 BufferedOutputStream；缓冲区字符流有 BufferedWriter 和 BufferedReader。他们是在数据流上加了一个缓冲区。读写数据时，数据以块为单位进入缓冲区，其后的读写操作则作用于缓冲区。

这种方式能降低不同硬件设备间的速度差异，提高 I/O 效率。

构造器：

new BufferedReader(reader);					//传入一个 Reader
new BufferedReader(reader, 1024);			//传入 Reader 并指定缓冲区大小
new BufferedWriter(writer);					//传入一个 Writer
new BufferedWriter(writer, 1024);			//传入 Writer 并指定缓冲区大小
											//追加还是覆盖，取决于 writer

方法：

• bufferedReader.readLine()：按行读取（不含换行符）。

  会返回一个字符串。返回 null 时，表示读取完毕。

  String line;
  while (line = bufferedReader.readLine() != null){
   ...
  }
  bufferedReader.close();

• bufferedWriter.write(String str)：插入字符串

• bufferedWriter.newLine()：插入一个（和系统相关的）换行

17.2.3.2 数据数据流

除了字节或字节数组外，处理的数据还有其他类型。为解决此问题，可以使用 DataInputStream 和 DataOutputStream。它们允许通过数据流来读写 Java 基本类型，如布尔型（boolean）、浮点型（float）等

构造器：

new DataInputStream(inputStream);
new DataOutputStream(outputStream);

方法：

• byte readByte()：读取下一个 byte

  int readInt()、double readDouble()、String readUTF()……

• void writeByte(byte b)：写入一个 byte

  void writeInt(int n)、void writeUTF(String str)……

  虽然有对字符串的读写方法，但应避免使用这些方法，转而使用字符输入/输出流。

17.2.3.3 对象流

当我们保存数据时，同时也把 数据类型 或 对象 保存。

以上要求，就是能够将 基本数据类型 或 对象 进行 序列化·反序列化 操作

序列化和反序列化

1. 把对象转成字符序列的过程称为序列化。保存数据时，保存数据的值和数据类型
2. 把字符序列转成对象的过程称为反序列化。恢复数据时，恢复数据的值和数据类型
3. 需要让某个对象支持序列化机制，则必须让其类是 可序列化的。由此，该类必须实现下列接口之一
   • Serializable：推荐。因为是标记接口，没有方法
   • Externalizable：该接口有方法需要实现

transient 关键字

1. 有一些对象状态不具有可持久性（如 Thread 对象或流对象），这样的成员变量必须用 transient 关键字标明。任何标有 transient 关键字的成员变量都不会被保存。
2. 一些需要保密的数据，不应保存在永久介质中。为保证安全，这些变量前应加上 transient 关键字。

• 构造器：

  new ObjectInputStream(InputStream inputStream);
  new ObjectOutputStream(OutputStream outputStream);

• 方法：

  反序列化顺序需要和序列化顺序一致，否则出现异常。

  • writeInt(Integer)：写入一个 int

    readInt()：读取一个 int

  • writeBoolean(Boolaen)：写入一个 boolean

    readBoolean()：读取一个 boolean

  • writeChar(Character)：写入一个 char

    readChar()：读取一个 char

  • writeDouble(Double)：写入一个 double

    readDouble()：读取一个 double

  • writeUTF(String)：写入一个 String

    readUTF()：读取一个 String

  • writeObject(Serializable)：写入一个 Obj

    readObject()：读取一个 Obj

    读取的场合，如果想要调用方法，需要向下转型。

    为此，需要该类其引入，或将类的定义拷贝到可以引用的位置。

• 注意事项

  1. 读写顺序要一致

  2. 实现序列化或反序列化的对象，要实现 Serializable 或 Externalizable 接口

  3. 序列化的类中建议添加 SerialVersionUID 以提高版本兼容性

     private static final long serialVersionUID = 1L;

     有此序列号的场合，后续修改该类，系统会认为只是版本修改，而非新的类

  4. 序列化对象时，默认将其中所有属性进行序列化（除了 static 和 tansient 修饰的成员）

  5. 序列化对象时，要求其属性也实现序列化接口

  6. 序列化具备可继承性。某类若实现可序列化，则其子类也可序列化

17.2.3.4 标准输入 / 输出流

Σ( ° △ °lll）	编译类型	运行类型	默认设备
System.in：标准输入	InputStream	BufferedInputStream	键盘
System.out：标准输出	PaintStream	PaintStream	显示器

17.2.3.5 打印流 PaintStream 和 PaintWriter

打印流只有输出流，没有输入流

1. PaintStream 是 OutputStream 的子类。PaintWriter 是 Writer 的子类。

2. 默认情况下，System.out 输出位置是 标准输出（即：显示器）

   修改默认输出位置：

   System.setOut(new PrintStream(path));

17.2.3.6 Properties 类

1. Properties 是专门用于读写配置文件的集合类

   底层维护了一个 Entry 数组

2. 配置文件格式：

   键=值
   键=值
   …ABNF

   注意：键值对不需要空格，值不需要引号（值默认 String）

3. 常见方法：

   • load(InputStream)

     load(Reader)：加载配置文件的键值对到 Properties 对象

     Properties properties = new Properties();
     properties.load(new FileReader("d:\\data.data"));

   • list(PaintStream)

     list(PaintWriter)：将数据显示到指定设备

     properties.list(System.out);			//在控制台显示

   • getProperty(key)：根据键获取值

     properties.get("IQ");

   • setProperty(key, value)：设置键值对到 Properties 对象

     如果没有该 key，就是创建。如有，就是替换。

     properties.set("IQ", 0);
     properties.set("Balance", 0);

   • store(Writer, String)

     store(OutputStream, String)：把 Properties 中的键值对存储到配置文件。

     后面的 String 是注释。如有，会被用 # 标记并写在文件最上方。注释可以为 null。

     IDEA 中，如果含有中文，会储存为 unicode 码

     查询 unicode 码

17.2.3.7 随机访问文件

程序阅读文件时不仅要从头读到尾，还要实现每次在不同位置进行读取。此时可以使用 RandomAccessFile

构造器：

new RandomAccessFile(String name, String mode);		//通过文件名
new RandomAccessFile(File file, String mode);		//通过文件对象

参数 mode 决定以只读方式 mode = "r" 还是读写方式 mode = "rw" 访问文件。

方法：

• long getFilePointer()：返回文档指针的当前位置

• void seek(long pos)：将文档指针置于指定的绝对位置 pos

  文档指针的位置从文档开始的字符处开始计算，pos = 0L 表示文档的开始

• long length()：返回文件长度

18 项目：坦克大战

还有很多细节、优化方法没实现，但困难的已经没有了。

先不打磨了，还是以学习 Java 为主。

二阶段毕业

关于 数量 的注释可能不对。那些注释是早些时候添加的。后来添加了新功能，这些注释没有及时更新

TankGame.java：程序的入口

MyPanel.java：窗口、图像的绘制。这是该项目的主干

Player.java、Enemy.java：己方、敌方的坦克类。Tank.java 是他们的父类

Vehicle.java：记录了所有坦克预设的枚举类。该包下还有另一个记录了所有子弹类型的枚举类 Bullet

Map.java：记录了地图数据的枚举类，包含不同关卡。但我没设计关卡

InputImage.java：所有导入的图片。是我准备的素材

Timing.java：一个计时器。当时能力有限，用这个作为某个计时功能的代替方案

• TankGame.java（入口）

  package com.melody.tank_game;
  
  import javax.swing.*;
  import java.io.*;
  import java.util.Scanner;
  
  /**
   * @author Melody
   * @version 1.0.ష
   * <p>
   * 小派蒙会开坦克吗？
   * <p>
   * ⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⠴⠒⠛⠲⡄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀
   * ⠀⠀⠀⠀   ⠀⢻⡄⣠⠶⣆⠀⣸⣀⣀⠀⠀
   * ⠀⠀⠀ ⠀⠀⢀⡠⠬⠛⢓⣏⠉⣾⣉⣀⠉⢹⡀⠀⠀⠀⠀⠀⠀⠀
   * ⠀⠀ ⠀⢀⡖⠋⣠⠴⠛⠙⢹⠞⢳⢀⣨⡵⠚⠀⠀⠀
   * ⠀⠀⠀⣰⠋⡠⠎⠁⣀⠤⠒⠚⠛⠙⠒⠳⠤⣄⡀⠀
   * ⠀⠀⠀⠘⠐⢼⠖⠋⠀⠀⢀⠀⠀⠀⠀⠀⠀⠘⣌⡒⠲⢹⠀⠀⠀⠀
   * ⠀⠀ ⠀⡸⠁⠀⠀⠀⠀⡆⠀⠀⠐⠀⠢⣄⠀⡽⡙⡲⠑⠒⠒⡒⠁
   * ⢀⡠⠴⠚⠀⠀⠀⠀⠀⣕⠝⣄⡀⢀⠀⠀⡇⠵⢍⠚⢾⡀⢠⠖⠁⠀       ___________________
   * ⠈⠦⣄⣀⠀⡔⠀⠀⢁⡞⠀⠉⠲⣄⡀⢲⢼⠀⢀⠳⡄⠁⠀⢣⠀⠀     /  坦克？是新游戏喔。   \
   * ⠀⠀⣠⠃⢐⠄⠀⠀⠴⠅⠠⡊⡢⠀⠉⠉⠁⠀⢆⠕⠹⡀⠀⠈⡆⠀  <   开玩笑，我超勇的好不好   \
   * ⠀⠠⡇⠀⡸⠀⠀⠀⠨⡅⠀⠒⠈⠀⢄⠠⠠⠔⠀⠀⠀⢻⠀⠀⢣⠀     \     我超会玩的啦 ~     /
   * ⠀⢸⠅⠀⡕⠀⠀⠀⠀⣇⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⡤⡏⠀⠀⢸⠀       \____________________/
   * ⠀⠈⡇⠀⣣⠀⠀⠈⠀⠸⡦⠴⠲⢚⢚⠙⠝⠙⠍⠝⣱⠏⢠⠀⢸⠅
   * ⠀⠀⠙⣆⠘⣄⠀⠠⣄⠀⠹⣌⠌⠀⠂⠐⢈⠄⡁⢌⠳⣺⠏⢀⡞⠀
   * ⠀⠀⠀⠀⠙⠺⠛⣲⠜⠟⡓⡚⣏⣔⡀⡌⣀⢂⣔⠴⠋⢏⠒⠁⠀⠀
   * <p>
   * 什么新游戏，比游戏还刺激！还可以教你 学 Ja va 哦 ~
   */
  
  public class TankGame extends JFrame {
  
      public static MyPanel mp;
      public static Thread thread;
      public static File savePath = new File("d:\\Program\\Melody\\TankGame\\saveData.sav");
      public boolean abandoned;
  
      public static void main(String[] args) {
          int width = 1200;
          int height = 800;
          int enemyNum = 5;
          Scanner scanner = new Scanner(System.in);
          char inpChar = ' ';
          mp = new MyPanel(width, height, enemyNum);
          if (savePath.isFile()) {
              System.out.println("开始新游戏？（Y新游戏/N读档）");
              while (true) {
                  inpChar = scanner.next().charAt(0);
                  try {
                      if (inpChar == 'Y' || inpChar == 'y') {
                          break;
                      } else if (inpChar == 'N' || inpChar == 'n') {
                          mp.pause = true;
                          mp.toLoad = true;
                      } else {
                          throw new RuntimeException();
                      }
                      break;
                  } catch (Exception e) {
                      System.out.println("错误！请重新输入（Y新游戏/N读档）");
                  }
              }
          }
          TankGame game = new TankGame(Math.abs(width), Math.abs(height), Math.abs(enemyNum));
          thread = new Thread(game.mp);
          thread.start();
      }
  
      public TankGame(int width, int height, int enemyNum) {
          width = Math.max(width, 800);
          height = Math.max(height, 600);
          this.add(mp);
          this.setSize(width + 20, height + 240);
          this.addKeyListener(mp);
          this.setVisible(true);
          this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
      }
  
  }

• MyPanel.java

  package com.melody.tank_game;
  
  import javax.swing.*;
  import java.awt.*;
  import java.awt.event.KeyEvent;
  import java.awt.event.KeyListener;
  import java.io.*;
  import java.util.Iterator;
  import java.util.LinkedHashMap;
  import java.util.Vector;
  
  /**
   * @author Melody
   * @version 1.0
   * ！！！！！！！！！！！！！！！该类需要重新整理！！！！！！！！！！！！！！！！
   */
  class MyPanel extends JPanel implements KeyListener, Runnable, Serializable {
      //5 个静态变量依次是：允许的同屏最大敌人数量的上限、战斗区域宽度、战斗区域高度、玩家、是否通关
      private static final int ENEMY_MAX = 20;
      public static int width = 1200;
      public static int height = 1000;
      private static Player player = new Player(640, 640);
      public static boolean gameSuspend = false;
      public static int[][][] mapData = new int[width][height][2];                        //*****此处需要修改*****
      private static final long serialVersionUID = 1L;
  
  
      //12 个成员变量，依次是：所有敌人坦克、所有被摧毁的敌人坦克、同屏最大敌人数量（用户设定）、敌人初始位置集（含坐标、占用情况）、
      //          敌人初始位置集（仅坐标）、关卡敌人总数、W键是否正被按下、A键是否正被按下、S键是否正被按下、D键是否正被按下、开火键是否正被按下、
      //          导入图片媒介、地图集、关卡数
      private Vector<Tank> enemy = new Vector<>();
      private Vector<Tank> deadEnemy = new Vector<>();
      private int enemyMax;
      private LinkedHashMap<int[], Boolean> enemyPositions = new LinkedHashMap<>();
      private int[][] enemyPosition;
      private transient boolean isPressingW = false;
      private transient boolean isPressingA = false;
      private transient boolean isPressingS = false;
      private transient boolean isPressingD = false;
      private transient boolean isFiring = false;
      private transient Image image = null;
      private Map[] maps = Map.values();
      private int level = -1;
      private Tank boss;
      private boolean bossActive = false;
      boolean pause = false;
      transient boolean saved = false;
      boolean loaded = false;
      transient boolean toLoad = false;
      private transient boolean toSave = false;
      transient boolean abandoned = false;
  
      //构造器
      public MyPanel(int width, int height, int enemyNum) {
          this.width = (int) (width / 40) * 40;
          this.height = (int) (height / 40) * 40;               //设置长宽
          enemyNum = Math.max(enemyNum, 0);
          enemyMax = Math.min(enemyNum, ENEMY_MAX);           //设置同屏最大敌人数量
          enemyPosition = new int[enemyMax][2];                //已经确定了要生成的敌人位置数量，生成位置数组（空）
          for (int i = 0; i < enemyMax; i++) {                //生成敌人初始位置。
              int[] tempPosition = new int[2];
              tempPosition[0] = i * 150 + 50;
              tempPosition[1] = 50;
              while (tempPosition[0] > (width - 100)) {
                  tempPosition[1] += 120;
                  tempPosition[0] -= (width - 150);
                  if (tempPosition[1] > height - 100) {
                      throw new RuntimeException();
                  }
              }
              enemyPosition[i][0] = tempPosition[0];
              enemyPosition[i][1] = tempPosition[1];
          }                                                    //此时 敌人初始位置数组 生成完毕。
          int n = 0;
          for (int[] ints : enemyPosition) {
              enemyPositions.put(ints, false);                 //装满 敌人初始位置集 默认全部是未占用
          }
  
      }
  
  
      @Override
      public void run() {
          nextLevel();
          player.start();             //启动玩家线程
          while (!abandoned) {
              creatEnemy();
              gameSuspend = false;//创建敌人坦克。这个方法同时会启动敌人坦克线程
              while (!gameSuspend) {
                  repaint();              //刷新
                  checkLevelClear();
                  if(toSave){
                      saveData();
                      toSave  = false;
                  } else if(toLoad){
                      loadData();
                      toLoad  = false;
                  }
              }
              pauseBetweenLevels(1200 + (bossActive ? 2000 : 0));
              while (!gameSuspend) {
                  repaint();
              }
              nextLevel();
          }
      }
  
  
      @Override
      public void paint(Graphics g) {
          drawUI(g);                      //画出 UI
          drawPlayer(g);                  //画出 玩家坦克（包含子弹）
          drawEnemy(g);                   //画出 所有敌人坦克（包含子弹）
          drawDeadTank(g);                //画出 被破坏坦克的残留动画和残留子弹
      }
  
      //画出 UI
      private void drawUI(Graphics g) {
          g.setColor(Color.BLACK);
          g.fillRect(0, 0, width, height);
          g.setColor(Color.GRAY);
          g.fillRect(2, 2, width - 4, height - 4);        //以上 4 行，画出了战斗场地
          g.setColor(Color.WHITE);
          g.fillRect(0, height, width, 200);
          drawHp(g);                                                      //画 HP 槽
          drawFireCD(g);                                                  //画 开火 槽
          drawEnemyNum(g);                                                //画 雷达 槽
          drawStars(g);                                                   //画 经验值 星星
          if (pause) {
              drawPause(g);
          }
      }
  
      //画 HP 槽
      private void drawHp(Graphics g) {
          //下面画出 绿色 HP 槽。随着 HP 减少，槽会变空
          g.setFont(new Font("等线", Font.ITALIC + Font.BOLD, 50));
          g.setColor(Color.BLACK);
          g.fillRect(50, height + 60, (int) (20 * player.vehicle.LIFE) + 4, 30);
          g.setColor(player.lifeRemains / player.vehicle.LIFE > 0.2 ? Color.GREEN : Color.RED);
          g.fill3DRect(52, height + 62, (int) (20 * Math.max(player.lifeRemains, 0)), 26, true);
          g.fill3DRect(52, height + 80, (int) (20 * Math.max(player.lifeRemains, 0) - 1), 6, false);
          //下面画出一段说明文
          g.setColor(Color.GRAY);
          if (player.vehicle == Vehicle.Basic) {
              g.drawString("防弹衣", 50, height + 140);
          } else {
              g.drawString(player.vehicle == Vehicle.Tank_Special ? "复合装甲" : "装甲", 50, height + 140);
          }
      }
  
      //画 开火 槽
      private void drawFireCD(Graphics g) {
          //以下画出 橙色 开火槽。随着装弹，槽会填满
          g.setFont(new Font("等线", Font.ITALIC + Font.BOLD, 50));
          g.setColor(Color.BLACK);
          g.fillRect((int) ((width / 2) + 60), height + 60, 205, 30);
          g.setColor(player.vehicle == Vehicle.Tank_Special ? Color.cyan : Color.ORANGE);
          g.fill3DRect((int) ((width / 2) + 62), height + 62,
                  (int) (player.getAtkSpeed() * (player.fireCD - Math.max(player.fireCount, 0)) + 1), 26, true);
          g.fill3DRect((int) ((width / 2) + 62), height + 80,
                  (int) (player.getAtkSpeed() * (player.fireCD - Math.max(player.fireCount, 0))), 6, false);
          //以下画出一段说明文字
          g.setColor(Color.GRAY);
          if (player.vehicle == Vehicle.Basic) {
              g.drawString(player.fireCount <= 10 ? "哒哒哒哒哒……" : player.fireCount == player.fireCD ? "加特林停了" : "加特林转啊！",
                      width / 2 + 60, height + 140);
          } else {
              g.drawString(player.fireCount <= 0 ? "弹药装填完毕" : "装填中…", width / 2 + 60, height + 140);
          }
      }
  
      //画出 敌人数量（这个方法是UI的一部分，统计数量，而不是画坦克）
      private void drawEnemyNum(Graphics g) {
          g.setFont(new Font("等线", Font.ITALIC + Font.BOLD, 20));
          g.setColor(Color.BLACK);
          g.drawString("雷达发现敌人数量：" + (maps[level].levelEnemyNum - deadEnemy.size()), (int) (width * 0.77), height + 22);
      }
  
      //画出 经验值。有几点就有几颗红星被点亮。
      private void drawStars(Graphics g) {
          switch (player.vehicle.LEVEL_UP_REQUIRED) {
              case 10:
                  g.drawImage(player.enhance >= 10 ? InputImage.star : InputImage.nStar,
                          280, height + 10, 30, 30, this);
                  g.drawImage(player.enhance >= 9 ? InputImage.star : InputImage.nStar,
                          250, height + 10, 30, 30, this);
                  g.drawImage(player.enhance >= 8 ? InputImage.star : InputImage.nStar,
                          220, height + 10, 30, 30, this);
                  g.drawImage(player.enhance >= 7 ? InputImage.star : InputImage.nStar,
                          190, height + 10, 30, 30, this);
                  g.drawImage(player.enhance >= 6 ? InputImage.star : InputImage.nStar,
                          160, height + 10, 30, 30, this);
              case 5:
                  g.drawImage(player.enhance >= 5 ? InputImage.star : InputImage.nStar,
                          130, height + 10, 30, 30, this);
              case 4:
                  g.drawImage(player.enhance >= 4 ? InputImage.star : InputImage.nStar,
                          100, height + 10, 30, 30, this);
              case 3:
                  g.drawImage(player.enhance >= 3 ? InputImage.star : InputImage.nStar,
                          70, height + 10, 30, 30, this);
              case 2:
                  g.drawImage(player.enhance >= 2 ? InputImage.star : InputImage.nStar,
                          40, height + 10, 30, 30, this);
              case 1:
                  g.drawImage(player.enhance >= 1 ? InputImage.star : InputImage.nStar,
                          10, height + 10, 30, 30, this);
                  break;
              default:
                  g.setColor(Color.GRAY);             //不能升级的坦克，画一个小小的圆
                  g.fillOval(40, height + 10, 10, 10);
                  break;
          }
      }
  
      private void drawPause(Graphics g) {
          g.setFont(new Font("等线", Font.ITALIC + Font.BOLD, 70));
          g.setColor(Color.DARK_GRAY);
          g.drawString("游戏暂停中，按 P 键继续游戏", (int) ((width / 2) * 0.2), (height / 2 - 100));
          if (saved){
              g.setFont(new Font("等线", Font.ITALIC + Font.BOLD, 50));
              g.setColor(Color.DARK_GRAY);
              g.drawString("存档成功！", (int) ((width / 2) * 0.8), (height / 2));
          } else if(loaded){
              g.setFont(new Font("等线", Font.ITALIC + Font.BOLD, 50));
              g.setColor(Color.DARK_GRAY);
              g.drawString("读档成功！", (int) ((width / 2) * 0.8), (height / 2));
          }
          if (deadEnemy.size() >= maps[level].levelEnemyNum && (!bossActive || !boss.alive)){
              g.setFont(new Font("黑体", Font.ITALIC + Font.BOLD, 70));
              g.setColor(Color.ORANGE);
              g.drawString("下一波敌人接近中！", (int) ((width / 2) * 0.5), (int)(height * 0.8));
                                                                                          //*****此处需要修改*****
          }
      }
  
      //画出 玩家坦克
      private void drawPlayer(Graphics g) {
          player.pause = this.pause;
          drawLivingTank(g, player);
      }
  
      //画出敌人坦克
      private void drawEnemy(Graphics g) {
          Iterator<Tank> iterator = enemy.iterator();
          int n = 0;
          while (iterator.hasNext()) {
              Tank temp = iterator.next();
              if (!temp.alive) {                              //这个分支，坦克已被摧毁
                  temp.releaseCollisionSize();                //消除其碰撞体积
                  iterator.remove();
                  deadEnemy.add(temp);                        //从 敌人集 把该坦克删除，加入 破坏坦克集
                  player.enhanced(temp.vehicle);              //给玩家结算经验
                  enemyPositions.put(enemyPosition[n], false);//该坦克占用的位置被解放
              }
              n++;
          }
          creatEnemy();                       //尝试生成新的坦克
          iterator = enemy.iterator();
          while (iterator.hasNext()) {
              Tank t = iterator.next();
              t.pause = this.pause;                //暂停设置
  //            if (t.specialCount > 0) {
  //                t.specialCount--;                                     //*****此处需要修改*****
  //            } else {
              drawLivingTank(g, t);       //画出所有（敌人的）坦克
  //            }
          }
          if (bossActive) {
              boss.pause = this.pause;
              drawBoss(g);
          }
      }
  
      private void drawBoss(Graphics g) {
          if (boss.alive) {
              drawTank(g, boss);
          } else {
              drawExplosion(g, boss);
          }
          drawBullet(g, boss);
      }
  
  
      //画出被摧毁的坦克的残留特效及其所有残留子弹
      private void drawDeadTank(Graphics g) {
          Iterator<Tank> iterator = deadEnemy.iterator();
          while (iterator.hasNext()) {
              Tank temp = iterator.next();
              temp.pause = this.pause;
              if (temp.specialCount > 0) {          //敌人的特殊计数残留时，画出其爆炸效果
                  temp.specialCount--;                                        //*****此处需要修改*****
                  drawExplosion(g, temp);
              }
              if (temp.bullets.size() > 0) {          //敌人的子弹有残留时，画出该子弹
                  drawBullet(g, temp);
              }
          }
      }
  
  
      //画出存活的坦克及其所有子弹
      private void drawLivingTank(Graphics g, Tank tank) {
          //以下部分画出坦克
          if (tank.alive) {
              drawTank(g, tank);       //存活的场合，画出坦克
              drawBullet(g, tank);                //画出子弹
          }
      }
  
  
      //画坦克。这个方法能画出朝向正确的坦克。
      private void drawTank(Graphics g, Tank tank) {
          boolean b = dirState2(tank.dir);
          switch (tank.vehicle) {
              case Tank_Lv1:
                  image = dirState(tank.dir) ? InputImage.tank1 : InputImage.tank1r;
                  break;
              case Tank_Lv2:
                  image = dirState(tank.dir) ? InputImage.tank2 : InputImage.tank2r;
                  break;
              case Tank_Lv3:
                  image = dirState(tank.dir) ? InputImage.tank3 : InputImage.tank3r;
                  break;
              case Tank_E1:
                  image = dirState(tank.dir) ? InputImage.tankE1 : InputImage.tankE1r;
                  break;
              case Tank_E2:
                  image = dirState(tank.dir) ? InputImage.tankE2 : InputImage.tankE2r;
                  break;
              case Tank_E3:
                  image = dirState(tank.dir) ? InputImage.tankE3 : InputImage.tankE3r;
                  break;
              case Tank_Special:
                  image = dirState(tank.dir) ? InputImage.tankSp : InputImage.tankSpr;
                  break;
              case Basic:
                  if (tank.fireCount <= 3) {
                      image = dirState(tank.dir) ? InputImage.basicL : InputImage.basicLR;
                  } else {
                      image = dirState(tank.dir) ? InputImage.basic : InputImage.basicR;
                  }
                  break;
          }
          g.drawImage(image, b ? tank.x + 80 : tank.x, b ? tank.y + 80 : tank.y, b ? -80 : 80, b ? -80 : 80, this);
          if (tank.invincible > 0) {
              switch (tank.vehicle) {             //无敌持续中的场合，画出护盾
                  case Tank_Special:
                  case Basic:
                      image = dirState(tank.dir) ? InputImage.bubble : InputImage.bubbleR;
                      break;
                  default:
                      image = dirState(tank.dir) ? InputImage.bubbleE : InputImage.bubbleER;
                      break;
              }
              g.drawImage(image, tank.x - 5, tank.y - 5, 90, 90, this);
          }
      }
  
  
      //画出子弹。这个方法也会判断子弹的状态（是否存活）
      private void drawBullet(Graphics g, Tank tank) {
          Iterator<Bullet> iterator = tank.bullets.iterator();
          while (iterator.hasNext()) {
              Bullet temp = iterator.next();
              temp.pause = pause;
              if (!temp.active) {                 //子弹消亡的场合，移除子弹
                  iterator.remove();
              } else {                            //走到这里，说明子弹存活。
                  switch (tank.party) {           //看看是哪个阵营发出的子弹，去判定别的阵营的坦克
                      case 0:
                          if (bossActive && checkHit(boss, temp, tank)) {
                              break;
                          }
                          for (Tank t : enemy) {
                              if (checkHit(t, temp, tank)) {      //遍历敌坦克，看看打中了谁。打中则停止判定
                                  break;
                              }
                          }
                          break;
                      case 1:
                          checkHit(player, temp, tank);           //看看有没有击中玩家
                      default:
                  }
                  drawBullet(g, tank.vehicle, temp.getDir(), temp.getX(), temp.getY());       //画出子弹
              }
          }
      }
  
      //画出子弹。这个方法通常由上个方法调用，能画出朝向正确的子弹
      private void drawBullet(Graphics g, Vehicle vehicle, char dir, int x, int y) {
          boolean b = dirState2(dir);
          switch (vehicle.BULLET) {
              case 'n':
                  image = dirState(dir) ? InputImage.nBullet : InputImage.nBulletR;
                  break;
              case 'e':
                  image = dirState(dir) ? InputImage.eBullet : InputImage.eBulletR;
                  break;
              case 'g':
                  image = dirState(dir) ? InputImage.gBullet : InputImage.gBulletR;
                  break;
          }
          g.drawImage(image, b ? x + 10 : x, b ? y + 10 : y, b ? -10 : 10, b ? -10 : 10, this);
      }
  
  
      //画出爆炸。爆炸分为几个阶段，而且不同坦克也有不同爆炸特效
      private void drawExplosion(Graphics g, Tank tank) {
          if (tank.specialCount > 350) {
              drawTank(g, tank);
          }
          switch (tank.vehicle) {
              case Tank_E3:
                  if (tank.specialCount < 600 && tank.specialCount >= 100) {
                      if (tank.specialCount >= 500) {
                          image = InputImage.explosion1;
                      } else if (tank.specialCount >= 400) {
                          image = InputImage.explosion2;
                      } else if (tank.specialCount >= 300) {
                          image = InputImage.explosion3;
                      } else if (tank.specialCount >= 200) {
                          image = InputImage.explosion4;
                      } else {
                          image = InputImage.explosion5;
                      }
                      g.drawImage(image, tank.x, tank.y, 80, 80, this);
                  }
                  break;
              case Tank_E1:
              case Tank_E2:
              default:
                  if (tank.specialCount < 450 && tank.specialCount >= 50) {
                      if (tank.specialCount >= 250) {
                          image = InputImage.explosion1;
                      } else if (tank.specialCount > 100) {
                          image = InputImage.explosion2;
                      } else {
                          image = InputImage.explosion3;
                      }
                      g.drawImage(image, tank.x, tank.y, 80, 80, this);
                  }
          }
          tank.specialCount = Math.max(tank.specialCount, 0);
      }
  
  
      //下面这两个方法可以帮助其他方法画出正确朝向的对象
      private boolean dirState(char dir) {
          return dir == 'u' || dir == 'd';
      }
      private boolean dirState2(char dir) {
          return dir == 'l' || dir == 'd';
      }
  
  
      //检查子弹是否击中目标
      private boolean checkHit(Tank tank, Bullet bullet, Tank from) {
          if (hit(tank, bullet) && !bullet.hasHit(tank)) {        //检查是否击中目标 及 目标是否已被击中过
              bullet.setHit(tank);
              if (tank.invincible > 0) {
                  bullet.pierce = 0;              //撞到无敌的坦克时，子弹直接报销
              }
              bullet.active = bullet.pierce > 0;          //子弹穿透降为 0 的场合，子弹消亡
              if (!tank.takeDamage(from, bullet.getDir())) {                      //坦克伤害计数完后，在这里把 HP 归 0 的坦克记为已销毁
                  tank.alive = false;
              }
              return true;
          }
          return false;
      }
  
      //看看子弹是否击中坦克。由上个方法调用
      private boolean hit(Tank tank, Bullet bullet) {
          if (!tank.alive) {
              return false;
          }
          if (tank.vehicle == Vehicle.Basic) {
              return pIn(tank.x + 30, 20, bullet.getX() + 5) && pIn(tank.y + 30, 20, bullet.getY() + 5);
          }
          switch (tank.getDir()) {
              case 'u':
              case 'd':
                  return pIn(tank.x + 20, 40, bullet.getX() + 5) && pIn(tank.y + 3, 76, bullet.getY() + 5);
              case 'r':
              case 'l':
                  return pIn(tank.x + 3, 76, bullet.getX() + 5) && pIn(tank.y + 20, 40, bullet.getY() + 5);
          }
          return false;
      }
  
      //看看某个坐标（横坐标或纵坐标）是否在[p, p + w]范围内
      private boolean pIn(int p, int w, int toCheck) {
          return toCheck >= p && toCheck <= (p + w);
      }
  
      @Override
      public void keyTyped(KeyEvent e) {
  
      }
  
  
      //监视器。以下方式保证了动画的流畅度
      @Override
      public void keyPressed(KeyEvent e) {
          switch (e.getKeyCode()) {
              case KeyEvent.VK_W:
                  isPressingW = true;
                  break;
              case KeyEvent.VK_A:
                  isPressingA = true;
                  break;
              case KeyEvent.VK_D:
                  isPressingD = true;
                  break;
              case KeyEvent.VK_S:
                  isPressingS = true;
                  break;
              case KeyEvent.VK_J:         //J 是开火键
                  isFiring = true;
                  break;
  //            //===================以下为测试用=====================
  //            case KeyEvent.VK_Q:                                     //该 case 仅测试用。  务必删除！务必删除！
  //                for (Tank tank : enemy) {
  //                    tank.alive = false;
  //                    tank.releaseCollisionSize();
  //                }
  //                break;
  //            case KeyEvent.VK_E:                                     //该 case 仅测试用。  务必删除！务必删除！
  //                deadEnemy.clear();
  //                break;
  //            case KeyEvent.VK_1:                                     //该 case 仅测试用。  务必删除！务必删除！
  //                player.setVehicle(Vehicle.Tank_Lv1);
  //                player.releaseCollisionSize();
  //                break;
  //            case KeyEvent.VK_2:                                     //该 case 仅测试用。  务必删除！务必删除！
  //                player.setVehicle(Vehicle.Tank_Lv2);
  //                player.releaseCollisionSize();
  //                break;
  //            case KeyEvent.VK_3:                                     //该 case 仅测试用。  务必删除！务必删除！
  //                player.setVehicle(Vehicle.Tank_Lv3);
  //                player.releaseCollisionSize();
  //                break;
  //            case KeyEvent.VK_4:                                     //该 case 仅测试用。  务必删除！务必删除！
  //                player.setVehicle(Vehicle.Tank_Special);
  //                player.releaseCollisionSize();
  //                break;
  //            case KeyEvent.VK_5:                                     //该 case 仅测试用。  务必删除！务必删除！
  //                player.setVehicle(Vehicle.Basic);
  //                player.releaseCollisionSize();
  //                break;
  //            case KeyEvent.VK_Z:                                     //该 case 仅测试用。  务必删除！务必删除！
  //                player.buffedDef = 100;
  //                break;
  //            case KeyEvent.VK_X:                                     //该 case 仅测试用。  务必删除！务必删除！
  //                player.buffedDef = 0;
  //                break;
  //            case KeyEvent.VK_C:                                     //该 case 仅测试用。  务必删除！务必删除！
  //                player.invincible = 1000000;
  //                break;
  //            case KeyEvent.VK_V:                                     //该 case 仅测试用。  务必删除！务必删除！
  //                player.invincible = 0;
  //                break;
              //===================以上为测试用=====================
          }
          isGoing();          //看看玩家是否正在移动
          isFiring();         //看看玩家是否正在开火
      }
  
  
      //同上
      @Override
      public void keyReleased(KeyEvent e) {
          switch (e.getKeyCode()) {
              case KeyEvent.VK_W:             //向上
                  isPressingW = false;
                  break;
              case KeyEvent.VK_A:             //向左
                  isPressingA = false;
                  break;
              case KeyEvent.VK_D:             //向右
                  isPressingD = false;
                  break;
              case KeyEvent.VK_S:             //向下
                  isPressingS = false;
                  break;
              case KeyEvent.VK_J:             //开火
                  isFiring = false;
                  break;
              case KeyEvent.VK_P:             //暂停
                  gamePause();
                  saved = false;
                  loaded = false;
                  break;
              case KeyEvent.VK_I:             //读档（需要暂停）
                  toLoad = true;
                  break;
              case KeyEvent.VK_O:             //存档（需要暂停）
                  toSave = true;
                  break;
          }
          isGoing();
          isFiring();
      }
  
  
      //更新玩家的移动状态
      private void isGoing() {
          if (!player.pause) {
              if (isPressingW) {
                  player.dir = 'u';
              } else if (isPressingS) {
                  player.dir = 'd';
              } else if (isPressingA) {
                  player.dir = 'l';
              } else if (isPressingD) {
                  player.dir = 'r';
              }
          }
          player.isMoving = isPressingA || isPressingS || isPressingD || isPressingW;
      }
  
      //更新玩家的开火状态
      private void isFiring() {
          player.isFiring = isFiring;
      }
  
      //生成敌人，直到允许的最大数量
      private void creatEnemy() {
          while (enemy.size() < enemyMax && enemy.size() < maps[level].levelEnemyNum - deadEnemy.size()) {
              int[] temp = null;
              for (int[] ints : enemyPosition) {
                  if (!enemyPositions.get(ints)) {            //为坦克分配初始位置
                      temp = ints;
                      enemyPositions.put(ints, true);
                      break;
                  }
              }
              if (temp == null) {                 //应该不会抛出异常。但，以防万一，加上这句
                  throw new RuntimeException();
              }
              Tank tempTank = new Enemy(temp[0], temp[1], maps[level]);
              if (deadEnemy.size() == 0) {
                  tempTank.specialCount = 0;          //坦克有延迟显示。这里取消了第一组坦克（初始敌人坦克）的延迟显示
              }
              enemy.add(tempTank);         //在 敌人集 中添加新的坦克
              tempTank.start();            //启动该新坦克线程
          }
      }
  
      //这个方法有两个作用：
      //  1. 其他敌人全灭时，激活 BOSS
      //  2. 所有敌人全灭时，进入下一关
      private void checkLevelClear() {
          if (deadEnemy.size() == maps[level].levelEnemyNum && !bossActive && boss != null && boss.alive) {
              boss.start();
              bossActive = true;
          } else if (deadEnemy.size() >= maps[level].levelEnemyNum && (boss == null || !boss.alive)) {
              gameSuspend = true;
          }
      }
  
      //关卡间设置短暂停顿
      private void pauseBetweenLevels(int time) {
          gameSuspend = false;
          new Thread(new Timing(time)).start();
      }
  
      //每次调用会切换 暂停状态。
      private void gamePause() {
          this.pause = !this.pause;
      }
  
      //进入下一关时，加载下一关数据
      private void nextLevel() {
          player.releaseCollisionSize();
          player.x = 200;
          player.y = height - 200;
          level++;
          for (int i = 0; i < maps[level].mapData.length; i++) {
              for (int j = 0; j < maps[level].mapData[i].length; j++) {
                  inputMapData(i, j);
              }
          }
          for (int[] ints : enemyPosition) {
              enemyPositions.put(ints, false);
          }
          for (Tank tank : deadEnemy) {
              tank.releaseCollisionSize();
          }
          enemy.clear();
          deadEnemy.clear();
          player.lifeRemains = player.vehicle.LIFE;
          player.invincible = 0;
          gameSuspend = false;
          boss = maps[level].boss;
          if (boss != null) {
              boss.x = Math.max(width / 2 - 40, 0);
              boss.y = 70;
          }
          bossActive = false;
      }
  
      //从 Map 类中 加载既定的地图数据
      private void inputMapData(int x, int y) {
          for (int k = 0; k < 40; k++) {
              for (int l = 0; l < 40; l++) {
                  mapData[(x * 40) + k][(y * 40) + l][1] = maps[level].mapData[x][y][1];
                  mapData[(x * 40) + k][(y * 40) + l][0] = maps[level].mapData[x][y][0];
              }
          }                                                                           //*****此处需要修改*****
          //这里需要对 地图逻辑、坦克行进逻辑 都进行修改。
          // 现行方法是：由 mapData[][] 记录每个像素的数据。每个像素点的占用情况实时更新。
          // 改成：由 mapData[][] 记录所有 40 * 40 方格的数据。
          //      相信这个办法应该能解决现行方法偶发的空气墙问题，扩展性也会更好。存档大小也能缩小，因而也有机会优化存档逻辑。
          //      目前的代码基本兼容这个新方法。Map 类的数据本来就是 40 * 40 方格模式。地图大小、各类模型尺寸也都是 40 的整数倍
      }
  
      //读档
      void loadData(){
          if (pause) {
              ObjectInputStream ois = null;
              try {
                  if (!TankGame.savePath.exists()) {
                      TankGame.savePath.createNewFile();
                  }
                  ois = new ObjectInputStream(new FileInputStream(TankGame.savePath));
                  if((MyPanel)ois.readObject() != null){
                      player = (Player) ois.readObject();
  //                    mapData = (int[][][]) ois.readObject();
                      enemy = (Vector<Tank>) ois.readObject();
                      deadEnemy = (Vector<Tank>) ois.readObject();
                      enemyPositions = (LinkedHashMap<int[], Boolean>) ois.readObject();
                      enemyPosition = (int[][]) ois.readObject();
                      maps = (Map[]) ois.readObject();
                      boss = (Tank) ois.readObject();
                      level = ois.readInt();
                      bossActive = ois.readBoolean();
                  }
              } catch (IOException | ClassNotFoundException ex) {
                  ex.printStackTrace();
              } finally {
                  try {
                      ois.close();
                  } catch (IOException ex) {
                      ex.printStackTrace();
                  }
              }
              pause = true;
              loaded = true;
              for (int i = 0; i < maps[level].mapData.length; i++) {
                  for (int j = 0; j < maps[level].mapData[i].length; j++) {
                      inputMapData(i, j);
                  }
              }
              for (Tank tank : enemy) {
                  tank.start();
                  for (Bullet bullet : tank.bullets) {
                      bullet.start();
                  }
              }
              for (Tank tank : deadEnemy) {
                  for (Bullet bullet : tank.bullets) {
                      bullet.start();
                  }
              }
              if(bossActive && boss.alive){
                  boss.start();
              }
              player.start();
          }
      }
  
      //存档
      private void saveData(){
          if (pause) {
              ObjectOutputStream oos = null;
              try {
                  if (!TankGame.savePath.exists()) {
                      TankGame.savePath.createNewFile();
                  }
                  oos = new ObjectOutputStream(new FileOutputStream(TankGame.savePath));
                  oos.writeObject(TankGame.mp);
                  oos.writeObject(player);
  //                oos.writeObject(mapData);         //占用太大
                  oos.writeObject(enemy);
                  oos.writeObject(deadEnemy);
                  oos.writeObject(enemyPositions);
                  oos.writeObject(enemyPosition);
                  oos.writeObject(maps);
                  oos.writeObject(boss);
                  oos.writeInt(level);
                  oos.writeBoolean(bossActive);
                  saved = true;
              } catch (IOException ex) {
                  ex.printStackTrace();
              } finally {
                  try {
                      oos.close();
                  } catch (IOException ex) {
                      ex.printStackTrace();
                  }
              }
          }
      }
  }

• Tank.java

  package com.melody.tank_game;
  
  import java.io.Serializable;
  import java.util.Vector;
  
  /**
   * @author Melody
   * @version 1.0
   */
  //坦克类。这是一个抽象类，Player 和 Enemy 类会继承此类
  abstract public class Tank extends Thread implements Serializable {             //为什么是 继承Thread 而不是 实现Runnable？因为我写这些代码的时候还没学到那里……
      /*从上到下依次是：横坐标、纵坐标、坦克类型、方向、当前生命值、速度增幅、攻速增幅、攻击范围增幅、攻击力增幅、防御力增幅、
                      开火间隔、开火间隔计时、子弹集、是否存活、无敌状态持续时间、阵营、死亡计时
       */
      protected int x;
      protected int y;
      protected Vehicle vehicle = Vehicle.Basic;
      protected char dir = 'u';
      protected double lifeRemains;
      protected int buffedSpeed = 0;
      protected int buffedAtkSpeed = 0;
      protected int buffedAtkRange = 0;
      protected int buffedAtk = 0;
      protected int buffedDef = 0;
      protected int fireCD = 1;
      public int fireCount = 0;
      public final Vector<Bullet> bullets = new Vector<>();   //所有活动中的子弹会被存放在里面
      protected boolean alive = true;
      public int invincible = 0;
      public int party;
      public boolean pause = false;
      public int specialCount = 800;             //坦克死亡后，该计时才开始计数。这个计数是为了播放爆炸动画。计数完毕后该对象会被消除。
  
      public Tank(int x, int y) {
          this.x = x;
          this.y = y;
          setVehicle(Vehicle.Basic);
      }
  
  
      //设置坦克种类
      public void setVehicle(Vehicle vehicle) {
          this.vehicle = vehicle;
          this.lifeRemains = vehicle.LIFE;
          this.fireCD = 200 / getAtkSpeed();      //开火间隔由这个公式算出
      }
  
      public char getDir() {
          return dir;
      }
  
      //受到伤害。这个方法由子类实现
      abstract protected boolean takeDamage(Tank tank, char dir);
  
  
      //移动。
  //    abstract void move(char move);
  
      protected abstract void move();
  
  
      protected int[] tryMove(){
          int[] temp = new int[2];
          temp[0] = x;
          temp[1] = y;
          switch (dir) {
              case 'u':
                  temp[1]--;
                  break;
              case 'd':
                  temp[1]++;
                  break;
              case 'l':
                  temp[0]--;
                  break;
              case 'r':
                  temp[0]++;
                  break;
          }
          return temp;
      }
  
      protected boolean outOfArea(int x, int y) {
          return x < 0 || y < 0 || x > MyPanel.width - 80 || y > MyPanel.height - 80;
      }
  
      protected boolean runIntoSth(int x, int y) {
          boolean checking = false;
          switch (dir) {
              case 'u':
                  checking = MyPanel.mapData[x + 40 - (vehicle.SIZE / 2)][y + 40 - (vehicle.SIZE / 2)][1] == 0 &&
                          MyPanel.mapData[x + 40][y + 40 - (vehicle.SIZE / 2)][1] == 0 &&
                          MyPanel.mapData[x + 39 + (vehicle.SIZE / 2)][y + 40 - (vehicle.SIZE / 2)][1] == 0;
                  break;
              case 'd':
                  checking = MyPanel.mapData[x + 40 - (vehicle.SIZE / 2)][y + 39 + (vehicle.SIZE / 2)][1] == 0 &&
                          MyPanel.mapData[x + 40][y + 40 + (vehicle.SIZE / 2)][1] == 0 &&
                          MyPanel.mapData[x + 39 + (vehicle.SIZE / 2)][y + 39 + (vehicle.SIZE / 2)][1] == 0;
                  break;
              case 'r':
                  checking = MyPanel.mapData[x + 39 + (vehicle.SIZE / 2)][y + 40 - (vehicle.SIZE / 2)][1] == 0 &&
                          MyPanel.mapData[x + 39 + (vehicle.SIZE / 2)][y + 40][1] == 0 &&
                          MyPanel.mapData[x + 39 + (vehicle.SIZE / 2)][y + 39 + (vehicle.SIZE / 2)][1] == 0;
                  break;
              case 'l':
                  checking = MyPanel.mapData[x + 40 - (vehicle.SIZE / 2)][y + 40 - (vehicle.SIZE / 2)][1] == 0 &&
                          MyPanel.mapData[x + 40 - (vehicle.SIZE / 2)][y + 40][1] == 0 &&
                          MyPanel.mapData[x + 40 - (vehicle.SIZE / 2)][y + 39 + (vehicle.SIZE / 2)][1] == 0;
                  break;
          }
          return !checking;
      }
  
      protected void setCollisionSize(int tempX, int tempY, int type, int hp) {
          for (int i = 0; i < vehicle.SIZE; i++) {
              for (int j = 0; j < vehicle.SIZE; j++) {
                  MyPanel.mapData[tempX + 40 - (vehicle.SIZE / 2) + i][tempY + 40 - (vehicle.SIZE / 2) + j][1] = type;
                  MyPanel.mapData[tempX + 40 - (vehicle.SIZE / 2) + i][tempY + 40 - (vehicle.SIZE / 2) + j][0] = hp;
              }
          }
      }
  
      protected void releaseCollisionSize() {
          for (int i = 0; i < vehicle.SIZE; i++) {
              for (int j = 0; j < vehicle.SIZE; j++) {
                  MyPanel.mapData[x + 40 - (vehicle.SIZE / 2) + i][y + 40 - (vehicle.SIZE / 2) + j][1] = 0;
                  MyPanel.mapData[x + 40 - (vehicle.SIZE / 2) + i][y + 40 - (vehicle.SIZE / 2) + j][0] = 0;
              }
          }
      }
  
      //开火
      public void fire() {
          if (fireCount > 0) {        //fireCount > 0 说明开火CD 还没好，直接 return
              return;
          }
          if (vehicle == Vehicle.Basic) {     //Basic 体积和一般坦克不同，故而发射子弹的位置也不同
              fireCount = 10;                 //其武器也不同，所以 开火CD 的逻辑也不同。这里使其每发子弹的间隔很短
              switch (dir) {
                  case 'u':
                      fire(x + 39, y + 17, dir, getAtkRange());
                      break;
                  case 'd':
                      fire(x + 31, y + 53, dir, getAtkRange());
                      break;
                  case 'l':
                      fire(x + 17, y + 31, dir, getAtkRange());
                      break;
                  case 'r':
                      fire(x + 53, y + 39, dir, getAtkRange());
                      break;
              }
          } else {
              fireCount = fireCD;
              switch (dir) {
                  case 'u':
                      fire(x + 35, y - 10, dir, getAtkRange());
                      break;
                  case 'd':
                      fire(x + 35, y + 80, dir, getAtkRange());
                      break;
                  case 'l':
                      fire(x - 10, y + 35, dir, getAtkRange());
                      break;
                  case 'r':
                      fire(x + 80, y + 35, dir, getAtkRange());
                      break;
              }
          }
      }
  
      public void fire(int x, int y, char dir, int range) {
          Bullet tempBullet = new Bullet(vehicle.BULLET, x, y, dir, range, this);
          bullets.add(tempBullet);  //创建一个新的 子弹 实例，并让其运行
          tempBullet.start();
      }
  
      protected boolean isFront(char dir) {               //判断是否被从正面击中。如若是，坦克的防御力生效
          switch (dir) {
              case 'u':
                  return this.dir == 'd';
              case 'd':
                  return this.dir == 'u';
              case 'r':
                  return this.dir == 'l';
              case 'l':
                  return this.dir == 'r';
              default:
                  return false;
          }
      }
  
      public void pause(boolean pause){
          this.pause = pause;
      }
  
  
      public int getAtk() {
          return vehicle.ATK + buffedAtk;
      }
  
      public int getDef() {
          return vehicle.DEF + buffedDef;
      }
  
      public int getAtkSpeed() {
          return vehicle.ATK_SPEED + buffedAtkSpeed;
      }
  
      public int getSpeed() {
          return vehicle.SPEED + buffedSpeed;
      }
  
      public int getAtkRange() {
          return vehicle.ATK_RANGE + buffedAtkRange;
      }
  
  }

• Player.java

  package com.melody.tank_game;
  
  /**
   * @author Melody
   * @version 1.0
   */
  
  
  public class Player extends Tank {
      //三个属性依次是：经验值、是否正在移动、是否正在开火
      public int enhance = 0;
      //这两个变量由 MyPanel 的 监视器决定。按下移动/开火键时，变为 true。松开时，变为 false
      public boolean isMoving = false;
      public boolean isFiring = false;
  
      public Player(int x, int y) {
          super(x, y);
          party = 0;              //阵营为 0
          setVehicle(Vehicle.Basic);          //设置初始坦克。               可以随意修改
      }
  
  
      @Override
      public void run() {
          while (alive) {
              try {
                  Thread.sleep(100 / getSpeed());         //速度越快、行动越快
              } catch (InterruptedException e) {
                  e.printStackTrace();
              }
              if (!pause) {
                  if (invincible > 0) {       //无敌冷却减少
                      invincible--;
                  }
                  if (isMoving) {             //正在移动的场合，使其移动
                      move();
                  }
                  if (isFiring) {             //正在开火的场合，使其开火
                      fire();
                  } else if (vehicle == Vehicle.Basic) {          //Basic 是特别的。按住开火键的场合，开火CD才减少，不然会增加。
                      // 这样做是为了模拟 加特林 的手感
                      fireCount += fireCount >= fireCD ? 0 : 1;
                  } else {
                      fireCount--;            //开火CD 自然减少
                  }
              }
          }
      }
  
  
      @Override
      protected void move() {
          int[] temp = tryMove();
          if (!outOfArea(temp[0], temp[1]) && !runIntoSth(temp[0], temp[1])) {
              releaseCollisionSize();
              setCollisionSize(temp[0], temp[1], -2, -1);
              x = temp[0];
              y = temp[1];
          }
      }
  
      @Override
      public void fire() {
          if (fireCount > 0) {            //如果 开火CD 没到，让其自然减少，然后 return
              fireCount--;
              return;
          }
          super.fire();               //真正的开火
      }
  
  
      //获得经验值。每次消灭敌人坦克会调用该方法
      public void enhanced(Vehicle vehicle) {
          if (this.vehicle == Vehicle.Basic && Math.random() > 0.9) {         //特殊设定：Basic 的场合，消灭敌人有概率夺取坦克
              switch (vehicle) {
                  case Tank_E1:
                      setVehicle(Vehicle.Tank_Lv1);
                      break;
                  case Tank_E2:
                      setVehicle(Vehicle.Tank_Lv2);
                      break;
                  case Tank_E3:
                      setVehicle(Vehicle.Tank_Lv3);
                      break;
                  case Tank_Special:
                      setVehicle(Vehicle.Tank_Special);
                      break;
              }
          } else {
              switch (vehicle) {
                  case Tank_E1:
                      enhance += 1;
                      break;
                  case Tank_E2:
                      enhance += 2;
                      break;
                  case Tank_E3:
                      enhance += 3;
                      break;
                  case Tank_Special:
                      enhance += 10;
                      break;
              }
              enhanced();         //看看能不能升级
          }
      }
  
  
  
      //查看是否升级
      private void enhanced() {
          if (vehicle.LEVEL_UP_REQUIRED > 0 && enhance >= vehicle.LEVEL_UP_REQUIRED) {
              enhance -= vehicle.LEVEL_UP_REQUIRED;
              releaseCollisionSize();
              switch (vehicle) {
                  case Basic:
                      setVehicle(Vehicle.Tank_Lv1);
                      break;
                  case Tank_Lv1:
                      setVehicle(Vehicle.Tank_Lv2);
                      break;
                  case Tank_Lv2:
                      setVehicle(Vehicle.Tank_Lv3);
                      break;
                  default:
              }
              setCollisionSize(x, y, -2, -1);
          }
      }
  
  
      //设置坦克。每次设置会重置经验值
      @Override
      public void setVehicle(Vehicle vehicle) {
          super.setVehicle(vehicle);
          this.enhance = 0;
          if (vehicle == Vehicle.Basic) {
              fireCount = fireCD;
          }
      }
  
  
      //受到伤害。传入的是造成伤害的坦克，和击中的子弹方向
      @Override
      protected boolean takeDamage(Tank tank, char dir) {
          double damage = tank.getAtk() * vehicle.DEF_BY_PERCENT - (isFront(dir) ? this.getDef() : 0);    //侧后方中弹，防御力不生效
          if (invincible > 0) {               //无敌的场合，不受伤害
              return true;
          } else if ((lifeRemains -= Math.max(damage, 0.1)) <= 0) {           //这里扣除了生命值。最少扣除 0.1。
              invincible += 200;              //坦克被打爆，给一段无敌时间
              releaseCollisionSize();
              switch (vehicle) {              //坦克降级。Basic 的场合，游戏结束
                  case Tank_Lv3:
                  case Tank_Lv2:
                  case Tank_Lv1:
                  case Tank_Special:
                      setVehicle(Vehicle.Basic);
                      break;
                  case Basic:
                      return false;
              }
             
              setCollisionSize(x, y, -2, -1);
          }
          invincible += 100;      //只要受到了伤害，产生短暂无敌时间
          return true;
      }
  }

• Enemy.java

  package com.melody.tank_game;
  
  /**
   * @author Melody
   * @version 1.0
   */
  
  //敌人的坦克
  public class Enemy extends Tank {
      //step：坦克的前进次数。归 0 时会转向
      private int step = 0;
      private final double FIRE_PROBABILITY;
  
      public Enemy(Vehicle vehicle) {
          super(0, 0);
          setVehicle(vehicle);
          party = 1;
          dir = 'd';
          invincible = 300;
          FIRE_PROBABILITY = 0.95;
      }
  
      public Enemy(int x, int y, Map map) {
          this(x, y);
          giveVehicle(map.probability_E1, map.probability_E2);
      }
  
      public Enemy(int x, int y) {
          super(x, y);
          party = 1;              //敌方坦克阵营为 1
  //        randomDir();
  //        giveVehicle();
          dir = 'd';
          invincible = 130;       //敌方坦克出生时，赋予短时间的无敌
          FIRE_PROBABILITY = 0.985;
      }
  
      @Override
      public void run() {
          try {
              Thread.sleep(700 + specialCount);          //坦克出生时，使其短暂休眠。
          } catch (InterruptedException e) {
              e.printStackTrace();
          }
          specialCount = 200 + (int) (80 * lifeRemains);         //坦克的 死亡计数，和坦克种类有关
          while (alive) {
              try {
                  Thread.sleep((100 / getSpeed()));       //坦克速度越快，其所有行动速度越快
              } catch (InterruptedException e) {
                  e.printStackTrace();
              }
              if (!pause) {
                  if (invincible > 0) {           //无敌时间减少
                      invincible--;
                  }
                  if (fireCount > 0) {            //开火CD计数减少
                      fireCount--;
                  }
                  move();               //移动
              }
          }
          releaseCollisionSize();
          while (specialCount >= 0) {
              try {
                  Thread.sleep(1);
              } catch (InterruptedException e) {
                  e.printStackTrace();
              }
              if (!pause) {
                  specialCount--;                                    //*****此处需要修改*****
              }
          }
      }
  
  
      private void giveVehicle(double probabilityE1, double probabilityE2) {
          double result = Math.random();
          if (result <= probabilityE1) {
              setVehicle(Vehicle.Tank_E1);
          } else if (result <= probabilityE2) {
              setVehicle(Vehicle.Tank_E2);
          } else {
              setVehicle(Vehicle.Tank_E3);
          }
      }
  
      @Override
      public void move() {            //传入的字符没用。
          if (step <= 0) {
              randomDir();                        //步数归 0 时，赋予其随机方向
              realMove();
              step = (int) (Math.random() * 200 + 60 - 3 * getSpeed());       //赋予其随机的步数
          } else if (step <= 60 - 2 * getSpeed()) {       //最后几步的时候，让坦克在原地稍作停留（不移动）
              step--;
          } else {
              realMove();
              step--;
          }
          if (Math.random() > FIRE_PROBABILITY) {            //使敌方坦克有 1.5% 的概率开火。这个概率经过测试，比较合适           这里可以更改
              fire();
          }
      }
  
      private void realMove() {
          int[] temp = tryMove();
          if (!outOfArea(temp[0], temp[1]) && !runIntoSth(temp[0], temp[1])) {
              releaseCollisionSize();
              setCollisionSize(temp[0], temp[1], -1, -1);
              x = temp[0];
              y = temp[1];
          } else {
              step -= 10;
          }
      }
  
      //赋予随机方向（概率均匀）
      private void randomDir() {
          switch ((int) (Math.random() * 4)) {
              case 0:
                  dir = 'u';
                  break;
              case 1:
                  dir = 'r';
                  break;
              case 2:
                  dir = 'd';
                  break;
              case 3:
                  dir = 'l';
                  break;
          }
      }
  
  
      //受伤。传入的是造成伤害的坦克（以计算伤害），及子弹方向（用于判断是否是正面中弹）
      @Override
      protected boolean takeDamage(Tank tank, char dir) {
          double damage = tank.getAtk() * vehicle.DEF_BY_PERCENT - (isFront(dir) ? getDef() : 0);     //侧后方中弹的场合，防御力不生效
          if (invincible > 0) {               //如果坦克无敌，不会受到伤害
              return true;
          } else {
              return (this.lifeRemains -= Math.max(damage, 0.1)) > 0;        //在这里进行了生命值的扣除，最少扣 0.1。返回是否生命值有剩
          }
      }
  }

• Vehicle.java

  package com.melody.tank_game;
  
  import java.io.Serializable;
  
  /**
   * @author Melody
   * @version 1.0
   */
  
  
  //该枚举类存放所有可能的坦克种类及其参数
  public enum Vehicle implements Serializable{
      //Basic 是特别的。设定上，Basic 是离开载具，扛着加特林的驾驶员。其体积和一般坦克不同
      Basic(1, 2, 0, 20, 3, 400, 5, 10, 'g', 10),
      Tank_Lv1(5, 11, 1, 12, 4, 1000, 5, 1, 'n'),
      Tank_Lv2(7, 15, 2, 12, 4, 1000, 10, 0.9, 'n'),
      Tank_Lv3(10, 17, 3, 12, 4, 1600, -1, 0.8, 'n'),
      Tank_E1(5, 5, 1, 11, 4, 1000, -1, 1, 'n'),
      Tank_E2(7, 10, 2, 10, 4, 1000, -1, 0.8, 'n'),
      Tank_E3(10, 18, 3, 9, 4, 1600, -1, 0.6, 'n'),
      Tank_Special(25, 13, 4, 18, 1, 100000, -1, 0.4, 'e');
  
      //从上到下依次是：攻击力、生命值、防御力、速度、攻击速度、攻击范围、升级经验、减伤、子弹种类
      public final int ATK;
      public final double LIFE;
      public final int DEF;
      public final int SPEED;
      public final int ATK_SPEED;
      public final int ATK_RANGE;
      public final int LEVEL_UP_REQUIRED;
      public final double DEF_BY_PERCENT;
      public final char BULLET;
      public final int SIZE;
  
  
      Vehicle(int atk, double life, int def, int speed, int atkSpeed, int atkRange,
              int levelUpRequired, double defByPercent, char bullet, int size) {
          this.ATK = atk;
          this.LIFE = life;
          this.DEF = def;
          this.SPEED = speed;
          this.ATK_SPEED = atkSpeed;
          this.ATK_RANGE = atkRange;
          this.LEVEL_UP_REQUIRED = levelUpRequired;
          this.DEF_BY_PERCENT = defByPercent;
          this.BULLET = bullet;
          this.SIZE = size;
      }
  
      Vehicle(int atk, double life, int def, int speed, int atkSpeed, int atkRange,
              int levelUpRequired, double defByPercent, char bullet) {
          this(atk, life, def, speed, atkSpeed, atkRange, levelUpRequired, defByPercent, bullet, 80);
      }
  }
  
  
  //子弹类
  class Bullet extends Thread implements Serializable {
      //从上到下依次是：横坐标、纵坐标、方向、子弹速度、子弹是否存在、最大飞行范围、穿透数量、已命中的坦克
      private int x;
      private int y;
      private char dir;
      private final int BULLET_SPEED;
      public boolean active = true;
      private int range;
      public int pierce;
      private Tank master;
      private Tank[] hit;
      public boolean pause = false;
  
  
      public Bullet(char type, int x, int y, char dir, int range, Tank master) {
          switch (type) {
              case 'e':
                  this.BULLET_SPEED = 3;
                  this.pierce = 3;
                  break;
              case 'g':
                  this.BULLET_SPEED = 2;
                  this.pierce = 1;
                  break;
              case 'n':
              default:
                  this.BULLET_SPEED = 1;
                  this.pierce = 1;
                  break;
  
          }
          hit = new Tank[pierce];
          this.x = x;
          this.y = y;
          this.dir = dir;
          this.range = range;
          this.master = master;
      }
  
      public void move() {
          switch (dir) {
              case 'u':
                  y -= BULLET_SPEED;
                  break;
              case 'd':
                  y += BULLET_SPEED;
                  break;
              case 'r':
                  x += BULLET_SPEED;
                  break;
              case 'l':
                  x -= BULLET_SPEED;
                  break;
          }
          if ((range -= BULLET_SPEED) <= 0 || outOfArea(x, y)) {     //如果达到最大飞行范围，则销毁该子弹
              active = false;
          }
      }
  
      private boolean outOfArea(int x, int y) {
          return x < 0 || y < 0 || x > MyPanel.width - 10 || y > MyPanel.height - 10;
      }
  
      public int getX() {
          return x;
      }
  
      public int getY() {
          return y;
      }
  
      public char getDir() {
          return dir;
      }
  
      public int getBULLET_SPEED() {
          return BULLET_SPEED;
      }
  
      public void setHit(Tank tank) {             //当有坦克被该子弹击中后，该方法会被调用。一般由 MyPanel 类中的 checkHit 方法调用
          hit[hit.length - pierce--] = tank;
      }
  
      public boolean hasHit(Tank tank) {          //判断一辆坦克是否已被击中过。一般由 MyPanel 类中的 checkHit 方法调用
          for (Tank t : hit) {
              if (t == tank) {
                  return true;
              }
          }
          return false;
      }
  
      public void pause(boolean pause) {
          this.pause = pause;
      }
  
  
      @Override
      public void run() {
          while (active) {
              try {
                  Thread.sleep(1);
              } catch (InterruptedException e) {
                  e.printStackTrace();
              }
              if (!pause) {
                  move();
              }
          }
      }
  }

• Map.java

  package com.melody.tank_game;
  
  import java.io.Serializable;
  
  /**
   * @author Melody
   * @version 1.0
   */
  public enum Map implements Serializable {
      Level1(10, 1, 1, null, 0, creatNewMap1()),
      Level2(15, 0.5, 1, Vehicle.Tank_E2, 10, creatNewMap2()),
      Level3(20, 0.33, 0.66, Vehicle.Tank_E3, 15, creatNewMap3()),
      Level4(20, 0.2, 0.5, Vehicle.Tank_Special, 20, creatNewMap4());
      public final int levelEnemyNum;
      public final double probability_E1;
      public final double probability_E2;
      public final Tank boss;
      public int[][][] mapData;
      //[0]：种类。-1 坦克；0 道路；1 墙；2 草丛；3 水池
      //[1]：HP。-1 不可破坏；0 可以通行；1 basic以外任意子弹击中1次可以破坏；2、3 同 1
  
      Map(int levelEnemyNum, double probability_E1, double probability_E2, Vehicle boss, int bossBuff, int[][][] map) {
          this.levelEnemyNum = levelEnemyNum;
          this.probability_E1 = probability_E1;
          this.probability_E2 = probability_E2;
          if (boss == null) {
              this.boss = null;
          } else {
              this.boss = new Enemy(boss);
              this.boss.lifeRemains += bossBuff;
          }
          mapData = map;
      }
  
  
      private static int[][][] creatNewMap1() {
          int[][][] newMap = creatNewMap();
          return newMap;
      }
      private static int[][][] creatNewMap2() {
          int[][][] newMap = creatNewMap();
          return newMap;
      }
      private static int[][][] creatNewMap3() {
          int[][][] newMap = creatNewMap();
          return newMap;
      }
      private static int[][][] creatNewMap4() {
          int[][][] newMap = creatNewMap();
          return newMap;
      }
  
      private static int[][][] creatNewMap() {
          int[][][] newMap = new int[30][20][2];
          newMap = creatBasicMap(newMap);
          return newMap;
      }
  
      private static int[][][] creatBasicMap(int[][][] map){
          for (int i = 0; i < map.length; i++) {
              for (int j = 0; j < map[i].length; j++) {
                  map[i][j][1] = 0;
                  map[i][j][0] = 0;
              }
          }
          return map;
      }
  
      private static void addWall(int[][][] map, int x, int y) {
          map[x][y][0] = 1;
          map[x][y][1] = -1;
      }
  
      private static void addArea(int[][][] map, int x, int y, int kind, int hp) {
          map[x][y][0] = kind;
          map[x][y][1] = hp;
      }
  
      private void removeTankCollisionSize(Tank tank) {
      }
  
      private void setTankCollisionSize(Tank tank) {
      }
  }

• InputImage.java

  package com.melody.tank_game;
  
  import java.awt.*;
  import java.io.Serializable;
  
  /**
   * @author Melody
   * @version 1.0
   */
  
  
  /*
  该类中存放所有需要的图片。
  包含：坦克图片（tank/basic：4 * 2 + 1 = 9 种）；
       子弹图片（bullet：2 * 2 = 4 种）；
       护盾图片（bubble：2 * 2 = 4种）；
       星星图片（star：2种）、爆炸图片（explosion：5种）;
       地形图片（4种）
   */
  public class InputImage implements Serializable {
      public static final Image tank1 = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Tank_Lv1.png"));
      public static final Image tank2 = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Tank_Lv2.png"));
      public static final Image tank3 = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Tank_Lv3.png"));
      public static final Image basic = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/P.png"));
      public static final Image basicL = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Pl.png"));
      public static final Image basicR = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Pr.png"));
      public static final Image basicLR = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Plr.png"));
      public static final Image tankE1 = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Tank_E1.png"));
      public static final Image tankE2 = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Tank_E2.png"));
      public static final Image tankE3 = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Tank_E3.png"));
      public static final Image tank1r = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Tank_Lv1r.png"));
      public static final Image tank2r = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Tank_Lv2r.png"));
      public static final Image tank3r = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Tank_Lv3r.png"));
      public static final Image tankE1r = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Tank_E1r.png"));
      public static final Image tankE2r = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Tank_E2r.png"));
      public static final Image tankE3r = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Tank_E3r.png"));
      public static final Image tankSp = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Tank_Sp.png"));
      public static final Image tankSpr = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Tank_Spr.png"));
      public static final Image bubble = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Bubble_red.png"));
      public static final Image bubbleR = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Bubble_red_r.png"));
      public static final Image bubbleE = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Bubble.png"));
      public static final Image bubbleER = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Bubble_r.png"));
      public static final Image eBullet = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/E_bullet.png"));
      public static final Image eBulletR = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/E_bullet_r.png"));
      public static final Image nBullet = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/N_bullet.png"));
      public static final Image nBulletR = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/N_bullet_r.png"));
      public static final Image gBullet = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/G_bullet.png"));
      public static final Image gBulletR = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/G_bullet_r.png"));
      public static final Image star = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Star.png"));
      public static final Image nStar = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Star_n.png"));
      public static final Image explosion1 = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Explosion/Explosion1.png"));
      public static final Image explosion2 = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Explosion/Explosion2.png"));
      public static final Image explosion3 = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Explosion/Explosion3.png"));
      public static final Image explosion4 = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Explosion/Explosion4.png"));
      public static final Image explosion5 = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Explosion/Explosion5.png"));
      public static final Image iron = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Landform/Iron.png"));
      public static final Image wall = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Landform/Wall.png"));
      public static final Image water = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Landform/Water.png"));
      public static final Image trees = Toolkit.getDefaultToolkit().getImage(Panel.class.getResource("/pic/Landform/Trees.png"));
  }

• Timing.java

  package com.melody.tank_game;
  
  /**
   * @author Melody
   * @version 1.0
   */
  public class Timing implements Runnable{
      private int time;
  
      public Timing(int time){
          this.time = time;
      }
      @Override
      public void run() {
          try {
              Thread.sleep(time);
          } catch (InterruptedException e) {
              e.printStackTrace();
          }
          MyPanel.gameSuspend = true;
      }
  }