Skip to content

Commit 8d011fa

Browse files
congcongcong250congcongcong250
committed
Finish Except Tree
1 parent 2ff2c32 commit 8d011fa

File tree

8 files changed

+386
-0
lines changed

8 files changed

+386
-0
lines changed

‎group02/609990377/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

‎group02/609990377/DataStructure/src/com/github/congcongcong250/coding2017/basic/ArrayList.java

Lines changed: 113 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,113 @@
1+
package com.github.congcongcong250.coding2017.basic;
2+
3+
import java.util.Arrays;
4+
import java.util.InputMismatchException;
5+
import java.util.NoSuchElementException;
6+
7+
public class ArrayList implements List {
8+
9+
private int size = 0;
10+
11+
private Object[] elementData = new Object[10];
12+
13+
public void add(Object o){
14+
15+
//check size limit
16+
if(size + 1 > elementData.length){
17+
int newlength = elementData.length * 3 / 2 + 1;
18+
elementData = Arrays.copyOf(elementData, newlength);
19+
}
20+
21+
elementData[size++] = o;
22+
}
23+
24+
public void add(int index, Object o){
25+
//Check Object class
26+
if(size >= 1){
27+
if(o.getClass() != elementData[0].getClass())
28+
throw new InputMismatchException("Index:"+index+" Size:"+size);
29+
}
30+
31+
//index Check
32+
if(index >= size || index < 0){
33+
throw new IndexOutOfBoundsException("Index:"+index+" Size:"+size);
34+
}
35+
36+
//check size limit
37+
if(size + 1 > elementData.length){
38+
Object oldData[] = elementData;
39+
int newlength = elementData.length * 3 / 2 + 1;
40+
elementData = Arrays.copyOf(elementData, newlength);
41+
}
42+
43+
for(int i = size-1; i >= index; i-- ){
44+
elementData[i] = elementData[i-1];
45+
}
46+
47+
elementData[index] = o;
48+
49+
}
50+
51+
public Object get(int index){
52+
//index Check
53+
if(index >= size || index < 0){
54+
throw new IndexOutOfBoundsException("Index:"+index+" Size:"+size);
55+
}
56+
57+
return elementData[index];
58+
}
59+
60+
public Object remove(int index){
61+
//index Check
62+
if(index >= size || index < 0){
63+
throw new IndexOutOfBoundsException("Index:"+index+" Size:"+size);
64+
}
65+
66+
Object old = elementData[index];
67+
for(int i = index; i < size-1 ; i++ ){
68+
elementData[i] = elementData[i+1];
69+
}
70+
elementData[--size] = null;
71+
return old;
72+
}
73+
74+
public int size(){
75+
return size;
76+
}
77+
78+
public Iterator iterator(){
79+
return new Itr();
80+
}
81+
82+
private class Itr implements Iterator{
83+
//index for next element to visit
84+
private int cursor = 0;
85+
86+
@Override
87+
public boolean hasNext() {
88+
return cursor != size;
89+
}
90+
91+
@Override
92+
public Object next() {
93+
if(cursor >= size){
94+
throw new NoSuchElementException();
95+
}
96+
return elementData[cursor++];
97+
}
98+
99+
@Override
100+
public void remove() {
101+
//Check bound
102+
if(cursor == 0){
103+
throw new NoSuchElementException();
104+
}
105+
106+
ArrayList.this.remove(--cursor);
107+
108+
}
109+
110+
111+
}
112+
113+
}

‎group02/609990377/DataStructure/src/com/github/congcongcong250/coding2017/basic/BinaryTreeNode.java

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package com.github.congcongcong250.coding2017.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+
}

‎group02/609990377/DataStructure/src/com/github/congcongcong250/coding2017/basic/Iterator.java

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

‎group02/609990377/DataStructure/src/com/github/congcongcong250/coding2017/basic/LinkedList.java

Lines changed: 163 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,163 @@
1+
package com.github.congcongcong250.coding2017.basic;
2+
3+
import java.util.NoSuchElementException;
4+
5+
public class LinkedList implements List {
6+
7+
private Node head;
8+
private int size;
9+
10+
public LinkedList(){
11+
head.next = head;
12+
head.previous = head;
13+
size = 0;
14+
}
15+
16+
public void add(Object o){
17+
addLast(o);
18+
}
19+
20+
public void add(int index , Object o){
21+
//Check bound
22+
if(index >= size){
23+
throw new IndexOutOfBoundsException("Index:"+index+" Size:"+size);
24+
}
25+
26+
Node nx = this.find(index);
27+
Node pr = nx.previous;
28+
Node in = new Node(o,pr,nx);
29+
nx.previous = in;
30+
pr.next = in;
31+
size++;
32+
}
33+
34+
public Object get(int index){
35+
//Check bound
36+
if(index >= size){
37+
throw new IndexOutOfBoundsException("Index:"+index+" Size:"+size);
38+
}
39+
return this.find(index);
40+
}
41+
42+
public Object remove(int index){
43+
//Check bound
44+
if(index >= size){
45+
throw new IndexOutOfBoundsException("Index:"+index+" Size:"+size);
46+
}
47+
Node rem = this.find(index);
48+
49+
Node pr = rem.previous;
50+
Node nx = rem.next;
51+
pr.next = nx;
52+
nx.previous = pr;
53+
54+
Object ret = rem.data;
55+
rem.previous = null;
56+
rem.next = null;
57+
rem.data = null;
58+
size--;
59+
return ret;
60+
}
61+
62+
public int size(){
63+
return size;
64+
}
65+
66+
public void addFirst(Object o){
67+
Node nx = head.next;
68+
Node in = new Node(o,head, nx);
69+
head.next = in;
70+
nx.previous = in;
71+
size++;
72+
}
73+
74+
public void addLast(Object o){
75+
Node last = head.previous;
76+
Node in = new Node(o,last,head);
77+
last.next = in;
78+
head.previous = in;
79+
80+
size++;
81+
}
82+
public Object removeFirst(){
83+
return remove(0);
84+
}
85+
public Object removeLast(){
86+
return remove(size-1);
87+
}
88+
public Iterator iterator(){
89+
return new ListItr();
90+
}
91+
92+
private Node find(int index){
93+
Node tra = head;
94+
95+
//If index < size/2
96+
if( index < (size >> 1)){
97+
for(int i = 0; i <= index; i++){
98+
tra = tra.next;
99+
}
100+
}else{
101+
for(int i = size; i >= index; i--){
102+
tra = tra.previous;
103+
}
104+
}
105+
return tra;
106+
}
107+
108+
private static class Node{
109+
Object data;
110+
Node next;
111+
Node previous;
112+
113+
public Node(Object obj,Node pre, Node nx){
114+
data = obj;
115+
next = nx;
116+
previous = pre;
117+
}
118+
119+
120+
}
121+
122+
private class ListItr implements Iterator{
123+
//Point to next node
124+
Node cursor;
125+
int nextIndex;
126+
127+
public ListItr(){
128+
cursor = head.next;
129+
nextIndex = 0;
130+
}
131+
132+
@Override
133+
public boolean hasNext() {
134+
return nextIndex < size;
135+
}
136+
137+
@Override
138+
public Object next() {
139+
Node re = cursor;
140+
cursor = cursor.next;
141+
nextIndex++;
142+
return re;
143+
}
144+
145+
public Object previous() {
146+
Node re = cursor.previous.previous;
147+
cursor = cursor.previous;
148+
nextIndex--;
149+
return re;
150+
}
151+
152+
@Override
153+
public void remove() {
154+
//Check bound
155+
if(nextIndex > size){
156+
throw new NoSuchElementException("Iterates to the end");
157+
}
158+
LinkedList.this.remove(--nextIndex);
159+
160+
}
161+
162+
}
163+
}

‎group02/609990377/DataStructure/src/com/github/congcongcong250/coding2017/basic/List.java

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

‎group02/609990377/DataStructure/src/com/github/congcongcong250/coding2017/basic/Queue.java

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
package com.github.congcongcong250.coding2017.basic;
2+
3+
public class Queue {
4+
private LinkedList elementData;
5+
6+
public Queue(){
7+
elementData = new LinkedList();
8+
}
9+
10+
public void enQueue(Object o){
11+
elementData.addFirst(o);
12+
}
13+
14+
public Object deQueue(){
15+
Object ret = elementData.removeLast();
16+
return ret;
17+
}
18+
19+
public Object peek(){
20+
return elementData.get(elementData.size()-1);
21+
}
22+
23+
public boolean isEmpty(){
24+
return (elementData.size() == 0);
25+
}
26+
27+
public int size(){
28+
return elementData.size();
29+
}
30+
}

‎group02/609990377/DataStructure/src/com/github/congcongcong250/coding2017/basic/Stack.java

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

0 commit comments

Comments
 (0)