Skip to content

Commit 9382b6c

Browse files
nusubmarine01nusubmarine01
authored
Merge pull request onlyliuxin#14 from sawyerwu/master
the first homework on 2.26
2 parents 7dfc9d3 + ef92c01 commit 9382b6c

File tree

8 files changed

+350
-0
lines changed

8 files changed

+350
-0
lines changed

‎group03/664269713/DataStructure/.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

‎group03/664269713/DataStructure/src/com/ace/coding/ArrayList.java

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
package com.ace.coding;
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+
public void add(Object o){
12+
checkArrayLength();
13+
elementData[size++] = o;
14+
}
15+
16+
private void checkArrayLength(){
17+
if(elementData.length < size() + 1){
18+
// expand the origin length of the array
19+
int newLength = size * 2 + 1;
20+
elementData = Arrays.copyOf(elementData, newLength);
21+
}
22+
}
23+
24+
private void checkIndex(int index){
25+
if(index < 0 || index >= size()){
26+
throw new IndexOutOfBoundsException("Index " + index + " is invalid.");
27+
}
28+
}
29+
30+
public void add(int index, Object o){
31+
checkIndex(index);
32+
checkArrayLength();
33+
System.arraycopy(elementData, index, elementData, index+1, size() - index);
34+
elementData[index] = o;
35+
size++;
36+
}
37+
38+
public Object get(int index){
39+
checkIndex(index);
40+
return elementData[index];
41+
}
42+
43+
public Object remove(int index){
44+
checkIndex(index);
45+
Object obj = elementData[index];
46+
if(index == size() - 1){
47+
elementData[index] = null;
48+
} else {
49+
System.arraycopy(elementData, index + 1, elementData, index, size() - index - 1);
50+
}
51+
size--;
52+
return obj;
53+
}
54+
55+
public int size(){
56+
return size;
57+
}
58+
59+
public Iterator iterator(){
60+
return null;
61+
// return new ListIterator();
62+
}
63+
64+
/*private class ListIterator implements Iterator{
65+
private int index = 0;
66+
67+
@Override
68+
public boolean hasNext() {
69+
// TODO Auto-generated method stub
70+
return index != size;
71+
}
72+
73+
@Override
74+
public Object next() {
75+
// TODO Auto-generated method stub
76+
if(index >= size){
77+
throw new IndexOutOfBoundsException("There's no next element.");
78+
}
79+
return elementData[index++];
80+
}
81+
82+
}*/
83+
84+
}

‎group03/664269713/DataStructure/src/com/ace/coding/BinaryTreeNode.java

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

‎group03/664269713/DataStructure/src/com/ace/coding/Iterator.java

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

‎group03/664269713/DataStructure/src/com/ace/coding/LinkedList.java

Lines changed: 123 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,123 @@
1+
package com.ace.coding;
2+
3+
public class LinkedList implements List {
4+
private Node head = null;
5+
private int size = 0;
6+
7+
public void add(Object o){
8+
Node newNode = new Node();
9+
newNode.data = o;
10+
if(head == null){
11+
head = newNode;
12+
} else {
13+
Node pNode = head;
14+
while(pNode.next != null){
15+
pNode = pNode.next;
16+
}
17+
pNode.next = newNode;
18+
}
19+
size++;
20+
}
21+
22+
public void add(int index , Object o){
23+
checkLinkedListIndex(index);
24+
25+
Node newNode = new Node();
26+
newNode.data = o;
27+
Node pNode = getNode(index);
28+
newNode.next = pNode.next;
29+
pNode.next = newNode;
30+
31+
size++;
32+
}
33+
34+
private Node getNode(int index){
35+
Node pNode = head;
36+
for(int i = 0; i < index; i++){
37+
pNode = pNode.next;
38+
}
39+
return pNode;
40+
}
41+
42+
public Object get(int index){
43+
Node pNode = getNode(index);
44+
return pNode.data;
45+
}
46+
public Object remove(int index){
47+
checkLinkedListIndex(index);
48+
49+
Node pNode = head;
50+
for(int i = 0; i < index - 1; i++){
51+
pNode = pNode.next;
52+
}
53+
Node tempNode = getNode(index);
54+
pNode.next = tempNode.next;
55+
size--;
56+
return tempNode.data;
57+
}
58+
59+
60+
public void addFirst(Object o){
61+
Node newNode = new Node();
62+
newNode.data = o;
63+
newNode.next = head;
64+
head = newNode;
65+
size++;
66+
}
67+
public void addLast(Object o){
68+
Node newNode = new Node();
69+
newNode.data = o;
70+
Node pNode = getNode(size() - 1);
71+
pNode.next = newNode;
72+
size++;
73+
}
74+
public Object removeFirst(){
75+
Node pNode = head;
76+
head = pNode.next;
77+
size--;
78+
return pNode.data;
79+
}
80+
public Object removeLast(){
81+
Object obj = remove(size() - 1);
82+
return obj;
83+
}
84+
85+
public int size(){
86+
return size;
87+
}
88+
89+
private void checkLinkedListIndex(int index){
90+
if(index < 0 || index >= size()){
91+
throw new IndexOutOfBoundsException("The index " + index + " is invalid.");
92+
}
93+
}
94+
95+
public Iterator iterator(){
96+
return null;
97+
// return new ListIterator();
98+
}
99+
100+
/*private class ListIterator implements Iterator{
101+
private Node pNode = head;
102+
103+
@Override
104+
public boolean hasNext() {
105+
// TODO Auto-generated method stub
106+
return pNode.next != null;
107+
}
108+
109+
@Override
110+
public Object next() {
111+
// TODO Auto-generated method stub
112+
Object obj = pNode.data;
113+
pNode = pNode.next;
114+
return obj;
115+
}
116+
117+
}*/
118+
119+
private static class Node{
120+
Object data;
121+
Node next;
122+
}
123+
}

‎group03/664269713/DataStructure/src/com/ace/coding/List.java

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package com.ace.coding;
2+
3+
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();
9+
}

‎group03/664269713/DataStructure/src/com/ace/coding/Queue.java

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package com.ace.coding;
2+
3+
public class Queue {
4+
private ArrayList arrayList = new ArrayList();
5+
private int size = 0;
6+
7+
public void enQueue(Object data){
8+
arrayList.add(size(), data);
9+
size++;
10+
}
11+
12+
public Object deQueue(){
13+
if(isEmpty()){
14+
throw new IndexOutOfBoundsException("The Queue is Empty.");
15+
}
16+
size--;
17+
return arrayList.remove(0);
18+
}
19+
20+
public boolean isEmpty(){
21+
return size()>0;
22+
}
23+
24+
public int size(){
25+
return size;
26+
}
27+
}

‎group03/664269713/DataStructure/src/com/ace/coding/Stack.java

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package com.ace.coding;
2+
3+
public class Stack {
4+
private ArrayList elementData = new ArrayList();
5+
private int size = 0;
6+
7+
public void push(Object o){
8+
elementData.add(o);
9+
size++;
10+
}
11+
12+
public Object pop(){
13+
checkStack();
14+
Object obj = elementData.remove(size()-1);
15+
size--;
16+
return obj;
17+
}
18+
19+
public Object peek(){
20+
checkStack();
21+
return elementData.get(size()-1);
22+
}
23+
24+
private void checkStack(){
25+
if(isEmpty()){
26+
throw new IndexOutOfBoundsException("This stack is empty");
27+
}
28+
}
29+
30+
public boolean isEmpty(){
31+
return size == 0;
32+
}
33+
public int size(){
34+
return size;
35+
}
36+
}

0 commit comments

Comments
 (0)