Java数据结构实现案例

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
package dataStructure;

/**
 * 稀疏数组
 *
 * @author zqh
 **/
public class XisuArray {
    public static void main(String[] args) {
        //初始化创建一个二维数组
        int[][] array = new int[11][11];
        array[1][2] = 1;
        array[2][3] = 2;
        System.out.println("原始的二维数组");
        for (int[] row : array) {
            for (int item : row) {
                System.out.printf("%dt", item);
            }
            System.out.println();
        }
        //获取有效的数字
        int sum = 0;
        int length = array.length;
        for (int[] row : array) {
            for (int j = 0; j < length; j++) {
                if (row[j] != 0) {
                    sum++;
                }
            }
        }
        System.out.println("有效数字：" + sum);
        //sum + 1因为第一行是存二维数组的行列 后面是值
        int[][] sparseArray = new int[sum + 1][3];
        sparseArray[0][0] = length;
        sparseArray[0][1] = length;
        sparseArray[0][2] = sum;

        //遍历二维数组给稀疏数组赋非0值
        int count = 0;
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length; j++) {
                if (array[i][j] != 0) {
                    count++;
                    sparseArray[count][0] = i;
                    sparseArray[count][1] = j;
                    sparseArray[count][2] = array[i][j];
                }
            }
        }
        System.out.println("稀疏数组");
        for (int[] ints : sparseArray) {
            System.out.printf("%dt%dt%dtn", ints[0], ints[1], ints[2]);
        }

        //将稀疏数组恢复成二维数组
        int[][] array2 = new int[sparseArray[0][0]][sparseArray[0][1]];

        for (int i = 1; i < sparseArray.length; i++) {
            array2[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }

        System.out.println("恢复后的二维数组");
        for (int[] row : array2) {
            for (int item : row) {
                System.out.printf("%dt", item);
            }
            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
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
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
package dataStructure;

import java.util.Stack;

/**
 * 单链表
 *
 * @author zqh
 **/
public class LinkedListDemo {
    public static void main(String[] args) {
        HeroNode h1 = new HeroNode(1, "小米");
        HeroNode h2 = new HeroNode(2, "小明");
        HeroNode h3 = new HeroNode(3, "小红");
        SingleLinkedList list = new SingleLinkedList();
        list.add(h1);
        list.add(h2);
        list.add(h3);
        list.list();

/*        System.out.println("递归反转链表：");
        HeroNode node1 = list.reverse(list.getHead());
        while (node1 != null && node1.next != null) {
            System.out.println(node1);
            node1 = node1.next;
        }*/

        System.out.println("链表反转后：");
        list.revHeroNode();
        list.list();

        System.out.println("反转打印（结构未反转）：");
        list.revHeroNode2();
        //修改
        HeroNode newH2 = new HeroNode(2, "小明~~");
        list.update(newH2);
        System.out.println("修改后");
        list.list();

        System.out.println("链表长度为：" + list.getLength());

        HeroNode node = list.findHeroNode(1);
        System.out.println("链表中倒数第k个节点：" + node);
    }
}

class SingleLinkedList {
    //初始化一个头节点，不存放实际数据
    private final HeroNode head = new HeroNode(0, "");

    public HeroNode getHead() {
        return head;
    }

    public void add(HeroNode heroNode) {
        HeroNode temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = heroNode;
    }

    public void update(HeroNode newHeroNode) {
        HeroNode temp = head.next;
        while (temp != null) {
            if (temp.id == newHeroNode.id) {
                temp.name = newHeroNode.name;
                break;
            }
            temp = temp.next;
        }
    }

    public void list() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        HeroNode temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }

    //返回链表有效长度 不包括头节点
    public int getLength() {
        if (head.next == null) {
            System.out.println("链表为空");
            return 0;
        }
        int length = 0;
        HeroNode temp = head.next;
        while (temp != null) {
            length++;
            temp = temp.next;
        }
        return length;
    }

    //获取链表中倒数第k个节点
    public HeroNode findHeroNode(int k) {
        if (head.next == null) {
            System.out.println("链表为空");
            return null;
        }
        int length = getLength();
        if (k < 0 || length < k) {
            return null;
        }
        HeroNode temp = head.next;
        for (int i = 0; i < length - k; i++) {
            temp = temp.next;
        }
        return temp;
    }

    //遍历反转链表结构
    public void revHeroNode() {
        //如果链表为空或只有一个元素时 则不需要反转
        if (head.next == null || head.next.next == null) {
            return;
        }
        //创建一个新的链表 遍历要反转的链表 使用头插法插入到行链表中
        HeroNode reverseHead = new HeroNode(0, ""), cur = head.next, next = null;
        while (cur != null) {
            //先保存当前节点的下一个节点
            next = cur.next;
            cur.next = reverseHead.next;
            reverseHead.next = cur;
            cur = next;
        }
        head.next = reverseHead.next;
    }

    //链表反转打印 结构未反转
    public void revHeroNode2() {
        //如果链表为空或只有一个元素时 则不需要反转
        if (head.next == null) {
            return;
        }
        HeroNode cur = head.next;
        //使用 栈的特性 先进后出
        Stack<HeroNode> stack = new Stack<>();
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }

    //使用递归反转链表 (返回链表头)
    public HeroNode reverse(HeroNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        HeroNode temp = head.next;
        HeroNode newHead = reverse(head.next);
        temp.next = head;
        head.next = null;
        return newHead;
    }

    //合并两个链表 合并后保持有序
    public HeroNode joinHeroNode(HeroNode n1, HeroNode n2) {
        //如果其中一个链表为空，则不必排序直接返回另一个链表
        if (n1 == null) {
            return n2;
        } else if (n2 == null) {
            return n1;
        }
        //节点排序
        HeroNode res = n1.id < n2.id ? n1 : n2;
        //使用递归确定链表的下一个节点
        res.next = joinHeroNode(res.next, res.next.next);
        return res;
    }
}

//链表的定义
class HeroNode {
    public int id;
    public String name;
    public HeroNode next;

    public HeroNode(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "id=" + id +
                ", name='" + name + ''' +
                '}';
    }
}

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
package dataStructure;

/**
 * 双向链表
 *
 * @author zqh
 **/
public class TwoLinkedListDemo {
    public static void main(String[] args) {
        HeroNode2 h1 = new HeroNode2(1, "小米");
        HeroNode2 h2 = new HeroNode2(2, "小明");
        HeroNode2 h3 = new HeroNode2(3, "小红");
        SingleTwoLinkedList list = new SingleTwoLinkedList();
        list.add(h1);
        list.add(h2);
        list.add(h3);
        list.list();

        list.del(3);
        System.out.println("删除后：");
        list.list();
    }
}

class SingleTwoLinkedList {
    //头结点
    private final HeroNode2 head = new HeroNode2(0, "");

    public void add(HeroNode2 node) {
        HeroNode2 temp = head;
        //添加到最后
        while (temp.next != null) {
            temp = temp.next;
        }
        //最后一个节点 = 新的节点
        temp.next = node;
        //新节点的前一个节点 = temp 即可形成双向链表
        node.pre = temp;
    }

    public void update(HeroNode2 newHeroNode) {
        HeroNode2 temp = head.next;
        while (temp != null) {
            if (temp.id == newHeroNode.id) {
                temp.name = newHeroNode.name;
                break;
            }
            temp = temp.next;
        }
    }

    public void del(int nodeId) {
        HeroNode2 temp = head;
        while (temp != null) {
            //找到要删除的节点
            if (temp.id == nodeId) {
                //将要删除的上个节点的下一个节点指向 需删除的后一个节点
                temp.pre.next = temp.next;
                //如删除的是最后一个节点 .next则=null，会触发空指针
                if (temp.next != null) {
                    temp.next.pre = temp;
                }
                break;
            }
            temp = temp.next;
        }
    }

    public void list() {
        HeroNode2 temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }
}

//双向链表的定义
class HeroNode2 {
    public int id;
    public String name;
    public HeroNode2 pre;
    public HeroNode2 next;

    public HeroNode2(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "HeroNode2{" +
                "id=" + id +
                ", name='" + name + ''' +
                '}';
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package dataStructure;

import java.util.Stack;

/**
 * 栈 特点 先进后出
 *
 * @author zqh
 **/
public class StackTest {
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();
        //入栈
        stack.push(1);
        stack.push(2);
        stack.push(3);
        //出栈 倒序打印
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}