Skip to content

Commit 4855142

Browse files
zhanglifengzhanglifeng
authored
Merge pull request onlyliuxin#11 from XiaoQin0000/master
提交作业：591010847
2 parents 170b7da + 31b86e6 commit 4855142

File tree

14 files changed

+1014
-0
lines changed

14 files changed

+1014
-0
lines changed

‎group05/591010847/job_2017_02/job_2017_02_19_data_structure/.gitignore

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
/vendor
2+
/node_modules
3+
Homestead.yaml
4+
Homestead.json
5+
.env
6+
.idea
7+
.xml

‎group05/591010847/job_2017_02/job_2017_02_19_data_structure/job_2017_02_19_data_structure.iml

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<module type="JAVA_MODULE" version="4">
3+
<component name="NewModuleRootManager" inherit-compiler-output="true">
4+
<exclude-output />
5+
<content url="file://$MODULE_DIR$">
6+
<sourceFolder url="file://$MODULE_DIR$/src" isTestSource="false" />
7+
</content>
8+
<orderEntry type="inheritedJdk" />
9+
<orderEntry type="sourceFolder" forTests="false" />
10+
<orderEntry type="module-library">
11+
<library name="JUnit4">
12+
<CLASSES>
13+
<root url="jar://$APPLICATION_HOME_DIR$/lib/junit-4.12.jar!/" />
14+
<root url="jar://$APPLICATION_HOME_DIR$/lib/hamcrest-core-1.3.jar!/" />
15+
</CLASSES>
16+
<JAVADOC />
17+
<SOURCES />
18+
</library>
19+
</orderEntry>
20+
</component>
21+
</module>

‎group05/591010847/job_2017_02/job_2017_02_19_data_structure/src/com/java/xiaoqin/impl/ArrayListImpl.java

Lines changed: 127 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,127 @@
1+
package com.java.xiaoqin.impl;
2+
3+
import com.java.xiaoqin.interfaces.IIterator;
4+
import com.java.xiaoqin.interfaces.IList;
5+
6+
/**
7+
* Created by xiaoqin on 17-2-25.
8+
*/
9+
public class ArrayListImpl<T> implements IList<T> {
10+
11+
private static final int DEFAULT_INIT_SIZE = 20;
12+
13+
private T[] data;
14+
15+
private int size = 0;
16+
17+
public ArrayListImpl() {
18+
this(DEFAULT_INIT_SIZE);
19+
}
20+
21+
public ArrayListImpl(int capacity) {
22+
if (capacity < 0) {
23+
throw new IllegalArgumentException("无效的capacity：" + capacity);
24+
}
25+
if (0 == capacity) {
26+
capacity = DEFAULT_INIT_SIZE;
27+
}
28+
data = (T[]) new Object[capacity];
29+
}
30+
31+
@Override
32+
public void add(T t) {
33+
group(size);
34+
data[size++] = t;
35+
}
36+
37+
@Override
38+
public void add(int index, T t) {
39+
if (index < 0) {
40+
throw new IllegalArgumentException("index < 0，index:" + index);
41+
}
42+
if (index > size) {
43+
throw new IndexOutOfBoundsException("index >= size。index:" + index + "\tsize:" + size);
44+
}
45+
group(size);
46+
T[] temp = (T[]) new Object[size - index];
47+
System.arraycopy(data, index, temp, 0, temp.length);
48+
data[index] = t;
49+
size++;
50+
System.arraycopy(temp, 0, data, index + 1, temp.length);
51+
}
52+
53+
@Override
54+
public T get(int index) {
55+
if (index < data.length) {
56+
return data[index];
57+
} else {
58+
throw new ArrayIndexOutOfBoundsException(index);
59+
}
60+
}
61+
62+
@Override
63+
public T remove(int index) {
64+
if (index < 0 || index >= size) {
65+
throw new IllegalArgumentException("index invalid!!!index:" + index);
66+
}
67+
T[] temp = (T[]) new Object[size - index - 1];
68+
System.arraycopy(data, index + 1, temp, 0, temp.length);
69+
T result = data[index];
70+
System.arraycopy(temp, 0, data, index, temp.length);
71+
data[--size] = null;
72+
return result;
73+
}
74+
75+
@Override
76+
public int size() {
77+
return size;
78+
}
79+
80+
@Override
81+
public boolean isEmpty() {
82+
return size == 0;
83+
}
84+
85+
@Override
86+
public IIterator<T> iterator() {
87+
return new ArrayIteratorImpl<>();
88+
}
89+
90+
@Override
91+
public String toString() {
92+
StringBuilder sbToString = new StringBuilder();
93+
for (T t :
94+
data) {
95+
sbToString.append(t).append("\t");
96+
}
97+
return sbToString.toString();
98+
}
99+
100+
private void group(int minSize) {
101+
if (minSize >= data.length) {
102+
T[] temp = (T[]) new Object[size];
103+
System.arraycopy(data, 0, temp, 0, size);
104+
int groupSize = (size >> 1) + size;
105+
data = (T[]) new Object[Math.max(groupSize, minSize)];
106+
System.arraycopy(temp, 0, data, 0, size);
107+
}
108+
}
109+
110+
private class ArrayIteratorImpl<T> implements IIterator<T> {
111+
112+
private int index = 0;
113+
114+
@Override
115+
public boolean hasNext() {
116+
return index < size;
117+
}
118+
119+
@Override
120+
public T next() {
121+
if (index >= size) {
122+
throw new ArrayIndexOutOfBoundsException("index out");
123+
}
124+
return (T) data[index++];
125+
}
126+
}
127+
}

‎group05/591010847/job_2017_02/job_2017_02_19_data_structure/src/com/java/xiaoqin/impl/BinaryTreeNode.java

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
package com.java.xiaoqin.impl;
2+
3+
/**
4+
* Created by xiaoqin on 17-2-26.
5+
*/
6+
public class BinaryTreeNode<T> {
7+
private T data;
8+
private BinaryTreeNode leftChild;
9+
private BinaryTreeNode rightChild;
10+
11+
public T getData() {
12+
return data;
13+
}
14+
15+
public void setData(T data) {
16+
this.data = data;
17+
}
18+
19+
public BinaryTreeNode getLeftChild() {
20+
return leftChild;
21+
}
22+
23+
public void setLeftChild(BinaryTreeNode leftChild) {
24+
this.leftChild = leftChild;
25+
}
26+
27+
public BinaryTreeNode getRightChild() {
28+
return rightChild;
29+
}
30+
31+
public void setRightChild(BinaryTreeNode rightChild) {
32+
this.rightChild = rightChild;
33+
}
34+
35+
public BinaryTreeNode insert(T o) {
36+
if (data == null) {
37+
data = o;
38+
return this;
39+
} else {
40+
return insert(this, o);
41+
}
42+
}
43+
44+
private BinaryTreeNode insert(BinaryTreeNode node, T o) {
45+
if (o instanceof Integer) {
46+
if ((Integer) node.data > (Integer) o) {
47+
if (null == node.leftChild) {
48+
node.leftChild = new BinaryTreeNode();
49+
node.leftChild.data = o;
50+
return node.leftChild;
51+
} else {
52+
return insert(node.leftChild, o);
53+
}
54+
} else if ((Integer) node.data < (Integer) o) {
55+
if (null == node.rightChild) {
56+
node.rightChild = new BinaryTreeNode();
57+
node.rightChild.data = o;
58+
return node.rightChild;
59+
} else {
60+
return insert(node.rightChild, o);
61+
}
62+
} else {
63+
return node;
64+
}
65+
} else {
66+
return null;
67+
}
68+
}
69+
70+
@Override
71+
public String toString() {
72+
StringBuilder sbToString = new StringBuilder();
73+
sbToString.append("data:").append(data);
74+
if (null != leftChild) {
75+
sbToString.append("\t").append(data).append("left:").append(leftChild.toString());
76+
}
77+
if (null != rightChild) {
78+
sbToString.append("\t").append(data).append("right:").append(rightChild.toString());
79+
}
80+
return sbToString.toString();
81+
}
82+
}

0 commit comments

Comments
 (0)