Skip to content

Commit c230748

Browse files
luoziyihaoluoziyihao
authored
Merge pull request onlyliuxin#11 from Wrecksoul/master
First homework,at 17/2/26
2 parents 97edd16 + 3dcacd1 commit c230748

File tree

11 files changed

+417
-1
lines changed

11 files changed

+417
-1
lines changed

‎group17/82427129/.gitignore

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
/.metadata/
2+
/RemoteSystemsTempFiles/
3+
4+
/JavaUtil/.settings/
5+
6+
.classpath
7+
.project

‎group17/82427129/JavaUtil/.gitignore

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

‎group17/82427129/JavaUtil/pom.xml

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
2+
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
3+
<modelVersion>4.0.0</modelVersion>
4+
<groupId>com.coding.basic</groupId>
5+
<artifactId>JavaUtil</artifactId>
6+
<version>0.0.1-SNAPSHOT</version>
7+
<build>
8+
<plugins>
9+
<plugin>
10+
<groupId>org.apache.maven.plugins</groupId>
11+
<artifactId>maven-compiler-plugin</artifactId>
12+
<configuration>
13+
<source>1.7</source>
14+
<target>1.7</target>
15+
</configuration>
16+
</plugin>
17+
</plugins>
18+
</build>
19+
<dependencies>
20+
<dependency>
21+
<groupId>junit</groupId>
22+
<artifactId>junit</artifactId>
23+
<version>4.7</version>
24+
<scope>test</scope>
25+
</dependency>
26+
</dependencies>
27+
</project>

‎group17/82427129/JavaUtil/src/main/java/com/coding/basic/ArrayList.java

Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
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+
private Object[] elementData;
10+
11+
private static Object[] EMPTY_ELEMENTDATA = {};
12+
13+
private static int INITIALCAPACITY = 10;
14+
15+
public ArrayList(){
16+
elementData = EMPTY_ELEMENTDATA;
17+
}
18+
19+
public ArrayList(int initialCapacity){
20+
elementData = new Object[INITIALCAPACITY];
21+
}
22+
23+
public void add(Object o){
24+
ensureCapacity(size+1);
25+
elementData[size++] = o;
26+
}
27+
28+
public void add(int index, Object o){
29+
rangeCheckForAdd(index);
30+
31+
ensureCapacity(size+1);
32+
System.arraycopy(elementData, index, elementData, index+1, size-index);
33+
elementData[index] = o;
34+
size++;
35+
}
36+
37+
public Object set(int index, Object o){
38+
rangeCheck(index);
39+
40+
Object oldValue = elementData[index];
41+
elementData[index] = o;
42+
return oldValue;
43+
}
44+
45+
public Object get(int index){
46+
rangeCheck(index);
47+
return elementData[index];
48+
}
49+
50+
public Object remove(int index){
51+
rangeCheck(index);
52+
Object oldValue = elementData[index];
53+
int movedLength = size - index - 1;
54+
if(movedLength > 0)//当要删除最后一个元素时，不需要移动数组，只需要把最后一个元素置null
55+
System.arraycopy(elementData, index+1, elementData, index, size-index-1);
56+
elementData[--size] = null;
57+
return oldValue;
58+
}
59+
60+
private void rangeCheckForAdd(int index){
61+
if( index > size || index<0 ){
62+
throw new IndexOutOfBoundsException(outofIndex(index));
63+
}
64+
}
65+
private void rangeCheck(int index){
66+
if( index >= size || index < 0){
67+
throw new IndexOutOfBoundsException(outofIndex(index));
68+
}
69+
}
70+
71+
public int size(){
72+
return size;
73+
}
74+
75+
public Iterator iterator(){
76+
return null;
77+
}
78+
79+
private void ensureCapacity(int minCapacity){
80+
if(elementData == EMPTY_ELEMENTDATA){
81+
minCapacity = Math.max(minCapacity, INITIALCAPACITY);//针对addall首次增加的数量就比INITIALCAPACITY多
82+
}
83+
if(minCapacity - elementData.length > 0){
84+
grow(minCapacity);
85+
}
86+
}
87+
88+
private void grow(int minCapcity){
89+
int oldCapacity = elementData.length;
90+
int newCapcity = oldCapacity + (oldCapacity>>1);
91+
if(newCapcity - minCapcity < 0){
92+
newCapcity = minCapcity;
93+
}
94+
elementData = Arrays.copyOf(elementData, newCapcity);
95+
}
96+
97+
private String outofIndex(int index){
98+
return "Index: "+index+", Size: "+size;
99+
}
100+
}

‎group17/82427129/JavaUtil/src/main/java/com/coding/basic/BinaryTreeNode.java

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
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+
return null;
30+
}
31+
32+
}

‎group17/82427129/JavaUtil/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+
}

‎group17/82427129/JavaUtil/src/main/java/com/coding/basic/LinkedList.java

Lines changed: 180 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,180 @@
1+
package com.coding.basic;
2+
3+
import java.util.NoSuchElementException;
4+
5+
public class LinkedList implements List {
6+
private int size = 0;
7+
8+
private Node first;
9+
10+
private Node last;
11+
12+
public void add(Object o){
13+
add(size,o);
14+
}
15+
public void add(int index , Object o){
16+
rangeCheck(index);
17+
18+
if(index == size){
19+
linkLast(o);
20+
}else{
21+
linkBefore(o, indexOf(index));
22+
}
23+
}
24+
private void linkBefore(Object o ,Node succ){
25+
final Node prev = succ.prev;
26+
final Node newNode = new Node(prev, o, succ);
27+
succ.prev = newNode;
28+
if(prev == null){
29+
first = newNode;
30+
}else{
31+
prev.next = newNode;
32+
}
33+
size++;
34+
}
35+
private void linkLast(Object o){
36+
final Node succ = last;
37+
final Node newNode = new Node(succ, o, null);
38+
last = newNode;
39+
if(succ == null){
40+
first = newNode;
41+
}else{
42+
succ.next = newNode;
43+
}
44+
size++;
45+
}
46+
private void rangeCheck(int index) {
47+
if(index > size|| index < 0 )
48+
throw new IndexOutOfBoundsException("Size"+size+":index"+index);
49+
}
50+
private void elementIndexCheck(int index){
51+
if(index >=size||index < 0)
52+
throw new IndexOutOfBoundsException("Size"+size+":index"+index);
53+
}
54+
/**
55+
* 获取“下标”为index的值,
56+
* index为size时返回null
57+
* @param index
58+
* @return
59+
*/
60+
private Node indexOf(int index){
61+
if(index < (this.size>>1) ){
62+
Node x = first;
63+
for (int i = 0; i < index; i++) {
64+
x = x.next;
65+
}
66+
return x;
67+
}else{
68+
Node x = last;
69+
for (int i = this.size-1; i > index; i--) {
70+
x = x.prev;
71+
}
72+
return x;
73+
}
74+
}
75+
76+
public Object get(int index){
77+
elementIndexCheck(index);
78+
79+
return indexOf(index);
80+
}
81+
public Object remove(int index){
82+
elementIndexCheck(index);
83+
84+
if(index == 0){
85+
return removeFirst();
86+
}else if(index == size) {
87+
return removeLast();
88+
}else{
89+
return unlinkNode(indexOf(index));
90+
}
91+
}
92+
93+
private Object unlinkNode(Node node) {
94+
final Node next = node.next;
95+
final Node prev = node.prev;
96+
final Object element = node.data;
97+
if(next == null){
98+
last = node;
99+
}else{
100+
next.prev = node;
101+
node.next = next;
102+
}
103+
if(prev == null){
104+
first = node;
105+
}else{
106+
prev.next = node;
107+
node.prev = prev;
108+
}
109+
size--;
110+
node.data = null;
111+
112+
return element;
113+
}
114+
public int size(){
115+
return size;
116+
}
117+
118+
public void addFirst(Object o){
119+
linkBefore(o, first);
120+
}
121+
122+
public void addLast(Object o){
123+
linkLast(o);
124+
}
125+
126+
public Object removeFirst(){
127+
if(first == null)
128+
throw new NoSuchElementException("first is null");
129+
130+
Object oldData = first.data;
131+
final Node next = first.next;
132+
first.data = null;
133+
first.next = null;//GC
134+
first = next;
135+
136+
if(next == null){
137+
last = null;
138+
}else{
139+
next.prev = null;
140+
}
141+
size--;
142+
143+
return oldData;
144+
}
145+
146+
public Object removeLast(){
147+
if(last == null)
148+
throw new NoSuchElementException("last is null");
149+
150+
Object oldData = last.data;
151+
final Node prev = last.prev;
152+
last.prev = null;
153+
last.data = null;//GC
154+
last = prev;
155+
156+
if(prev == null){
157+
first = null;
158+
}else{
159+
prev.next = null;
160+
}
161+
size--;
162+
163+
return oldData;
164+
}
165+
166+
public Iterator iterator(){
167+
return null;
168+
}
169+
170+
private static class Node{
171+
Object data;
172+
Node next;
173+
Node prev;
174+
Node(Node prev,Object data,Node next){
175+
this.data = data;
176+
this.next = next;
177+
this.prev = prev;
178+
}
179+
}
180+
}

‎group17/82427129/JavaUtil/src/main/java/com/coding/basic/List.java

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package com.coding.basic;
2+
3+
public interface List {
4+
public void add(Object o);
5+
public void add(int index, Object o);
6+
public Object get(int index);
7+
public Object remove(int index);
8+
public int size();
9+
}

‎group17/82427129/JavaUtil/src/main/java/com/coding/basic/Queue.java

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
package com.coding.basic;
2+
3+
public class Queue {
4+
private LinkedList elementData = new LinkedList();
5+
6+
public void enQueue(Object o){
7+
elementData.addLast(o);
8+
}
9+
10+
public Object deQueue(){
11+
return elementData.removeLast();
12+
}
13+
14+
public boolean isEmpty(){
15+
return size() == 0;
16+
}
17+
18+
public int size(){
19+
return elementData.size();
20+
}
21+
}

0 commit comments

Comments
 (0)