Skip to content

Commit 9b12a29

Browse files
sofkylesofkyle
committed
提交第一次作业
1 parent 28616d8 commit 9b12a29

File tree

6 files changed

+686
-0
lines changed

6 files changed

+686
-0
lines changed

‎group09/396077060/20170226/src/per/zyf/bds/ArrayList.java

Lines changed: 174 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,174 @@
1+
/**
2+
* @Title: ArrayList.java
3+
* @Description: TODO(用一句话描述该文件做什么)
4+
* @author glorychou
5+
* @date 2017年2月22日 下午10:41:58
6+
*/
7+
package per.zyf.bds;
8+
9+
import java.util.Arrays;
10+
11+
/**
12+
* ArrayList的存储结构其实就是一维数组
13+
* 只不过在这个类中将对数组的一些操作（包括添加元素、删除元素等）封装了起来
14+
* @author glorychou
15+
*
16+
* @param <E>
17+
* @see per.zyf.bds.List<E>
18+
*/
19+
public class ArrayList<E> implements List<E> {
20+
// 默认数组大小
21+
private static final int DEFAULT_CAPACITY = 10;
22+
23+
// 数组实际大小
24+
private int size;
25+
26+
// 存储元素的数组
27+
protected Object[] elementData;
28+
29+
// 一个用来记录初始状态的空数组实例
30+
private static final Object[] CAPACITY_EMPTY_ELEMENTDATA = {};
31+
32+
/***
33+
* 构造初始元素数组
34+
*/
35+
public ArrayList() {
36+
this.elementData = CAPACITY_EMPTY_ELEMENTDATA;
37+
}
38+
39+
/***
40+
*
41+
* @Description: 在末尾添加元素
42+
* @param e 元素
43+
*/
44+
@Override
45+
public boolean add(E e) {
46+
int minCapacity = size + 1;
47+
48+
// 判断数组中是否有元素
49+
if (elementData == CAPACITY_EMPTY_ELEMENTDATA) {
50+
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
51+
}
52+
53+
// 判断是否溢出
54+
if (minCapacity - elementData.length > 0)
55+
grow(minCapacity);
56+
57+
// 添加元素
58+
elementData[size++] = e;
59+
60+
return true;
61+
}
62+
63+
/***
64+
*
65+
* @Description: 在索引指定位置增加元素
66+
* @param index 索引
67+
* @param e 元素
68+
*/
69+
@Override
70+
public boolean add(int index, E e) {
71+
int minCapacity = size + 1;
72+
73+
// 索引位置不合法抛出异常
74+
rangeCheck(index);
75+
76+
// 判断数组中是否有元素
77+
if (elementData == CAPACITY_EMPTY_ELEMENTDATA) {
78+
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
79+
}
80+
81+
// 判断是否溢出
82+
if (minCapacity - elementData.length > 0)
83+
grow(minCapacity);
84+
85+
// 插入点后的元素后移
86+
System.arraycopy(elementData, index, elementData, index + 1, size - index);
87+
88+
// 在索引处加入数据
89+
elementData[index] = e;
90+
91+
return true;
92+
}
93+
94+
/***
95+
*
96+
* @Description: 得到索引指定位置的元素
97+
* @param index 索引
98+
* @return E 索引指定的元素
99+
*/
100+
@Override
101+
@SuppressWarnings("unchecked")
102+
public E get(int index) {
103+
// 索引位置不合法抛出异常
104+
rangeCheck(index);
105+
106+
return (E) elementData[index];
107+
}
108+
109+
/***
110+
*
111+
* @Description: 删除索引指定位置的元素
112+
* @param index 索引
113+
* @return void
114+
*/
115+
@Override
116+
@SuppressWarnings("unchecked")
117+
public E remove(int index) {
118+
// 索引位置不合法抛出异常
119+
rangeCheck(index);
120+
121+
E removeElement = (E) elementData[index];
122+
123+
// 将要移除元素后的元素前移
124+
System.arraycopy(elementData, index + 1, elementData, index, size - index - 1);
125+
// 数组大小减一，并清除多余元素
126+
elementData[--size] = null;
127+
128+
return removeElement;
129+
}
130+
131+
/*
132+
* @see per.zyf.bds.List#size()
133+
*/
134+
@Override
135+
public int size() {
136+
return size;
137+
}
138+
139+
140+
/*
141+
* @see per.zyf.bds.List#isEmpty()
142+
*/
143+
@Override
144+
public boolean isEmpty() {
145+
if (elementData == CAPACITY_EMPTY_ELEMENTDATA) {
146+
return true;
147+
}
148+
return false;
149+
}
150+
151+
/***
152+
*
153+
* @Description: 溢出时增长空间
154+
* @param minCapacity 最小容量
155+
* @return void
156+
*/
157+
private void grow(int minCapacity) {
158+
int oldCapacity = elementData.length;
159+
// 容量增大一半
160+
int newCapacity = oldCapacity + (oldCapacity >> 1);
161+
elementData = Arrays.copyOf(elementData, newCapacity);
162+
}
163+
164+
/***
165+
*
166+
* @Description: 索引范围检查
167+
* @param index 索引
168+
* @return void
169+
*/
170+
private void rangeCheck(int index) {
171+
if (index < 0 || index > size)
172+
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
173+
}
174+
}

‎group09/396077060/20170226/src/per/zyf/bds/BinaryTree.java

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
/**
2+
* @Title: BinaryTree.java
3+
* @Description: TODO(用一句话描述该文件做什么)
4+
* @author glorychou
5+
* @date 2017年2月25日 下午10:22:03
6+
*/
7+
package per.zyf.bds;
8+
9+
import java.util.Comparator;
10+
11+
/**
12+
* @author glorychou
13+
*
14+
*/
15+
public class BinaryTree<E extends Comparable<E>> {
16+
// 根节点
17+
private Node<E> root;
18+
// 树大小
19+
private int size;
20+
21+
/**
22+
* @Description: 在树中插入元素
23+
* @param e 节点数据
24+
* @return boolean 处理情况
25+
*/
26+
public boolean add(E e) {
27+
28+
// 创建新节点
29+
final Node<E> newNode = new Node<>(null, e, null);
30+
31+
// 按照二叉排序方式插入
32+
if (root != null) {
33+
Node<E> parentNode = null;
34+
Node<E> compareNode = root;
35+
36+
while(compareNode != null) {
37+
// 新节点大于比较节点则插入右子树中
38+
if(e.compareTo(compareNode.item) > 0) {
39+
parentNode = compareNode;
40+
compareNode = compareNode.rightChild;
41+
42+
if(compareNode == null)
43+
parentNode.rightChild = newNode;
44+
} else {// 新节点小于或等于比较节点则插入左子树中
45+
parentNode = compareNode;
46+
compareNode = compareNode.leftChild;
47+
48+
if(compareNode == null)
49+
parentNode.rightChild = newNode;
50+
}
51+
}
52+
} else
53+
root = newNode;
54+
55+
return true;
56+
}
57+
58+
/**
59+
* @Description: 中序遍历输出
60+
* @return void 返回类型
61+
*/
62+
public void inorderPrint(Node<E> e) {
63+
if(e == null) return;
64+
inorderPrint(e.leftChild);
65+
System.out.print(e.item.toString() + " ");
66+
inorderPrint(e.rightChild);
67+
}
68+
69+
// 树节点
70+
private static class Node<E> {
71+
E item;
72+
Node<E> leftChild;
73+
Node<E> rightChild;
74+
75+
Node(Node<E> l, E e, Node<E> r) {
76+
leftChild = l;
77+
item = e;
78+
rightChild = r;
79+
}
80+
}
81+
}

0 commit comments

Comments
 (0)