Skip to content

Commit 00c7584

Browse files
nusubmarine01nusubmarine01
authored
Merge pull request onlyliuxin#12 from barrywangmeng/master
为.gitignore添加空格。
2 parents bd10c5c + a20b467 commit 00c7584

File tree

8 files changed

+638
-0
lines changed

8 files changed

+638
-0
lines changed

‎group03/510782645/.gitignore

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
# Class files
2+
*.class
3+
4+
# Package Files
5+
*.jar
6+
*.war
7+
*.ear
8+
9+
# Virtual machine crash logs, see http://www.java.com/en/download/help/error_hotspot.xml
10+
hs_err_pid*
11+
12+
# Ignore web-site project
13+
*web-site/
14+
15+
# Temporary files
16+
.DS_STORE
17+
*.log
18+
19+
# Maven related
20+
/*/target/
21+
target
22+
23+
# Netbeans related
24+
nb-configuration.xml
25+
nbactions.xml
26+
nbproject
27+
28+
# Eclipse related
29+
*.classpath
30+
*.project
31+
.settings
32+
33+
# IntelliJ related
34+
.idea
35+
*.iml
36+
*.ipr
37+
*.iws
38+
39+
# Jrebel related
40+
rebel.xml
41+
rebel-remote.xml
42+
43+
# design model
44+
*.eab
45+
46+
.idea/workspace.xml

‎group03/510782645/src/com/coding/basic/ArrayList.java

Lines changed: 152 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,152 @@
1+
package com.coding.basic;
2+
3+
import java.util.Arrays;
4+
import java.util.ConcurrentModificationException;
5+
6+
public class ArrayList implements List {
7+
/**
8+
* 当数组进行add/remove时， 对modCount进行++
9+
*/
10+
protected transient int modCount = 0;
11+
/**
12+
* 数组的大小
13+
*/
14+
private int size = 0;
15+
16+
/**
17+
* 数组，用来存放ArrayList的内容。
18+
*/
19+
private Object[] elementData;
20+
21+
public ArrayList() {
22+
this(10);
23+
}
24+
25+
public ArrayList(int intialSize) {
26+
elementData = new Object[intialSize];
27+
}
28+
29+
public void add(Object o) {
30+
modCount++;
31+
// 检测是否要扩容，当添加的元素大于数组的长度后， 扩容
32+
increment(size + 1);
33+
elementData[size++] = o;
34+
}
35+
36+
public void add(int index, Object o) {
37+
modCount++;
38+
increment(size + 1);
39+
/**
40+
* @param src
41+
* 源数组
42+
* @param srcPos
43+
* 源数组要复制的起始位置
44+
* @param dest
45+
* 目的数组
46+
* @param destPos
47+
* 目的数组放置的起始位置
48+
* @param length
49+
* 复制的长度 从index位置开始copy，
50+
*/
51+
System.arraycopy(elementData, index, elementData, index + 1, size - index);
52+
elementData[index] = o;
53+
}
54+
55+
/**
56+
* 验证是否要扩容。
57+
*
58+
* @param capacity
59+
*/
60+
private void increment(int capacity) {
61+
if (capacity - elementData.length > 0) {
62+
grow(capacity);
63+
}
64+
}
65+
66+
/**
67+
* 扩容，扩容规则为：oldCapacity + oldCapacity/2
68+
*
69+
* @param capacity
70+
*/
71+
private void grow(int capacity) {
72+
int oldCapacity = elementData.length;
73+
int newCapacity = oldCapacity + oldCapacity / 2;
74+
elementData = Arrays.copyOf(elementData, newCapacity);
75+
}
76+
77+
public Object get(int index) throws Exception {
78+
checkSize(index);
79+
return elementData[index];
80+
}
81+
82+
public Object remove(int index) throws Exception {
83+
modCount++;
84+
checkSize(index);
85+
Object oldValue = elementData[index];
86+
System.arraycopy(elementData, index + 1, elementData, index, size - index - 1);
87+
//回收多出来的内存。
88+
elementData[size--] = null;
89+
return oldValue;
90+
}
91+
92+
/**
93+
* 验证给定的数组下标是否小于数组的长度。
94+
*
95+
* @param index
96+
* @return
97+
*/
98+
private void checkSize(int index) throws Exception {
99+
if (index > size) {
100+
// 数组下标越界异常。
101+
throw new IndexOutOfBoundsException();
102+
}
103+
}
104+
105+
public int size() {
106+
return size;
107+
}
108+
109+
public Iterator iterator() {
110+
return new Itr();
111+
}
112+
113+
private class Itr implements Iterator {
114+
int cursor;//记录下一个元素的索引
115+
int lastReturn = -1;//记录最后一个元素的索引
116+
int expectCount = modCount;
117+
118+
@Override
119+
public boolean hasNext() {
120+
return (cursor != size);
121+
}
122+
123+
@Override
124+
public Object next() {
125+
checkForComodification();
126+
int i = cursor;
127+
Object[] elementData = ArrayList.this.elementData;
128+
cursor = i+ 1;
129+
return elementData[lastReturn = i];
130+
}
131+
132+
/**
133+
* 核心方法， 这里remove可以避免fail-fast快速失败原则。
134+
* @throws Exception
135+
*/
136+
public void remove() throws Exception {
137+
checkForComodification();
138+
ArrayList.this.remove(lastReturn);
139+
cursor = lastReturn;
140+
lastReturn = -1;
141+
expectCount = modCount;
142+
}
143+
144+
/**
145+
* 验证fail-fast规则。
146+
*/
147+
final void checkForComodification() {
148+
if (modCount != expectCount)
149+
throw new ConcurrentModificationException();
150+
}
151+
}
152+
}

‎group03/510782645/src/com/coding/basic/BinaryTreeNode.java

Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,83 @@
1+
package com.coding.basic;
2+
3+
public class BinaryTreeNode {
4+
5+
static class Node {
6+
Integer data;
7+
Node parent;
8+
Node left;
9+
Node right;
10+
11+
public Node(Integer data, Node parent, Node left, Node right) {
12+
this.data = data;
13+
this.parent = parent;
14+
this.left = left;
15+
this.right = right;
16+
}
17+
18+
public String toString(){
19+
return "[data=" + data + "]";
20+
}
21+
22+
public boolean equals(Object obj){
23+
if(this == obj){
24+
return true;
25+
}
26+
27+
if(obj.getClass() == Node.class){
28+
Node target = (Node) obj;
29+
return data.equals(target.data) && left == target.left
30+
&& right == target.right && parent == target.parent;
31+
}
32+
33+
return false;
34+
}
35+
}
36+
private Node root;
37+
38+
BinaryTreeNode() {
39+
root = null;
40+
}
41+
42+
BinaryTreeNode(Integer data) {
43+
root = new Node(data, null, null, null);
44+
}
45+
46+
/**
47+
* 暂且使用Intenger作为节点数据。
48+
* @param o
49+
*/
50+
public void insert(Integer o) {
51+
if (root == null) {
52+
root = new Node(o, null, null, null);
53+
} else {
54+
Node current = root;
55+
Node parent = null;
56+
int cmp;
57+
58+
//搜索合适的叶子节点，以该叶子节点为父节点添加新节点
59+
do {
60+
parent = current;
61+
cmp = o.compareTo(current.data);
62+
63+
//如果新节点的值大于当前节点的值
64+
if (cmp > 0) {
65+
//以当前节点的右子节点作为当前节点
66+
current = current.right;
67+
} else {
68+
current = current.left;
69+
}
70+
} while (current != null);
71+
72+
//创建新节点
73+
Node newNode = new Node(o, parent, null, null);
74+
75+
//如果新节点的值大于父节点的值
76+
if (cmp > 0) {
77+
parent.right = newNode;
78+
} else {
79+
parent.left = newNode;
80+
}
81+
}
82+
}
83+
}

‎group03/510782645/src/com/coding/basic/Iterator.java

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

0 commit comments

Comments
 (0)