Skip to content

Commit 8d39052

Browse files
zhijiaxinyuzhijiaxinyu
authored
Merge pull request onlyliuxin#1 from denghuaij/master
提交第一周作业
2 parents d4a25d6 + dc28777 commit 8d39052

File tree

11 files changed

+577
-0
lines changed

11 files changed

+577
-0
lines changed

‎group10/875867419/.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>

‎group10/875867419/.gitignore

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

‎group10/875867419/.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>coding2017</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>

‎group10/875867419/src/com/work/week01/MyArrayList.java

Lines changed: 203 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,203 @@
1+
package com.work.week01;
2+
3+
import java.io.Serializable;
4+
import java.util.Arrays;
5+
6+
/**
7+
* 实现List<E>接口，以数组的方式实现自己的ArrayList
8+
* @author denghuaijun
9+
*
10+
* @param <E>
11+
*/
12+
public class MyArrayList<E> implements MyList<E>,Serializable {
13+
14+
private static final long serialVersionUID = 4145346362382387995L;
15+
16+
/**
17+
* 设置<MyArrayList>默认大小
18+
*/
19+
private static final int DEFAULT_CAPACITY = 10;
20+
21+
/**
22+
* 设置<MyArrayList>默认空数组
23+
*/
24+
private static final Object[] EMPTY_ELEMENTDATA = {};
25+
26+
transient Object[] elementData;
27+
28+
/**
29+
* <MyArrayList>大小
30+
*/
31+
private int size;
32+
33+
public MyArrayList(){
34+
this.elementData = EMPTY_ELEMENTDATA;
35+
}
36+
37+
public MyArrayList(int capacity){
38+
if(capacity > 0){
39+
this.elementData = new Object[capacity];
40+
}else if(capacity == 0){
41+
this.elementData = EMPTY_ELEMENTDATA;
42+
}else{
43+
throw new IllegalArgumentException("非法参数");
44+
}
45+
}
46+
47+
private void ensureCapacity(int minCapacity){
48+
if(this.elementData == EMPTY_ELEMENTDATA){
49+
minCapacity = Math.max(minCapacity, DEFAULT_CAPACITY);
50+
}
51+
if(minCapacity > elementData.length){//索引位置大于现有数组长度
52+
grow(minCapacity);
53+
}
54+
}
55+
56+
private void grow(int minCapacity){
57+
int oldCapacity = elementData.length;
58+
int newCapacity = oldCapacity + (oldCapacity >> 1);
59+
if(newCapacity < minCapacity){
60+
newCapacity = minCapacity;
61+
}
62+
elementData = Arrays.copyOf(elementData, newCapacity);
63+
}
64+
65+
@Override
66+
public boolean add(E element) {
67+
ensureCapacity(size + 1);
68+
elementData[size++] = element;
69+
return true;
70+
}
71+
72+
@Override
73+
public void add(int index, E element) {
74+
//确认index是否越界
75+
checkAddRange(index);
76+
//确认数组长度是否足够
77+
ensureCapacity(size + 1);
78+
System.arraycopy(elementData, index, elementData, index + 1, size - index);
79+
elementData[index] = element;
80+
size++;
81+
}
82+
83+
private void checkAddRange(int index){
84+
if(index < 0 || index > size){//index == size 则在数组最后加元素
85+
throw new IndexOutOfBoundsException("数组越界");
86+
}
87+
}
88+
89+
@SuppressWarnings("unchecked")
90+
@Override
91+
public E get(int index) {
92+
checkRange(index);
93+
return (E) elementData[index];
94+
}
95+
96+
private void checkRange(int index){
97+
if(index < 0 || index >= size){
98+
throw new IndexOutOfBoundsException("数组越界");
99+
}
100+
}
101+
102+
@SuppressWarnings("unchecked")
103+
@Override
104+
public E remove(int index) {
105+
checkRange(index);
106+
E element = (E) elementData[index];
107+
int numMoved = size - index - 1;
108+
if(numMoved > 0){
109+
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
110+
}
111+
elementData[size--] = null;
112+
return element;
113+
}
114+
115+
@Override
116+
public int size() {
117+
return size;
118+
}
119+
120+
@Override
121+
public boolean isEmpty() {
122+
return size == 0;
123+
}
124+
125+
public int indexOf(Object o) {
126+
if(o == null){
127+
for(int i=0;i<size;i++){
128+
if(elementData[i] == null){
129+
return i;
130+
}
131+
}
132+
}else{
133+
for(int i=0;i<size;i++){
134+
if(o.equals(elementData[i])){
135+
return i;
136+
}
137+
}
138+
}
139+
return -1;
140+
}
141+
142+
public int lastIndexOf(Object o) {
143+
if(o == null){
144+
for(int i=size-1;i>=0;i--){
145+
if(elementData[i] == null){
146+
return i;
147+
}
148+
}
149+
}else{
150+
for(int i=size-1;i>=0;i--){
151+
if(o.equals(elementData[i])){
152+
return i;
153+
}
154+
}
155+
}
156+
return -1;
157+
}
158+
159+
@Override
160+
public MyIterator<E> iterator() {
161+
return new MyIter();
162+
}
163+
164+
private class MyIter implements MyIterator<E>{
165+
166+
int flag = -1;
167+
168+
public MyIter(){
169+
flag = size; //数组长度
170+
}
171+
172+
@Override
173+
public boolean hasNext() {
174+
return flag > 0;
175+
}
176+
177+
@SuppressWarnings("unchecked")
178+
@Override
179+
public E next() {
180+
if(!hasNext()){
181+
throw new IndexOutOfBoundsException("索引值超出数组范围");
182+
}
183+
return (E) elementData[size-(flag--)];
184+
}
185+
186+
}
187+
public static void main(String[] args) {
188+
MyArrayList<String> array = new MyArrayList<String>();
189+
array.add("1");
190+
array.add("2");
191+
array.add("3");
192+
array.add("4");
193+
array.remove(2);
194+
array.add(2, "1");
195+
System.out.println("size="+array.size());
196+
System.out.println("indexOf(3)="+array.indexOf("3"));
197+
System.out.println("lastIndexOf(1)="+array.lastIndexOf("1"));
198+
MyIterator<String> itr = array.iterator();
199+
while(itr.hasNext()){
200+
System.out.println(itr.next());
201+
}
202+
}
203+
}

‎group10/875867419/src/com/work/week01/MyBinaryTree.java

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
package com.work.week01;
2+
3+
public class MyBinaryTree<E> {
4+
5+
private MyBinaryTreeNode<E> parent;
6+
7+
public MyBinaryTree(){
8+
this.parent = new MyBinaryTreeNode<E>(null, null, null);
9+
}
10+
11+
public void insertNode(E element){
12+
MyBinaryTreeNode<E> node = new MyBinaryTreeNode<E>(element, null, null);
13+
if(parent.element == null){
14+
parent = node;
15+
return;
16+
}
17+
insertNode(parent, node);
18+
}
19+
20+
private void insertNode(MyBinaryTreeNode<E> parentNode, MyBinaryTreeNode<E> newNode){
21+
if(parentNode.compareTo(newNode) <= 0){//
22+
if(parentNode.right == null){
23+
parentNode.right = newNode;
24+
}else{
25+
insertNode(parentNode.right, newNode);
26+
}
27+
}else{
28+
if(parentNode.left == null){
29+
parentNode.left = newNode;
30+
}else{
31+
insertNode(parentNode.left, newNode);
32+
}
33+
}
34+
}
35+
36+
private void printNode(MyBinaryTreeNode<E> node, int count){
37+
if(node.left != null){
38+
printNode(node.left, count++);
39+
}
40+
if(node.right != null){
41+
printNode(node.right, count++);
42+
}
43+
for(int i=0;i<count;i++){
44+
System.out.println();
45+
}
46+
System.out.print(node.element);
47+
}
48+
49+
public void printTree(){
50+
printNode(this.parent, 0);
51+
}
52+
53+
private class MyBinaryTreeNode<T> implements Comparable<MyBinaryTreeNode<T>> {
54+
55+
private T element;
56+
private MyBinaryTreeNode<T> left;
57+
private MyBinaryTreeNode<T> right;
58+
59+
public MyBinaryTreeNode(T element, MyBinaryTreeNode<T> left, MyBinaryTreeNode<T> right){
60+
this.element = element;
61+
this.left = left;
62+
this.right = right;
63+
}
64+
65+
@Override
66+
public int compareTo(MyBinaryTreeNode<T> o) {
67+
Integer src = (Integer) this.element;
68+
Integer dest = (Integer) o.element;
69+
return src.compareTo(dest);
70+
}
71+
}
72+
73+
public static void main(String[] args) {
74+
MyBinaryTree<Integer> tree = new MyBinaryTree<Integer>();
75+
tree.insertNode(5);
76+
tree.insertNode(7);
77+
tree.insertNode(3);
78+
tree.insertNode(9);
79+
tree.insertNode(4);
80+
tree.printTree();
81+
}
82+
}

‎group10/875867419/src/com/work/week01/MyIterator.java

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
package com.work.week01;
2+
3+
public interface MyIterator<E> {
4+
boolean hasNext();
5+
E next();
6+
}

0 commit comments

Comments
 (0)