Skip to content

Commit 3505a81

Browse files
heyucoolheyucool
authored
Merge pull request onlyliuxin#14 from liyanyang0316/master
first homework
2 parents 76187af + 61d2c9a commit 3505a81

File tree

11 files changed

+386
-0
lines changed

11 files changed

+386
-0
lines changed

‎group14/630254746/2017Leaning/.classpath

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
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/org.eclipse.jdt.internal.debug.ui.launcher.StandardVMType/JavaSE-1.7"/>
5+
<classpathentry kind="con" path="org.eclipse.jdt.junit.JUNIT_CONTAINER/4"/>
6+
<classpathentry kind="output" path="bin"/>
7+
</classpath>

‎group14/630254746/2017Leaning/.gitignore

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

‎group14/630254746/2017Leaning/.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>2017Leaning</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>

‎group14/630254746/2017Leaning/.settings/org.eclipse.jdt.core.prefs

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
eclipse.preferences.version=1
2+
org.eclipse.jdt.core.compiler.codegen.inlineJsrBytecode=enabled
3+
org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.7
4+
org.eclipse.jdt.core.compiler.codegen.unusedLocal=preserve
5+
org.eclipse.jdt.core.compiler.compliance=1.7
6+
org.eclipse.jdt.core.compiler.debug.lineNumber=generate
7+
org.eclipse.jdt.core.compiler.debug.localVariable=generate
8+
org.eclipse.jdt.core.compiler.debug.sourceFile=generate
9+
org.eclipse.jdt.core.compiler.problem.assertIdentifier=error
10+
org.eclipse.jdt.core.compiler.problem.enumIdentifier=error
11+
org.eclipse.jdt.core.compiler.source=1.7

‎group14/630254746/2017Leaning/src/com/leaning/code/ArrayList.java

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,87 @@
1+
package com.leaning.code;
2+
3+
import java.util.Arrays;
4+
5+
public class ArrayList implements List {
6+
7+
private int size; // 记录集合中的元素个数
8+
9+
private Object[] elementsData;
10+
11+
private int totalCount = 1; // 记录集合的大小
12+
13+
public ArrayList() {
14+
this.elementsData = new Object[totalCount];
15+
}
16+
17+
private void grow() {
18+
if (size >= totalCount) {
19+
// 进行扩容
20+
int oldCapacity = size;
21+
int newCapacity = oldCapacity + oldCapacity << 1;
22+
totalCount = newCapacity;
23+
elementsData = Arrays.copyOf(elementsData, newCapacity);
24+
}
25+
}
26+
27+
@Override
28+
public void add(Object o) {
29+
if (totalCount > size) {
30+
elementsData[size++] = o;
31+
} else {
32+
grow();
33+
elementsData[size++] = o;
34+
}
35+
}
36+
37+
@Override
38+
public void add(int index, Object o) {
39+
if (index < size) {
40+
if (totalCount <= size + 1) {
41+
grow();
42+
}
43+
System.arraycopy(elementsData, index, elementsData, index + 1, size
44+
- index);
45+
elementsData[index] = 0;
46+
47+
} else {
48+
throw new RuntimeException("数组下标越界");
49+
}
50+
size++;
51+
}
52+
53+
@Override
54+
public Object get(int index) {
55+
if (index < size)
56+
return elementsData[index];
57+
else
58+
throw new RuntimeException("数组下标越界");
59+
}
60+
61+
@Override
62+
public Object remove(int index) {
63+
if (index >= size || index < 0) {
64+
throw new RuntimeException("数组下标越界");
65+
}
66+
Object o = elementsData[index];
67+
68+
int numMoved = size - index - 1;
69+
if (numMoved > 0)
70+
System.arraycopy(elementsData, index + 1, elementsData, index,
71+
numMoved);
72+
elementsData[--size] = null;
73+
74+
return o;
75+
}
76+
77+
@Override
78+
public int size() {
79+
return size;
80+
}
81+
82+
@Override
83+
public String toString() {
84+
return "ArrayList [elementsData=" + Arrays.toString(elementsData) + "]";
85+
}
86+
87+
}

‎group14/630254746/2017Leaning/src/com/leaning/code/Iterator.java

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
package com.leaning.code;
2+
3+
public interface Iterator {
4+
5+
public boolean hasNext();
6+
7+
public Object Next();
8+
}

‎group14/630254746/2017Leaning/src/com/leaning/code/LinkedList.java

Lines changed: 150 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,150 @@
1+
package com.leaning.code;
2+
3+
4+
5+
6+
7+
8+
public class LinkedList implements List {
9+
10+
private Node head;
11+
12+
private Node last;
13+
14+
private int size;
15+
16+
17+
void linkLast(Object o){
18+
Node lastNode = last;
19+
Node newNode = new Node(lastNode, o, null);
20+
last = newNode;
21+
if (lastNode == null)
22+
head = newNode;
23+
else
24+
lastNode.next = newNode;
25+
size++;
26+
}
27+
28+
void linkHead(Object o){
29+
Node headNode = head;
30+
Node newNode = new Node(null, o, headNode);
31+
head = newNode;
32+
if (head == null)
33+
last = newNode;
34+
else
35+
head.prev = newNode;
36+
size++;
37+
}
38+
39+
@Override
40+
public void add(Object o) {
41+
linkLast(o);
42+
}
43+
44+
@Override
45+
public void add(int index, Object o) {
46+
if (index < 0 || index >= size) {
47+
throw new RuntimeException("Êý×éϱêÔ½½ç");
48+
}
49+
Node n = find(index);
50+
Node pred = n.prev;
51+
Node newNode = new Node(pred, o, n);
52+
n.prev = newNode;
53+
if (pred == null)
54+
head = newNode;
55+
else
56+
pred.next = newNode;
57+
size++;
58+
}
59+
60+
@Override
61+
public Object get(int index) {
62+
return find(index).item;
63+
}
64+
65+
Node find(int index){
66+
if (index < (size >> 1)) {
67+
Node n = head;
68+
for (int i = 0; i < index; i++)
69+
n = n.next;
70+
return n;
71+
} else {
72+
Node n = last;
73+
for (int i = size - 1; i > index; i--)
74+
n = n.prev;
75+
return n;
76+
}
77+
}
78+
79+
@Override
80+
public Object remove(int index) {
81+
Node n = find(index);
82+
Object o = n.item;
83+
final Node prev = n.prev;
84+
final Node next = n.next;
85+
if (null != prev) {
86+
prev.next = next;
87+
}
88+
if (null != next) {
89+
next.prev = prev;
90+
}
91+
n.item = null;
92+
n.next = null;
93+
n.prev = null;
94+
size-- ;
95+
return o;
96+
}
97+
98+
@Override
99+
public int size() {
100+
return size;
101+
}
102+
103+
public void addFrist(Object o){
104+
linkHead(o);
105+
}
106+
107+
public void addLast(Object o){
108+
linkLast(o);
109+
}
110+
111+
public Object removeFirst(){
112+
Object o = head.item;
113+
Node n = head.next;
114+
head = n;
115+
if (n == null)
116+
last = null;
117+
else
118+
n.prev = null;
119+
size --;
120+
return o;
121+
}
122+
123+
public Object removeLaset(){
124+
Object o = last.item;
125+
Node p = last.prev;
126+
last = p;
127+
if (p == null)
128+
head = null;
129+
else
130+
p.next = null;
131+
size --;
132+
return o;
133+
}
134+
135+
public Iterator iterator(){
136+
return null;
137+
}
138+
139+
public static class Node{
140+
Object item;
141+
Node next;
142+
Node prev;
143+
144+
Node(Node prev, Object element, Node next) {
145+
this.item = element;
146+
this.next = next;
147+
this.prev = prev;
148+
}
149+
}
150+
}

‎group14/630254746/2017Leaning/src/com/leaning/code/List.java

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

‎group14/630254746/2017Leaning/src/com/leaning/code/Queue.java

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

‎group14/630254746/2017Leaning/src/com/leaning/code/Stack.java

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package com.leaning.code;
2+
3+
public class Stack {
4+
5+
private ArrayList list = new ArrayList();
6+
7+
private int size;
8+
9+
10+
public void push(Object o){
11+
list.add(o);
12+
size ++;
13+
}
14+
15+
public Object pop(){
16+
return list.get(--size);
17+
}
18+
19+
public Object peek(){
20+
return list.get(size-1);
21+
}
22+
23+
public boolean isEmpty(){
24+
return size == 0;
25+
}
26+
27+
public int size(){
28+
return size;
29+
}
30+
31+
}

‎group14/630254746/2017Leaning/src/com/leaning/code/test/ArrayListTest.java

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
package com.leaning.code.test;
2+
3+
import org.junit.Test;
4+
5+
import com.leaning.code.ArrayList;
6+
import com.leaning.code.LinkedList;
7+
8+
public class ArrayListTest {
9+
10+
@Test
11+
public void test01(){
12+
ArrayList list = new ArrayList();
13+
list.add("a");
14+
list.add("b");
15+
list.add("c");
16+
17+
System.out.println(list.remove(0));
18+
System.out.println(list);
19+
20+
}
21+
22+
@Test
23+
public void test02(){
24+
LinkedList list = new LinkedList();
25+
list.add("a");
26+
list.add("b");
27+
list.add("c");
28+
29+
list.add(2, "d");
30+
31+
System.out.println(list.remove(0));
32+
System.out.println(list.get(0));
33+
System.out.println(list.get(2));
34+
35+
36+
}
37+
}

0 commit comments

Comments
 (0)