Skip to content

Commit 480b655

Browse files
jodie-zssjodie-zss
authored
Merge pull request onlyliuxin#2 from wa122as/master
基本数据结构作业
2 parents d4a25d6 + 272a04f commit 480b655

File tree

8 files changed

+850
-0
lines changed

8 files changed

+850
-0
lines changed

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

Lines changed: 150 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,150 @@
1+
package com.coding.basic;
2+
3+
import java.util.Arrays;
4+
import java.util.NoSuchElementException;
5+
6+
/**
7+
* Created by wanc on 2017/2/21.
8+
* 实现ArrayList
9+
*/
10+
public class ArrayList implements List {
11+
/**
12+
* 实例化空数组 不用每次都new
13+
*/
14+
private static final Object[] Empty_elementData = {};
15+
/**
16+
* 计数
17+
*/
18+
private int size = 0;
19+
/**
20+
* 数据存放
21+
*/
22+
private Object[] elementData = new Object[100];
23+
24+
public ArrayList() {
25+
this.elementData = Empty_elementData;
26+
}
27+
28+
/**
29+
* 检查是否越界
30+
*/
31+
private void checkLenght(int index) {
32+
if (index - size > 0)
33+
throw new IndexOutOfBoundsException();
34+
}
35+
36+
/**
37+
* 增加数组容量
38+
*/
39+
private void kuorong() {
40+
elementData = Arrays.copyOf(elementData, size + 1);
41+
}
42+
43+
/**
44+
* 添加数据
45+
*
46+
* @param o
47+
*/
48+
public void add(Object o) {
49+
//扩容
50+
kuorong();
51+
//添加数据
52+
elementData[size++] = o;
53+
}
54+
55+
/**
56+
* 在指定索引添加数据
57+
*
58+
* @param index
59+
* @param o
60+
*/
61+
public void add(int index, Object o) {
62+
//扩容
63+
kuorong();
64+
//移动数据
65+
System.arraycopy(elementData, index, elementData, index + 1, size - index);
66+
//添加数据
67+
elementData[index] = o;
68+
size++;
69+
}
70+
71+
/**
72+
* 获取指定索引数据
73+
*
74+
* @param index
75+
* @return
76+
*/
77+
public Object get(int index) {
78+
//检查是否越界
79+
checkLenght(index);
80+
return elementData[index];
81+
}
82+
83+
/**
84+
* 移除指定索引数据
85+
*
86+
* @param index
87+
* @return
88+
*/
89+
public Object remove(int index) {
90+
//检查是否越界
91+
checkLenght(index);
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;
99+
return element;
100+
}
101+
102+
/**
103+
* 返回数量
104+
*
105+
* @return
106+
*/
107+
public int size() {
108+
return size;
109+
}
110+
111+
/**
112+
* 获取迭代器
113+
*
114+
* @return
115+
*/
116+
public Iterator iterator() {
117+
return new ArrayItr();
118+
}
119+
120+
//迭代器实现类部类
121+
private class ArrayItr implements Iterator {
122+
int cursor;//游标
123+
124+
@Override
125+
public boolean hasNext() {
126+
return cursor != size;
127+
}
128+
129+
@Override
130+
public Object next() {
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;
136+
return newElementData[i];
137+
}
138+
}
139+
140+
/**
141+
* 重写toString 方便打印
142+
*
143+
* @return
144+
*/
145+
@Override
146+
public String toString() {
147+
Object[] s = Arrays.copyOf(elementData, size);
148+
return Arrays.toString(s);
149+
}
150+
}

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

Lines changed: 184 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,184 @@
1+
package com.coding.basic;
2+
3+
import org.junit.Assert;
4+
import org.junit.Test;
5+
6+
/**
7+
* Created by wanc on 2017/2/21.
8+
*/
9+
public class BasicTest {
10+
11+
@Test
12+
public void test() {
13+
//测试
14+
testArrayList();
15+
testLinkedList();
16+
testBinaryTreeNode();
17+
testStack();
18+
testQueue();
19+
}
20+
21+
22+
public void testQueue(){
23+
Queue queue = new Queue();
24+
queue.enQueue("S");
25+
queue.enQueue("Y");
26+
queue.enQueue(5);
27+
System.out.println(queue);
28+
System.out.println("queue.size()="+queue.size());
29+
System.out.println("queue.deQueue()="+queue.deQueue());
30+
System.out.println(queue);
31+
System.out.println("queue.isEmpty()="+queue.isEmpty());
32+
System.out.println(queue);
33+
}
34+
public void testStack(){
35+
Stack stack = new Stack();
36+
stack.push("S");
37+
stack.push("Y");
38+
stack.push(5);
39+
System.out.println("stack.size()="+stack.size());
40+
System.out.println("stack.peek()="+stack.peek());
41+
System.out.println(stack);
42+
System.out.println("stack.isEmpty()="+stack.isEmpty());
43+
stack.pop();
44+
System.out.println(stack);
45+
}
46+
public void testBinaryTreeNode(){
47+
System.out.println("-------------------BinaryTreeNode 测试开始-------------------");
48+
System.out.println("new 一个实例");
49+
BinaryTreeNode root = new BinaryTreeNode();
50+
root.insert(5);
51+
root.insert(6);
52+
root.insert(9);
53+
root.insert(3);
54+
root.insert(3);
55+
root.insert(2);
56+
root.insert(10);
57+
System.out.println(root);
58+
System.out.println("-------------------LinkedList 测试结束-------------------");
59+
}
60+
public void testLinkedList() {
61+
System.out.println("-------------------LinkedList 测试开始-------------------");
62+
63+
System.out.println("new 一个实例");
64+
LinkedList list = new LinkedList();
65+
66+
System.out.println("添加元素----A");
67+
list.add("A");
68+
Assert.assertEquals(list.get(list.size()-1),"A");
69+
System.out.println("结果："+list);
70+
71+
System.out.println();
72+
System.out.println("添加元素----B");
73+
list.add("B");
74+
Assert.assertEquals(list.get(list.size()-1),"B");
75+
System.out.println("结果："+list);
76+
77+
System.out.println();
78+
System.out.println("添加元素----3");
79+
list.add(3);
80+
Assert.assertEquals(list.get(list.size()-1),3);
81+
System.out.println("结果："+list);
82+
83+
System.out.println();
84+
System.out.println("在下标1插入元素----3");
85+
list.add(1, 3);
86+
Assert.assertEquals(list.get(1),3);
87+
System.out.println("结果："+list);
88+
89+
System.out.println();
90+
System.out.println("在下标3插入元素----6");
91+
list.add(3, 6);
92+
Assert.assertEquals(list.get(3),6);
93+
System.out.println("结果："+list);
94+
95+
System.out.println();
96+
System.out.println("删除下标0元素");
97+
list.remove(0);
98+
System.out.println("结果："+list);
99+
100+
System.out.println();
101+
System.out.println("获取size");
102+
System.out.println("结果："+list.size());
103+
104+
System.out.println();
105+
System.out.println("在首位前插入F");
106+
list.addFirst("F");
107+
Assert.assertEquals(list.get(0),"F");
108+
System.out.println("结果："+list);
109+
110+
System.out.println();
111+
System.out.println("在末位前插入K");
112+
list.addLast("K");
113+
Assert.assertEquals(list.get(list.size()-1),"K");
114+
System.out.println("结果："+list);
115+
116+
System.out.println();
117+
System.out.println("删除首位");
118+
list.removeFirst();
119+
System.out.println("结果："+list);
120+
121+
System.out.println();
122+
System.out.println("删除末尾");
123+
list.removeLast();
124+
System.out.println("结果："+list);
125+
126+
System.out.println();
127+
System.out.println("迭代器输出：");
128+
Iterator i = list.iterator();
129+
while (i.hasNext()){
130+
System.out.print(i.next()+" ");
131+
}
132+
System.out.println("-------------------LinkedList 测试结束-------------------");
133+
}
134+
135+
/**
136+
* 测试 ArrayList
137+
*/
138+
public void testArrayList() {
139+
System.out.println("-------------------ArrayList 测试开始-------------------");
140+
141+
System.out.println("new 一个实例");
142+
ArrayList list = new ArrayList();
143+
144+
System.out.println("添加元素 A");
145+
list.add("A");
146+
Assert.assertEquals(list.get(list.size()-1),"A");
147+
148+
System.out.println("添加元素 B");
149+
list.add("B");
150+
Assert.assertEquals(list.get(list.size()-1),"B");
151+
152+
System.out.println("添加元素 3");
153+
list.add(3);
154+
Assert.assertEquals(list.get(list.size()-1),3);
155+
System.out.println("输出："+list);
156+
157+
System.out.println("添加元素 3 到索引 1");
158+
list.add(1, 3);
159+
Assert.assertEquals(list.get(1),3);
160+
System.out.println("输出："+list);
161+
162+
System.out.println("添加元素 6 到索引 3");
163+
list.add(3, 6);
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());
177+
Iterator i = list.iterator();
178+
System.out.print("迭代器输出：");
179+
while (i.hasNext()){
180+
System.out.print(i.next()+" ");
181+
}
182+
System.out.println("-------------------ArrayList 测试结束-------------------");
183+
}
184+
}

0 commit comments

Comments
 (0)