IT小白

这个屌丝很懒，什么也没留下！

热门标签

头歌JAVA数据结构答案_头歌结构与联合的答案

作者：IT小白 | 2024-05-14 05:12:49

踩

头歌结构与联合的答案

头歌JAVA数据结构答案

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

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

package step1;
/**
 * Created by sykus on 2018/1/15.
 */
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;
    }
    /**
     * 添加到链表尾部
     *
     * @param item
     */
    public void add(int item) {
        /********** Begin *********/
        Node node = new Node(item, tail.next);
        tail.next = node;
        tail = node;
        ++size;
        /********** End *********/
    }
    /**
     * 遍历链表并输出元素
     */
    public void output() {
        /********** Begin *********/
        Node p = head;
        while (p.next != head) {
            p = p.next;
            System.out.println(p.item);
        }
        /********** End *********/
    }
    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;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

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

package step2;
/**
 * Created by sykus on 2018/1/15.
 */
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;
    }
    /**
     * 添加到链表尾部
     *
     * @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);
        /********** Begin *********/
        Node f = head;
        while ((index--) > 0) {
            f = f.next;
        }
        Node del = f.next;
        if (del == tail) {//要删除的是尾结点
            tail = f;//使tail依然指向末尾结点
        }
        f.next = del.next;
        del.next = null;
        int oldVal = del.item;
        del = null;
        --size;
        return oldVal;
        /********** End *********/
    }
    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;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

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

package step3;
/**
 * Created by sykus on 2018/1/15.
 */
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;
        tail = head;
        size = 0;
    }
    /**
     * 添加元素到表尾
     *
     * @param item
     */
    public void add(int item) {
        /********** Begin *********/
        Node newNode = new Node(null, item, null);
        tail.next = newNode;
        newNode.prev = tail;
        newNode.next = head;
        head.prev = newNode;
        tail = newNode;
        ++size;
        /********** End *********/
    }
    /**
     * 打印双向链表
     *
     * @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;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

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

package step4;
/**
 * Created by sykus on 2018/1/15.
 */
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;
        tail = head;
        size = 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);//
        /********** Begin *********/
        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;
        /********** End *********/
    }
    /**
     * 打印双向链表
     *
     * @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;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

二、Java数据结构-线性表的设计与实现

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

package step1;
/**
 * Created by zengpeng on 2017/12/25.
 */
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);
        }
        /********** Begin *********/
        elements[size++] = item;
        /********** End *********/
    }
    /**
     * 添加一个元素到指定位置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);
        }
        /********** Begin *********/
        for (int i = size; i > index; i--) {
            elements[i] = elements[i - 1];
        }
        elements[index] = item;
        size++;
        /********** End *********/
    }
    /**
     * 删除指定位置index的元素,并返回被删除的元素
     *
     * @param index
     * @return
     */
    public int remove(int index) {
        validateRange(index);
        /********** Begin *********/
        int oldVal=elements[index];
        for (int i = index; i < size - 1; i++) {
            elements[i] = elements[i + 1];
        }
        --size;
        return oldVal;
        /********** 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

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

package step2;
/**
 * Created by zengpeng on 2017/12/25.
 */
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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

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

package step3;
/**
 * Created by zengpeng on 2017/12/25.
 */
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) {
        /********** Begin *********/
        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;
        /********** End *********/
    }
    /**
     * 添加数据item到指定位置index
     * index从0开始
     * @param index
     * @param item
     */
    public void add(int index, int item) {
        checkPosIndex(index);
        /********** Begin *********/
        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;
        /********** End *********/
    }
    /**
     * 删除指定位置index处的元素并返回, index从0开始
     * @param index
     * @return
     */
    public int remove(int index) {
        checkPosIndex(index);
        /********** Begin *********/
        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;
        /********** End *********/
    }
    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;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

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

package step4;
/**
 * Created by zengpeng on 2017/12/25.
 */
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
     */
    public int get(int index) {
        checkPosIndex(index);
        /********** Begin *********/
        Node f = first.next;
        while ((index--) > 0) {
            f = f.next;
        }
        int val = f.item;
        return val;
        /********** End *********/
    }
    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;
        }
    }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

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

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

package step1;
import java.util.NoSuchElementException;
/**
 * Created by sykus on 2018/1/26.
 */
public class MyStack<T> {
    private T[] S;
    private int top;//栈顶元素下标，初始为-1
    public MyStack() {
        this(1);
    }
    public MyStack(int capacity) {
        S = (T[]) new Object[capacity];
        top = -1;
    }
    /**
     * 入栈操作，把item压入栈中
     *
     * @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("栈为空！");
        }
        /********** Begin *********/
        T val = S[top--];
        return val;
        /********** End *********/
    }
    /**
     * 判断栈是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        if (top < 0)
            return true;
        else
            return false;
    }
    /**
     * 动态扩展数组大小
     *
     * @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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

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

package step2;
import java.util.NoSuchElementException;
/**
 * Created by sykus on 2017/12/29.
 */
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;
        --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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

第3关：基于数组的队列

package step3;
/**
 * Created by zengpeng on 2018/1/30.
 */
public class MyQueue<T> {
    private T[] Q;
    private int head;
    private int tail;
    private int size;
    public MyQueue() {
        this(1);
    }
    public MyQueue(int capacity) {
        Q = (T[]) new Object[capacity];
        size = 0;
        head = tail = 0;
    }
    /**
     * 入队操作
     *
     * @param item
     */
    public void enqueue(T item) {
        /********** Begin *********/
        Q[tail] = item;
        tail = (tail + 1) % Q.length;
        ++size;
        /********** End *********/
    }
    /**
     * 出队操作
     *
     * @return
     */
    public T dequeue() {
        /********** Begin *********/
        T val = Q[head];
        head = (head + 1) % Q.length;
        --size;
        return val;
        /********** End *********/
    }
    /**
     * 判断队列是否为空
     * @return
     */
    public boolean isEmpty() {
        return (head == tail) && (size < Q.length);
    }
    public int size() {
        return size;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

第4关：基于链表的队列

package step4;
import java.util.NoSuchElementException;
/**
 * Created by sykus on 2017/12/29.
 */
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;
        size = 0;
    }
    /**
     * 入队
     *
     * @param item
     */
    public void enqueue(T item) {
        /********** Begin *********/
        Node<T> oldTail = tail;
        Node<T> newNode = new Node<T>();
        newNode.item = item;
        newNode.next = null;
        if (null == front) {//空队列
            head.next = newNode;
            front = newNode;
        } else {
            oldTail.next = newNode;
        }
        tail = newNode;
        ++size;
        /********** End *********/
    }
    /**
     * 出队
     *
     * @return
     */
    public T dequeue() {
        if (isEmpty())
            throw new NoSuchElementException("队列为空！");
        /********** Begin *********/
        T val = front.item;
        head.next = front.next;
        front.next = null;
        front = head.next;//此时队头为后继结点
        --size;
        if (null == head.next) {//出队的是队列中的最后一个元素
            front = tail = null;
        }
        return val;
        /********** End *********/
    }
    /**
     * 返回队列中元素数量
     *
     * @return
     */
    public int size() {
        return size;
    }
    /**
     * 判断一个队列是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return (front == null);
    }
    /**
     * 链表结点内部类
     */
    private static class Node<E> {
        private E item;
        private Node<E> next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

四、Java 数据结构之二叉搜索树

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

package step1;
/**
 * Created by zengpeng on 2018/3/3.
 */
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;//始终指向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);
        }
        /********** 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;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88

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

package step2;
/**
 * Created by zengpeng on 2018/3/14.
 */
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;
        }
        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;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

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

package step3;
/**
 * Created by zengpeng on 2018/3/14.
 */
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
     */
    public boolean search(int key) {
        /********** Begin *********/
        TreeNode p = root;
        while (p != null && key != p.item) {
            if (key < p.item) {
                p = p.leftChild;
            } else {
                p = p.rightChild;
            }
        }
        if (p == null) {
            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;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150

五、Java 数据结构之二叉树
第1关：二叉树的实现之前序遍历

package step1;
/**
 * Created by zengpeng on 2018/2/9.
 */
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;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

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

package step2;
/**
 * Created by zengpeng on 2018/2/12.
 */
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;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

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

package step3;
/**
 * Created by zengpeng on 2018/2/12.
 */
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;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

六、Java 数据结构之排序

第1关：选择排序

package step1;
/**
 * Created by sykus on 2018/3/20.
 */
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();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

第2关插入排序

package step2;
/**
 * Created by sykus on 2018/3/20.
 */
public class InsertionSort {
    public static void sort(int arr[]) {
        /********** Begin *********/
        for (int i = 1; i < arr.length; i++) {
            int j = i;
            int tmp = arr[j];
            while (j > 0 && tmp < arr[j - 1]) {
                arr[j] = arr[j - 1];
                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();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

第3关归并排序

package step3;
/**
 * Created by sykus on 2018/3/20.
 */
public class MergeSort {
    /**
     * lo, 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);
        }
    }
    private static void merge(int arr[], int p, int q, int r) {
        /********** Begin *********/
        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++;
            }
        }
        /********** End *********/
    }
    private static void print(int arr[]) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

第4关快速排序

package step4;
/**
 * Created by sykus on 2018/3/20.
 */
public class QuickSort {
    public void sort(int arr[], int low, int high) {
        /********** Begin *********/
        int i = low;
        int j = high + 1;
        int povit = arr[low];
        while (i < j) {
            while (j > low && arr[--j] >= povit) ;
            while (i < high && arr[++i] <= povit) ;
            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();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

第5关堆排序

package step5;
/**
 * Created by sykus on 2018/3/20.
 */
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;
            int k = 1;
            n--;
            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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

七、Java 数据结构之图

第1关图的表示

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;
        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);
        adj[w].add(v);
        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();
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

第2关深度优先搜索

package step2;
import java.util.ArrayList;
public class DFSGraph {
    private boolean[] marked;
    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 *********/
        marked[v] = true;
        System.out.print(v + " ");
        for (int w : adj[v]) {
            if (!marked[w]) {
                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();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

第3关广度优先搜索

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("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 BFS(int s) {
        /********** Begin *********/
        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;
                }
            }
        }
        /********** 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();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

第4关单源最短路径

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) {
        /********** Begin *********/
        Queue<Integer> Q = new LinkedList<Integer>();
        dist[source] = 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);
            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] + " ");
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

最后的图的代码来只班级内同学的支持！！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/567452