Skip to content

Commit fe1ca4e

Browse files
nusubmarine01nusubmarine01
authored
Merge pull request onlyliuxin#8 from ztc-dev/master
datastructure
2 parents fe6852e + 81c40c9 commit fe1ca4e

File tree

9 files changed

+537
-0
lines changed

9 files changed

+537
-0
lines changed

‎group03/569045298/pom.xml

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
<project xmlns="http://maven.apache.org/POM/4.0.0"
2+
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
3+
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/maven-v4_0_0.xsd">
4+
<modelVersion>4.0.0</modelVersion>
5+
<groupId>com.ztc</groupId>
6+
<artifactId>JavaLevelUp</artifactId>
7+
<packaging>war</packaging>
8+
<version>1.0-SNAPSHOT</version>
9+
<name>JavaLevelUp Maven Webapp</name>
10+
<url>http://maven.apache.org</url>
11+
12+
<dependencies>
13+
<dependency>
14+
<groupId>junit</groupId>
15+
<artifactId>junit</artifactId>
16+
<version>3.8.1</version>
17+
<scope>test</scope>
18+
</dependency>
19+
<dependency>
20+
<groupId>org.junit.jupiter</groupId>
21+
<artifactId>junit-jupiter-api</artifactId>
22+
<version>RELEASE</version>
23+
</dependency>
24+
<dependency>
25+
<groupId>junit</groupId>
26+
<artifactId>junit</artifactId>
27+
<version>4.12</version>
28+
</dependency>
29+
</dependencies>
30+
31+
<build>
32+
<finalName>JavaLevelUp</finalName>
33+
</build>
34+
35+
</project>

‎group03/569045298/src/main/com/coding/basic/datastructure/ArrayList.java

Lines changed: 108 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,108 @@
1+
package com.coding.basic.datastructure;
2+
3+
4+
/**
5+
* Created by zt on 2017/2/19.
6+
*/
7+
public class ArrayList implements List {
8+
9+
private static final int DEFAULT_CAPACITY = 10;
10+
private int size = 0;
11+
private Object[] elementData = null;
12+
13+
public ArrayList() {
14+
elementData = new Object[DEFAULT_CAPACITY];
15+
}
16+
17+
public ArrayList(int initialCapacity) {
18+
if (initialCapacity < 0) {
19+
throw new RuntimeException("initialCapacity is smaller than zero");
20+
}
21+
elementData = new Object[initialCapacity];
22+
}
23+
24+
@Override
25+
public void add(Object o) {
26+
checkCapacity(size + 1);
27+
elementData[size] = o;
28+
size++;
29+
}
30+
31+
@Override
32+
public void add(int index, Object o) {
33+
checkCapacity(size + 1);
34+
System.arraycopy(elementData, index, elementData, index + 1, size - index);
35+
elementData[index] = o;
36+
size++;
37+
}
38+
39+
@Override
40+
public Object get(int index) {
41+
checkRange(index);
42+
return elementData[index];
43+
}
44+
45+
@Override
46+
public Object remove(int index) {
47+
Object removedObject = elementData[index];
48+
System.arraycopy(elementData, index + 1, elementData, index, elementData.length - index - 1);
49+
elementData[--size] = null;
50+
return removedObject;
51+
}
52+
53+
@Override
54+
public int size() {
55+
return size;
56+
}
57+
58+
private void checkRange(int index) {
59+
if (index < 0 || index > elementData.length) {
60+
throw new IndexOutOfBoundsException();
61+
}
62+
}
63+
64+
private void checkCapacity(int size) {
65+
if (size > elementData.length) {
66+
int newLength = elementData.length * 2;
67+
Object[] newObject = new Object[newLength];
68+
System.arraycopy(elementData, 0, newObject, 0, elementData.length);
69+
elementData = newObject;
70+
}
71+
}
72+
73+
public Iterator iterator() {
74+
return new ArrayListIterator(this);
75+
}
76+
77+
private class ArrayListIterator implements Iterator {
78+
79+
ArrayList arrayList = null;
80+
int pos = 0;
81+
82+
private ArrayListIterator(ArrayList arrayList) {
83+
this.arrayList = arrayList;
84+
}
85+
86+
@Override
87+
public boolean hasNext() {
88+
// TODO
89+
pos++;
90+
if (pos > size) {
91+
return false;
92+
}
93+
return true;
94+
}
95+
96+
@Override
97+
public Object next() {
98+
// TODO
99+
return elementData[pos];
100+
}
101+
102+
@Override
103+
public Object remove() {
104+
// TODO
105+
return null;
106+
}
107+
}
108+
}

‎group03/569045298/src/main/com/coding/basic/datastructure/BinaryTreeNode.java

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package com.coding.basic.datastructure;
2+
3+
/**
4+
* Created by zt on 2017/2/19.
5+
*/
6+
public class BinaryTreeNode {
7+
8+
private Object data;
9+
10+
private BinaryTreeNode left;
11+
12+
private BinaryTreeNode right;
13+
14+
public Object getData() {
15+
return data;
16+
}
17+
18+
public void setData(Object data) {
19+
this.data = data;
20+
}
21+
22+
public BinaryTreeNode getLeft() {
23+
return left;
24+
}
25+
26+
public void setLeft(BinaryTreeNode left) {
27+
this.left = left;
28+
}
29+
30+
public BinaryTreeNode getRight() {
31+
return right;
32+
}
33+
34+
public void setRight(BinaryTreeNode right) {
35+
this.right = right;
36+
}
37+
38+
public BinaryTreeNode insert(Object object) {
39+
return null;
40+
}
41+
}

‎group03/569045298/src/main/com/coding/basic/datastructure/Iterator.java

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
package com.coding.basic.datastructure;
2+
3+
/**
4+
* Created by zt on 2017/2/19.
5+
*/
6+
public interface Iterator {
7+
8+
boolean hasNext();
9+
10+
Object next();
11+
12+
Object remove();
13+
}

‎group03/569045298/src/main/com/coding/basic/datastructure/LinkedList.java

Lines changed: 167 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,167 @@
1+
package com.coding.basic.datastructure;
2+
3+
/**
4+
* Created by zt on 2017/2/19.
5+
*/
6+
public class LinkedList implements List {
7+
8+
private Node head;
9+
10+
private Node tail;
11+
12+
private int size = 0;
13+
14+
public LinkedList() {
15+
16+
}
17+
18+
@Override
19+
public void add(Object object) {
20+
if (null == head) {
21+
head = new Node(object);
22+
head.next = null;
23+
tail = head;
24+
size++;
25+
} else {
26+
// 尾插法
27+
Node newNode = new Node(object);
28+
tail.next = newNode;
29+
tail = newNode;
30+
tail.next = null;
31+
size++;
32+
}
33+
}
34+
35+
@Override
36+
public void add(int index, Object object) {
37+
checkRange(index);
38+
if (null == head) {
39+
add(object);
40+
return;
41+
}
42+
if (index == 0) {
43+
addFirst(object);
44+
return;
45+
}
46+
Node pre = node(index - 1);
47+
Node newNode = new Node(object);
48+
newNode.next = pre.next;
49+
pre.next = newNode;
50+
size++;
51+
}
52+
53+
@Override
54+
public Object get(int index) {
55+
checkRange(index);
56+
checkNodeNotNull();
57+
Node node = node(index);
58+
return node.data;
59+
}
60+
61+
@Override
62+
public Object remove(int index) {
63+
checkRange(index);
64+
checkNodeNotNull();
65+
if (index == 0) {
66+
removeFirst();
67+
return head;
68+
}
69+
Node pre = node(index - 1);
70+
pre.next = pre.next.next;
71+
size--;
72+
return head;
73+
}
74+
75+
@Override
76+
public int size() {
77+
return size;
78+
}
79+
80+
public void addFirst(Object object) {
81+
if (null == head) {
82+
head = new Node(object);
83+
head.next = null;
84+
size++;
85+
} else {
86+
Node firstNode = new Node(object);
87+
firstNode.next = head;
88+
head = firstNode;
89+
size++;
90+
}
91+
}
92+
93+
public Object removeFirst() {
94+
checkNodeNotNull();
95+
head = head.next;
96+
size--;
97+
return head;
98+
}
99+
100+
public Object removeLast() {
101+
checkNodeNotNull();
102+
if (size == 1) {
103+
head = null;
104+
}
105+
Node pre = node(size() - 2);
106+
pre.next = null;
107+
size--;
108+
return head;
109+
}
110+
111+
private void checkRange(int index) {
112+
if (index > size - 1 || index < 0) {
113+
throw new IndexOutOfBoundsException();
114+
}
115+
}
116+
117+
private void checkNodeNotNull() {
118+
if (null == head) {
119+
throw new NullPointerException();
120+
}
121+
}
122+
123+
private Node node(int index) {
124+
Node node = head;
125+
for (int i = 0; i < index; i++) {
126+
node = node.next;
127+
}
128+
return node;
129+
}
130+
131+
private static class Node {
132+
Node next;
133+
private Object data;
134+
135+
public Node() {
136+
137+
}
138+
139+
public Node(Object data) {
140+
this.data = data;
141+
}
142+
143+
public Node(Object data, Node next) {
144+
this.data = data;
145+
this.next = next;
146+
}
147+
148+
public Node(Object data, Node next, Node prev) {
149+
this.data = data;
150+
this.next = next;
151+
}
152+
}
153+
154+
/*@Override
155+
public void add(Object object) {
156+
if (null == head) {
157+
head = new Node(object);
158+
head.next = null;
159+
} else {
160+
// 头插法
161+
Node nextNode = new Node(object);
162+
nextNode.next = head.next;
163+
head.next = nextNode;
164+
}
165+
}*/
166+
167+
}

‎group03/569045298/src/main/com/coding/basic/datastructure/List.java

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
package com.coding.basic.datastructure;
2+
3+
/**
4+
* Created by zt on 2017/2/19.
5+
*/
6+
public interface List {
7+
8+
void add(Object o);
9+
10+
void add(int index, Object o);
11+
12+
Object get(int index);
13+
14+
Object remove(int index);
15+
16+
int size();
17+
}

0 commit comments

Comments
 (0)