Skip to content

Commit f21458d

Browse files
zavierzavier
committed
第一周数据结构作业
1 parent d4a25d6 commit f21458d

File tree

13 files changed

+729
-0
lines changed

13 files changed

+729
-0
lines changed

‎group01/765324639/src/zavier/week01/basic/ArrayList.java

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
package zavier.week01.basic;
2+
3+
import java.util.Arrays;
4+
5+
public class ArrayList implements List {
6+
7+
private int size = 0;
8+
9+
private Object[] elementData = new Object[100];
10+
11+
@Override
12+
public void add(Object o) {
13+
ensureCapacity(size + 1);
14+
elementData[size++] = o;
15+
}
16+
17+
private void ensureCapacity(int size) {
18+
if (size > elementData.length) {
19+
grow();
20+
}
21+
}
22+
23+
private void grow() {
24+
elementData = Arrays.copyOf(elementData, size * 2);
25+
}
26+
27+
@Override
28+
public void add(int index, Object o) {
29+
rangeCheckForAdd(index);
30+
ensureCapacity(size + 1);
31+
System.arraycopy(elementData, index, elementData, index + 1, size - index);
32+
elementData[index] = o;
33+
size++;
34+
}
35+
36+
private void rangeCheckForAdd(int index) {
37+
if (index < 0 || index > size) {
38+
throw new IndexOutOfBoundsException();
39+
}
40+
}
41+
42+
@Override
43+
public Object get(int index) {
44+
rangeCheck(index);
45+
return elementData[index];
46+
}
47+
48+
private void rangeCheck(int index) {
49+
if (index >= size || index < 0) {
50+
throw new IndexOutOfBoundsException();
51+
}
52+
}
53+
54+
@Override
55+
public Object remove(int index) {
56+
rangeCheck(index);
57+
Object dest = elementData[index];
58+
System.arraycopy(elementData, index + 1, elementData, index, size - index - 1);
59+
size--;
60+
return dest;
61+
}
62+
63+
@Override
64+
public int size() {
65+
return size;
66+
}
67+
68+
public Iterator iterator() {
69+
return new Iterator() {
70+
71+
private int index = 0;
72+
73+
@Override
74+
public Object next() {
75+
return elementData[index++];
76+
}
77+
78+
@Override
79+
public boolean hasNext() {
80+
return index < size;
81+
}
82+
};
83+
}
84+
85+
}

‎group01/765324639/src/zavier/week01/basic/BinaryTreeNode.java

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
package zavier.week01.basic;
2+
3+
public class BinaryTreeNode {
4+
5+
private Integer data;
6+
private BinaryTreeNode left;
7+
private BinaryTreeNode right;
8+
9+
public BinaryTreeNode(Integer data) {
10+
this.data = data;
11+
}
12+
13+
public Integer getData() {
14+
return data;
15+
}
16+
17+
public void setData(Integer data) {
18+
this.data = data;
19+
}
20+
21+
public BinaryTreeNode getLeft() {
22+
return left;
23+
}
24+
25+
public void setLeft(BinaryTreeNode left) {
26+
this.left = left;
27+
}
28+
29+
public BinaryTreeNode getRight() {
30+
return right;
31+
}
32+
33+
public void setRight(BinaryTreeNode right) {
34+
this.right = right;
35+
}
36+
37+
public BinaryTreeNode insert(Integer o) {
38+
39+
if (o > this.data) {
40+
41+
if (this.getRight() == null) {
42+
BinaryTreeNode node = new BinaryTreeNode(o);
43+
this.setRight(node);
44+
return node;
45+
} else {
46+
return this.getRight().insert(o);
47+
}
48+
49+
} else {
50+
51+
if (this.getLeft() == null) {
52+
BinaryTreeNode node = new BinaryTreeNode(o);
53+
this.setLeft(node);
54+
return node;
55+
} else {
56+
return this.getLeft().insert(o);
57+
}
58+
59+
}
60+
61+
}
62+
63+
}

‎group01/765324639/src/zavier/week01/basic/Iterator.java

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
package zavier.week01.basic;
2+
3+
public interface Iterator {
4+
public boolean hasNext();
5+
6+
public Object next();
7+
8+
}

‎group01/765324639/src/zavier/week01/basic/LinkedList.java

Lines changed: 148 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,148 @@
1+
package zavier.week01.basic;
2+
3+
import java.util.NoSuchElementException;
4+
5+
public class LinkedList implements List {
6+
7+
private Node head;
8+
9+
private int size = 0;
10+
11+
@Override
12+
public void add(Object o) {
13+
if (head == null) {
14+
head = new Node(o);
15+
} else {
16+
Node tail = head;
17+
while (tail.next != null) {
18+
tail = tail.next;
19+
}
20+
Node node = new Node(o);
21+
22+
tail.next = node;
23+
}
24+
size++;
25+
}
26+
27+
@Override
28+
public void add(int index, Object o) {
29+
rangeCheckForAdd(index);
30+
if (index == 0) {
31+
Node node = new Node(o);
32+
node.next = head;
33+
head = node;
34+
} else {
35+
Node preDest = head;
36+
for (int i = 0; i < index - 1; i++) {
37+
preDest = preDest.next;
38+
}
39+
Node node = new Node(o);
40+
node.next = preDest.next;
41+
preDest.next = node;
42+
}
43+
44+
size++;
45+
}
46+
47+
private void rangeCheckForAdd(int index) {
48+
if (index > size || index < 0) {
49+
throw new IndexOutOfBoundsException();
50+
}
51+
}
52+
53+
@Override
54+
public Object get(int index) {
55+
rangeCheck(index);
56+
57+
Node dest = head;
58+
for (int i = 0; i < index; i++) {
59+
dest = dest.next;
60+
}
61+
return dest.data;
62+
}
63+
64+
private void rangeCheck(int index) {
65+
if (index >= size || index < 0) {
66+
throw new IndexOutOfBoundsException();
67+
}
68+
}
69+
70+
@Override
71+
public Object remove(int index) {
72+
rangeCheck(index);
73+
74+
Node preDest = head;
75+
for (int i = 0; i < index - 1; i++) {
76+
preDest = preDest.next;
77+
}
78+
Node dest = preDest.next;
79+
preDest.next = dest.next;
80+
81+
size--;
82+
return dest.data;
83+
}
84+
85+
@Override
86+
public int size() {
87+
return size;
88+
}
89+
90+
public void addFirst(Object o) {
91+
Node node = new Node(o);
92+
node.next = head;
93+
head = node;
94+
size++;
95+
}
96+
97+
public void addLast(Object o) {
98+
Node lastNode = head;
99+
while (lastNode.next != null) {
100+
lastNode = lastNode.next;
101+
}
102+
103+
Node node = new Node(o);
104+
lastNode.next = node;
105+
size++;
106+
}
107+
108+
public Object removeFirst() {
109+
if (head == null) {
110+
throw new NoSuchElementException();
111+
}
112+
Node target = head;
113+
head = head.next;
114+
size--;
115+
return target.data;
116+
}
117+
118+
public Object removeLast() {
119+
if (head == null) {
120+
throw new NoSuchElementException();
121+
}
122+
123+
Node preDest = head;
124+
while (preDest.next.next != null) {
125+
preDest = preDest.next;
126+
}
127+
Node dest = preDest.next;
128+
preDest.next = null;
129+
130+
size--;
131+
return dest.data;
132+
}
133+
134+
public Iterator iterator() {
135+
return null;
136+
}
137+
138+
139+
private static class Node {
140+
Object data;
141+
Node next;
142+
143+
Node(Object data) {
144+
this.data = data;
145+
next = null;
146+
}
147+
}
148+
}

‎group01/765324639/src/zavier/week01/basic/List.java

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
package zavier.week01.basic;
2+
3+
public interface List {
4+
public void add(Object o);
5+
6+
public void add(int index, Object o);
7+
8+
public Object get(int index);
9+
10+
public Object remove(int index);
11+
12+
public int size();
13+
}

‎group01/765324639/src/zavier/week01/basic/Queue.java

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package zavier.week01.basic;
2+
3+
public class Queue {
4+
5+
private LinkedList list = new LinkedList();
6+
7+
public void enQueue(Object o) {
8+
list.add(o);
9+
}
10+
11+
public Object deQueue() {
12+
if (list.size() == 0) {
13+
return null;
14+
}
15+
return list.removeFirst();
16+
}
17+
18+
public boolean isEmpty() {
19+
return list.size() == 0;
20+
}
21+
22+
public int size() {
23+
return list.size();
24+
}
25+
}

‎group01/765324639/src/zavier/week01/basic/Stack.java

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
package zavier.week01.basic;
2+
3+
import java.util.EmptyStackException;
4+
5+
public class Stack {
6+
private ArrayList elementData = new ArrayList();
7+
8+
public void push(Object o) {
9+
elementData.add(o);
10+
}
11+
12+
public Object pop() {
13+
if (elementData.size() == 0) {
14+
throw new EmptyStackException();
15+
}
16+
return elementData.remove(elementData.size() - 1);
17+
}
18+
19+
public Object peek() {
20+
if (elementData.size() == 0) {
21+
throw new EmptyStackException();
22+
}
23+
return elementData.get(elementData.size() - 1);
24+
}
25+
26+
public boolean isEmpty() {
27+
return elementData.size() == 0;
28+
}
29+
30+
public int size() {
31+
return elementData.size();
32+
}
33+
}

‎group01/765324639/src/zavier/week01/test/AllTests.java

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,12 @@
1+
package zavier.week01.test;
2+
3+
import org.junit.runner.RunWith;
4+
import org.junit.runners.Suite;
5+
import org.junit.runners.Suite.SuiteClasses;
6+
7+
@RunWith(Suite.class)
8+
@SuiteClasses({ArrayListTest.class, LinkedListTest.class, QueueTest.class, StackTest.class,
9+
BinaryTreeNodeTest.class})
10+
public class AllTests {
11+
12+
}

0 commit comments

Comments
 (0)