Skip to content

Commit a3262c5

Browse files
author
GallenZhang
committed
Merge remote-tracking branch 'zavier/master'
2 parents 094f0be + 582902a commit a3262c5

16 files changed

+1006
-0
lines changed

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

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

‎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 traverse(Visitor visitor) {
12+
traverse(root, visitor);
13+
}
14+
15+
private void traverse(BinaryTreeNode node, Visitor visitor) {
16+
if (node == null) {
17+
return;
18+
}
19+
traverse(node.getLeft(), visitor);
20+
visitor.visit(node);
21+
traverse(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/BinaryTreeNode.java

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package datastructure.basic;
2+
3+
public class BinaryTreeNode {
4+
5+
private Object data;
6+
private BinaryTreeNode left;
7+
private BinaryTreeNode right;
8+
9+
public Object getData() {
10+
return data;
11+
}
12+
public void setData(Object data) {
13+
this.data = data;
14+
}
15+
public BinaryTreeNode getLeft() {
16+
return left;
17+
}
18+
public void setLeft(BinaryTreeNode left) {
19+
this.left = left;
20+
}
21+
public BinaryTreeNode getRight() {
22+
return right;
23+
}
24+
public void setRight(BinaryTreeNode right) {
25+
this.right = right;
26+
}
27+
28+
public BinaryTreeNode insert(Object o){
29+
return null;
30+
}
31+
32+
}

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

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

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

Lines changed: 132 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,132 @@
1+
package datastructure.basic;
2+
3+
import datastructure.exception.EmptyListException;
4+
5+
public class LinkedList implements List {
6+
7+
private Node head;
8+
private int size;
9+
10+
public LinkedList() {
11+
head = new Node();
12+
}
13+
14+
@Override
15+
public void add(Object o) {
16+
addLast(o);
17+
}
18+
19+
@Override
20+
public void add(int index , Object o) {
21+
Node pre = findNode(index - 1);
22+
Node node = new Node();
23+
node.data = o;
24+
addNode(node, pre);
25+
}
26+
27+
@Override
28+
public Object get(int index) {
29+
checkIndex(index);
30+
return findNode(index).data;
31+
}
32+
33+
@Override
34+
public Object remove(int index) {
35+
checkIndex(index);
36+
Node pre = findNode(index - 1);
37+
Node removed = pre.next;
38+
removeNode(removed, pre);
39+
return removed.data;
40+
}
41+
42+
@Override
43+
public int size() {
44+
return size;
45+
}
46+
47+
public void addFirst(Object o) {
48+
Node node = new Node();
49+
node.data = o;
50+
addNode(node, head);
51+
}
52+
53+
public void addLast(Object o) {
54+
Node node = new Node();
55+
node.data = o;
56+
Node pre = findNode(size() - 1);
57+
addNode(node, pre);
58+
}
59+
60+
public Object removeFirst() {
61+
if (size() == 0) {
62+
throw new EmptyListException();
63+
}
64+
Node removed = head.next;
65+
removeNode(head.next, head);
66+
return removed.data;
67+
}
68+
69+
public Object removeLast() {
70+
if (size() == 0) {
71+
throw new EmptyListException();
72+
}
73+
return remove(size() - 1);
74+
}
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+
};
91+
}
92+
93+
private static class Node{
94+
Object data;
95+
Node next;
96+
}
97+
98+
private Node findNode(int index) {
99+
if (index == -1) {
100+
return head;
101+
} else {
102+
checkIndex(index);
103+
}
104+
Node node = head.next;
105+
for (int i = 0; i < index; ++i) {
106+
node = node.next;
107+
}
108+
return node;
109+
}
110+
111+
private void checkIndex(int index) {
112+
if (index >= size() || index < 0) {
113+
throw new IndexOutOfBoundsException(indexOutOfBoundMessage(index));
114+
}
115+
}
116+
117+
private String indexOutOfBoundMessage(int index) {
118+
return "index: " + index + ", size: " + size();
119+
}
120+
121+
private void addNode(Node node, Node pre) {
122+
node.next = pre.next;
123+
pre.next = node;
124+
size++;
125+
}
126+
127+
private void removeNode(Node node, Node pre) {
128+
pre.next = node.next;
129+
node.next = null;
130+
size--;
131+
}
132+
}

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

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
package datastructure.basic;
2+
3+
public interface List {
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();
10+
}

0 commit comments

Comments
 (0)