数据结构总结

一.Java数据结构-线性表的设计与实现

第1关：顺序表的实现之增删功能

**任务描述**
​
本关任务：实现一个顺序表，并实现增加元素，删除元素功能。
​
**编程要求**
​
本关的编程任务是补全右侧代码片段中所有`Begin`至`End`中间的代码，具体要求如下：
​
- 向表中添加元素；
- 向表中指定位置添加元素；
- 删除指定位置的元素并返回被删除的元素。
​
具体请参见后续测试样例。
​
**测试说明**
​
测试过程：
​
- 平台将创建用户补全后的`MyArrayList`类的对象；
- 调用对象的`Add(int item)`方法，向表中添加测试数据；
- 调用对象的`Add(int index, int item)`方法，向表中指定位置添加测试数据；
- 调用对象的`remove(int index)`方法删除指定位置的数据并输出；
- 调用对象的`size()`方法返回表的大小；
- 根据输出结果判断程序是否正确。
​
以下是测试样例：
list.Add(0, 3);
        list.Add(5);
        list.Add(7);
        list.Add(-1);
        list.Add(2, 4);
        list.Add(-6);
        list.remove(0);
        while (list.size() > 0) {
            System.out.println(list.remove(0));
        }
​
预期输出  547-1-6

package step1;
public class MyArrayList {
    private int[] elements;//元素
    private int size;//List中当前的元素个数
    public MyArrayList() {
        this(1);//List默认大小为1
    }
    /**
     * 按指定大小capacity构造List
     *
     * @param capacity List初始化时的大小
     */
    public MyArrayList(int capacity) {
        elements = new int[capacity];
        size = 0;
    }
    /**
     * 返回List中元素的个数
     *
     * @return
     */
    public int size() {
        return size;
    }
    /**
     * 添加一个元素到末尾
     *
     * @param item
     */
    public void Add(int item) {
        int len = elements.length;
        // 如果当前元素个数等于数组长度减1，说明数组已满，需要扩展数组容量
        if (size == len - 1) {
            resize(2 * len);
        }
        /********** 开始 *********/
        elements[size++] = item; // 将元素添加到末尾，并更新size计数
        /********** 结束 *********/
    }
    /**
     * 添加一个元素到指定位置index
     *
     * @param index 要插入的位置
     * @param item  要插入的元素
     */
    public void Add(int index, int item) {
        validateRangeForAdd(index); // 检查插入位置的合法性
        int len = elements.length;
        // 如果当前元素个数等于数组长度减1，说明数组已满，需要扩展数组容量
        if (size == len - 1) {
            resize(2 * len);
        }
        /********** 开始 *********/
        int i = size;
        // 将从插入位置开始的元素后移一位，为新元素腾出空间
        for (i = size; i > index; i--) {
            elements[i] = elements[i - 1];
        }
        elements[index] = item; // 在指定位置插入元素
        size++; // 更新元素个数计数
        /********** 结束 *********/
    }
    /**
     * 删除指定位置index的元素,并返回被删除的元素
     *
     * @param index 要删除的位置
     * @return 被删除的元素
     */
    public int remove(int index) {
        validateRange(index); // 检查删除位置的合法性
        /********** 开始 *********/
        int out = elements[index]; // 保存被删除的元素
        // 将删除位置后的元素往前移动一位来覆盖被删除元素
        for (int i = index; i < size - 1; i++) {
            elements[i] = elements[i + 1];
        }
        size--; // 更新元素个数计数
        return out; // 返回被删除的元素
        /********** 结束 *********/
    }
    /**
     * 校验索引范围
     *
     * @param index
     */
    private void validateRange(int index) {
        if (index >= size || index < 0) {
            throw new ArrayIndexOutOfBoundsException("索引越界了哦！Index: " + index + ", Size: " + size);
        }
    }
    /**
     * 校验索引范围
     *
     * @param index
     */
    private void validateRangeForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException("索引越界了哦！Index: " + index + ", Size: " + size);
    }
    /**
     * 动态扩展数组大小
     *
     * @param capacity
     */
    private void resize(int capacity) {
        assert capacity > size;
        int[] tmp = new int[capacity];
        for (int i = 0; i < size; i++) {
            tmp[i] = elements[i];
        }
        elements = tmp;
    }
}

第2关： 顺序表的实现之查询功能

**任务描述**
​
在上一关，我们实现了表的基本功能：添加元素，删除元素。本关的任务是在上一关的基础上，实现获取指定位置元素的功能。
​
如`list.get(2)`返回表中下标为`2`的元素，即表中第`3`个元素。
​
**相关知识**
​
请参考上一关。
​
**编程要求**
​
本关的编程任务是补全右侧代码片段中`Begin`至`End`中间的代码，具体要求如下：
​
- 返回表中下标为`index`的元素。
​
具体请参见后续测试样例。
​
**测试说明**
​
测试过程：
- 平台将创建用户补全后的`MyArrayList`类的对象；
- 调用对象的`Add(int item)`方法，向表中添加测试数据；
- 调用对象的`Add(int index, int item)`方法，向表中指定位置添加测试数据；
- 调用对象的`remove(int index)`方法删除指定位置的数据；
- 调用对象的`size()`方法返回表的大小；
- 调用对象的`get(int index)`方法返回`index`处的元素并输出；
- 根据输出结果判断程序是否正确。
​
以下是测试样例：
list.Add(0, 3);
        list.Add(5);
        list.Add(7);
        list.Add(-1);
        list.Add(2, 4);
        list.Add(-6);
        list.remove(0);
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }

package step2;
​
public class MyArrayList {
    private int[] elements;//元素
    private int size;//List中当前的元素个数
    public MyArrayList() {
        this(1);//List默认大小为1
    }
    /**
     * 按指定大小capacity构造List
     *
     * @param capacity List初始化时的大小
     */
    public MyArrayList(int capacity) {
        elements = new int[capacity];
        size = 0;
    }
    /**
     * 返回List中元素的个数
     *
     * @return
     */
    public int size() {
        return size;
    }
    /**
     * 添加一个元素到末尾
     *
     * @param item
     */
    public void Add(int item) {
        int len = elements.length;
        if (size == len - 1) {
            resize(2 * len);
        }
        elements[size++] = item;
    }
    /**
     * 添加一个元素到指定位置index
     *
     * @param index
     * @param item
     */
    public void Add(int index, int item) {
        validateRangeForAdd(index);
        int len = elements.length;
        if (size == len - 1) {
            resize(2 * len);
        }
        for (int i = size; i > index; i--) {
            elements[i] = elements[i - 1];
        }
        elements[index] = item;
        size++;
    }
    /**
     * 删除指定位置index的元素,并返回被删除的元素
     *
     * @param index
     * @return 被删除的元素
     */
    public int remove(int index) {
        validateRange(index);
        int oldVal = elements[index];
        for (int i = index; i < size - 1; i++) {
            elements[i] = elements[i + 1];
        }
        --size;
        return oldVal;
    }
    /**
     * 返回表中下标为index的元素
     *
     * @param index 下标
     * @return
     */
    public int get(int index) {
​
        validateRange(index);
        /********** Begin *********/
        return elements[index];
        /********** End *********/
    }
    /**
     * 校验索引范围
     *
     * @param index
     */
    private void validateRange(int index) {
        if (index >= size || index < 0) {
            throw new ArrayIndexOutOfBoundsException("索引越界了哦！Index: " + index + ", Size: " + size);
        }
    }
    /**
     * 校验索引范围
     *
     * @param index
     */
    private void validateRangeForAdd(int index) {
        if (index > size || index < 0)
            throw new IndexOutOfBoundsException("索引越界了哦！Index: " + index + ", Size: " + size);
    }
    /**
     * 动态扩展数组大小
     *
     * @param capacity
     */
    private void resize(int capacity) {
        assert capacity > size;
        int[] tmp = new int[capacity];
        for (int i = 0; i < size; i++) {
            tmp[i] = elements[i];
        }
        elements = tmp;
    }
}

第3关：单链表的实现之增删功能

**任务描述**
​
在之前的实训中，我们用数组实现了表，在本关我们将使用另外一种数据组织方式实现表。
​
我们注意到，在之前的关卡中为了防止数组溢出，我们在必要的时候对数组进行了扩展，但这样做的缺点是很明显的，每次扩展数组时都需要移动数据。而且在为新插入的元素腾出空间或者弥合删除后留下的间隙时，也要移动数据。而之所以要移动数据，是因为表是连续存储的，所以如果我们能保证表可以不连续存储，那么这种开销是可以避免的。
​
本关任务：实现一个带头结点的单链表，并实现基本功能：插入元素，删除元素
​
**编程要求**
​
本关的编程任务是补全右侧代码片段中所有`Begin`至`End`中间的代码，具体要求如下：
​
- 向链表中添加元素，补全`add(int item)`方法；
- 向链表中指定位置添加元素，补全`add(int index, int item)`方法；
- 删除链表指定位置的元素并返回其值，补全`remove(int index)`方法。
​
**测试说明**
​
测试过程：
​
- 平台将创建用户补全后的`MyLinkedList`类的对象；
- 调用对象的`add(int item)`方法，向表中添加测试数据；
- 调用对象的`add(int index, int item)`方法，向表中指定位置添加测试数据；
- 调用对象的`size()`方法返回表的大小；
- 调用对象的`remove(int index)`方法删除指定位置的数据；
- 根据输出结果判断程序是否正确。
​
以下是测试样例：
 list.add(0,1);
        list.add(5);
        list.add(7);
        list.add(-1);
        list.add(0, 3);
        list.add(2, 4);
        list.add(-6);
        list.remove(6);
        list.add(33);
        while (list.size()>0){
            System.out.println(list.remove(0));
        }

package step3;
public class MyLinkedList {
    private Node first;//头结点，不存数据
    private Node last;//指向链表的最后一个节点
    private int size;
    public MyLinkedList() {
        size = 0;
        first = new Node(0, null);
        last = null;
    }
    /**
     * 添加到链表尾部
     *
     * @param item 待添加的元素
     */
    public void add(int item) {
        /********** 开始 *********/
        final Node l = last; // 保存当前尾部节点的引用
        final Node node = new Node(item, null); // 创建新节点
        last = node; // 更新尾部节点为新节点
        if (first.next == null) { // 如果链表为空
            first.next = node; // 链表的头节点指向新节点
        } else {
            l.next = node; // 将新节点连接到链表尾部
        }
        size++; // 更新链表大小
        /********** 结束 *********/
    }
    /**
     * 添加数据item到指定位置index
     * index从0开始
     *
     * @param index 插入位置
     * @param item  待插入的元素
     */
    public void add(int index, int item) {
        checkPosIndex(index); // 检查插入位置的合法性
        /********** 开始 *********/
        int n = index;
        Node l = first;
        while ((n--) > 0) { // 移动到插入位置的前一个节点
            l = l.next;
        }
        final Node node = new Node(item, null); // 创建新节点
        if (null == first.next) { // 如果链表为空
            last = node; // 新节点为尾节点
        }
        node.next = l.next; // 新节点指向原插入位置的节点
        l.next = node; // 前一个节点指向新节点
        size++; // 更新链表大小
        /********** 结束 *********/
    }
    /**
     * 删除指定位置index处的元素并返回，index从0开始
     *
     * @param index 待删除元素的位置
     * @return 被删除的元素值
     */
    public int remove(int index) {
        checkPosIndex(index); // 检查删除位置的合法性
​
        /********** 开始 *********/
        Node f = first;
        while ((index--) > 0) { // 移动到删除位置的前一个节点
            f = f.next;
        }
        Node del = f.next; // 待删除的节点
        if (del == last) { // 如果待删除的节点为尾节点
            last = f; // 更新尾节点为待删除节点的前一个节点
        }
        f.next = del.next; // 前一个节点指向待删除节点的下一个节点
        del.next = null; // 删除节点的引用置空
        int PUT = del.item; // 获取删除节点的元素值
        del = null; // 删除节点对象置空，协助垃圾回收
        size--; // 更新链表大小
        return PUT; // 返回被删除的元素值
        /********** 结束 *********/
    }
    public int size() {
        return size;
    }
    private void checkPosIndex(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }
    //结点内部类
    private static class Node {
        int item;
        Node next;
​
        Node(int item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

第4关：单链表的实现之查询功能

**任务描述**
​
在上一关，我们实现了单链表的基本功能：添加元素，删除元素。链式实现的表无法实现随机存取，因此要获取指定位置的元素，只能从头结点开始遍历。 本关任务：在上一关的基础上继续完善单链表的功能，实现获取指定位置元素的功能。
​
**编程要求**
​
本关的编程任务是补全右侧代码片段中`Begin`至`End`中间的代码，具体要求如下：
​
- 获取指定位置`index`处的元素并返回，补全`get(int index)`方法。
​
具体请参见后续测试样例。
​
**测试说明**
​
测试过程：
​
- 平台将创建用户补全后的`MyLinkedList`类的对象；
​
- 调用对象的`add(int item)`方法，向表中添加测试数据；
​
- 调用对象的`add(int index, int item)`方法，向表中指定位置添加测试数据；
​
- 调用对象的`size()`方法返回表的大小；
​
- 调用对象的`remove(int index)`方法删除指定位置的数据；
​
- 调用对象的`get(int index)`方法返回`index`处的元素并输出；
​
- 根据输出结果判断程序是否正确。
​
 list.add(0,1);
        list.add(5);
        list.add(7);
        list.add(-1);
        list.add(0, 3);
        list.add(2, 4);
        list.add(-6);
        list.remove(6);
        list.add(33);
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }
​
预期输出
3
1
4
5
7
-1
33

package step4;
public class MyLinkedList {
    private Node first;//头结点，不存数据
    private Node last;//指向链表的最后一个节点
    private int size;
    public MyLinkedList() {
        size = 0;
        first = new Node(0, null);
        last = null;
    }
    /**
     * 添加到链表尾部
     *
     * @param item
     */
    public void add(int item) {
        final Node l = last;
        final Node node = new Node(item, null);
        last = node;
        if (first.next == null) {//首次添加
            first.next = node;
        } else {
            l.next = node;
        }
        ++size;
    }
    /**
     * 添加数据item到指定位置index
     * index从0开始
     *
     * @param index
     * @param item
     */
    public void add(int index, int item) {
        checkPosIndex(index);
        int n = index;
        Node l = first;
        while ((n--) > 0) {
            l = l.next;
        }
​
        final Node node = new Node(item, null);
        if (null == first.next) {//首次添加
            last = node;
        }
        node.next = l.next;
        l.next = node;
        ++size;
    }
    /**
     * 删除指定位置index处的元素并返回, index从0开始
     *
     * @param index
     * @return
     */
    public int remove(int index) {
        checkPosIndex(index);
        Node f = first;
        while ((index--) > 0) {
            f = f.next;
        }
        Node del = f.next;
        if (del == last) {//删除最后一个元素
            last = f;
        }
        f.next = del.next;
        del.next = null;
​
        int oldVal = del.item;
​
        del = null;
        --size;
        return oldVal;
    }
    /**
     * 获取链表中第index个元素
     *
     * @param index 元素位置
     * @return 第index个元素的值
     */
    public int get(int index) {
        checkPosIndex(index); // 检查位置的合法性
        /********** 开始 *********/
        Node f = first.next; // 从头节点的下一个节点开始
        while ((index--) > 0) { // 移动到指定位置的节点
            f = f.next;
        }
        int out = f.item; // 获取指定位置节点的元素值
        return out; // 返回元素值
        /********** 结束 *********/
    }
    public int size() {
        return size;
    }
    private void checkPosIndex(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }
    //结点内部类
    private static class Node {
        int item;
        Node next;
​
        Node(int item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}

二.Java数据结构-循环链表的设计与实现

第1关：单循环链表的实现—链表的添加、遍历

**任务描述**
​
在操作单链表时，我们有时希望从单链表中的任一结点出发都能遍历整个链表，但对于单链表来说，只有从头结点开始才能扫描表中的全部结点。因此我们需要改动链表，使其首尾相接，这样就能满足我们的需求。
​
本关任务：完成带头结点的单循环链表的添加功能，遍历链表并输出。
​
**编程要求**
​
本关的编程任务是补全右侧代码片段中`Begin`至`End`中间的代码，具体要求如下：
​
- 完成单循环链表的添加功能；
- 遍历单循环链表，并输出元素的值。
​
具体请参见后续测试样例
​
**测试说明**
​
测试过程：
​
- 平台将创建用户补全后的`MyCircleLinkedList`类的对象；
- 调用对象的`add(int item)`方法，添加数据；
- 调用对象的`output()`方法遍历链表并输出；
- 接着根据程序的输出判断程序是否正确。
​
以下是测试样例：
测试输入：2 0 5 1 1
预期输出：
​
2
0
5
1
1

package step1;
public class MyCircleLinkedList {
    private Node head; // 头结点，不存储数据
    private Node tail; // 尾结点，指向链表的最后一个节点
    private int size; // 链表大小
    // 构造函数，初始化链表
    public MyCircleLinkedList() {
        head = new Node(Integer.MIN_VALUE, null); // 头结点指向空，并设为最小值
        head.next = head; // 头结点的下一个节点指向自身，形成循环
        tail = head; // 初始化尾结点为头结点
        size = 0; // 初始链表大小为0
    }
    /**
     * 添加元素到链表尾部
     *
     * @param item 要添加的元素
     */
    public void add(int item) {
        Node node = new Node(item, tail.next); // 创建一个新节点，其指向尾结点的下一个节点
        tail.next = node; // 尾结点的下一个节点指向新节点
        tail = node; // 尾结点更新为新节点
        size++; // 链表大小增加
    }
    /**
     * 遍历链表并输出元素
     */
    public void output() {
        Node p = head; // 从头结点开始遍历
        while (p.next != head) { // 当遍历到头结点时停止，遍历完整个链表
            p = p.next; // 移动到下一个节点
            System.out.println(p.item); // 输出节点中的元素值
        }
    }
    // 检查链表是否为空
    public boolean isEmpty() {
        return head.next == head; // 头结点的下一个节点是否指向自身，是则为空链表
    }
    // 获取链表大小
    public int size() {
        return size; // 返回链表中元素的个数
    }
    // 结点内部类
    private static class Node {
        int item; // 存储的元素值
        Node next; // 指向下一个节点
​
        Node(int item, Node next) {
            this.item = item; // 初始化节点的值
            this.next = next; // 初始化节点的下一个节点
        }
    }
}

第2关：单循环链表的实现—链表的删除

**任务描述**
​
在上一关，我们已经完成了单循环链表的添加、遍历功能，我们已经可以向表中添加数据并输出，现在我们将要实现其删除功能。
​
本关任务：删除循环链表中指定位置的结点，并返回其值。
​
**编程要求**
​
本关的编程任务是补全右侧代码片段中`Begin`至`End`中间的代码，具体要求如下：
​
- 完成删除指定位置`index`处结点，并返回其值。
​
 具体请参见后续测试样例。
​
**测试说明**
​
测试过程：
​
- 平台将创建用户补全后的`MyCircleLinkedList`类的对象；
- 调用对象的`add(int item)`方法；
- 调用对象的`remove(int index)`方法，并输出返回值；
- 调用对象的`output()`方法；
- 接着根据程序的输出判断程序是否正确。

以下是测试文件代码：
package step2;
public class MyCircleLinkedListTest {
    public static void main(String[] args) {
        MyCircleLinkedList list = new MyCircleLinkedList();
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int item = in.nextInt();
            list.add(item);
        }
        System.out.println(list.remove(1));
        list.output();
    }
}

预期输入：2 0 5 1 1
预期输出：
0
2
5
1
1

​
package step2;
public class MyCircleLinkedList {
    private Node head; // 头结点，不存储数据
    private Node tail; // 尾结点，指向链表的最后一个节点
    private int size; // 链表大小
    // 构造函数，初始化链表
    public MyCircleLinkedList() {
        head = new Node(Integer.MIN_VALUE, null); // 头结点指向空，并设为最小值
        head.next = head; // 头结点的下一个节点指向自身，形成循环
        tail = head; // 初始化尾结点为头结点
        size = 0; // 初始链表大小为0
    }
    /**
     * 添加元素到链表尾部
     *
     * @param item 要添加的元素
     */
    public void add(int item) {
        Node node = new Node(item, tail.next); // 创建一个新节点，其指向尾结点的下一个节点
        tail.next = node; // 尾结点的下一个节点指向新节点
        tail = node; // 尾结点更新为新节点
        ++size; // 链表大小增加
    }
    /**
     * 遍历链表并输出元素
     */
    public void output() {
        Node p = head; // 从头结点开始遍历
        while (p.next != head) { // 当遍历到头结点时停止，遍历完整个链表
            p = p.next; // 移动到下一个节点
            System.out.println(p.item); // 输出节点中的元素值
        }
    }
    /**
     * 删除从头结点开始的第 index 个结点
     * index 从 0 开始
     *
     * @param index 要删除的节点索引
     * @return 被删除节点的值
     */
    public int remove(int index) {
        checkPosIndex(index); // 检查索引是否合法
​
        Node f = head; // 用于记录待删除节点的前一个节点
        while ((index--) > 0) {
            f = f.next; // 移动到待删除节点的前一个节点
        }
        Node del = f.next; // 获取待删除的节点
        if (del == tail) {
            tail = f; // 如果待删除节点是尾结点，则更新尾结点为其前一个节点
        }
        f.next = del.next; // 删除待删除节点
        del.next = null; // 清除节点的连接
        int oldVal = del.item; // 获取被删除节点的值
        del = null; // 释放被删除的节点
        --size; // 链表大小减少
        return oldVal; // 返回被删除节点的值
    }
    // 检查链表是否为空
    public boolean isEmpty() {
        return head.next == head; // 头结点的下一个节点是否指向自身，是则为空链表
    }
    // 获取链表大小
    public int size() {
        return size; // 返回链表中元素的个数
    }
    // 检查索引是否合法
    private void checkPosIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }
    // 结点内部类
    private static class Node {
        int item; // 存储的元素值
        Node next; // 指向下一个节点
​
        Node(int item, Node next) {
            this.item = item; // 初始化节点的值
            this.next = next; // 初始化节点的下一个节点
        }
    }
}

第3关：双向循环链表的实现—链表的插入

**任务描述**
​
在单链表中，当我们要访问某一个结点的前驱结点时，要从头结点开始遍历；要删除链表中的一个结点时，仅给出该结点的指针还不行；在指定结点前插入一个新结点，同样需要从头开始遍历。对于这些问题，双向循环链表可以解决。
​
本关任务：实现双向循环链表的添加功能。
​
**编程要求**
​
本关的编程任务是补全右侧代码片段中`Begin`至`End`中间的代码，具体要求如下：
​
- 补全`add(int item)`方法，实现双向循环链表的添加功能。
​
具体请参见后续测试样例。
​
**测试说明**
​
测试过程：
​
- 平台将创建用户补全后的`MyDoubleLinkedList `类的对象；
- 调用对象的`add(int item)`方法向链表中添加数据；
- 调用对象的`printList(boolean flag)`方法正反方向输出链表；
- 接着根据程序的输出判断程序是否正确。

以下是测试文件代码：
​
package step3;
public class MyDoubleLinkedListTest {
    public static void main(String[] args){
        MyDoubleLinkedList list = new MyDoubleLinkedList();
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int item = in.nextInt();
            list.add(item);
        }
        list.printList(true);//从左向右输出链表元素
        System.out.println();
        list.printList(false);//从右向左输出链表元素
    }
}
测试输入：1 2 3 4 5
预期输出：
​
1 2 3 4 5
5 4 3 2 1

package step3;
public class MyDoubleLinkedList {
    private Node head;  // 头结点
    private Node tail;  // 指向链表的尾结点
    private int size;  // 链表大小
    // 构造函数，初始化链表
    public MyDoubleLinkedList() {
        head = new Node(null, Integer.MIN_VALUE, null); // 头结点初始化
        head.next = head.prev = head; // 头结点的next和prev都指向自身，表示空链表
        tail = head; // 尾结点指向头结点，初始化为空链表
        size = 0; // 初始链表大小为0
    }
    /**
     * 添加元素到表尾
     *
     * @param item 要添加的元素
     */
    public void add(int item) {
        Node newNode = new Node(null, item, null); // 创建新节点
        tail.next = newNode; // 尾结点的下一个节点指向新节点
        newNode.prev = tail; // 新节点的前一个节点指向尾结点
        newNode.next = head; // 新节点的下一个节点指向头结点
        head.prev = newNode; // 头结点的前一个节点指向新节点
        tail = newNode; // 更新尾结点为新节点
        ++size; // 链表大小增加
    } 
    /**
     * 打印双向链表
     *
     * @param flag true从左向右顺序打印, false从右向左顺序打印
     */
    public void printList(boolean flag) {
        Node f = head; // 从头结点开始遍历
        if (flag) { // 向右打印
            while (f.next != head) {
                f = f.next;
                System.out.print(f.item + " "); // 打印节点元素
            }
        } else { // 向左打印
            while (f.prev != head) {
                f = f.prev;
                System.out.print(f.item + " "); // 打印节点元素
            }
        }
    }
    // 获取链表大小
    public int size() {
        return size; // 返回链表中元素的个数
    }
    // 结点内部类
    private static class Node {
        int item; // 存储的元素值
        Node next; // 直接后继引用
        Node prev; // 直接前驱引用
 
        Node(Node prev, int item, Node next) {
            this.prev = prev; // 初始化节点的前驱
            this.item = item; // 初始化节点的值
            this.next = next; // 初始化节点的后继
        }
    }
}

第4关：双向循环链表的实现—链表的删除

**任务描述**
​
上一关实现了双向循环链表的添加功能，可以向表中添加元素，现在实现双向循环链表的删除功能。
​
本关任务：在上一关的基础上，实现双向循环链表的删除功能。
​
**编程要求**
​
本关的编程任务是补全右侧代码片段中`Begin`至`End`中间的代码，具体要求如下：
​
- 补全`remove(int index)`方法，实现删除指定位置`index`处结点并返回其值的功能。
​
具体请参见后续测试样例。
​
**测试说明**
​
测试过程：
​
- 平台将创建用户补全后的`MyDoubleLinkedList`类的对象；
- 调用对象的`add(int item)`方法，向表中添加数据；
- 调用对象的`remove(int index)`方法，删除数据；
- 调用对象的`printList(boolean flag)`方法输出链表数据；
- 接着根据程序的输出判断程序是否正确。

以下是测试文件代码：
​
package step4;
public class MyDoubleLinkedListTest {
    public static void main(String[] args){
        MyDoubleLinkedList list = new MyDoubleLinkedList();
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int item = in.nextInt();
            list.add(item);
        }
        list.remove(0);
        list.printList(true);//从左向右输出链表元素
        System.out.println();
        list.printList(false);//从右向左输出链表元素
    }
}
预期输入：1 2 3 4 5
预期输出：
​
2 3 4 5 
5 4 3 2 

package step4;
public class MyDoubleLinkedList {
    private Node head;// 头结点
    private Node tail;// 指向链表的尾结点
    private int size; // 链表大小
    // 构造函数，初始化链表
    public MyDoubleLinkedList() {
        head = new Node(null, Integer.MIN_VALUE, null); // 头结点初始化
        head.next = head.prev = head; // 头结点的next和prev都指向自身，表示空链表
        tail = head; // 尾结点指向头结点，初始化为空链表
        size = 0; // 初始链表大小为0
    } 
    /**
     * 添加元素到表尾
     *
     * @param item 要添加的元素
     */
    public void add(int item) {
        Node newNode = new Node(null, item, null); // 创建新节点
        tail.next = newNode; // 尾结点的下一个节点指向新节点
        newNode.prev = tail; // 新节点的前一个节点指向尾结点
        newNode.next = head; // 新节点的下一个节点指向头结点
        head.prev = newNode; // 头结点的前一个节点指向新节点
        tail = newNode; // 更新尾结点为新节点
        ++size; // 链表大小增加
    } 
    /**
     * 删除指定位置index处的结点，并返回其值
     *
     * @param index 要删除的节点位置
     * @return 被删除节点的值
     */
    public int remove(int index) {
        checkPosIndex(index); // 检查索引是否合法
 
        Node p = head.next; // 从头结点的下一个节点开始遍历
        while ((index--) > 0) {
            p = p.next; // 移动到待删除节点
        }
        if (p == tail) {
            tail = p.prev; // 如果待删除节点是尾结点，则更新尾结点为其前一个节点
        }
        p.prev.next = p.next; // 删除待删除节点
        p.next.prev = p.prev;
        int val = p.item; // 获取被删除节点的值
        p = null; // 释放被删除节点
        --size; // 链表大小减少
        return val; // 返回被删除节点的值
    } 
    /**
     * 打印双向链表
     *
     * @param flag true从左向右顺序打印, false从右向左顺序打印
     */
    public void printList(boolean flag) {
        Node f = head; // 从头结点开始遍历
        if (flag) { // 向右打印
            while (f.next != head) {
                f = f.next;
                System.out.print(f.item + " "); // 打印节点元素
            }
        } else { // 向左打印
            while (f.prev != head) {
                f = f.prev;
                System.out.print(f.item + " "); // 打印节点元素
            }
        }
    } 
    // 获取链表大小
    public int size() {
        return size; // 返回链表中元素的个数
    }
    // 检查索引是否合法
    private void checkPosIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
    }
    // 结点内部类
    private static class Node {
        int item; // 存储的元素值
        Node next; // 直接后继引用
        Node prev; // 直接前驱引用
        Node(Node prev, int item, Node next) {
            this.prev = prev; // 初始化节点的前驱
            this.item = item; // 初始化节点的值
            this.next = next; // 初始化节点的后继
        }
    }
}

三.Java 数据结构之栈、队列

第1关：实现基于数组的栈

**任务描述**
​
在日常生活中，栈是常见的事物。餐厅里的一叠盘子、弹夹都是栈的例子。如弹夹，最先弹出的子弹是最后压入的那颗。
​
栈可以用数组实现，也可以用链表实现。
​
本关任务：基于数组，利用`Java`中泛型实现一个栈，并具有基本的入栈、出栈功能。
​
**编程要求**
​
本关的编程任务是补全右侧代码片段中`Begin`至`End`中间的代码，具体要求如下：
​
- 补全`push(T item)`方法，实现入栈功能；
- 补全`pop()`方法，实现出栈功能。
​
具体请参见后续测试样例。
​
**测试说明**
​
测试过程：
​
- 平台将创建用户补全后的`MyStack`类的对象；
- 调用对象的`push(T item)`方法，添加数据；
- 调用对象的`pop()`方法；
- 接着根据程序的输出判断程序是否正确。
​
预期输入：
to be or not to - be - - that - - - is
预期输出：
to be not that or be 

package step1;
import java.util.NoSuchElementException;
public class MyStack<T> {
    private T[] S; // 存放栈元素的数组
    private int top; // 栈顶元素下标，初始为-1
    // 默认构造函数，默认容量为1
    public MyStack() {
        this(1);
    }
    // 带容量参数的构造函数
    public MyStack(int capacity) {
        S = (T[]) new Object[capacity]; // 初始化数组
        top = -1; // 初始化栈顶元素下标为-1
    }
    /**
     * 入栈操作，将元素压入栈中
     *
     * @param item 待压入的元素
     */
    public void push(T item) {
        int len = S.length;
        if (top == len - 1) { // 如果栈已满，扩展数组容量
            resize(2 * len);
        }
        /********** Begin *********/
        S[++top] = item; // 栈顶指针加一，元素入栈
        /********** End *********/
    }
    /**
     * 返回栈顶元素并从栈中移除
     *
     * @return 返回被移除的栈顶元素
     */
    public T pop() {
        if (isEmpty()) { // 如果栈为空，则抛出异常
            throw new NoSuchElementException("栈为空！");
        }
        T out = S[top]; // 获取栈顶元素
        S[top--] = null; // 将栈顶元素置为空，栈顶指针减一
        return out; // 返回栈顶元素
    }
    /**
     * 判断栈是否为空
     *
     * @return 若栈为空，返回true，否则返回false
     */
    public boolean isEmpty() {
        return top < 0; // 根据栈顶指针是否小于0判断栈是否为空
    }
    /**
     * 动态扩展数组大小
     *
     * @param capacity 新的数组容量
     */
    private void resize(int capacity) {
        assert capacity > top;
        T[] tmp = (T[]) new Object[capacity]; // 创建新的数组
        for (int i = 0; i <= top; i++) { // 将原数组元素复制到新数组
            tmp[i] = S[i];
        }
        S = tmp; // 将新数组赋值给原数组
    }
}

第2关：实现基于链表的栈

**任务描述**
​
上一关，我们介绍了`Java`泛型，并用数组实现了栈，这一关我们将基于链表实现栈。
​
本关任务：基于单链表实现一个栈，并具备入栈、出栈功能。
​
**测试说明**
​
测试过程：
​
- 平台将创建用户补全后的`MyStack`类的对象；
- 调用对象的`push(E item)`方法，添加数据到栈中；
- 调用对象的`pop()`方法，弹出栈顶，并输出；
- 接着根据程序的输出判断程序是否正确。
​
以下是测试样例：
测试输入：to be or not to - be - - that - - - is
预期输出：to be not that or be 

package step2;
import java.util.NoSuchElementException;
public class MyStack<E> {
    private Node<E> head;//头结点
    private Node<E> top;//栈顶
    private int size;//栈中元素个数
    public MyStack() {
        head = new Node<E>();
        head.next = null;
        top = null;//栈顶初始化为null
        size = 0;
    }
    /**
     * 把item压入栈中
     *
     * @param item
     */
    public void push(E item) {
        /********** Begin *********/
        Node<E> newNode = new Node<E>(); // 创建新节点
        newNode.item = item; // 新节点存储元素值
        newNode.next = head.next; // 新节点的下一个节点指向当前头结点的下一个节点
        head.next = newNode; // 头结点的下一个节点更新为新节点
        top = newNode; // 更新栈顶为新节点
        size++; // 栈大小增加
        /********** End *********/
    }
    /**
     * 返回它栈顶元素并删除
     */
    public E pop() {
        if (isEmpty()) // 如果栈为空，抛出异常
            throw new NoSuchElementException("栈为空！");
        /********** Begin *********/
        Node<E> node = top; // 获取栈顶元素
        top = top.next; // 更新栈顶为下一个节点
        head.next = top; // 头结点的下一个节点更新为栈顶
        node.next = null; // 被删除节点的下一个节点置为null
        size--; // 栈大小减少
        return node.item; // 返回栈顶元素
        /********** End *********/
    }
    /**
     * 返回栈中元素个数
     *
     * @return
     */
    public int size() {
        return size;
    }
    /**
     * 判断一个栈是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return (null == head);
    }
    //链表结点内部类
    private static class Node<E> {
        private E item;
        private Node<E> next;
    }
}

第3关：基于数组的队列

**任务描述**
​
像栈一样，队列也是表。但使用队列时，插入在一端进行而删除则在另一端进行。
​
如同栈的情形一样，任何的表的实现对于队列来说都是合法的。
​
本关任务：基于数组实现一个循环队列，并具有基本的添加、删除功能。
​
**编程要求**
​
本关的编程任务是补全右侧代码片段中`Begin`至`End`中间的代码，具体要求如下：
​
- 补全`enqueue(T item)`方法，实现入队操作；
- 补全`dequeue()`方法，实现出队操作。
​
具体请参见后续测试样例。
​
**测试说明**
​
测试过程：
​
- 平台将创建用户补全后的`MyQueue`类的对象；
- 调用对象的`enqueue(T item)`方法，入队数据；
- 调用对象的`dequeue()`方法，出队数据，并输出返回值；
- 接着根据程序的输出判断程序是否正确。
​
以下是测试样例：
测试输入：to be or not to - be - - that - - - is
预期输出：
to
be
or
not
to
be

package step3;
public class MyQueue<T> {
    private T[] Q; // 存放队列元素的数组
    private int head; // 队首指针
    private int tail; // 队尾指针
    private int size; // 队列中元素个数
    // 默认构造函数，默认容量为1
    public MyQueue() {
        this(1);
    }
    // 带容量参数的构造函数
    public MyQueue(int capacity) {
        Q = (T[]) new Object[capacity]; // 初始化数组
        size = 0; // 初始队列元素个数为0
        head = tail = 0; // 初始化队首和队尾指针为0
    }
    /**
     * 入队操作
     *
     * @param item 待入队的元素
     */
    public void enqueue(T item) {
        Q[tail] = item; // 元素入队
        tail++; // 队尾指针后移
        tail = tail % Q.length; // 实现循环队列
        size++; // 队列元素个数增加
    }
    /**
     * 出队操作
     *
     * @return 返回出队的元素
     */
    public T dequeue() {
        /********** Begin *********/
        T out = Q[head]; // 获取队首元素
        head++; // 队首指针后移
        head = head % Q.length; // 实现循环队列
        size--; // 队列元素个数减少
        return out; // 返回出队元素
        /********** End *********/
    }
    /**
     * 判断队列是否为空
     *
     * @return 若队列为空，返回true，否则返回false
     */
    public boolean isEmpty() {
        return (head == tail) && (size < Q.length); // 判断队列是否为空
    }
    /**
     * 返回队列中元素个数
     *
     * @return 队列中元素个数
     */
    public int size() {
        return size; // 返回队列中元素个数
    }
}

第4关：基于链表的队列

**任务描述**
​
在上一关，我们用数组实现了队列，但是在使用时需要预先估计所需队列的大小。而链式队列具有内存动态分配，内存利用率高的特点，在一些无法预先估计所需队列大小的场合使用链式队列是一个十分好的选择。
​
本关任务：实现链式队列，并具备入队、出队操作。
​
**编程要求**
​
本关的编程任务是补全右侧代码片段中`Begin`至`End`中间的代码，具体要求如下：
​
- 补全`enqueue(T item)`方法，实现入队操作；
- 补全`dequeue()`方法，实现出队操作。
​
具体请参见后续测试样例。
​
**测试说明**
​
测试过程：
​
- 平台将创建用户补全后的`MyQueue`类的对象；
​
- 调用对象的`enqueue(T item)`方法，执行入队操作；
​
- 调用对象的`dequeue()`方法，执行出队操作；
​
- 输出队列中剩余元素的个数；
​
- 接着根据程序的输出判断程序是否正确。
​
以下是测试样例：
测试输入：to - be or not to - be - - that - - is
预期输出：
to be or not to be
2

package step4;
import java.util.NoSuchElementException;
public class MyQueue<T> {
    private Node<T> head; // 头结点，不存数据
    private Node<T> front; // 指向队头结点
    private Node<T> tail; // 指向队尾结点
    private int size; // 队列元素个数 
    // 默认构造函数
    public MyQueue() {
        head = new Node<T>(); // 头结点初始化
        front = tail = null; // 队头和队尾初始化为null
        size = 0; // 队列大小初始化为0
    }
    /**
     * 入队操作
     *
     * @param item 待入队的元素
     */
    public void enqueue(T item) {
        Node<T> out = tail; // 存储尾节点
        Node<T> newNode = new Node<T>(); // 创建新节点
        newNode.item = item; // 节点存储元素值
        newNode.next = null; // 新节点的下一个节点为null
        if (null == front) { // 若队列为空
            head.next = newNode; // 头结点的下一个节点为新节点
            front = newNode; // 队头指向新节点
        } else { // 若队列不为空
            out.next = newNode; // 尾节点的下一个节点为新节点
        }      
        tail = newNode; // 更新队尾为新节点
        size++; // 队列元素个数增加
    } 
    /**
     * 出队操作
     *
     * @return 返回出队的元素
     */
    public T dequeue() {
        if (isEmpty()) // 如果队列为空，抛出异常
            throw new NoSuchElementException("队列为空！")
        /********** Begin *********/
        T put = front.item; // 获取队头元素值
        head.next = front.next; // 头结点的下一个节点更新为队头的下一个节点
        front.next = null; // 队头的下一个节点置为null
        front = head.next; // 更新队头为头结点的下一个节点
        size--; // 队列元素个数减少
        // 若队列为空
        if (null == head.next) {
            front = tail = null; // 队头和队尾都置为null
        }
        return put; // 返回出队的元素
        /********** End *********/
    }
    /**
     * 返回队列中元素数量
     *
     * @return 返回队列中元素个数
     */
    public int size() {
        return size; // 返回队列中元素个数
    }
    /**
     * 判断队列是否为空
     *
     * @return 若队列为空，返回true，否则返回false
     */
    public boolean isEmpty() {
        return (front == null); // 判断队列是否为空
    }
    /**
     * 链表结点内部类
     */
    private static class Node<E> {
        private E item; // 存储的元素值
        private Node<E> next; // 下一个节点
    }
}

四.Java 数据结构之二叉树

第1关：二叉树的实现之前序遍历

**任务描述**
​
树在计算机领域中有着广泛的应用，例如在编译程序中，用树来表示源程序的语法结构；在数据库系统中，数据的信息也是用树来组织的，以及操作系统中的目录结构。
​
本关任务：完成用二叉链表存储的二叉树的前序遍历算法。
​
**编程要求**
​
本关的编程任务是补全右侧代码片段中`Begin`至`End`中间的代码，具体要求如下：
​
- 补全`preOrder(TreeNode root)`方法，实现二叉树的前序遍历功能，并输出结点的值。
​
具体请参见后续测试样例。
​
**测试说明**
​
测试过程：
​
- 平台将创建用户补全后的`BinaryTree`类的对象，
​
- 调用对象的`createTree(int arr[])`方法，用`arr`中的数据构建二叉树，并返回根结点，
​
- 调用对象的`preOrder(TreeNode root)`方法，进行前序遍历并输出结点值，
​
- 接着根据程序的输出判断程序是否正确。
​
以下是测试样例：
测试输入：
6
3 4 7 0 5 6

package step1;
public class BinaryTree {
    private TreeNode root;//根节点
    public BinaryTree() {
        root = null;
    } 
    public void preOrder(TreeNode root) {
        /********** Begin *********/    
        if(root==null){
            return;
        }
        System.out.println(root.item);//根
        preOrder(root.leftChild);//左
        preOrder(root.rightChild);//右   
        /********** End *********/
    }
 
    /**
     *以数组arr的数据，依次从上至下，从左至右构建一颗二叉树
     *
     * @param arr
     * @param n
     * @return
     */
    public TreeNode createTree(int arr[]) {
        TreeNode tmp[] = new TreeNode[arr.length + 1];
        for (int k = 1; k <= arr.length; k++) {
            TreeNode node = new TreeNode(arr[k - 1]);
            tmp[k] = node;
            if (k == 1) {
                root = node;
            } else {
                int j = k / 2;
                if (k % 2 == 0) {
                    tmp[j].leftChild = node;
                } else {
                    tmp[j].rightChild = node;
                }
            }
        }
        return root;
    }
 
    public static class TreeNode {
        private TreeNode leftChild;
        private TreeNode rightChild;
        private int item;
        public TreeNode(int item) {
            this(null, null, item);
        }
        public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
            this.leftChild = leftChild;
            this.rightChild = rightChild;
            this.item = item;
        }
    }
 
}

第2关：二叉树的实现之中序遍历

**任务描述**
​
在上一关，我们实现了二叉树的前序遍历，本关我们将实现二叉树的中序遍历。
​
本关任务：实现以二叉链表存储的二叉树的中序遍历算法。
​
**编程要求**
​
本关的编程任务是补全右侧代码片段中`Begin`至`End`中间的代码，具体要求如下：
​
- 补全`inOrder(TreeNode root)`方法，实现二叉树的中序遍历功能，并输出结点的值。
​
具体请参见后续测试样例。
​
**测试说明**
​
测试过程：
​
- 平台将创建用户补全后的`BinaryTree`类的对象，
- 调用对象的`createTree(int arr[])`方法，用`arr`中的数据构建二叉树，并返回根结点，
- 调用对象的`inOrder(TreeNode root)`方法，进行中序遍历并输出结点值，
- 接着根据程序的输出判断程序是否正确。
​
以下是测试样例：
​
测试输入：
​
6
3 4 7 0 5 6
预期输出：0 4 5 3 6 7

package step2;
public class BinaryTree {
    private TreeNode root;//根节点
    public BinaryTree() {
        root = null;
    }
    public void inOrder(TreeNode root) {
        /********** Begin *********/
        if(root==null){
            return;
        }
        inOrder(root.leftChild);//左
        System.out.println(root.item);//根   
        inOrder(root.rightChild);//右
        /********** End *********/
    }
    /**
     * 以数组arr的数据，依次从上至下，从左至右构建一颗二叉树
     *
     * @param arr
     * @param n
     * @return
     */
    public TreeNode createTree(int arr[]) {
        TreeNode tmp[] = new TreeNode[arr.length + 1];
        for (int k = 1; k <= arr.length; k++) {
            TreeNode node = new TreeNode(arr[k - 1]);
            tmp[k] = node;
            if (k == 1) {
                root = node;
            } else {
                int j = k / 2;
                if (k % 2 == 0) {
                    tmp[j].leftChild = node;
                } else {
                    tmp[j].rightChild = node;
                }
            }
        }
        return root;
    }
 
    public static class TreeNode {
        private TreeNode leftChild;
        private TreeNode rightChild;
        private int item;
        public TreeNode(int item) {
            this(null, null, item);
        }
        public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
            this.leftChild = leftChild;
            this.rightChild = rightChild;
            this.item = item;
        }
    }
}

第3关： 二叉树的实现之后序遍历

**任务描述**
​
本关任务：实现以二叉链表存储的二叉树的后序遍历算法。
​
**编程要求**
​
本关的编程任务是补全右侧代码片段中`Begin`至`End`中间的代码，具体要求如下：
​
- 补全`postOrder(TreeNode root)`方法，实现后序遍历功能，并输出结点值。
​
具体请参见后续测试样例。
​
**测试说明**
​
测试过程：
​
- 平台将创建用户补全后的`BinaryTree`类的对象，
​
- 调用对象的`createTree(int arr[])`方法，用`arr`中的数据构建二叉树，并返回根结点，
​
- 调用对象的`postOrder(TreeNode root)`方法，进行后序遍历并输出结点值，
​
- 接着根据程序的输出判断程序是否正确。
​
以下是测试样例：
​
测试输入：
6
3 4 7 0 5 6
预期输出：0 5 4 6 7 3

package step3;
public class BinaryTree {
    private TreeNode root;//根节点
    public BinaryTree() {
        root = null;
    }
    public void postOrder(TreeNode root) {
        /********** Begin *********/
        if(root==null){
            return;
        }
        postOrder(root.leftChild);//左
        postOrder(root.rightChild);//右
        System.out.println(root.item);//根
        /********** End *********/
    }
    /**
     * 以数组arr的数据，依次从上至下，从左至右构建一颗二叉树
     *
     * @param arr
     * @param n
     * @return
     */
    public TreeNode createTree(int arr[]) {
        TreeNode tmp[] = new TreeNode[arr.length + 1];
        for (int k = 1; k <= arr.length; k++) {
            TreeNode node = new TreeNode(arr[k - 1]);
            tmp[k] = node;
            if (k == 1) {
                root = node;
            } else {
                int j = k / 2;
                if (k % 2 == 0) {
                    tmp[j].leftChild = node;
                } else {
                    tmp[j].rightChild = node;
                }
            }
        }
        return root;
    }
    public static class TreeNode {
        private TreeNode leftChild;
        private TreeNode rightChild;
        private int item;
        public TreeNode(int item) {
            this(null, null, item);
        }
        public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
            this.leftChild = leftChild;
            this.rightChild = rightChild;
            this.item = item;
        }
    }
}

第4关： 向二叉树中插入叶子节点

**任务描述**
​
本关任务：向二叉树中插入左叶子节点，请补全`insertLeft(T x, Node<T> parent)`函数实现插入左叶子节点的功能。
​
**测试说明**
​
测试输入：3,9,20,null,null,15,7
​
需要你补全代码后生成如下二叉树：
    3
   / \
  9  20
    /  \
   15   7
   
点击测评后程序会调用你的函数，并使用前序遍历输出该二叉树；
预期输出：
​
3 9 20 15 7 

package step4;
class Node<T> {
    private T data; // 结点数据
    public Node<T> lChild; // 左子节点
    public Node<T> rChild; // 右子节点
    public Node() {
        data = null; // 无参构造函数初始化数据为null
        lChild = null; // 左子节点初始化为null
        rChild = null; // 右子节点初始化为null
    }
    public Node(T elem) {
        data = elem; // 有参构造函数初始化数据为传入元素值
        lChild = null; // 左子节点初始化为null
        rChild = null; // 右子节点初始化为null
    }
    public T getData() {
        return data; // 获取结点数据
    }
}
public class BinaryTree<T> {
    private final int maxNodes = 100; // 二叉树最大结点数
    public Node<T> root; // 根节点
    public BinaryTree()  // 创建一棵空二叉树
    {
        this.root = new Node<T>(); // 初始化根节点
    }
    public BinaryTree(T x)   // 创建一棵以数据元素x为根结点的二叉树
    {
        this.root = new Node<T>(x); // 初始化根节点为传入的元素值x
    }
    public BinaryTree(Node<T> node) {
        this.root = node; // 以指定节点为根节点构建二叉树
    }
    // 在当前二叉树的parent节点中插入一个新的左子结点，若已存在左子树，则将该左子树变成新左子结点的右子树
    public boolean insertLeft(T x, Node<T> parent) {
        /********** Begin *********/
        if (parent == null) return false; // 若父节点为null，返回false
        Node<T> p = new Node<T>(x); // 创建新结点
        if (parent.lChild == null) {
            parent.lChild = p; // 直接将新结点作为左子节点
        } else {
            p.rChild = parent.lChild; // 将已存在的左子节点作为新结点的右子节点
            parent.lChild = p; // 将新结点设置为左子节点
        }
        return true;
        /********** End *********/
    }
    // 在当前二叉树的parent节点中插入一个新的右子结点，若已存在右子树，则将该右子树变成新右子结点的左子树
    public boolean insertRight(T x, Node<T> parent) {
        if (parent == null) return false; // 若父节点为null，返回false
        Node<T> p = new Node<T>(x); // 创建新结点
        if (parent.rChild == null) {
            parent.rChild = p; // 直接将新结点作为右子节点
        } else {
            p.rChild = parent.rChild; // 将已存在的右子节点作为新结点的右子节点
            parent.rChild = p; // 将新结点设置为右子节点
        }
        return true;
    }
    //删除在当前二叉树的parent节点中的左子树
    public boolean deleteLeft(Node<T> parent) {
        if (parent == null) {
            return false; // 若父节点为null，返回false
        } else {
            parent.lChild = null; // 将左子节点置为null
            return true;
        }
    }
    public boolean deleteRight(Node<T> parent) {
        if (parent == null) {
            return false;
        } else {
            parent.rChild = null;
            return true;
        }
    }
    //删除在当前二叉树的parent节点中的右子树
    public boolean search(T x) {
        return false;
    } //在当前二叉树中查找数据x
    public void preorder(Node<T> node) {
        if (node == null) {
            return;
        } else {
            System.out.print(node.getData() + " ");
            preorder(node.lChild);
            preorder(node.rChild);
        }
    }
    public void inorder(Node<T> node) {
        if (node == null) {
            return;
        } else {
            inorder(node.lChild);
            System.out.print(node.getData());
            inorder(node.rChild);
        }
    }
    public void postorder(Node<T> node) {
        if (node == null) {
            return;
        } else {
            postorder(node.lChild);
            postorder(node.rChild);
            System.out.print(node.getData());
        }
    }
    public void levelorder() {
        Node<T>[] queue = new Node[this.maxNodes];
        int front, rear;
        if (this.root == null) return;
        front = -1;
        rear = 0;
        queue[rear] = this.root;
        while (front != rear) {
            front++;
            System.out.print(queue[front].getData());    /*访问队首结点的数据域*/
            /*将队首结点的左孩子结点进队列*/
            if (queue[front].lChild != null) {
                rear++;
                queue[rear] = queue[front].lChild;
            }
            /*将队首结点的右孩子结点进队列*/
​
            if (queue[front].rChild != null) {
                rear++;
                queue[rear] = queue[front].rChild;
            }
        }
    }
    //按指定方式遍历二叉树
    //i=0表示先序遍历，=1表示中序遍历，=2表示后序遍历，=3表示层次遍历
    public void traversal(int i) {
        switch (i) {
            case 0:
                preorder(this.root);
                break;
            case 1:
                inorder(this.root);
                break;
            case 2:
                postorder(this.root);
                break;
            default:
                levelorder();
        }
    }
    public int getHeight(Node<T> parent) {
        int lh, rh, max;
        if (parent != null) {
            lh = getHeight(parent.lChild);
            rh = getHeight(parent.rChild);
            max = lh > rh ? lh : rh;
            return (max + 1);
        } else return 0;
    }
}

五.Java 数据结构之二叉搜索树

第1关：二叉搜索树的介绍与构建

**任务描述**
​
顾名思义，一棵二叉搜索树是以一棵二叉树来组织的，但是在组织的时候需要满足一些特定的性质。
​
本关任务：构建一棵二叉搜索树，向其中添加结点。
​
**编程要求**
​
本关的编程任务是补全右侧代码片段中`Begin`至`End`中间的代码，具体要求如下：
​
- 补全`build(TreeNode node, int a)`方法，构建一棵二叉搜索树。
​
具体请参见后续测试样例。
​
**测试说明**
​
测试过程：
​
- 平台将创建用户补全后的`BSTree`类的对象；
- 调用对象的`insert(int key)`方法，向树中添加结点；
- 调用对象的`preOrder()`方法执行前序遍历；
- 调用对象的`inOrder()`方法执行中序遍历；
- 调用对象的`postOrder()`方法执行后序遍历；
- 接着根据程序的输出判断程序是否正确。
​
测试输入：
3 2 1 0 21
预期输出：
前序遍历: 3 2 1 0 21 
中序遍历: 0 1 2 3 21 
后序遍历: 0 1 2 21 3

package step1;
public class BSTree {
    private TreeNode root;//根结点
    public BSTree() {
        root = null;
    }
    /**
     * 向树root中插入key
     *
     * @param key 要插入的值
     */
    public void insert(int key) {
        /********** Begin *********/
        TreeNode x = root;
        TreeNode p = null;
        while (x != null) {
            p = x;
            if (key < x.item) {
                x = x.leftChild;
            } else {
                x = x.rightChild;
            }
        }
        if (null == p) {
            root = new TreeNode(key); // 若根节点为null，新建节点作为根节点
        } else if (key < p.item) {
            p.leftChild = new TreeNode(key); // 插入左子树
        } else {
            p.rightChild = new TreeNode(key); // 插入右子树
        }
        /********** End *********/
    }
    public void preOrder() {
        preOrder(root);
    }
    public void inOrder() {
        inOrder(root);
    }
    public void postOrder() {
        postOrder(root);
    }
    private void preOrder(TreeNode node) {
        if (node != null) {
            System.out.print(node.item + " ");
            preOrder(node.leftChild);
            preOrder(node.rightChild);
        }
    }
    private void inOrder(TreeNode node) {
        if (node != null) {
            inOrder(node.leftChild);
            System.out.print(node.item + " ");
            inOrder(node.rightChild);
        }
    }
    private void postOrder(TreeNode node) {
        if (node != null) {
            postOrder(node.leftChild);
            postOrder(node.rightChild);
            System.out.print(node.item + " ");
        }
    }
    public static class TreeNode {
        private TreeNode leftChild;
        private TreeNode rightChild;
        private int item;
        public TreeNode(int item) {
            this(null, null, item);
        }
        public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
            this.leftChild = leftChild;
            this.rightChild = rightChild;
            this.item = item;
        }
    }
}

第2关：二叉搜索树的删除

**任务描述**
​
在上一关，我们构建了一棵二叉搜索树，并且可以向其添加结点数据，本关将实现在二叉搜索树的删除功能。
​
本关任务是：实现二叉搜索树的删除功能。
​
**编程要求**
​
本关的编程任务是补全右侧代码片段中`Begin`至`End`中间的代码，具体要求如下：
​
- 补全`delete(TreeNode x, int key)`方法，实现删除功能。
​
具体请参见后续测试样例。
​
**测试说明**
​
测试过程：
​
- 平台将创建用户补全后的`BSTree`类的对象；
- 调用对象的`insert(int key)()`方法，构建一棵二叉搜索树；
- 调用对象的遍历方法，输出删除元素前的各种遍历结果；
- 调用对象的`delete(int key)`方法，删除元素`key`；
- 调用对象的遍历方法，输出删除元素后的各种遍历结果；
- 接着根据程序的输出判断程序是否正确。
​
以下是测试样例：
​
测试输入：3 2 1 0 21
预期输出：
前序遍历: 3 2 1 0 21 
中序遍历: 0 1 2 3 21 
后序遍历: 0 1 2 21 3 
前序遍历: 21 2 1 0 
中序遍历: 0 1 2 21 
后序遍历: 0 1 2 21 

package step2;
public class BSTree {
    private TreeNode root;//根结点
​
    public BSTree() {
        root = null;//// 初始化根节点为空
    }
    /**
     * 向树root中插入a
     *
     * @param key 要插入的值
     */
    public void insert(int key) {
        TreeNode x = root;
        TreeNode p = null;//始终指向x的父结点
        while (x != null) {
            p = x;
            if (key < x.item) {
                x = x.leftChild;
            } else {
                x = x.rightChild;
            }
        }
        if (null == p) {//空树
            root = new TreeNode(key);
        } else if (key < p.item) {
            p.leftChild = new TreeNode(key);
        } else {
            p.rightChild = new TreeNode(key);
        }
    }
    /**
     * 在树root中删除结点key
     *
     * @param key
     * @return
     */
    public void delete(int key) {
        root = delete(root, key);
    }
    private TreeNode delete(TreeNode x, int key) {
        /********** Begin *********/
        if (x == null) {
            return null; // 如果树为空，直接返回null
        }
        if (key < x.item) {
            x.leftChild = delete(x.leftChild, key); // 递归地在左子树中查找并删除指定节点
        } else if (key > x.item) {
            x.rightChild = delete(x.rightChild, key); // 递归地在右子树中查找并删除指定节点
        } else {
            if (x.leftChild == null) return x.rightChild; // 如果只有右子节点，则返回右子节点
            if (x.rightChild == null) return x.leftChild; // 如果只有左子节点，则返回左子节点
            TreeNode t = x;
            x = min(t.rightChild); // 找到右子树中最小的节点
            x.rightChild = deleteMin(t.rightChild); // 删除右子树中最小节点
            x.leftChild = t.leftChild; // 重新连接左子树
        }
        return x; // 返回处理后的树
        /********** End *********/
    }
    /**
     * 删除树x中的最小结点
     *
     * @param x
     * @return
     */
    private TreeNode deleteMin(TreeNode x) {
        if (x.leftChild == null) return x.rightChild;
        x.leftChild = deleteMin(x.leftChild);
        return x;
    }
    /**
     * 查找树x中的最小结点
     *
     * @param x
     * @return
     */
    private TreeNode min(TreeNode x) {
        TreeNode p = x;
        while (p.leftChild != null) {
            p = p.leftChild;
        }
        return p;
    }
    public void preOrder() {
        preOrder(root);
    }
    private void preOrder(TreeNode node) {
        if (node != null) {
            System.out.print(node.item + " ");
            preOrder(node.leftChild);
            preOrder(node.rightChild);
        }
    }
    public void inOrder() {
        inOrder(root);
    }
    private void inOrder(TreeNode node) {
        if (node != null) {
            inOrder(node.leftChild);
            System.out.print(node.item + " ");
            inOrder(node.rightChild);
        }
    }
    public void postOrder() {
        postOrder(root);
    }
    private void postOrder(TreeNode node) {
        if (node != null) {
            postOrder(node.leftChild);
            postOrder(node.rightChild);
            System.out.print(node.item + " ");
        }
    }
    public static class TreeNode {
        private TreeNode leftChild;
        private TreeNode rightChild;
        private int item;
​
        public TreeNode(int item) {
            this(null, null, item);
        }
        public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
            this.leftChild = leftChild;
            this.rightChild = rightChild;
            this.item = item;
        }
    }
}

第3关：二叉搜索树的查找

**任务描述**
​
我们经常需要查找一个存储在二叉搜索树中的关键字，本关卡将讨论并实现查找功能。
​
本关任务：实现二叉搜索树的查找功能，如果指定的元素`x`存在树中则返回`true`，否则返回`false`。
​
**编程要求**
​
本关的编程任务是补全右侧代码片段中`Begin`至`End`中间的代码，具体要求如下：
​
- 补全`search(int key)`方法，实现二叉搜索树的查找功能。
​
具体请参见后续测试样例。
​
**测试说明**
​
测试过程：
​
- 平台将创建用户补全后的`BSTree`类的对象；
- 调用对象的`insert(int key)`方法，构建一棵二叉搜索树；
- 调用对象的`preOrder()`方法，输出删除操作前树中的结点；
- 调用对象的`delete(int key)`方法，删除最先添加的结点和最后添加的结点；
- 调用对象的`preOrder()`方法，输出删除操作后树中的结点；
- 调用对象的`search(int key)`方法，测试原来的结点哪些还在树中；
- 接着根据程序的输出判断程序是否正确。
​
以下是测试样例：
​
测试输入：1 5 4 3 2 6
预期输出：
删除前树中的结点：1 5 4 3 2 6 
删除后树中的结点：5 4 3 2 
false true true true true false 

package step3; 
public class BSTree {
    private TreeNode root;//根结点
    public BSTree() {
        root = null;
    }
    /**
     * 向树root中插入a
     *
     * @param key 要插入的值
     */
    public void insert(int key) {
        TreeNode x = root;
        TreeNode p = null;//始终指向x的父结点
        while (x != null) {
            p = x;
            if (key < x.item) {
                x = x.leftChild;
            } else {
                x = x.rightChild;
            }
        }
        if (null == p) {//空树
            root = new TreeNode(key);
        } else if (key < p.item) {
            p.leftChild = new TreeNode(key);
        } else {
            p.rightChild = new TreeNode(key);
        }
    }
    /**
     * 判断树root中是否包含key，包含则返回true，不包含返回false
     *
     * @param key 要查找的值
     * @return 包含返回true，不包含返回false
     */
    public boolean search(int key) {
        /********** Begin *********/
        TreeNode p = root; // 从根节点开始遍历
        while (p != null && key != p.item) { // 循环直到找到节点或者遍历完整个树
            if (key < p.item) { // 如果key小于当前节点值，则继续在左子树中查找
                p = p.leftChild;
            } else { // 如果key大于当前节点值，则继续在右子树中查找
                p = p.rightChild;
            }
        }
        if (p == null) { // 如果找到了节点，则返回true；否则返回false
            return false;
        } else {
            return true;
        }
        /********** End *********/
    }
    /**
     * 在树root中删除结点key
     *
     * @param key
     * @return
     */
    public void delete(int key) {
        root = delete(root, key);
    }
    private TreeNode delete(TreeNode x, int key) {
        if (x == null) {
            return null;
        }
​
        if (key < x.item) {
            x.leftChild = delete(x.leftChild, key);
        } else if (key > x.item) {
            x.rightChild = delete(x.rightChild, key);
        } else {
            if (x.leftChild == null) return x.rightChild;
            if (x.rightChild == null) return x.leftChild;
            TreeNode t = x;
            x = min(t.rightChild);
            x.rightChild = deleteMin(t.rightChild);
            x.leftChild = t.leftChild;
        }
        return x;
    }
    /**
     * 删除树x中的最小结点
     *
     * @param x
     * @return
     */
    private TreeNode deleteMin(TreeNode x) {
        if (x.leftChild == null) return x.rightChild;
        x.leftChild = deleteMin(x.leftChild);
        return x;
    }
    /**
     * 查找树x中的最小结点
     *
     * @param x
     * @return
     */
    private TreeNode min(TreeNode x) {
        TreeNode p = x;
        while (p.leftChild != null) {
            p = p.leftChild;
        }
        return p;
    }
    public void preOrder() {
        preOrder(root);
    }
    public void inOrder() {
        inOrder(root);
    }
    public void postOrder() {
        postOrder(root);
    }
    private void preOrder(TreeNode node) {
        if (node != null) {
            System.out.print(node.item + " ");
            preOrder(node.leftChild);
            preOrder(node.rightChild);
        }
    
    private void inOrder(TreeNode node) {
        if (node != null) {
            inOrder(node.leftChild);
            System.out.print(node.item + " ");
            inOrder(node.rightChild);
        }
    }
    private void postOrder(TreeNode node) {
        if (node != null) {
            postOrder(node.leftChild);
            postOrder(node.rightChild);
            System.out.print(node.item + " ");
        }
    }
    public static class TreeNode {
        private TreeNode leftChild;
        private TreeNode rightChild;
        private int item;
        public TreeNode(int item) {
            this(null, null, item);
        }
        public TreeNode(TreeNode leftChild, TreeNode rightChild, int item) {
            this.leftChild = leftChild;
            this.rightChild = rightChild;
            this.item = item;
        }
    }
}

六.Java 数据结构之图

第1关：图的表示

任务描述
图（Graph）是表示一些事物或者状态的关系的表达方法。由于许多问题都可以归约为图的问题，人们提出了许多和图相关的算法。
本关任务：学习图的相关概念和表示，并用邻接表示图。
​
编程要求
本关的编程任务是补全右侧代码片段中Begin至End中间的代码，具体要求如下：
以邻接表表示图，补全addEdge(int v, int w)方法；
输出每个顶点所连接的边。
具体请参见后续测试样例。
​
测试说明
测试过程：
平台将创建用户补全后的Graph类的对象。
调用对象的addEdge(int v, int w)方法，添加边构造一个图。
接着根据程序的输出判断程序是否正确。
以下是测试样例：
测试输入：
5 7
1 2
1 5
2 5
2 4
2 3
3 4
4 5
（第一行中的5和7分别表示顶点数和边数，不会作为函数addEdge()的参数传入。）

预期输出：

package step1; 
import java.util.ArrayList;
public class Graph {
    private int V;//顶点数
    private int E;//边数
    private ArrayList<Integer>[] adj;//邻接表
    public Graph(int v) {
        if (v < 0) throw new IllegalArgumentException("Number of vertices must be nonnegative");
        V = v;
        E = 0;
         //index+1=v   索引+1=顶点
        //如：1顶点在0索引处
        adj = new ArrayList[V + 1];
        for (int i = 0; i <= this.V; i++) {
            adj[i] = new ArrayList<Integer>();
        }
    } 
    public void addEdge(int v, int w) {
        /********** Begin *********/
        adj[v].add(w);//顶点“w”添加到顶点“v”的邻接列表
        adj[w].add(v);//顶点“v”添加到顶点“w”的邻接列表
        this.E ++;//递增图形中边 （'E'） 的计数
 
        /********** End *********/
    }
    public String toString() {
        StringBuilder s = new StringBuilder();
        s.append(V + " 个顶点, " + E + " 条边\n");
        for (int v = 1; v <= V; v++) {
            s.append(v + ": ");
            for (int w : adj[v]) {
                s.append(w + " ");
            }
            s.append("\n");
        }
        return s.toString();
    }
}

第2关：深度优先搜索(dfs)

任务描述
像遍历树的结点那样，按照特定顺序访问图的所有顶点的算法就是图的搜索（search）算法。图的搜索过程中，利用哪些边，以何种顺序访问顶点等信息可以帮助我们分析出图的结构。
本关任务：实现深度优先搜索。
​
测试说明
测试过程：
​
平台将创建用户补全后的DFSGraph类的对象；
调用对象的void addEdge(int v, int w)方法，构造一个图；
调用对象的void DFS(int v)方法，从顶点v开始进行深度优先搜索，测试文件中是从1号顶点开始；
接着根据程序的输出判断程序是否正确。
​
以下是测试样例：
测试输入：
​
5 7
1 2
1 5
2 5
2 4
2 3
3 4
4 5
（第一行5和7表示顶点数和边数）

预期输出：

package step2;
    import java.util.ArrayList;
    public class DFSGraph {
        private boolean[] marked;//默认为false 数组中的每个索引都对应于图形中的一个顶点。当在遍历过程中访问一个顶点时，它在“marked”数组中的相应索引设置为“true”，表示该顶点已被访问。
        private int V;//顶点数
        private int E;//边数
        private ArrayList<Integer>[] adj;//邻接表
        public DFSGraph(int v) {
            if (v < 0) throw new IllegalArgumentException("Number of vertices must be nonnegative");
            V = v;
            E = 0;
            adj = new ArrayList[V + 1];
            marked = new boolean[V + 1];
            for (int i = 0; i <= this.V; i++) {
                adj[i] = new ArrayList<Integer>();
            }
        }
        public void addEdge(int v, int w) {
            adj[v].add(w);
            adj[w].add(v);
            E++;
        }
        public void DFS(int v) {
           /********** Begin *********/
          if(marked[v]){//该节点遍历过了，回溯
            return;
          }
          marked[v] = true;
          System.out.print(v + " ");
           //遍历与该节点有关系且未遍历的节点
          for (int w : adj[v]) {
              if (!marked[w]) {//检查顶点w之前是否被访问过,当没有未访问的相邻顶点时，控件将流回对“DFS”的上一个递归调用
                  DFS(w);//递归
              }
          }
            /********** End *********/
        }
        public String toString() {
            StringBuilder s = new StringBuilder();
            s.append(V + " 个顶点, " + E + " 条边\n");
            for (int v = 1; v <= V; v++) {
                s.append(v + ": ");
                for (int w : adj[v]) {
                    s.append(w + " ");
                }
                s.append("\n");
            }
            return s.toString();
        }
    }
//在递归的上下文中，“回流”是指程序从嵌套函数调用返回的过程，一个接一个地解析每个调用，直到它到达启动递归的原始函数调用。此过程类似于在递归展开时返回到调用堆栈中先前调用的控制流。
//回流”的概念可以通过调用堆栈可视化。每个函数调用都会添加到调用堆栈中，当满足基本情况或完成递归调用时，这些函数调用将从堆栈中删除（即，它们返回其值，程序“流回”到上一个函数调用）

第3关：广度优先搜索(bfs)

任务描述
本关介绍另一种图搜索算法————广度优先搜索法（Breadth First Search，BFS）。与深度搜索法一样，广度优先搜索法也得到广泛应用。广度优先搜索与深度优先搜索相互配合，就能形成图搜索方式的两个轴。
​
本关任务：实现图的广度优先搜索。
编程要求
本关的编程任务是补全右侧代码片段中Begin至End中间的代码，具体要求如下：
​
补全void BFS(int s)方法，实现广度优先搜索；
​
按访问顺序输出每个结点的值。
​
具体请参见后续测试样例。
​
测试说明
测试过程：
​
平台将创建用户补全后的BFSGraph类的对象；
​
调用对象的void addEdge(int v, int w)方法，构建一个图；
​
调用对象的void BFS(int s)方法从结点s开始广度优先搜素；
​
接着根据程序的输出判断程序是否正确。
​
以下是测试样例：
​
测试输入：
​
6 8
1 2
1 3
1 6
2 3
3 4
3 5
4 5
4 6
（6和8表示顶点数和边数）

预期输出：

package step3;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
public class BFSGraph {
    private int V; // 顶点数
    private int E; // 边数
    private boolean[] marked; // 记录已访问的顶点
    private ArrayList<Integer>[] adj; // 邻接表表示图的结构
    public BFSGraph(int v) {
        if (v < 0) throw new IllegalArgumentException("顶点数不能为负数");
        V = v;
        E = 0;
        adj = new ArrayList[V + 1];
        marked = new boolean[V + 1];
        for (int i = 0; i <= this.V; i++) {
            adj[i] = new ArrayList<Integer>(); // 初始化每个顶点的邻接表
        }
    }
    public void addEdge(int v, int w) {
        adj[v].add(w); // 添加顶点v和w之间的边
        adj[w].add(v); // 对于无向图，双向添加边
        E++;
    }
    public void BFS(int s) {
        // 从顶点s开始进行BFS遍历
        Queue<Integer> que = new LinkedList<>(); // 创建队列存储顶点
        que.offer(s); // 将起始顶点入队
        marked[s] = true; // 标记起始顶点为已访问
​
        while (!que.isEmpty()) {
            // 当队列中还有顶点时
            int v = que.poll(); // 出队一个顶点
            System.out.print(v + " "); // 访问出队的顶点（在这里打印）
​
            // 将未访问的相邻顶点入队
            for (int w : adj[v]) {
                if (!marked[w]) {
                    que.offer(w); // 入队未访问的相邻顶点
                    marked[w] = true; // 标记为已访问
                }
            }
        }
    }
    public String toString() {
        StringBuilder s = new StringBuilder();
        s.append(V + " 个顶点, " + E + " 条边\n");
        for (int v = 1; v <= V; v++) {
            s.append(v + ": ");
            for (int w : adj[v]) {
                s.append(w + " "); // 构建图的字符串表示
            }
            s.append("\n");
        }
        return s.toString();
    }
}

第4关：单源最短路径(Dijkstra算法)

任务描述
在图的应用中，有一个很重要的需求：我们需要知道从某一个点开始，到其他所有点的最短路径。这其中，Dijkstra算法是典型的最短路径算法。
​
本关任务：实现Dijkstra算法求单源最短路径。
​
测试说明
测试过程：
​
平台将创建用户补全后的ShortestPath类的对象；
​
调用对象的addEdge(int u, int v, int w)方法，添加边和边的权重信息，构建图G；
​
调用对象的Paths(int source)方法执行Dijkstra算法，求最短路径，并输出返回的最短路径，这里源点设置为1；
​
接着根据程序的输出判断程序是否正确。
​
以下是测试样例：
​
测试输入：
​
5 7
1 2 8
1 3 1
1 4 2
3 4 2
2 4 3
3 5 3
4 5 3
(5和7分别表示顶点数和边数)

预期输出：

package step4;
import java.util.*;
public class ShortestPath {
    private int V;//顶点数
    private int E;//边数
    private int[] dist;
    private ArrayList<Integer>[] adj;//邻接表
    private int[][] weight;//权重
    public ShortestPath(int v, int e) {
        V = v;
        E = e;
        dist = new int[V + 1];
        adj = new ArrayList[V + 1];
        weight = new int[V + 1][V + 1];
        for (int i = 0; i <= this.V; i++) {
            adj[i] = new ArrayList<Integer>();
        }
    }
    public void addEdge(int u, int v, int w) {
        adj[u].add(v);
        adj[v].add(u);
        weight[u][v] = weight[v][u] = w;
    }
    public int[] Paths(int source) {
        Queue<Integer> Q = new LinkedList<Integer>(); // 创建一个队列用于最短路径计算
        dist[source] = 0; // 将起始点到自身的距离设为0
        for (int i = 1; i <= V; i++) {
            if (i != source) {
                dist[i] = Integer.MAX_VALUE; // 其他顶点到源点的距离设为无穷大
            }
            Q.offer(i); // 将所有顶点加入队列
        }
        while (!Q.isEmpty()) {
            int minV = Integer.MAX_VALUE; // 最小距离设为最大值
            int v = source; // 记录最小距离对应的顶点
            for (int i = 0; i < Q.size(); i++) { // 寻找队列中距离最小的顶点
                int index = ((LinkedList<Integer>) Q).get(i);
                if (dist[index] < minV) {
                    minV = dist[index];
                    v = index;
                }
            }
            Q.poll(); // 移除队列中距离最小的顶点
            Q.remove(v);//从队列中移除标记为当前最小距离的顶点 v，当一个顶点被处理完毕并确定了最短路径后，它会被从处理队列中移除，因为它的最短路径已经被计算出来了
            for (int u : adj[v]) { // 遍历与最小距离顶点相邻的顶点
                int alt = dist[v] + weight[v][u]; // 计算经过最小距离顶点到达相邻顶点的距离
                if (alt < dist[u]) {
                    dist[u] = alt; // 更新源点到相邻顶点的距离
                }
            }
        }
        return dist; // 返回源点到各顶点的最短距离数组
        /********** End *********/
    }
    /**
     * 打印源点到所有顶点的距离，INF为无穷大
     *
     * @param dist
     */
    public void print(int[] dist) {
        for (int i = 1; i <= V; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                System.out.print("INF ");
            } else {
                System.out.print(dist[i] + " ");
            }
        }
    }
​
}

迪杰斯特拉(Dijkstra)算法图解

以上图为例，来对迪杰斯特拉进行算法演示(以顶点D为起点)。

初始状态：S是已计算出最短路径的顶点集合，U是未计算除最短路径的顶点的集合！ 第1步：将顶点D加入到S中。 此时，S={D(0)}, U={A(∞),B(∞),C(3),E(4),F(∞),G(∞)}。 注:C(3)表示C到起点D的距离是3。

第2步：将顶点C加入到S中。 上一步操作之后，U中顶点C到起点D的距离最短；因此，将C加入到S中，同时更新U中顶点的距离。以顶点F为例，之前F到D的距离为∞；但是将C加入到S之后，F到D的距离为9=(F,C)+(C,D)。 此时，S={D(0),C(3)}, U={A(∞),B(13),E(4),F(9),G(∞)}。

第3步：将顶点E加入到S中。 上一步操作之后，U中顶点E到起点D的距离最短；因此，将E加入到S中，同时更新U中顶点的距离。还是以顶点F为例，之前F到D的距离为9；但是将E加入到S之后，F到D的距离为6=(F,E)+(E,D)。 此时，S={D(0),C(3),E(4)}, U={A(∞),B(13),F(6),G(12)}。

第4步：将顶点F加入到S中。 此时，S={D(0),C(3),E(4),F(6)}, U={A(22),B(13),G(12)}。

第5步：将顶点G加入到S中。 此时，S={D(0),C(3),E(4),F(6),G(12)}, U={A(22),B(13)}。

第6步：将顶点B加入到S中。 此时，S={D(0),C(3),E(4),F(6),G(12),B(13)}, U={A(22)}。

第7步：将顶点A加入到S中。 此时，S={D(0),C(3),E(4),F(6),G(12),B(13),A(22)}。

此时，起点D到各个顶点的最短距离就计算出来了：A(22) B(13) C(3) D(0) E(4) F(6) G(12)。

七.Java 数据结构之排序

第1关：选择排序

1.简单选择排序

任务描述
给定一组无序的数据，如果要把它们从小到大重新排序，我们要如何实现这个排序功能呢？
​
本关任务：实现选择排序。
编程要求
本关的编程任务是补全右侧代码片段中Begin至End中间的代码，具体要求如下：
​
补全void sort(int arr[])方法，实现选择排序，对数组arr中的元素排序，并输出每一次排序后的结果。
具体请参见后续测试样例。
​
测试说明
测试过程：
​
平台将创建用户补全后的SelectionSort类的对象，
​
调用对象的sort(int arr[])方法，对arr中的数据排序，并输出每一次排序后的结果。
​
接着根据程序的输出判断程序是否正确。
​
以下是测试样例：
​
测试输入：2 8 7 1 3 5 6 4

预期输出：

package step1;
public class SelectionSort {
    /**
     * 选择排序
     *
     * @param arr
     */
    public static void sort(int arr[]) {
        /********** Begin *********/
        for (int i = 0; i < arr.length-1; i++) {//排序次数为数组中的元素个数减一
            for (int j = i + 1; j < arr.length; j++) {//从第二个元素开始，到末尾元素
                if (arr[j] < arr[i]) {
                    int tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                }
            }
            print(arr);
        }
        /********** End *********/
    }
    private static void print(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
 
}

//优化
package step1;
public class SelectionSort {
    /**
     * 选择排序
     *
     * @param arr
     */
    public static void sort(int arr[]) {
        /********** Begin *********/
        if(arr==null||arr.length<2){
            return;
        }
        for (int minIndex,i = 0; i < arr.length-1; i++) {
            minIndex=i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                   minIndex=j;
                }
            }
            swap(arr,i,minIndex);//交换arr[i]和arr[minIndex]
            print(arr);
        }
        /********** End *********/
    }
    private static void print(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
 
}

2.堆排序

第2关：插入排序

1.直接插入排序

编程要求
本关的编程任务是补全右侧代码片段中Begin至End中间的代码，具体要求如下：
​
补全sort(int arr[])方法，实现插入排序功能，并且输出每一次排序结果。
具体请参见后续测试样例。
​
测试说明
测试过程：
​
平台将创建用户补全后的InsertionSort类的对象，
​
调用的sort(int arr[])方法，对数组arr排序，并输出每一次排序的结果。
​
接着根据程序的输出判断程序是否正确。
​
以下是测试样例：
​
测试输入：
​
6
1 5 4 3 2 6

预期输出：

​
public class InsertionSort {
    public static void sort(int arr[]) {
        /********** Begin *********/
        for (int i = 1; i < arr.length; i++) {//共插入arr.length-1次
            int j = i;//将i的值传递给j一份
            int tmp = arr[j];//储存当前的要插入的值
            while (j > 0 && tmp < arr[j - 1]) {//注意要使tmp为定值
                arr[j] = arr[j - 1];//使arr[j]的上一个值往后移动，覆盖arr[j]
                j--;
            }
            arr[j] = tmp;//将值插入到空缺位
            print(arr);
        }
        /********** End *********/
    }
 
    private static void print(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

2.交换插入排序

public static void insertionSort(int []arr){
    if(arr=null||arr.length<2){
        return;
    }
    for(int i=1;j<arr.length;i++){
        for(int j=i-1;j>=0&&arr[j]>arr[j+1];j--){
            swap(arr,j,j+1);
        }
    }
}

第3关：归并排序

任务描述
本关任务：实现归并排序。
​
测试说明
测试过程：
​
平台将调用MergeSort类的静态方法sort(int arr[], int lo, int hi)对数组arr进行排序。这里lo和hi都是数组下标，
接着根据程序的输出判断程序是否正确。
以下是测试样例：
​
测试输入：
​
6
1 5 4 3 2 6

预期输出：

package step3; 
public class MergeSort {
 
    /**
     * 归并排序的实现函数
     * 
     * @param arr 待排序的数组
     * @param lo  左边界下标
     * @param hi  右边界下标
     */
    public static void sort(int arr[], int lo, int hi) {
        if (lo < hi) {
            // 计算中间位置
            int mid = (lo + hi) / 2;
            // 分别对左右两边进行排序
            sort(arr, lo, mid);
            sort(arr, mid + 1, hi);
            // 合并两个已排序的部分
            merge(arr, lo, mid, hi);
            // 打印当前排序结果
            print(arr);
        }
    }
    /**
     * 合并两个已排序的子数组
     * @param arr 待排序的数组
     * @param p   第一个子数组的起始下标
     * @param q   第一个子数组的结束下标
     * @param r   第二个子数组的结束下标
     */
    private static void merge(int arr[], int p, int q, int r) {
        // 计算两个子数组的长度
        int n1 = q - p + 1;
        int n2 = r - q;
        // 创建左右两个临时数组
        int L[] = new int[n1 + 1];
        int R[] = new int[n2 + 1];       
        // 将数据复制到临时数组中
        for (int i = 0; i < n1; i++) {
            L[i] = arr[p + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = arr[q + j + 1];
        }
        // 设置临时数组的最后一位为正无穷大（哨兵）
        L[n1] = Integer.MAX_VALUE;
        R[n2] = Integer.MAX_VALUE;       
        // 归并两个子数组
        int i = 0, j = 0;
        for (int k = p; k <= r; k++) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
        }
    } 
    /**
     * 打印数组元素
     * 
     * @param arr 待打印的数组
     */
    private static void print(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

归并排序 二路归并排序 Merge Sort

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用 分治法（Divide and Conquer） 的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

一般说到的归并排序就是这种二路归并。

算法描述

1.把长度为n的输入序列分成两个长度为n/2的子序列； 2.对这两个子序列分别采用归并排序； 3.将两个排序好的子序列合并成一个最终的排序序列。

动图演示

图示算法

第4关：快速排序

任务描述
本关任务：实现快速排序。
​
编程要求
本关的编程任务是补全右侧代码片段中Begin至End中间的代码，具体要求如下：
​
补全方法sort(int arr[], int low, int high)，实现快速排序功能。low,high为数组下标。
程序输出每次交换的结果。
具体请参见后续测试样例。
​
测试说明
测试过程：
​
平台将创建用户补全后的QuickSort类的对象，
​
调用对象的sort(int arr[], int low, int high)方法，对数组arr进行快速排序，并输出每次交换的结果
​
接着根据程序的输出判断程序是否正确。
​
以下是测试样例：
​
测试输入：
​
10
6 1 2 7 9 3 4 5 10 8

预期输出：

//交换数据法
package step4;
public class QuickSort {
    public void sort(int arr[], int low, int high) {
        /********** Begin *********/
        // 设置左右指针和基准值
        int i = low;
        int j = high + 1;
        int pivot = arr[low];      
        // 开始进行快速排序
        while (i < j) {
            // 从右往左找到第一个小于基准值的元素
            while (j > low && arr[--j] >= pivot) ;
            // 从左往右找到第一个大于基准值的元素
            while (i < high && arr[++i] <= pivot) ;
            // 如果左右指针相遇，结束循环
            if (i >= j) break;
            
            // 交换左右指针所指的元素
            int temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
            // 打印当前排序结果
            print(arr);
        }    
        // 将基准值放置到正确的位置
        int temp = arr[j];
        arr[j] = arr[low];
        arr[low] = temp;
        // 打印当前排序结果
        print(arr);     
        // 递归地对左右两边子数组进行快速排序
        if (i > low) sort(arr, low, j - 1);
        if (j < high) sort(arr, j + 1, high);
        /********** End *********/
    } 
    // 打印数组元素
    private static void print(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

//优化快速排序,直接插入数据
package step4; 
public class QuickSort {
    public void sort(int arr[], int low, int high) {
        /********** Begin *********/
        // 设置左右指针和基准值
        int i = low;
        int j = high + 1;
        int pivot = arr[low];        
        // 开始进行快速排序
        while (i < j) {
            // 从右往左找到第一个小于基准值的元素
            while (j > low && arr[--j] >= pivot) ;
            // 从左往右找到第一个大于基准值的元素
            while (i < high && arr[++i] <= pivot) ;
            // 如果左右指针相遇，结束循环
            if (i >= j) break;
            
            // 直接插入数据
            arr[i] = arr[i] + arr[j];
            arr[j] = arr[i] - arr[j];
            arr[i] = arr[i] - arr[j];
            // 打印当前排序结果
            print(arr);
        }       
        // 将基准值放置到正确的位置
        arr[low] = arr[low] + arr[j];
        arr[j] = arr[low] - arr[j];
        arr[low] = arr[low] - arr[j];
        // 打印当前排序结果
        print(arr);
        
        // 递归地对左右两边子数组进行快速排序
        if (i > low) sort(arr, low, j - 1);
        if (j < high) sort(arr, j + 1, high);
        /********** End *********/
    }
    // 打印数组元素
    private static void print(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}
​

第5关：堆排序

任务描述
本关任务：在本关，我们将实现另一种排序算法——堆排序(heapsort)。
编程要求
本关的编程任务是补全右侧代码片段中Begin至End中间的代码，具体要求如下：
​
补全sort(int arr[])方法，实现堆排序，对数组arr进行排序，
输出每一次堆排序的结果。
具体请参见后续测试样例。
​
测试说明
测试过程：
​
平台将调用HeapSort类的sort(int arr[])方法，对arr进行排序，并输出每次堆排序的结果
​
接着根据程序的输出判断程序是否正确。
​
以下是测试样例：
​
测试输入：
​
8
2 8 7 1 3 5 6 4

预期输出：

package step5;
public class HeapSort {
    public static void sort(int arr[]) {
        /********** Begin *********/
        int n = arr.length;    
        // 构建最大堆
        for (int k = n / 2; k >= 1; k--) {
            int l = k;
            // 下沉操作，维护最大堆性质
            while (2 * l <= n) {
                int j = 2 * l;
                // 选择左右孩子中较大的节点
                if (j < n && arr[j - 1] < arr[j + 1 - 1]) j++;
                // 若父节点大于等于孩子节点，则维持最大堆性质
                if (arr[l - 1] > arr[j - 1]) break;
                // 否则交换父节点和孩子节点的值，并继续向下调整
                int tmp = arr[l - 1];
                arr[l - 1] = arr[j - 1];
                arr[j - 1] = tmp;
                l = j;
            }
        }        
        // 从堆中取出元素，再次调整为最大堆
        while (n > 1) {
            // 交换堆顶元素（最大值）和末尾元素
            int tmp = arr[0];
            arr[0] = arr[n - 1];
            arr[n - 1] = tmp;
            // 堆的大小减一
            n--;
            int k = 1;
            // 下沉操作，维护最大堆性质
            while (2 * k <= n) {
                int j = 2 * k;
                // 选择左右孩子中较大的节点
                if (j < n && arr[j - 1] < arr[j]) j++;
                // 若父节点大于等于孩子节点，则维持最大堆性质
                if (arr[k - 1] > arr[j - 1]) break;
                // 否则交换父节点和孩子节点的值，并继续向下调整
                tmp = arr[k - 1];
                arr[k - 1] = arr[j - 1];
                arr[j - 1] = tmp;
                k = j;
            }
            // 打印当前排序结果
            print(arr);
        }
        /********** End *********/
    } 
    // 打印数组元素
    private static void print(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

交换排序

1.冒泡排序

//方法一
public static void bubbleSort(int[]arr){
    int len = arr.size();
    for (int i = 0; i < len - 1; i++) {//需要冒泡len-1次
        for (int j = 0; j < len - 1 - i; j++) {//len-1减去已经冒泡过的元素
            if (arr[j] > arr[j + 1]) {       // 相邻元素两两对比
                int temp = arr[j + 1];       // 元素交换
                arr[j + 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

//方法二
public static void bubbleSort(int[]arr){
    if(arr==null||arr.length<2){
        return;
    }
    for(int end =arr.length-1;end>0;end--){
        for(int i=0;i<end;j++){
            if(arr[i]>arr[i+1]){
                int temp=arr[i];
                arr[i]=arr[i+1];
                arr[i+1]=temp;
            }
        }
    }
}

冒泡排序 Bubble Sort

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换， 也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法描述

1.比较相邻的元素。如果第一个比第二个大，就交换它们两个； 2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数； 3.针对所有的元素重复以上的步骤，除了最后一个； 4.重复步骤1~3，直到排序完成。

动图演示

2.快速排序

八.二分查找

第1关：折半查找（二分查找）

任务描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
​
( 例如，数组[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2])。
​
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它在数组中的下标，否则返回 -1 。
​
已知的是，数组中不存在重复的元素。
​
你的算法时间复杂度必须是 O(logn) 级别。
​
编程要求
补全右侧函数，实现计算目标值T在数组nums中位置的功能，将计算的结果作为返回值返回。
​
测试说明
样例1：
​
测试输入: n = 7 , nums = [4,5,6,7,0,1,2], T = 0
​
预期输出: 4
​
样例2：
​
测试输入: n = 7 , nums = [4,5,6,7,0,1,2], T = 3
​
预期输出: -1
​
开始你的任务吧，祝你成功！

package step1;
public class Task { 
    public int search(int n,int[] nums,int T){
        /********* Begin *********/
        int l=0;//左指针
        int r=n-1;//右指针
        //搜索区域: [0,n-1]    搜索结果:  等于T的索引
        while(l<=r){
            int mid=(l+r)/2;//区间中间比较值
            if(nums[mid]>T){//要找的数在区间左边
                r=mid-1;
            }else if(nums[mid]<T){//要找的数在区间右边
                l=mid+1;
            }else{//找到了
                return mid;
            }
        }
        return -1;      
        /********* End *********/
    }
    
}

第2关：求平方根

任务描述
本关任务：编写一个能求出整数x平方根的小程序。
​
编程要求
使用二分查找，实现int mySqrt(int x)函数，求平方根的功能。
​
计算并返回 x 的平方根，其中 x 是非负整数。
​
由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。
​
测试说明
样例1：
​
测试输入：4
​
预期输出：2
​
样例2：
​
测试输入：8
​
预期输出：2
​
解释：8 的平方根是 2.82842...,  由于返回类型是整数，小数部分将被舍去。

package step2;
public class Task { 
    public int mySqrt(int x){
        /********* Begin *********/
        // 寻找第一个小于等于target的元素
        int l=0;
        int r=x;
        int ans=-1;
        //搜索区间:  [1,x]   搜索结果:  第一个平方<=target的元素索引
        while(l<=r){
            int mid = (l+r)/2;
            if((long) mid * mid <= x){
                l=mid+1;
                ans=mid;
            }else{
                r=mid-1;
            }
        }
        return ans;
        //当x=8时，[0 1 2 3 4 5 6 7 8]  
        //mid=(l+r)/2=4    [0 1 2 3 '4' 5 6 7 8]
        //mid*mid=16>8  r=mid-1=3
        //mid=(l+r)/2=1     [0 '1' 2 3 ]
        //mid*mid=1< 8  l=2 ans=1
        //mid=(l+r)/2=2     [2 3 ] 
        //mid*mid=4<8    l=3  ans =2  
        //l=r
        //rsturn and=2 
        /********* End *********/
    }
    
}

第3关：搜索数组

任务描述
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
​
( 例如，数组[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2])。
​
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它在数组中的下标，否则返回 -1 。
​
已知的是，数组中不存在重复的元素。
​
你的算法时间复杂度必须是 O(logn) 级别。
​
编程要求
补全右侧函数，实现计算目标值T在数组nums中位置的功能，将计算的结果作为返回值返回。
​
测试说明
样例1：
​
测试输入: n = 7 , nums = [4,5,6,7,0,1,2], T = 0
​
预期输出: 4
​
样例2：
​
测试输入: n = 7 , nums = [4,5,6,7,0,1,2], T = 3
​
预期输出: -1

package step3;
​
public class Task { 
    public int search(int n,int[] nums,int T){
        /********* Begin *********/
        if (n == 1) {
            return nums[0] == T ? 0 : -1;
        }
        //搜索区间： [右半段] & [左半段]  搜索结果： 等于target的索引
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (nums[mid] == T) {//找到了
                return mid;
            }
            if (nums[0] <= nums[mid]) {//mid在右半段区间中
                if (nums[0] <= T && T < nums[mid]) {//T也在右区间，向左缩小查找区间
                    r = mid - 1;
                } else {//向右缩小查找区间
                    l = mid + 1;
                }
            } else {//mid在左半段区间中
                if (nums[mid] < T && T <= nums[n - 1]) {//T也在左区间，向右缩小查找区间
                    l = mid + 1;
                } else {//向左缩小查找区间
                    r = mid - 1;
                }
            }
        }
        return -1;
        /********* End *********/
    }
}