Skip to content

Commit 7c65027

Browse files
onlyliuxinonlyliuxin
authored
Merge pull request onlyliuxin#27 from eloiseSJTU/master
group 2 week 1
2 parents 3387a9c + 37551bd commit 7c65027

File tree

131 files changed

+7420
-0
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

131 files changed

+7420
-0
lines changed

‎group02/106614649/106614649Learnin/src/com/github/Ven13/coding2017/basic/ArrayList.java

Lines changed: 97 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,97 @@
1+
package com.github.Ven13.coding2017.basic;
2+
3+
public class ArrayList implements List {
4+
5+
//返回集合大小
6+
private int size = 0;
7+
8+
//先给定一个长度为10的数组
9+
Object[] elementData = new Object[100];
10+
11+
@Override
12+
//动态添加元素
13+
public void add(Object o) {
14+
//先判断数组是否已满
15+
if(size == elementData.length) {
16+
Object[] newObjects = new Object[elementData.length * 2];
17+
System.arraycopy(elementData, 0, newObjects, 0, elementData.length);
18+
elementData = newObjects;
19+
}
20+
21+
//为新添加的元素指定下标
22+
elementData[size] = o;
23+
size++;
24+
}
25+
26+
@Override
27+
public void add(int index, Object o) {
28+
//先判断数组是否已满
29+
if(size == elementData.length) {
30+
Object[] newObjects = elementData;
31+
this.elementData = new Object[elementData.length * 2];
32+
for(int j = 0; j < newObjects.length; j++) {
33+
this.elementData[j] = newObjects[j];
34+
}
35+
}
36+
37+
for(int i = size - 1; i >= index; i--) {
38+
elementData[i+1] = elementData[i];
39+
}
40+
41+
elementData[index] = o;
42+
size++;
43+
}
44+
45+
@Override
46+
public Object get(int index) {
47+
return elementData[index];
48+
}
49+
50+
@Override
51+
public Object remove(int index) {
52+
if (index > size) {
53+
return null;
54+
};
55+
56+
int moveSize = size - index - 1;
57+
58+
if (moveSize > 0) {
59+
System.arraycopy(elementData, index + 1, elementData, index, size - index - 1);
60+
}
61+
elementData[--size] = null;
62+
63+
//for(int i = index; i < elementData.length; i++) {
64+
// elementData[i] = elementData[i+1];
65+
//}
66+
67+
return elementData;
68+
}
69+
70+
@Override
71+
public int size() {
72+
return size;
73+
}
74+
75+
public Iterator iterator(){
76+
return new ArrayListIterator();
77+
}
78+
79+
private class ArrayListIterator implements Iterator {
80+
81+
private int currentIndex = 0;
82+
83+
@Override
84+
public boolean hasNext() {
85+
if(currentIndex >= size) return false;
86+
else return true;
87+
}
88+
89+
@Override
90+
public Object next() {
91+
Object o = elementData[currentIndex];
92+
currentIndex ++;
93+
return o;
94+
}
95+
}
96+
97+
}

‎group02/106614649/106614649Learnin/src/com/github/Ven13/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.Ven13.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/106614649/106614649Learnin/src/com/github/Ven13/coding2017/basic/Iterator.java

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

‎group02/106614649/106614649Learnin/src/com/github/Ven13/coding2017/basic/LinkedList.java

Lines changed: 173 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,173 @@
1+
package com.github.Ven13.coding2017.basic;
2+
3+
public class LinkedList implements List {
4+
5+
//表示该链表的长度
6+
private int size;
7+
8+
//链表的头元素
9+
private Node head;
10+
//链表的尾元素
11+
private Node tail;
12+
13+
//使用内部类来实现链表的每一个节点，每个节点有一个指向下一个元素的next，以及自身的data
14+
private static class Node {
15+
public Object data;
16+
public Node next;
17+
18+
public Node(Object data) {
19+
this.data = data;
20+
}
21+
}
22+
23+
//链表的构造方法
24+
public LinkedList() {
25+
}
26+
27+
@Override
28+
public void add(Object o) {
29+
add(size, o);
30+
}
31+
32+
@Override
33+
public void add(int index, Object o) {
34+
if(index == 0) {
35+
addFirst(o);
36+
} else {
37+
if(index >= size) {
38+
addLast(o);
39+
} else {
40+
Node node = head;
41+
for (int i = 1; i < index; i++) {
42+
head = head.next;
43+
}
44+
Node nextNode = node.next;
45+
Node temp = new Node(o);
46+
node.next = temp;
47+
temp.next = nextNode;
48+
size++;
49+
}
50+
}
51+
}
52+
53+
//添加前面
54+
public void addFirst(Object o) {
55+
Node newNode = new Node(o);
56+
newNode.next = head;
57+
head = newNode;
58+
size++;
59+
if(tail == null) {
60+
tail = head;
61+
}
62+
}
63+
64+
//添加后面
65+
public void addLast(Object o) {
66+
if(tail == null) {
67+
tail = head = new Node(o);
68+
} else {
69+
Node newNode = new Node(o);
70+
tail.next = newNode;
71+
tail = tail.next;
72+
}
73+
size++;
74+
}
75+
76+
77+
@Override
78+
public Object get(int index) {
79+
Node node = head;
80+
for(int i = 0; i < index; i++) {
81+
node = node.next;
82+
}
83+
return node.data;
84+
}
85+
86+
@Override
87+
public Object remove(int index) {
88+
if(size == 0) {
89+
throw new java.util.NoSuchElementException();
90+
}
91+
if(index == 0) {
92+
Node node = head;
93+
Node temp = node.next;
94+
head = temp;
95+
size--;
96+
return node.data;
97+
} else {
98+
if(index >= size) {
99+
throw new java.util.NoSuchElementException();
100+
} else {
101+
Node node = head;
102+
for(int i = 1; i < index; i++) {
103+
node = node.next;
104+
}
105+
Node temp = node.next;
106+
node.next = temp.next;
107+
size--;
108+
return node.data;
109+
}
110+
}
111+
112+
}
113+
114+
@Override
115+
public int size() {
116+
return size;
117+
}
118+
119+
public Object removeFirst() {
120+
//通过头指针创建头节点
121+
Node hNode = head;
122+
if (hNode == null) {
123+
throw new java.util.NoSuchElementException();
124+
}
125+
Node nNode = hNode.next;
126+
Object element = hNode.data;
127+
128+
//移除
129+
hNode.data = null;
130+
hNode.next = null;
131+
head = nNode;
132+
//判断是否为尾节点
133+
if (nNode == null) {
134+
tail = null;
135+
}else {
136+
nNode = null;
137+
}
138+
size --;
139+
return element;
140+
}
141+
142+
public Object removeLast() {
143+
return remove(size - 1);
144+
}
145+
146+
public Iterator iterator() {
147+
return new LinkedListIterator();
148+
}
149+
150+
private class LinkedListIterator implements Iterator {
151+
152+
private Node node = head.next;
153+
154+
@Override
155+
public boolean hasNext() {
156+
return node != tail;
157+
}
158+
159+
@Override
160+
public Object next() {
161+
162+
if(!hasNext()) {
163+
throw new java.util.NoSuchElementException();
164+
}
165+
Object nextData = node.data;
166+
node = node.next;
167+
return nextData;
168+
}
169+
170+
}
171+
172+
173+
}

‎group02/106614649/106614649Learnin/src/com/github/Ven13/coding2017/basic/List.java

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
package com.github.Ven13.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+
10+
public Iterator iterator();
11+
}

‎group02/106614649/106614649Learnin/src/com/github/Ven13/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.Ven13.coding2017.basic;
2+
3+
public class Queue {
4+
5+
private LinkedList list = new LinkedList();
6+
private int size = 0;
7+
8+
public void enQueue(Object o){
9+
size++;
10+
list.addLast(o);
11+
}
12+
13+
public Object deQueue(){
14+
size--;
15+
return list.removeFirst();
16+
}
17+
18+
public boolean isEmpty(){
19+
if(size == 0) {
20+
return true;
21+
} else {
22+
return false;
23+
}
24+
}
25+
26+
public int size(){
27+
return size;
28+
}
29+
30+
}

‎group02/106614649/106614649Learnin/src/com/github/Ven13/coding2017/basic/Stack.java

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

‎group02/106614649/106614649Learnin/src/com/github/Ven13/coding2017/basic/test/ArrayListTest.java

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
package com.github.Ven13.coding2017.basic.test;
2+
3+
import org.junit.Before;
4+
5+
import com.github.Ven13.coding2017.basic.*;
6+
7+
public class ArrayListTest extends ListTest{
8+
9+
10+
11+
}

0 commit comments

Comments
 (0)