Skip to content

Commit 829aec0

Browse files
author
Rong Huang
authored
Merge pull request onlyliuxin#3 from FelixCJF/master
第一周作业提交
2 parents b62ffb6 + c707d7d commit 829aec0

File tree

12 files changed

+770
-0
lines changed

12 files changed

+770
-0
lines changed

‎group02/1554421063/src/com/github/FelixCJF/coding2017/basic/ArrayList.java

Lines changed: 105 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,105 @@
1+
package com.github.FelixCJF.coding2017.basic;
2+
3+
4+
public class ArrayList implements List {
5+
6+
private int size = 0;
7+
8+
private Object[] elementData = new Object[100];
9+
10+
public void add(Object o){
11+
//容量增加
12+
ensureCapacity(size + 1);
13+
//添加
14+
elementData[size ++] = o;
15+
}
16+
17+
public void add(int index, Object o){
18+
19+
//检查是否越界
20+
rangeCheck(index);
21+
// 进行扩容检查
22+
ensureCapacity(size + 1);
23+
// 对数组进行复制处理，目的就是空出index的位置插入element，并将index后的元素位移一个位置
24+
System. arraycopy(elementData, index, elementData, index + 1,
25+
size - index);
26+
// 将指定的index位置赋值为Object o
27+
elementData[index] = o;
28+
// 自增一位长度
29+
size++;
30+
}
31+
32+
public Object get(int index){
33+
rangeCheck(index);
34+
return elementData[index];
35+
}
36+
37+
public Object remove(int index){
38+
// 数组越界检查
39+
rangeCheck(index);
40+
// 取出要删除位置的元素，供返回使用
41+
Object oldValue = elementData[index];
42+
// 计算数组要复制的数量
43+
int numMoved = size - index - 1;
44+
// 数组复制，就是将index之后的元素往前移动一个位置
45+
if (numMoved > 0)
46+
System. arraycopy(elementData, index+1, elementData, index,
47+
numMoved);
48+
// 将数组最后一个元素置空（因为删除了一个元素，然后index后面的元素都向前移动了，所以最后一个就没用了），好让gc尽快回收
49+
// 不要忘了size减一
50+
elementData[--size] = null;
51+
return oldValue;
52+
}
53+
54+
public int size(){
55+
return size;
56+
}
57+
58+
public Iterator iterator(){
59+
return new ArrayListIterator();
60+
}
61+
62+
//内部类，实现Iterator
63+
private class ArrayListIterator implements Iterator{
64+
65+
private int currentIndex = 0; //当前索引
66+
67+
public boolean hasNext() {
68+
if (currentIndex >= size) {
69+
return false;
70+
}
71+
return true;
72+
}
73+
74+
public Object next() {
75+
Object object = elementData[currentIndex];
76+
currentIndex ++ ;
77+
return object;
78+
}
79+
}
80+
//扩容
81+
public void ensureCapacity( int minCapacity) {
82+
// 当前数组的长度
83+
int oldCapacity = elementData .length;
84+
// 最小需要的容量大于当前数组的长度则进行扩容
85+
if (minCapacity > oldCapacity) {
86+
// 扩容
87+
int newCapacity = oldCapacity + (oldCapacity >> 1);
88+
// 如果新扩容的数组长度还是比最小需要的容量小，则以最小需要的容量为长度进行扩容
89+
if (newCapacity < minCapacity)
90+
newCapacity = minCapacity;
91+
//数组复制
92+
Object[] elementData2 = new Object[newCapacity];
93+
for (int i = 0; i < oldCapacity; i++) {
94+
elementData2[i] = elementData[i];
95+
}
96+
elementData = elementData2;
97+
}
98+
}
99+
//检查是否越界
100+
private void rangeCheck(int index){
101+
if (index < 0 || index >= this.size) {
102+
throw new IndexOutOfBoundsException("index :" + index + "size :" + size);
103+
}
104+
}
105+
}

‎group02/1554421063/src/com/github/FelixCJF/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.FelixCJF.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/1554421063/src/com/github/FelixCJF/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.FelixCJF.coding2017.basic;
2+
3+
public interface Iterator {
4+
5+
public boolean hasNext();
6+
public Object next();
7+
8+
}

‎group02/1554421063/src/com/github/FelixCJF/coding2017/basic/LinkedList.java

Lines changed: 214 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,214 @@
1+
package com.github.FelixCJF.coding2017.basic;
2+
3+
import java.util.NoSuchElementException;
4+
5+
public class LinkedList implements List {
6+
7+
private Node head;//头指针
8+
private Node last;//尾指针
9+
private int size = 0;
10+
11+
public void add(Object o){
12+
addLast(o);
13+
}
14+
15+
public void add(int index , Object o){
16+
//检查是否越界
17+
checkIndex(index);
18+
19+
Node indexNode = node(index);
20+
21+
if (index == size) {
22+
addLast(o);
23+
} else {
24+
final Node pred = indexNode.prv;
25+
26+
final Node newNode = new Node();
27+
newNode.data = o;
28+
newNode.next = indexNode;
29+
newNode.prv = pred;
30+
31+
indexNode.prv = newNode;
32+
33+
if (pred == null) {
34+
head = newNode;
35+
} else {
36+
pred.next = newNode;
37+
}
38+
}
39+
size ++;
40+
}
41+
public Object get(int index){
42+
//检查是否越界
43+
checkIndex(index);
44+
45+
Node indexNode = node(index);
46+
47+
return indexNode.data;
48+
}
49+
public Object remove(int index){
50+
//检查是否越界
51+
checkIndex(index);
52+
53+
Node indexNode = node(index);
54+
Object element = indexNode.data;
55+
Node pre = indexNode.prv;
56+
Node next = indexNode.next;
57+
58+
if (pre == null) {
59+
head = next;
60+
} else {
61+
pre.next = next;
62+
indexNode.prv = null;
63+
}
64+
65+
if (next == null) {
66+
last = pre;
67+
} else {
68+
next.prv = pre;
69+
indexNode.next = null;
70+
}
71+
72+
indexNode.data = null;
73+
74+
size --;
75+
76+
return element;
77+
}
78+
79+
public int size(){
80+
return size;
81+
}
82+
83+
public void addFirst(Object o){
84+
//节点变量存放原来的头指针
85+
final Node oldHead = head;
86+
//创建新的节点对象
87+
final Node newNode = new Node();
88+
newNode.data = o;
89+
newNode.next = head;
90+
newNode.prv = null;
91+
//判断oldhead是否为null
92+
if (oldHead == null) {
93+
last = newNode;
94+
}else {
95+
//头指针指向新创建的节点对象
96+
oldHead.prv = newNode;
97+
}
98+
//将newNode变为头指针
99+
head = newNode;
100+
size ++;
101+
}
102+
public void addLast(Object o){
103+
//节点新变量放原先的尾指针
104+
final Node oldLast = last;
105+
//创建新节点，加入要添加的对象
106+
final Node newNode = new Node();
107+
newNode.data = o;
108+
newNode.next = null;
109+
newNode.prv = oldLast;
110+
if (oldLast == null) {
111+
head = newNode;
112+
} else {
113+
//尾指针指向新创建的节点
114+
oldLast.next = newNode;
115+
}
116+
//newNode变为尾指针
117+
last = newNode;
118+
size++;
119+
}
120+
public Object removeFirst(){
121+
//通过头指针创建头节点
122+
final Node hNode = head;
123+
if (hNode == null) {
124+
throw new NoSuchElementException();
125+
}
126+
final Node next = hNode.next;
127+
final Object element = hNode.data;
128+
129+
//移除
130+
hNode.data = null;
131+
hNode.next = null;
132+
head = next;
133+
//判断是否为尾节点
134+
if (next == null) {
135+
last = null;
136+
}else {
137+
next.prv = null;
138+
}
139+
size --;
140+
return element;
141+
}
142+
public Object removeLast(){
143+
//通过尾指针创建节点
144+
final Node lastNode = last;
145+
if (lastNode == null) {
146+
throw new NoSuchElementException();
147+
}
148+
final Object element = lastNode.data;
149+
final Node prve = lastNode.prv;
150+
151+
//移除
152+
lastNode.data = null;
153+
lastNode.prv = null;
154+
last = prve;
155+
156+
if (prve == null) {
157+
head = null;
158+
} else {
159+
prve.next = null;
160+
}
161+
size --;
162+
return element;
163+
}
164+
public Iterator iterator(){
165+
return new LinkedListIterator();
166+
}
167+
168+
private class LinkedListIterator implements Iterator{
169+
170+
private Node currentNode = head;//当前节点
171+
172+
public boolean hasNext() {
173+
if (currentNode == null) {
174+
return false;
175+
}
176+
return true;
177+
}
178+
179+
public Object next() {
180+
Object element = currentNode.data;
181+
currentNode = currentNode.next;
182+
return element;
183+
}
184+
185+
}
186+
187+
//查找index节点,并返回该节点
188+
Node node(int index) {
189+
// assert isElementIndex(index);
190+
191+
if (index < (size >> 1)) {
192+
Node x = head;
193+
for (int i = 0; i < index; i++)
194+
x = x.next;
195+
return x;
196+
} else {
197+
Node x = last;
198+
for (int i = size - 1; i > index; i--)
199+
x = x.prv;
200+
return x;
201+
}
202+
}
203+
//检查索引
204+
private void checkIndex(int index){
205+
if (index < 0 || index > size) {
206+
throw new IndexOutOfBoundsException();
207+
}
208+
}
209+
private static class Node{
210+
Object data;
211+
Node next;
212+
Node prv;
213+
}
214+
}

‎group02/1554421063/src/com/github/FelixCJF/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.FelixCJF.coding2017.basic;
2+
3+
4+
public interface List {
5+
public void add(Object o);
6+
public void add(int index, Object o);
7+
public Object get(int index);
8+
public Object remove(int index);
9+
public int size();
10+
public Iterator iterator();
11+
}

0 commit comments

Comments
 (0)