Skip to content

Commit 07d5f8e

Browse files
matthewpengmatthewpeng
committed
2月19号作业
实现基本的数据结构ArrayList,Stack,LinkedList, Queue, 二叉树,Iterator;
1 parent a537538 commit 07d5f8e

File tree

11 files changed

+514
-0
lines changed

11 files changed

+514
-0
lines changed

‎group18/68773479/.classpath

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<classpath>
3+
<classpathentry kind="src" path="src"/>
4+
<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER"/>
5+
<classpathentry kind="output" path="bin"/>
6+
</classpath>

‎group18/68773479/.gitignore

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
/bin/

‎group18/68773479/.project

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<projectDescription>
3+
<name>CodingPractice</name>
4+
<comment></comment>
5+
<projects>
6+
</projects>
7+
<buildSpec>
8+
<buildCommand>
9+
<name>org.eclipse.jdt.core.javabuilder</name>
10+
<arguments>
11+
</arguments>
12+
</buildCommand>
13+
</buildSpec>
14+
<natures>
15+
<nature>org.eclipse.jdt.core.javanature</nature>
16+
</natures>
17+
</projectDescription>

‎group18/68773479/src/com/matthew/practice/structure/BinaryTreeNode.java

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package com.matthew.practice.structure;
2+
3+
4+
public class BinaryTreeNode {
5+
private Object data;
6+
private BinaryTreeNode left;
7+
private BinaryTreeNode right;
8+
9+
public Object getData() {
10+
return data;
11+
}
12+
13+
public void setData(Object data) {
14+
this.data = data;
15+
}
16+
17+
public BinaryTreeNode getLeft() {
18+
return left;
19+
}
20+
21+
public void setLeft(BinaryTreeNode left) {
22+
this.left = left;
23+
}
24+
25+
public BinaryTreeNode getRight() {
26+
return right;
27+
}
28+
29+
public void setRight(BinaryTreeNode right) {
30+
this.right = right;
31+
}
32+
33+
public BinaryTreeNode insert(Object o) {
34+
return null;
35+
}
36+
}

‎group18/68773479/src/com/matthew/practice/structure/Iterator.java

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

‎group18/68773479/src/com/matthew/practice/structure/MyArrayList.java

Lines changed: 97 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,97 @@
1+
package com.matthew.practice.structure;
2+
3+
4+
import java.util.Arrays;
5+
6+
public class MyArrayList<E> implements MyList<E> {
7+
//思考为什么要用transient
8+
//elementData数组相当于容器，当容器不足时就会再扩充容量，但是容器的容量往往都是大于或者等于ArrayList所存元素的个数。
9+
//比如，现在实际有了8个元素，那么elementData数组的容量可能是8x1.5=12，如果直接序列化elementData数组，那么就会浪费4
10+
//个元素的空间，特别是当元素个数非常多时，这种浪费是非常不合算的。所以ArrayList的设计者将elementData设计为transient，
11+
//然后在writeObject方法中手动将其序列化，并且只序列化了实际存储的那些元素，而不是整个数组。
12+
transient Object[] elementData;
13+
private static final Object[] EMPTY_ELEMENTDATA = {};
14+
private int size;
15+
//容器的默认大小
16+
private static final int DEFAULT_CAPACITY = 10;
17+
18+
//添加元素
19+
@Override
20+
public void add(E o) {
21+
//加入这个元素后 数组的容量至少要 +1 确保容量足够
22+
ensureCapacityInternal(size + 1); // Increments modCount!!
23+
elementData[size++] = o;
24+
}
25+
26+
27+
private void ensureCapacityInternal(int minCapacity) {
28+
if (elementData == EMPTY_ELEMENTDATA) {
29+
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
30+
}
31+
32+
ensureExplicitCapacity(minCapacity);
33+
}
34+
35+
private void ensureExplicitCapacity(int minCapacity) {
36+
37+
if (minCapacity - elementData.length > 0)
38+
grow(minCapacity);
39+
}
40+
41+
private void grow(int minCapacity) {
42+
int oldCapacity = elementData.length;
43+
// >>1: 右移1位， 右移一位相当于除2，右移n位相当于除以2的n次方。扩大原来的一半
44+
int newCapacity = oldCapacity + (oldCapacity >> 1);
45+
//容量的最小值minCapacity 比新的容量大小newCapacity还要大的时候 就赋值给newCapacity
46+
if (newCapacity - minCapacity < 0)
47+
newCapacity = minCapacity;
48+
//底层System.arraycopy
49+
elementData = Arrays.copyOf(elementData, newCapacity);
50+
}
51+
52+
@Override
53+
public void add(int index, E o) {
54+
if (index > size || index < 0)
55+
//数组越界异常
56+
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
57+
ensureCapacityInternal(size + 1);
58+
System.arraycopy(elementData, index, elementData, index + 1,
59+
size - index);
60+
elementData[index] = o;
61+
size++;
62+
}
63+
64+
private String outOfBoundsMsg(int index) {
65+
return "Index: " + index + ", Size: " + size;
66+
}
67+
68+
@Override
69+
public E get(int index) {
70+
if (index >= size)
71+
//数组越界异常
72+
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
73+
return (E) elementData[index];
74+
}
75+
76+
//将后面的元素向前移
77+
@Override
78+
public E remove(int index) {
79+
if (index >= size)
80+
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
81+
82+
E oldValue = (E) elementData[index];
83+
84+
int numMoved = size - index - 1;
85+
if (numMoved > 0)
86+
System.arraycopy(elementData, index + 1, elementData, index,
87+
numMoved);
88+
elementData[--size] = null;
89+
90+
return (E) oldValue;
91+
}
92+
93+
@Override
94+
public int size() {
95+
return size;
96+
}
97+
}

‎group18/68773479/src/com/matthew/practice/structure/MyArrayQueue.java

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
package com.matthew.practice.structure;
2+
3+
4+
public class MyArrayQueue<T> implements MyQueue<T> {
5+
private T[] data;
6+
private int size;//元素个数
7+
private int front;//队列中第一个对象的位置
8+
private int rear;//队列中当前对象的位置
9+
10+
public MyArrayQueue() {
11+
data = (T[]) new Object[10];
12+
size = 0;
13+
front = 0;
14+
rear = 0;
15+
}
16+
17+
@Override
18+
public void add(T t) {
19+
if (isFull()) {
20+
resize();
21+
front = 0;
22+
}
23+
rear = (front + size) % data.length;
24+
data[rear] = t;
25+
size++;
26+
}
27+
28+
@Override
29+
public T remove() {
30+
if (isEmpty()) {
31+
throw new RuntimeException("队列为空!");
32+
}
33+
T tempData = data[front];
34+
data[front] = null;
35+
//思考一下这里有必要进行除法运算吗?
36+
37+
front = (front + 1) % (data.length);
38+
size--;
39+
return tempData;
40+
}
41+
42+
@Override
43+
public int size() {
44+
return size;
45+
}
46+
47+
@Override
48+
public boolean isEmpty() {
49+
return size == 0;
50+
}
51+
52+
@Override
53+
public T front() {
54+
if (isEmpty()) {
55+
throw new RuntimeException("队列为空!");
56+
}
57+
return data[front];
58+
}
59+
60+
/**
61+
* 判断当前队列是否已满
62+
*
63+
* @return
64+
*/
65+
public boolean isFull() {
66+
return size == data.length;
67+
}
68+
69+
/**
70+
* 扩容，2倍
71+
*/
72+
public void resize() {
73+
/*注意重新扩容的时候并不需要去设置size
74+
* 队列的大小并不能通过数组的大小直观的显示出来。
75+
* 但是栈就可以直观的通过数组的大小显示出来*/
76+
T[] tmp = (T[]) new Object[data.length * 2];
77+
System.arraycopy(data, 0, tmp, 0, data.length);
78+
data = tmp;
79+
tmp = null;//引用置为空，便于gc处理
80+
}
81+
}

0 commit comments

Comments
 (0)