Skip to content

Commit 272a04f

Browse files
author
wa122as
committed
基本数据结构作业
1 parent 6edb4f1 commit 272a04f

File tree

6 files changed

+391
-104
lines changed

6 files changed

+391
-104
lines changed

‎group15/1521_653895972/src/com/coding/basic/ArrayList.java

Lines changed: 87 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -3,79 +3,148 @@
33
import java.util.Arrays;
44
import java.util.NoSuchElementException;
55

6+
/**
7+
* Created by wanc on 2017/2/21.
8+
* 实现ArrayList
9+
*/
610
public class ArrayList implements List {
7-
//实例化空数组 不用每次都new
11+
/**
12+
* 实例化空数组 不用每次都new
13+
*/
814
private static final Object[] Empty_elementData = {};
15+
/**
16+
* 计数
17+
*/
918
private int size = 0;
10-
19+
/**
20+
* 数据存放
21+
*/
1122
private Object[] elementData = new Object[100];
1223

1324
public ArrayList() {
1425
this.elementData = Empty_elementData;
1526
}
16-
//检查是否越界
17-
private void checkLenght(int index){
27+
28+
/**
29+
* 检查是否越界
30+
*/
31+
private void checkLenght(int index) {
1832
if (index - size > 0)
1933
throw new IndexOutOfBoundsException();
2034
}
21-
//增加数组容量
22-
private void kuorong(){
35+
36+
/**
37+
* 增加数组容量
38+
*/
39+
private void kuorong() {
2340
elementData = Arrays.copyOf(elementData, size + 1);
2441
}
42+
43+
/**
44+
* 添加数据
45+
*
46+
* @param o
47+
*/
2548
public void add(Object o) {
49+
//扩容
2650
kuorong();
51+
//添加数据
2752
elementData[size++] = o;
2853
}
2954

55+
/**
56+
* 在指定索引添加数据
57+
*
58+
* @param index
59+
* @param o
60+
*/
3061
public void add(int index, Object o) {
62+
//扩容
3163
kuorong();
64+
//移动数据
3265
System.arraycopy(elementData, index, elementData, index + 1, size - index);
66+
//添加数据
3367
elementData[index] = o;
3468
size++;
3569
}
3670

71+
/**
72+
* 获取指定索引数据
73+
*
74+
* @param index
75+
* @return
76+
*/
3777
public Object get(int index) {
78+
//检查是否越界
3879
checkLenght(index);
3980
return elementData[index];
4081
}
4182

83+
/**
84+
* 移除指定索引数据
85+
*
86+
* @param index
87+
* @return
88+
*/
4289
public Object remove(int index) {
90+
//检查是否越界
4391
checkLenght(index);
44-
Object element =elementData[index];
45-
int movesize=size-index-1;
46-
System.arraycopy(elementData,index+1,elementData,index,movesize);
47-
elementData[--size]=null;
92+
Object element = elementData[index];
93+
//计算移除该元素后，要前移的个数
94+
int movesize = size - index - 1;
95+
//移动数据
96+
System.arraycopy(elementData, index + 1, elementData, index, movesize);
97+
//删除末尾元素
98+
elementData[--size] = null;
4899
return element;
49100
}
50101

102+
/**
103+
* 返回数量
104+
*
105+
* @return
106+
*/
51107
public int size() {
52108
return size;
53109
}
54110

111+
/**
112+
* 获取迭代器
113+
*
114+
* @return
115+
*/
55116
public Iterator iterator() {
56117
return new ArrayItr();
57118
}
58-
private class ArrayItr implements Iterator{
119+
120+
//迭代器实现类部类
121+
private class ArrayItr implements Iterator {
59122
int cursor;//游标
123+
60124
@Override
61125
public boolean hasNext() {
62-
return cursor!=size;
126+
return cursor != size;
63127
}
64128

65129
@Override
66130
public Object next() {
67-
int i=cursor;
68-
if (i>size)throw new NoSuchElementException();
69-
Object [] newElementData = ArrayList.this.elementData;
70-
if (i>newElementData.length)throw new IndexOutOfBoundsException();
71-
cursor=i+1;
131+
int i = cursor;
132+
if (i > size) throw new NoSuchElementException();
133+
Object[] newElementData = ArrayList.this.elementData;
134+
if (i > newElementData.length) throw new IndexOutOfBoundsException();
135+
cursor = i + 1;
72136
return newElementData[i];
73137
}
74138
}
75139

140+
/**
141+
* 重写toString 方便打印
142+
*
143+
* @return
144+
*/
76145
@Override
77146
public String toString() {
78-
Object[] s = Arrays.copyOf(elementData,size);
147+
Object[] s = Arrays.copyOf(elementData, size);
79148
return Arrays.toString(s);
80149
}
81150
}

‎group15/1521_653895972/src/com/coding/basic/BasicTest.java

Lines changed: 76 additions & 42 deletions
Original file line numberDiff line numberDiff line change
@@ -11,10 +11,10 @@ public class BasicTest {
1111
@Test
1212
public void test() {
1313
//测试
14-
// testArrayList();
15-
// testLinkedList();
16-
// testBinaryTreeNode();
17-
// testStack();
14+
testArrayList();
15+
testLinkedList();
16+
testBinaryTreeNode();
17+
testStack();
1818
testQueue();
1919
}
2020

@@ -59,91 +59,125 @@ public void testBinaryTreeNode(){
5959
}
6060
public void testLinkedList() {
6161
System.out.println("-------------------LinkedList 测试开始-------------------");
62+
6263
System.out.println("new 一个实例");
6364
LinkedList list = new LinkedList();
64-
System.out.println("1.add(\"A\") 添加元素----A");
65+
66+
System.out.println("添加元素----A");
6567
list.add("A");
68+
Assert.assertEquals(list.get(list.size()-1),"A");
6669
System.out.println("结果："+list);
70+
6771
System.out.println();
68-
System.out.println("2.add(\"B\") 添加元素----B");
72+
System.out.println("添加元素----B");
6973
list.add("B");
74+
Assert.assertEquals(list.get(list.size()-1),"B");
7075
System.out.println("结果："+list);
76+
7177
System.out.println();
72-
System.out.println("3.add(3) 添加元素----3");
78+
System.out.println("添加元素----3");
7379
list.add(3);
80+
Assert.assertEquals(list.get(list.size()-1),3);
7481
System.out.println("结果："+list);
82+
7583
System.out.println();
76-
System.out.println("4.add(1, 3) 在下标1插入元素----3");
84+
System.out.println("在下标1插入元素----3");
7785
list.add(1, 3);
86+
Assert.assertEquals(list.get(1),3);
7887
System.out.println("结果："+list);
88+
7989
System.out.println();
80-
System.out.println("5.add(3, 6) 在下标3插入元素----6");
90+
System.out.println("在下标3插入元素----6");
8191
list.add(3, 6);
92+
Assert.assertEquals(list.get(3),6);
8293
System.out.println("结果："+list);
94+
8395
System.out.println();
84-
System.out.println("6.remove(0) 删除下标0元素");
96+
System.out.println("删除下标0元素");
8597
list.remove(0);
8698
System.out.println("结果："+list);
99+
87100
System.out.println();
88-
System.out.println("7.size() 获取size");
101+
System.out.println("获取size");
89102
System.out.println("结果："+list.size());
103+
90104
System.out.println();
91-
System.out.println("8.addFirst(\"F\") 在首位前插入F");
105+
System.out.println("在首位前插入F");
92106
list.addFirst("F");
107+
Assert.assertEquals(list.get(0),"F");
93108
System.out.println("结果："+list);
94-
System.out.println("9.addLast(\"K\") 在末位前插入K");
109+
110+
System.out.println();
111+
System.out.println("在末位前插入K");
95112
list.addLast("K");
113+
Assert.assertEquals(list.get(list.size()-1),"K");
96114
System.out.println("结果："+list);
97-
System.out.println("10.removeFirst() 删除首位");
115+
116+
System.out.println();
117+
System.out.println("删除首位");
98118
list.removeFirst();
99119
System.out.println("结果："+list);
100-
System.out.println("11.removeLast() 删除末尾");
120+
121+
System.out.println();
122+
System.out.println("删除末尾");
101123
list.removeLast();
102124
System.out.println("结果："+list);
125+
103126
System.out.println();
104-
System.out.println("12.迭代器");
127+
System.out.println("迭代器输出：");
105128
Iterator i = list.iterator();
106129
while (i.hasNext()){
107-
System.out.println(i.next());
130+
System.out.print(i.next()+" ");
108131
}
109132
System.out.println("-------------------LinkedList 测试结束-------------------");
110133
}
134+
135+
/**
136+
* 测试 ArrayList
137+
*/
111138
public void testArrayList() {
112139
System.out.println("-------------------ArrayList 测试开始-------------------");
140+
113141
System.out.println("new 一个实例");
114142
ArrayList list = new ArrayList();
115-
System.out.println("1.添加元素----A");
143+
144+
System.out.println("添加元素 A");
116145
list.add("A");
117-
Assert.assertEquals(list.get(0),"A");
118-
System.out.println("结果："+list);
119-
System.out.println();
120-
System.out.println("2.添加元素----B");
146+
Assert.assertEquals(list.get(list.size()-1),"A");
147+
148+
System.out.println("添加元素 B");
121149
list.add("B");
122-
System.out.println("结果："+list);
123-
System.out.println();
124-
System.out.println("3.添加元素----3");
150+
Assert.assertEquals(list.get(list.size()-1),"B");
151+
152+
System.out.println("添加元素 3");
125153
list.add(3);
126-
System.out.println("结果："+list);
127-
System.out.println();
128-
System.out.println("4.在下标1插入元素----3");
154+
Assert.assertEquals(list.get(list.size()-1),3);
155+
System.out.println("输出："+list);
156+
157+
System.out.println("添加元素 3 到索引 1");
129158
list.add(1, 3);
130-
System.out.println("结果："+list);
131-
System.out.println();
132-
System.out.println("5.在下标3插入元素----6");
159+
Assert.assertEquals(list.get(1),3);
160+
System.out.println("输出："+list);
161+
162+
System.out.println("添加元素 6 到索引 3");
133163
list.add(3, 6);
134-
System.out.println("结果："+list);
135-
System.out.println();
136-
System.out.println("6.删除下标0元素");
137-
list.remove(0);
138-
System.out.println("结果："+list);
139-
System.out.println();
140-
System.out.println("7.获取size");
141-
System.out.println("结果："+list.size());
142-
System.out.println();
143-
System.out.println("8.迭代器");
164+
Assert.assertEquals(list.get(3),6);
165+
System.out.println("输出："+list);
166+
167+
System.out.println("移除 索引 4 元素");
168+
Object rm = list.remove(4);
169+
System.out.println("输出："+list);
170+
171+
System.out.println("获取 索引 4 元素");
172+
Object get = list.get(4);
173+
Assert.assertNotEquals(rm,get);
174+
175+
System.out.println("输出："+list);
176+
System.out.println("数量："+list.size());
144177
Iterator i = list.iterator();
178+
System.out.print("迭代器输出：");
145179
while (i.hasNext()){
146-
System.out.println(i.next());
180+
System.out.print(i.next()+" ");
147181
}
148182
System.out.println("-------------------ArrayList 测试结束-------------------");
149183
}

0 commit comments

Comments
 (0)