Skip to content

Commit 8ee1ef8

Browse files
Viscaria233Viscaria233
committed
add unit test for data structures(week 1)
1 parent 7bc4437 commit 8ee1ef8

21 files changed

+735
-1053
lines changed

‎group01/895457260/code/src/datastructure/basic/ArrayList.java

Lines changed: 61 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,10 @@
11
package datastructure.basic;
22

33
public class ArrayList implements List {
4-
4+
55
private int size = 0;
6-
7-
Object[] elementData;
6+
7+
private Object[] elementData;
88

99
public ArrayList() {
1010
elementData = new Object[100];
@@ -14,37 +14,37 @@ public ArrayList(int initCapacity) {
1414
elementData = new Object[initCapacity];
1515
}
1616

17-
public void add(Object o){
17+
public void add(Object o) {
1818
autoGrow();
1919
elementData[size()] = o;
2020
size++;
2121
}
2222

23-
public void add(int index, Object o){
23+
public void add(int index, Object o) {
2424
autoGrow();
2525
System.arraycopy(elementData, index, elementData, index + 1, size() - index);
2626
elementData[index] = o;
2727
size++;
2828
}
2929

30-
public Object get(int index){
30+
public Object get(int index) {
3131
checkIndex(index);
3232
return elementData[index];
3333
}
3434

35-
public Object remove(int index){
35+
public Object remove(int index) {
3636
checkIndex(index);
3737
Object removed = elementData[index];
38-
System.arraycopy(elementData, index + 1, elementData, index, size() - index);
38+
System.arraycopy(elementData, index + 1, elementData, index, size() - index - 1);
3939
size--;
4040
return removed;
4141
}
4242

43-
public int size(){
43+
public int size() {
4444
return size;
4545
}
4646

47-
public Iterator iterator(){
47+
public Iterator iterator() {
4848
return new Iterator() {
4949
int index = -1;
5050
@Override
@@ -82,4 +82,55 @@ private String indexOutOfBoundMessage(int index) {
8282
return "index: " + index + ", size: " + size();
8383
}
8484

85+
public static void main(String[] args) {
86+
ArrayList list = new ArrayList();
87+
for (int i = 0; i < 10; ++i) {
88+
list.add(i);
89+
list.add(10 - i);
90+
}
91+
System.out.println("------------------size");
92+
System.out.println("size: " + list.size());
93+
94+
System.out.println("------------------for(int i)");
95+
for (int i = 0; i < list.size(); ++i) {
96+
System.out.print(list.get(i) + " ");
97+
}
98+
99+
System.out.println("\n-----------------iterator");
100+
Iterator iterator = list.iterator();
101+
while (iterator.hasNext()) {
102+
System.out.print(iterator.next() + " ");
103+
}
104+
105+
System.out.println("\n-----------------add at index 0 100~104");
106+
for (int i = 100; i < 105; ++i) {
107+
list.add(0, i);
108+
}
109+
list.print();
110+
System.out.println("-----------------add at last 200~204");
111+
for (int i = 200; i < 205; ++i) {
112+
list.add(list.size(), i);
113+
}
114+
list.print();
115+
116+
System.out.println("-----------------removeFirst x4");
117+
for (int i = 0; i < 4; ++i) {
118+
list.remove(0);
119+
}
120+
list.print();
121+
122+
System.out.println("\n-----------------removeLast x4");
123+
for (int i = 0; i < 4; ++i) {
124+
list.remove(list.size() - 1);
125+
}
126+
list.print();
127+
}
128+
129+
public void print() {
130+
Iterator iterator = iterator();
131+
while (iterator.hasNext()) {
132+
System.out.print(iterator.next() + " ");
133+
}
134+
System.out.println("\nsize: " + size());
135+
}
85136
}

‎group01/895457260/code/src/datastructure/basic/BinarySortedTree.java

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
package datastructure.basic;
2+
3+
/**
4+
* Created by Haochen on 2017/2/24.
5+
* TODO:
6+
*/
7+
public class BinarySortedTree<T extends Comparable> {
8+
9+
private BinaryTreeNode root = null;
10+
11+
public void traversal(Visitor visitor) {
12+
traversal(root, visitor);
13+
}
14+
15+
private void traversal(BinaryTreeNode node, Visitor visitor) {
16+
if (node == null) {
17+
return;
18+
}
19+
traversal(node.getLeft(), visitor);
20+
visitor.visit(node);
21+
traversal(node.getRight(), visitor);
22+
}
23+
24+
public interface Visitor {
25+
void visit(BinaryTreeNode node);
26+
}
27+
28+
//不递归的写法
29+
public void add(T o) {
30+
//根节点空，直接加入
31+
if (root == null) {
32+
root = new BinaryTreeNode();
33+
root.setData(o);
34+
} else {
35+
BinaryTreeNode target = root;
36+
//从根结点不断向下比较target和o，o小则往左，o大则往右，相等不加入
37+
while (true) {
38+
int compare = o.compareTo(target.getData());
39+
if (compare == 0) {//相等不加入
40+
return;
41+
} else if (compare < 0) {//o小往左
42+
if (target.getLeft() == null) {//左空则加入
43+
target.setLeft(new BinaryTreeNode());
44+
target.getLeft().setData(o);
45+
return;
46+
} else {//不空继续比较
47+
target = target.getLeft();
48+
}
49+
} else {//o大往右
50+
if (target.getRight() == null) {
51+
target.setRight(new BinaryTreeNode());
52+
target.getRight().setData(o);
53+
return;
54+
} else {
55+
target = target.getRight();
56+
}
57+
}
58+
}
59+
}
60+
}
61+
}

‎group01/895457260/code/src/datastructure/basic/Iterator.java

Lines changed: 2 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,6 @@
11
package datastructure.basic;
22

33
public interface Iterator {
4-
public boolean hasNext();
5-
public Object next();
6-
4+
boolean hasNext();
5+
Object next();
76
}

‎group01/895457260/code/src/datastructure/basic/LinkedList.java

Lines changed: 47 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
package datastructure.basic;
22

3+
import datastructure.exception.EmptyListException;
4+
35
public class LinkedList implements List {
46

57
private Node head;
@@ -8,58 +10,86 @@ public class LinkedList implements List {
810
public LinkedList() {
911
head = new Node();
1012
}
11-
12-
public void add(Object o){
13+
14+
@Override
15+
public void add(Object o) {
1316
addLast(o);
1417
}
1518

16-
public void add(int index , Object o){
19+
@Override
20+
public void add(int index , Object o) {
1721
Node pre = findNode(index - 1);
1822
Node node = new Node();
1923
node.data = o;
2024
addNode(node, pre);
2125
}
2226

23-
public Object get(int index){
27+
@Override
28+
public Object get(int index) {
2429
checkIndex(index);
25-
return findNode(index);
30+
return findNode(index).data;
2631
}
27-
public Object remove(int index){
32+
33+
@Override
34+
public Object remove(int index) {
2835
checkIndex(index);
2936
Node pre = findNode(index - 1);
3037
Node removed = pre.next;
3138
removeNode(removed, pre);
3239
return removed.data;
3340
}
34-
35-
public int size(){
41+
42+
@Override
43+
public int size() {
3644
return size;
3745
}
3846

39-
public void addFirst(Object o){
47+
public void addFirst(Object o) {
4048
Node node = new Node();
4149
node.data = o;
4250
addNode(node, head);
4351
}
44-
public void addLast(Object o){
52+
53+
public void addLast(Object o) {
4554
Node node = new Node();
4655
node.data = o;
47-
Node pre = findNode(size());
56+
Node pre = findNode(size() - 1);
4857
addNode(node, pre);
4958
}
50-
public Object removeFirst(){
59+
60+
public Object removeFirst() {
61+
if (size() == 0) {
62+
throw new EmptyListException();
63+
}
5164
Node removed = head.next;
5265
removeNode(head.next, head);
5366
return removed.data;
5467
}
55-
public Object removeLast(){
68+
69+
public Object removeLast() {
70+
if (size() == 0) {
71+
throw new EmptyListException();
72+
}
5673
return remove(size() - 1);
5774
}
58-
public Iterator iterator(){
59-
return null;
75+
76+
@Override
77+
public Iterator iterator() {
78+
return new Iterator() {
79+
Node node = head;
80+
@Override
81+
public boolean hasNext() {
82+
return node.next != null;
83+
}
84+
85+
@Override
86+
public Object next() {
87+
node = node.next;
88+
return node.data;
89+
}
90+
};
6091
}
61-
62-
92+
6393
private static class Node{
6494
Object data;
6595
Node next;

‎group01/895457260/code/src/datastructure/basic/List.java

Lines changed: 6 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,10 @@
11
package datastructure.basic;
22

33
public interface List {
4-
public void add(Object o);
5-
public void add(int index, Object o);
6-
public Object get(int index);
7-
public Object remove(int index);
8-
public int size();
4+
void add(Object o);
5+
void add(int index, Object o);
6+
Object get(int index);
7+
Object remove(int index);
8+
int size();
9+
Iterator iterator();
910
}

‎group01/895457260/code/src/datastructure/basic/Queue.java

Lines changed: 18 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -1,29 +1,42 @@
11
package datastructure.basic;
22

3+
import datastructure.exception.EmptyQueueException;
4+
35
public class Queue {
46
//数组实现自增长的循环队列
5-
private Object[] array = new Object[10];
7+
private Object[] array;
68
private int head = 0;
79
private int rear = 0;
810

9-
public void enQueue(Object o){
11+
public Queue() {
12+
this.array = new Object[10];
13+
}
14+
15+
public Queue(int initCapacity) {
16+
this.array = new Object[initCapacity];
17+
}
18+
19+
public void enQueue(Object o) {
1020
int target = mapIndex(rear);
1121
autoGrow();
1222
array[target] = o;
1323
rear++;
1424
}
1525

1626
public Object deQueue() {
27+
if (isEmpty()) {
28+
throw new EmptyQueueException();
29+
}
1730
Object obj = array[mapIndex(head)];
1831
head++;
1932
return obj;
2033
}
21-
22-
public boolean isEmpty(){
34+
35+
public boolean isEmpty() {
2336
return head == rear;
2437
}
2538

26-
public int size(){
39+
public int size() {
2740
return rear - head;
2841
}
2942

@@ -52,21 +65,4 @@ private int nextCapacity() {
5265
private int mapIndex(int index) {
5366
return index >= capacity() ? index % capacity() : index;
5467
}
55-
56-
public static void main(String[] args) {
57-
Queue queue = new Queue();
58-
for (int i = 0; i < 22; ++i) {
59-
queue.enQueue(i);
60-
}
61-
for (int i = 0; i < 6; ++i) {
62-
System.out.print(queue.deQueue() + " ");
63-
}
64-
for (int i = 22; i < 41; ++i) {
65-
queue.enQueue(i);
66-
}
67-
while (!queue.isEmpty()) {
68-
System.out.print(queue.deQueue() + " ");
69-
}
70-
System.out.println();
71-
}
7268
}

0 commit comments

Comments
 (0)