Skip to content

Commit 62eae1c

Browse files
author
sshfuture
committed
group 18 744888802 submit task
1 parent f83a5a8 commit 62eae1c

File tree

9 files changed

+571
-0
lines changed

9 files changed

+571
-0
lines changed

‎group18/744888802/dataStructure/pom.xml

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<project xmlns="http://maven.apache.org/POM/4.0.0"
3+
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
4+
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
5+
<modelVersion>4.0.0</modelVersion>
6+
7+
<groupId>dataStructure</groupId>
8+
<artifactId>dataStructure</artifactId>
9+
<version>1.0-SNAPSHOT</version>
10+
<build>
11+
<plugins>
12+
<plugin>
13+
<groupId>org.apache.maven.plugins</groupId>
14+
<artifactId>maven-compiler-plugin</artifactId>
15+
<configuration>
16+
<source>1.6</source>
17+
<target>1.6</target>
18+
</configuration>
19+
</plugin>
20+
</plugins>
21+
</build>
22+
23+
24+
</project>

‎group18/744888802/dataStructure/src/main/java/com/coding/basic/ArrayList.java

Lines changed: 109 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,109 @@
1+
package com.coding.basic;
2+
3+
import java.util.Arrays;
4+
5+
public class ArrayList implements List {
6+
7+
private int size = 0;
8+
9+
//每次增加的长度
10+
private Integer addArrayLength = 10;
11+
//初始 数组长度
12+
private Object[] elementData = new Object[10];
13+
14+
public void add(Object o){
15+
if(size < elementData.length)
16+
{
17+
elementData[size]=o;
18+
}else{
19+
//扩容数组
20+
grow();
21+
elementData[size] = 0;
22+
}
23+
size++;
24+
25+
}
26+
public void add(int index, Object o){
27+
if(index>size)
28+
{
29+
throw new RuntimeException("ArrayIndexOutOfBoundsException");
30+
}
31+
32+
//截取索引开始到原数组结尾 组成一个新的数组
33+
Object [] tempObjs = Arrays.copyOfRange(elementData,index,elementData.length);
34+
//覆盖原有索引位置的对象
35+
elementData[index] = o;
36+
//数组扩容
37+
elementData = Arrays.copyOf(elementData,elementData.length+1);
38+
39+
//将临时生成的数组合并回原数组
40+
System.arraycopy(tempObjs,0,elementData,index+1,tempObjs.length);
41+
size++;
42+
}
43+
44+
45+
public Object get(int index){
46+
return elementData[index];
47+
}
48+
49+
public Object remove(int index){
50+
51+
if(index>size)
52+
{
53+
throw new RuntimeException("ArrayIndexOutOfBoundsException");
54+
}
55+
56+
Object o = elementData[index];
57+
58+
//截取索引开始到原数组结尾 组成一个新的数组
59+
Object [] tempObjs = Arrays.copyOfRange(elementData,index+1,elementData.length);
60+
elementData = Arrays.copyOf(elementData,elementData.length-1);
61+
//将临时生成的数组合并回原数组
62+
System.arraycopy(tempObjs,0,elementData,index,tempObjs.length);
63+
size--;
64+
65+
return o;
66+
}
67+
68+
public int size(){
69+
return this.size;
70+
}
71+
72+
public Iterator iterator(){
73+
ArratListIterator arratListIterator = new ArratListIterator(this);
74+
75+
return arratListIterator;
76+
}
77+
78+
private void grow(){
79+
elementData = Arrays.copyOf(elementData,elementData.length+addArrayLength);
80+
}
81+
82+
class ArratListIterator implements Iterator{
83+
84+
ArrayList arrayList = new ArrayList();
85+
86+
int index = 0;
87+
88+
ArratListIterator(ArrayList arrayList){
89+
90+
this.arrayList = arrayList;
91+
index = arrayList.size;
92+
}
93+
94+
@Override
95+
public boolean hasNext() {
96+
if(index == 0)
97+
{
98+
return false;
99+
}
100+
return true;
101+
}
102+
103+
@Override
104+
public Object next() {
105+
return this.arrayList.get(--index);
106+
}
107+
}
108+
109+
}

‎group18/744888802/dataStructure/src/main/java/com/coding/basic/BinaryTreeNode.java

Lines changed: 84 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,84 @@
1+
package com.coding.basic;
2+
3+
public class BinaryTreeNode {
4+
5+
private Object data;
6+
private BinaryTreeNode left;
7+
private BinaryTreeNode right;
8+
9+
public Object getData() {
10+
return data;
11+
}
12+
public void setData(Object 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(Object o) {
29+
30+
BinaryTreeNode binaryTreeNode = new BinaryTreeNode();
31+
binaryTreeNode.data = o;
32+
33+
add(this, binaryTreeNode);
34+
return this;
35+
}
36+
37+
private void add(BinaryTreeNode binaryTreeNodeOld, BinaryTreeNode binaryTreeNodeNew) {
38+
if (binaryTreeNodeOld.data == null) {
39+
binaryTreeNodeOld.data = binaryTreeNodeNew.data;
40+
return;
41+
}
42+
43+
44+
if (binaryTreeNodeOld.left == null) {
45+
binaryTreeNodeOld.left = binaryTreeNodeNew;
46+
return;
47+
}
48+
if (binaryTreeNodeOld.right == null) {
49+
if (comparator(binaryTreeNodeNew, binaryTreeNodeOld.left)){
50+
binaryTreeNodeOld.right = binaryTreeNodeNew;
51+
}else{
52+
binaryTreeNodeOld.right = binaryTreeNodeOld.left;
53+
binaryTreeNodeOld.left = binaryTreeNodeNew;
54+
}
55+
return;
56+
}
57+
58+
if(comparator(binaryTreeNodeOld.left, binaryTreeNodeNew))
59+
{
60+
add(binaryTreeNodeOld.left,binaryTreeNodeNew);
61+
return;
62+
}
63+
64+
if(comparator(binaryTreeNodeOld.right, binaryTreeNodeNew)){
65+
add(binaryTreeNodeOld.right,binaryTreeNodeNew);
66+
return;
67+
}else{
68+
binaryTreeNodeNew.left = binaryTreeNodeOld.right;
69+
binaryTreeNodeOld.right = binaryTreeNodeNew;
70+
}
71+
72+
73+
74+
75+
}
76+
77+
private boolean comparator(BinaryTreeNode binaryTreeNode1, BinaryTreeNode binaryTreeNode2) {
78+
if ((Integer) binaryTreeNode1.getData() > (Integer) binaryTreeNode2.getData()) {
79+
return true;
80+
}
81+
return false;
82+
}
83+
84+
}

‎group18/744888802/dataStructure/src/main/java/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)