Skip to content

Commit be0e506

Browse files
dracomedracome
authored
Merge pull request onlyliuxin#9 from NaixiaoZhang/master
Add week 01 homework
2 parents 199f857 + ac3d7fe commit be0e506

File tree

14 files changed

+732
-0
lines changed

14 files changed

+732
-0
lines changed

‎group09/601862675/Week01/pom.xml

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<project xmlns="http://maven.apache.org/POM/4.0.0"
3+
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
4+
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
5+
<parent>
6+
<artifactId>coding2017</artifactId>
7+
<groupId>me.sidzh</groupId>
8+
<version>1.0-SNAPSHOT</version>
9+
</parent>
10+
<modelVersion>4.0.0</modelVersion>
11+
12+
<artifactId>Week01</artifactId>
13+
<dependencies>
14+
<dependency>
15+
<groupId>junit</groupId>
16+
<artifactId>junit</artifactId>
17+
<version>4.12</version>
18+
<scope>test</scope>
19+
</dependency>
20+
<dependency>
21+
<groupId>com.github.stefanbirkner</groupId>
22+
<artifactId>system-rules</artifactId>
23+
<version>1.16.0</version>
24+
<scope>test</scope>
25+
</dependency>
26+
</dependencies>
27+
28+
29+
</project>

‎group09/601862675/Week01/src/main/java/ArrayList.java

Lines changed: 102 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,102 @@
1+
public class ArrayList implements List{
2+
3+
private Object[] elements;
4+
5+
private static final int INITIAL_SIZE = 16;
6+
7+
public static final int MAX_LIST_SIZE = 48;
8+
9+
private int size = 0;
10+
11+
private int capacity = 0;
12+
13+
public ArrayList() {
14+
elements = new Object[INITIAL_SIZE];
15+
capacity = INITIAL_SIZE;
16+
}
17+
18+
public void add(int index, Object obj) {
19+
if (index < 0 || index > size) {
20+
throw new IndexOutOfBoundsException();
21+
}
22+
ensureSpace();
23+
if (index == size) {
24+
add(obj);
25+
} else {
26+
System.arraycopy(elements, index, elements, index + 1, size - index);
27+
elements[index] = obj;
28+
size++;
29+
}
30+
}
31+
32+
public void add(Object obj) {
33+
ensureSpace();
34+
elements[size++] = obj;
35+
}
36+
37+
public int size() {
38+
return size;
39+
}
40+
41+
@Override
42+
public String toString() {
43+
StringBuilder builder = new StringBuilder("List: [ ");
44+
for (int i = 0; i < size; ++ i) {
45+
builder.append(elements[i]).append(" ");
46+
}
47+
builder.append("]");
48+
return builder.toString();
49+
}
50+
51+
private void ensureSpace() {
52+
if (size == capacity) {
53+
if (size == MAX_LIST_SIZE) {
54+
throw new IndexOutOfBoundsException();
55+
}
56+
int newCapacity = capacity*2 > MAX_LIST_SIZE ? MAX_LIST_SIZE : capacity*2;
57+
grow(newCapacity);
58+
}
59+
}
60+
61+
private void grow(int newLength) {
62+
Object[] newElements = new Object[newLength];
63+
System.arraycopy(elements, 0, newElements, 0, elements.length);
64+
elements = newElements;
65+
capacity = newLength;
66+
}
67+
68+
public Object get(int index) {
69+
if (index < 0 || index >= size) {
70+
throw new IllegalArgumentException();
71+
}
72+
73+
return elements[index];
74+
}
75+
76+
public Object remove(int index) {
77+
if (index < 0 || index >= size) {
78+
throw new IllegalArgumentException();
79+
}
80+
Object toRemove = elements[index];
81+
System.arraycopy(elements, index + 1, elements, index, size - index -1);
82+
--size;
83+
return toRemove;
84+
}
85+
86+
public Iterator iterator() {
87+
return new ArrayListIterator();
88+
}
89+
90+
private class ArrayListIterator implements Iterator{
91+
92+
private int pos = 0;
93+
94+
public boolean hasNext() {
95+
return pos < size();
96+
}
97+
98+
public Object next() {
99+
return elements[pos++];
100+
}
101+
}
102+
}

‎group09/601862675/Week01/src/main/java/BinaryTree.java

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

‎group09/601862675/Week01/src/main/java/Iterator.java

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
/**
2+
* Created by spike on 2/19/17.
3+
*/
4+
public interface Iterator {
5+
boolean hasNext();
6+
Object next();
7+
}

‎group09/601862675/Week01/src/main/java/LinkedList.java

Lines changed: 128 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,128 @@
1+
/**
2+
* Created by spike on 2/19/17.
3+
*/
4+
public class LinkedList implements List {
5+
6+
private LinkedListNode head;
7+
private LinkedListNode tail;
8+
private int size;
9+
10+
private static class LinkedListNode {
11+
private Object data;
12+
private LinkedListNode prev;
13+
private LinkedListNode next;
14+
15+
private LinkedListNode(Object data, LinkedListNode prev, LinkedListNode next) {
16+
this.data = data;
17+
this.prev = prev;
18+
this.next = next;
19+
}
20+
}
21+
22+
@Override
23+
public String toString() {
24+
StringBuilder builder = new StringBuilder("List: [ ");
25+
LinkedListNode idx = head;
26+
while (idx != null) {
27+
builder.append(idx.data);
28+
builder.append(" ");
29+
idx = idx.next;
30+
}
31+
32+
builder.append("]");
33+
return builder.toString();
34+
}
35+
36+
public void add(int index, Object object) {
37+
if (index < 0 || index > size) {
38+
throw new IllegalArgumentException();
39+
}
40+
if (index == size) { // insert after
41+
add(object);
42+
} else { // insert before
43+
LinkedListNode target = findNodeByIndex(index);
44+
LinkedListNode nd = new LinkedListNode(object, target.prev, target);
45+
if (head == target) {
46+
head = nd;
47+
} else {
48+
target.prev.next = nd;
49+
}
50+
}
51+
++size;
52+
}
53+
54+
public void add(Object object) {
55+
if (head == null) {
56+
LinkedListNode nd = new LinkedListNode(object, null, null);
57+
head = tail = nd;
58+
} else {
59+
LinkedListNode nd = new LinkedListNode(object, tail, null);
60+
tail.next = nd;
61+
tail = nd;
62+
}
63+
++size;
64+
}
65+
66+
public Object get(int index) {
67+
if (index < 0 || index >= size) {
68+
throw new IllegalArgumentException();
69+
}
70+
LinkedListNode target = findNodeByIndex(index);
71+
return target.data;
72+
}
73+
74+
public Object remove(int index) {
75+
if (index < 0 || index >= size) {
76+
throw new IllegalArgumentException();
77+
}
78+
LinkedListNode target = findNodeByIndex(index);
79+
if (target == head) {
80+
if (head == tail) {
81+
head = tail = null;
82+
} else {
83+
head = head.next;
84+
head.prev = null;
85+
}
86+
} else if (target == tail) {
87+
tail = tail.prev;
88+
tail.next = null;
89+
} else {
90+
target.prev.next = target.next;
91+
target.next.prev = target.prev;
92+
}
93+
target.prev = target.next = null;
94+
--size;
95+
return target.data;
96+
}
97+
98+
private LinkedListNode findNodeByIndex(int index) {
99+
LinkedListNode target = head;
100+
for (int i = 0; i != index; ++i) {
101+
target = target.next;
102+
}
103+
return target;
104+
}
105+
106+
public int size() {
107+
return size;
108+
}
109+
110+
public Iterator iterator() {
111+
return new LinkedListIterator();
112+
}
113+
114+
private class LinkedListIterator implements Iterator {
115+
116+
LinkedListNode cursor = head;
117+
118+
public boolean hasNext() {
119+
return cursor != null;
120+
}
121+
122+
public Object next() {
123+
Object toRet = cursor.data;
124+
cursor = cursor.next;
125+
return toRet;
126+
}
127+
}
128+
}

‎group09/601862675/Week01/src/main/java/List.java

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
public interface List {
2+
void add(int index, Object object);
3+
void add(Object object);
4+
Object get(int i);
5+
Object remove(int i);
6+
int size();
7+
}

‎group09/601862675/Week01/src/main/java/Queue.java

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
public class Queue {
2+
3+
private LinkedList llist = new LinkedList();
4+
5+
public void enQueue(Object o){
6+
llist.add(o);
7+
}
8+
9+
public Object deQueue(){
10+
if (llist.size() == 0) {
11+
throw new UnsupportedOperationException();
12+
}
13+
return llist.remove(0);
14+
}
15+
16+
public boolean isEmpty(){
17+
return llist.size() == 0;
18+
}
19+
20+
public int size(){
21+
return llist.size();
22+
}
23+
24+
@Override
25+
public String toString() {
26+
StringBuilder builder = new StringBuilder("Queue: [ ");
27+
Iterator iter = llist.iterator();
28+
while (iter.hasNext()) {
29+
builder.append(iter.next());
30+
builder.append(" ");
31+
}
32+
builder.append("]");
33+
return builder.toString();
34+
}
35+
}

‎group09/601862675/Week01/src/main/java/Stack.java

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
public class Stack {
2+
private ArrayList elementData = new ArrayList();
3+
4+
public void push(Object o){
5+
elementData.add(o);
6+
}
7+
8+
public Object pop(){
9+
if (elementData.size() == 0) {
10+
throw new UnsupportedOperationException();
11+
}
12+
return elementData.remove(elementData.size()-1);
13+
}
14+
15+
public Object peek(){
16+
return elementData.get(elementData.size()-1);
17+
}
18+
19+
public boolean isEmpty(){
20+
return elementData.size() == 0;
21+
}
22+
23+
public int size(){
24+
return elementData.size();
25+
}
26+
27+
@Override
28+
public String toString() {
29+
StringBuilder builder = new StringBuilder("Stack: [ ");
30+
Iterator iter = elementData.iterator();
31+
while (iter.hasNext()) {
32+
builder.append(iter.next());
33+
builder.append(" ");
34+
}
35+
builder.append("]");
36+
return builder.toString();
37+
}
38+
}

0 commit comments

Comments
 (0)