Skip to content

Commit 2ff2c32

Browse files
author
Rong Huang
authored
Merge pull request onlyliuxin#6 from eloiseSJTU/dev
finish basic data structures, pass all unit tests
2 parents b0fb337 + 021a19d commit 2ff2c32

File tree

14 files changed

+751
-0
lines changed

14 files changed

+751
-0
lines changed

‎group02/851113375/.gitignore

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
/bin/
2+
.classpath
3+
.project

‎group02/851113375/src/com/github/eloiseSJTU/coding2017/basic/ArrayList.java

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

‎group02/851113375/src/com/github/eloiseSJTU/coding2017/basic/BinaryTreeNode.java

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

‎group02/851113375/src/com/github/eloiseSJTU/coding2017/basic/Iterator.java

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

‎group02/851113375/src/com/github/eloiseSJTU/coding2017/basic/LinkedList.java

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

‎group02/851113375/src/com/github/eloiseSJTU/coding2017/basic/List.java

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
package com.github.eloiseSJTU.coding2017.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+
14+
public Iterator iterator();
15+
}

‎group02/851113375/src/com/github/eloiseSJTU/coding2017/basic/Queue.java

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

0 commit comments

Comments
 (0)