Skip to content

Commit 37eb345

Browse files
zavierzavier
authored
Merge pull request onlyliuxin#13 from fei028/master
pull
2 parents 4c2f4ab + fb20d12 commit 37eb345

File tree

15 files changed

+813
-0
lines changed

15 files changed

+813
-0
lines changed

‎group01/2137642225/work01/.classpath

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
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="con" path="org.eclipse.jdt.junit.JUNIT_CONTAINER/4"/>
6+
<classpathentry kind="output" path="bin"/>
7+
</classpath>

‎group01/2137642225/work01/.gitignore

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

‎group01/2137642225/work01/.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>work01</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>

‎group01/2137642225/work01/src/com/coding/mybasic/ArrayList.java

Lines changed: 139 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,139 @@
1+
package com.coding.mybasic;
2+
3+
public class ArrayList implements List{
4+
5+
private static final int DEF_CAPACITY = 10;
6+
private int size;
7+
private Object[] elementData;
8+
9+
public ArrayList(){
10+
elementData = new Object[DEF_CAPACITY];
11+
}
12+
13+
public ArrayList(int initCapacity) {
14+
if(initCapacity <= 0){
15+
throw new RuntimeException("初始化长度必须大于0");
16+
}
17+
elementData = new Object[initCapacity];
18+
}
19+
20+
@Override
21+
public void add(Object element) {
22+
checkArrayOutOfRange();
23+
elementData[size++] = element;
24+
}
25+
26+
27+
@Override
28+
public void add(int index, Object element) {
29+
// 末尾插入
30+
if(index == size){
31+
add(element);
32+
return;
33+
}
34+
// index 在 0到size 之间,index之后元素要后移
35+
checkIndex(index);
36+
checkArrayOutOfRange();
37+
moveBackwardElement(index);
38+
elementData[index] = element;
39+
size++;
40+
}
41+
42+
43+
@Override
44+
public Object get(int index) {
45+
checkIndex(index);
46+
return elementData[index];
47+
}
48+
49+
@Override
50+
public Object remove(int index) {
51+
checkIndex(index);
52+
Object temp = elementData[index];
53+
moveForwardElement(index);
54+
elementData[size--] = null;
55+
return temp;
56+
}
57+
58+
59+
60+
@Override
61+
public int size() {
62+
return size;
63+
}
64+
65+
@Override
66+
public Iterator iterator() {
67+
return new ArrayListIterator();
68+
}
69+
70+
private class ArrayListIterator implements Iterator{
71+
private int i = 0;
72+
@Override
73+
public boolean hasNext() {
74+
return i < size;
75+
}
76+
77+
@Override
78+
public Object next() {
79+
checkIndex(i);
80+
return elementData[i++];
81+
}
82+
83+
}
84+
85+
/**
86+
* 数组增长
87+
* @param newCapacity 新数组容量
88+
*/
89+
private void grow(int newCapacity) {
90+
Object[] dest = new Object[newCapacity];
91+
System.arraycopy(elementData, 0, dest , 0, elementData.length);
92+
elementData = dest;
93+
}
94+
95+
/**
96+
* 检查index index >=0 且 < size
97+
* @param index
98+
* @throws Exception
99+
*/
100+
private void checkIndex(int index) {
101+
if(index < 0){
102+
throw new RuntimeException("index 必须大于0");
103+
}
104+
// 越界
105+
if(index >= size){
106+
throw new RuntimeException("index 必须小于size:" + size);
107+
}
108+
}
109+
110+
/**
111+
* 检查数组容量是否已满，已满则扩容
112+
*/
113+
private void checkArrayOutOfRange() {
114+
if(size >= elementData.length){
115+
// 扩容 默认新容量是原来容量的2倍
116+
grow(elementData.length * 2);
117+
}
118+
}
119+
120+
/**
121+
* 后移元素，从index开始
122+
* @param index
123+
*/
124+
private void moveBackwardElement(int index) {
125+
for (int i = size; i > index; i--) {
126+
elementData[i] = elementData[i - 1];
127+
}
128+
}
129+
/**
130+
* 前移元素,从index开始
131+
* @param index
132+
*/
133+
private void moveForwardElement(int index) {
134+
for (int i = index; i < size; i++) {
135+
elementData[i] = elementData[i + 1];
136+
}
137+
}
138+
139+
}

‎group01/2137642225/work01/src/com/coding/mybasic/BinaryTreeNode.java

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
package com.coding.mybasic;
2+
3+
public class BinaryTreeNode {
4+
5+
private Integer data;
6+
private BinaryTreeNode left;
7+
private BinaryTreeNode right;
8+
9+
public Object getData() {
10+
return data;
11+
}
12+
public void setData(Integer data) {
13+
this.data = data;
14+
}
15+
public BinaryTreeNode getLeft() {
16+
return left;
17+
}
18+
public void setLeft(BinaryTreeNode left) {
19+
this.left = left;
20+
}
21+
public BinaryTreeNode getRight() {
22+
return right;
23+
}
24+
public void setRight(BinaryTreeNode right) {
25+
this.right = right;
26+
}
27+
28+
public BinaryTreeNode insert(Integer o){
29+
if(o == null){
30+
throw new RuntimeException("不能插入空值");
31+
}
32+
BinaryTreeNode searchNode = search(this,o);
33+
if(isExistData(searchNode,o)){
34+
throw new RuntimeException("该值已存在 无法插入");
35+
}
36+
if(searchNode != null){
37+
BinaryTreeNode binaryTreeNode = new BinaryTreeNode();
38+
binaryTreeNode.setData(o);
39+
if(searchNode.data.intValue() > o.intValue()){
40+
searchNode.setLeft(binaryTreeNode);
41+
}else{
42+
searchNode.setRight(binaryTreeNode);
43+
}
44+
} else {
45+
throw new RuntimeException("根节点未赋值,无法插入");
46+
}
47+
return this;
48+
}
49+
50+
private boolean isExistData(BinaryTreeNode searchNode,Integer data) {
51+
return searchNode != null && searchNode.data.intValue() == data.intValue();
52+
53+
}
54+
55+
private BinaryTreeNode search(BinaryTreeNode binaryTreeNode, Integer data) {
56+
if(binaryTreeNode == null || binaryTreeNode.data == null){
57+
return null;
58+
}
59+
Integer curNodeData = binaryTreeNode.data;
60+
if(curNodeData.intValue() > data.intValue()){// 左 curNodeData > data
61+
if(binaryTreeNode.left != null){
62+
return search(binaryTreeNode.left,data);
63+
}
64+
}else if(curNodeData.intValue() < data.intValue()){
65+
if(binaryTreeNode.right != null){
66+
return search(binaryTreeNode.right,data);
67+
}
68+
69+
}
70+
return binaryTreeNode;
71+
}
72+
73+
}

‎group01/2137642225/work01/src/com/coding/mybasic/Iterator.java

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

0 commit comments

Comments
 (0)