Skip to content

Commit c4a3bee

Browse files
zhijiaxinyuzhijiaxinyu
authored
Merge pull request onlyliuxin#5 from KellyXiao/master
first week job
2 parents 1b0a316 + e249651 commit c4a3bee

File tree

13 files changed

+522
-0
lines changed

13 files changed

+522
-0
lines changed

‎group10/205301442/src/com/coding/week1/ArrayList.java

Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
package com.coding.week1;
2+
3+
4+
5+
6+
public class ArrayList implements List{
7+
private int size = 0;
8+
9+
private Object[] elementData = {};
10+
11+
public void add(Object o){
12+
extendIndex();
13+
elementData[size] = o;
14+
size++;
15+
}
16+
public void add(int index, Object o){
17+
18+
if(index>size){
19+
System.out.println("Exception in thread \""+Thread.currentThread()+"\" java.lang.IndexOutOfBoundsException:Index:"+index+",Size:"+size);
20+
return;
21+
}
22+
int length = elementData.length;
23+
if(size==elementData.length){
24+
length=elementData.length+1;
25+
}
26+
Object[] newElement = new Object[length];
27+
System.arraycopy(elementData, 0, newElement, 0, index);
28+
System.arraycopy(elementData, index, newElement,index+1,size-index );
29+
newElement[index]=o;
30+
elementData = newElement;
31+
size++;
32+
}
33+
34+
public Object get(int index){
35+
boolean isRange=rangeCheck(index);
36+
if(!isRange){
37+
return null;
38+
}
39+
return elementData[index];
40+
}
41+
42+
public Object remove(int index){
43+
boolean isRange=rangeCheck(index);
44+
if(!isRange){
45+
return null;
46+
}
47+
Object rmData = elementData[index];
48+
Object[] newElement = new Object[elementData.length];
49+
System.arraycopy(elementData, 0, newElement, 0, index);;
50+
System.arraycopy(elementData, index+1, newElement,index,size-index-1 );
51+
elementData = newElement;
52+
size--;
53+
return rmData;
54+
}
55+
56+
public int size(){
57+
return size;
58+
}
59+
60+
public com.coding.week1.Iterator iterator(){
61+
return new Ito();
62+
}
63+
public boolean rangeCheck(int index){
64+
65+
if(index>size-1||index<0){
66+
System.err.println("Exception in thread \""+Thread.currentThread()+"\" java.lang.IndexOutOfBoundsException:Index:"+index+",Size:"+size);
67+
return false;
68+
}
69+
return true;
70+
}
71+
public void extendIndex(){
72+
Object[] newElement = new Object[elementData.length+1];
73+
System.arraycopy(elementData, 0, newElement, 0, size);
74+
elementData = newElement;
75+
76+
}
77+
public class Ito implements com.coding.week1.Iterator{
78+
int cursor;
79+
@Override
80+
public boolean hasNext() {
81+
if(cursor!=size){
82+
return true;
83+
}
84+
return false;
85+
}
86+
87+
@Override
88+
public Object next() {
89+
Object o=elementData[cursor];
90+
cursor++;
91+
return o;
92+
}
93+
}
94+
95+
96+
}

‎group10/205301442/src/com/coding/week1/BinaryTreeNode.java

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

‎group10/205301442/src/com/coding/week1/Iterator.java

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

‎group10/205301442/src/com/coding/week1/LinkedList.java

Lines changed: 162 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,162 @@
1+
package com.coding.week1;
2+
3+
public class LinkedList implements List {
4+
private int size;
5+
private Node first;
6+
private Node last;
7+
public static class Node{
8+
Object data;
9+
Node next;
10+
Node prev;
11+
public Node(Node prev,Object data,Node next){
12+
this.data = data;
13+
this.next = next;
14+
this.prev = prev;
15+
}
16+
}
17+
18+
@Override
19+
public void add(Object o) {
20+
final Node l = last;
21+
Node newNode = new Node(last,o,null);
22+
last = newNode;
23+
if(first==null){
24+
first = newNode;
25+
}else{
26+
l.next = newNode;
27+
}
28+
size++;
29+
30+
}
31+
32+
@Override
33+
public void add(int index, Object o) {
34+
35+
if(index>size){
36+
System.out.println("Exception in thread \""+Thread.currentThread()+"\" java.lang.IndexOutOfBoundsException:Index:"+index+",Size:"+size);
37+
return;
38+
}
39+
Node newNode = new Node(null,o,null);
40+
Node nodePre = node(index-1);
41+
Node oldNode = node(index);
42+
if(nodePre!=null){
43+
nodePre.next =newNode;
44+
newNode.prev = nodePre;
45+
}else{
46+
first = newNode;
47+
}
48+
if(oldNode!=null){
49+
oldNode.prev = newNode;
50+
newNode.next = oldNode;
51+
}else{
52+
last = newNode;
53+
}
54+
size++;
55+
}
56+
57+
@Override
58+
public Object get(int index) {
59+
if(!rangeCheck(index)){
60+
return null;
61+
}
62+
63+
return node(index).data;
64+
}
65+
66+
@Override
67+
public Object remove(int index) {
68+
if(!rangeCheck(index)){
69+
return null;
70+
}
71+
Node prevNode = node(index-1);
72+
Node nextNode = node(index+1);
73+
Node rmNode = node(index);
74+
if(prevNode!=null){
75+
prevNode.next = nextNode;
76+
}else{
77+
first=nextNode;
78+
}
79+
if(nextNode!=null){
80+
nextNode.prev = prevNode;
81+
}else{
82+
last = prevNode;
83+
}
84+
size--;
85+
return rmNode.data;
86+
}
87+
88+
@Override
89+
public int size() {
90+
// TODO Auto-generated method stub
91+
return size;
92+
}
93+
public Object head(){
94+
return first.data;
95+
}
96+
public Object last(){
97+
return last.data;
98+
}
99+
public void addFirst(Object o){
100+
add(0,o);
101+
}
102+
public void addLast(Object o){
103+
add(size,o);
104+
}
105+
public Object removeFirst(){
106+
Node f = first;
107+
remove(0);
108+
return f.data;
109+
}
110+
public Object removeLast(){
111+
Node l = last;
112+
remove(size-1);
113+
return l.data;
114+
}
115+
public Node node(int index){
116+
if(index<0){
117+
return null;
118+
}
119+
Node x =null;
120+
if(index<(size<<1)){
121+
x = first;
122+
for(int i=0;i<index;i++ ){
123+
x = x.next;
124+
}
125+
}else{
126+
x = last;
127+
for(int i=size-1;i>index;i--){
128+
x = x.prev;
129+
}
130+
}
131+
return x;
132+
}
133+
public boolean rangeCheck(int index){
134+
135+
if(index>size-1||index<0){
136+
System.err.println("Exception in thread \""+Thread.currentThread()+"\" java.lang.IndexOutOfBoundsException:Index:"+index+",Size:"+size);
137+
return false;
138+
}
139+
return true;
140+
}
141+
public Ito iterator(){
142+
return new Ito();
143+
}
144+
public class Ito implements Iterator{
145+
int cursor;
146+
@Override
147+
public boolean hasNext() {
148+
if(cursor!=size){
149+
return true;
150+
}
151+
return false;
152+
}
153+
154+
@Override
155+
public Object next() {
156+
Object o=node(cursor).data;
157+
cursor++;
158+
return o;
159+
}
160+
161+
}
162+
}

‎group10/205301442/src/com/coding/week1/List.java

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

‎group10/205301442/src/com/coding/week1/Queue.java

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package com.coding.week1;
2+
3+
public class Queue {
4+
ArrayList list = new ArrayList();
5+
public void enQueue(Object o){
6+
list.add(o);
7+
}
8+
9+
public Object deQueue(){
10+
return list.remove(0);
11+
}
12+
13+
public boolean isEmpty(){
14+
if(list.size()==0){
15+
return true;
16+
}
17+
return false;
18+
}
19+
20+
public int size(){
21+
return list.size();
22+
}
23+
}

‎group10/205301442/src/com/coding/week1/Stack.java

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package com.coding.week1;
2+
3+
public class Stack {
4+
private ArrayList elementData = new ArrayList();
5+
6+
public void push(Object o){
7+
elementData.add(o);
8+
}
9+
10+
public Object pop(){
11+
int top = elementData.size()-1;
12+
return elementData.remove(top);
13+
}
14+
15+
public Object peek(){
16+
int top = elementData.size()-1;
17+
return elementData.get(top);
18+
}
19+
public boolean isEmpty(){
20+
if(elementData.size()==0){
21+
return true;
22+
}
23+
return false;
24+
}
25+
public int size(){
26+
return elementData.size();
27+
}
28+
}

‎group10/205301442/test/com/coding/week1/AllTests.java

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
package com.coding.week1;
2+
3+
import org.junit.runner.RunWith;
4+
import org.junit.runners.Suite;
5+
import org.junit.runners.Suite.SuiteClasses;
6+
7+
@RunWith(Suite.class)
8+
@SuiteClasses({ TestArrayList.class, TestLinkedList.class, TestQueue.class, TestStack.class })
9+
public class AllTests {
10+
11+
}

0 commit comments

Comments
 (0)