Skip to content

Commit c707d7d

Browse files
AdministratorAdministrator
Administrator
authored and
Administrator
committed
第一周作业测试通过
1 parent f3f4984 commit c707d7d

File tree

5 files changed

+68
-53
lines changed

5 files changed

+68
-53
lines changed

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

Lines changed: 52 additions & 44 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,5 @@
11
package com.github.FelixCJF.coding2017.basic;
22

3-
import java.util.Arrays;
43

54
public class ArrayList implements List {
65

@@ -12,50 +11,44 @@ public void add(Object o){
1211
//容量增加
1312
ensureCapacity(size + 1);
1413
//添加
15-
elementData[size++] = o;
14+
elementData[size ++] = o;
1615
}
1716

1817
public void add(int index, Object o){
19-
//容量增加
20-
ensureCapacity(size + 1);
21-
//临时变量
22-
Object[] elementData3 = new Object[size + 1];
23-
//将index前数据复制
24-
for (int i = 0; i < index + 1 ; i++) {
25-
elementData3[i] = elementData[i];
26-
}
27-
//插入的数据
28-
elementData3 [index + 1] = o;
29-
//插入数据之后的后半段复制
30-
for (int i = index + 2 ; i < elementData3.length; i++) {
31-
elementData3[i] = elementData[i-1];
32-
}
33-
elementData = elementData3;
34-
size++;
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++;
3530
}
3631

3732
public Object get(int index){
38-
if (index < 0 || index >= this.size) {
39-
throw new IndexOutOfBoundsException();
40-
}
33+
rangeCheck(index);
4134
return elementData[index];
4235
}
4336

4437
public Object remove(int index){
45-
if (index < 0 || index >= this.size) {
46-
throw new IndexOutOfBoundsException();
47-
}
48-
Object oldValue = elementData[index];
49-
Object[] elementData4 = new Object[size - 1];
50-
for (int i = 0; i < index; i++) {
51-
elementData4[i] = elementData[i];
52-
}
53-
for (int i = index; i < elementData4.length; i++) {
54-
elementData4[i] = elementData[i + 1];
55-
}
56-
elementData = elementData4;
57-
size--;
58-
return oldValue;
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;
5952
}
6053

6154
public int size(){
@@ -84,14 +77,29 @@ public Object next() {
8477
return object;
8578
}
8679
}
87-
public void ensureCapacity(int minCapacity) {
88-
int oldCapacity = elementData.length;
89-
if (minCapacity > oldCapacity) {
90-
int newCapacity = (oldCapacity * 3) / 2 + 1;
91-
if (newCapacity < minCapacity)
92-
newCapacity = minCapacity;
93-
elementData = Arrays.copyOf(elementData, newCapacity);
94-
}
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+
}
95104
}
96-
97105
}

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

Lines changed: 3 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -7,30 +7,28 @@ public class Stack {
77
//存放栈内元素的容器
88
private ArrayList elementData = new ArrayList();
99
//记录栈内元素个数
10-
private int size = 0;
1110

1211
public void push(Object o){
1312
elementData.add(o);
14-
size ++;
1513
}
1614

1715
public Object pop(){
1816
if (isEmpty()) {
1917
throw new EmptyStackException();
2018
}
21-
return elementData.remove(size - 1);
19+
return elementData.remove(elementData.size() - 1);
2220
}
2321

2422
public Object peek(){
2523
if (isEmpty()) {
2624
throw new EmptyStackException();
2725
}
28-
return elementData.get(size - 1);
26+
return elementData.get(elementData.size() - 1);
2927
}
3028
public boolean isEmpty(){
3129
return elementData.size() == 0;
3230
}
3331
public int size(){
34-
return size;
32+
return elementData.size();
3533
}
3634
}

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

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -6,9 +6,9 @@
66

77
public class ArrayListTest extends ListTest {
88

9-
@Before
9+
/* @Before
1010
public void setUpArrayList() {
1111
aList = new ArrayList();
12-
}
12+
}*/
1313

1414
}

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

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7,14 +7,17 @@
77
import org.junit.Before;
88
import org.junit.Test;
99

10+
import com.github.FelixCJF.coding2017.basic.ArrayList;
1011
import com.github.FelixCJF.coding2017.basic.LinkedList;
12+
import com.github.FelixCJF.coding2017.basic.List;
1113

1214
public class LinkedListTest extends ListTest{
1315

1416
private LinkedList aLinkedList;
1517

1618
@Before
1719
public void setUpLinkedList() {
20+
List aList = new ArrayList();
1821
aList = new LinkedList();
1922
aLinkedList = new LinkedList();
2023
}

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

Lines changed: 8 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -6,17 +6,18 @@
66
import org.junit.Test;
77
import org.junit.rules.ExpectedException;
88

9+
import com.github.FelixCJF.coding2017.basic.ArrayList;
910
import com.github.FelixCJF.coding2017.basic.Iterator;
1011
import com.github.FelixCJF.coding2017.basic.List;
1112

1213
public class ListTest {
1314

1415

15-
protected static List aList;
16-
16+
//protected static List aList = new ArrayList();
1717

1818
@Test
1919
public void testFunctional() {
20+
List aList = new ArrayList();
2021
aList.add(1);
2122
aList.add(2);
2223
assertEquals(1, aList.get(0));
@@ -41,6 +42,7 @@ public void testFunctional() {
4142

4243
@Test
4344
public void testAdd() {
45+
List aList = new ArrayList();
4446
for (int i=0; i<100; i++)
4547
aList.add(i);
4648
assertEquals(0, aList.get(0));
@@ -50,6 +52,7 @@ public void testAdd() {
5052

5153
@Test
5254
public void testRemove() {
55+
List aList = new ArrayList();
5356
aList.add(1);
5457
aList.add(2);
5558
aList.add(3);
@@ -73,6 +76,7 @@ public void testRemove() {
7376

7477
@Test
7578
public void testSize() {
79+
List aList = new ArrayList();
7680
for (int i=0; i<10; i++)
7781
aList.add(i*2);
7882
assertEquals(10, aList.size());
@@ -83,6 +87,7 @@ public void testSize() {
8387

8488
@Test
8589
public void testException() {
90+
List aList = new ArrayList();
8691
expectedEx.expect(Exception.class);
8792

8893
aList.remove(1);
@@ -93,6 +98,7 @@ public void testException() {
9398

9499
@Test
95100
public void testIterator() {
101+
List aList = new ArrayList();
96102
Iterator it = aList.iterator();
97103
assertEquals(false, it.hasNext());
98104

0 commit comments

Comments
 (0)