Skip to content

Commit ee6dc8b

Browse files
author
louisliu
committed
刘毅第一周数据结构作业
1 parent 1c60eec commit ee6dc8b

File tree

13 files changed

+480
-0
lines changed

13 files changed

+480
-0
lines changed

‎group07/396868934/DataStructure/.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.8"/>
5+
<classpathentry kind="con" path="org.eclipse.jdt.junit.JUNIT_CONTAINER/4"/>
6+
<classpathentry kind="output" path="bin"/>
7+
</classpath>

‎group07/396868934/DataStructure/.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>DataStructure</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>

‎group07/396868934/DataStructure/.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.8
4+
org.eclipse.jdt.core.compiler.codegen.unusedLocal=preserve
5+
org.eclipse.jdt.core.compiler.compliance=1.8
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.8

‎group07/396868934/DataStructure/bin/.gitignore

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

‎group07/396868934/DataStructure/src/com/louisly/java/LYArrayLink.java

Lines changed: 93 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,93 @@
1+
package com.louisly.java;
2+
3+
public class LYArrayLink {
4+
5+
private int currentCount = 0;
6+
private LYNode header = null;
7+
private LYNode lastNode = null;
8+
public void addObject(Object obj) {
9+
if (obj == null) return;
10+
11+
currentCount++;
12+
LYNode node = new LYNode();
13+
node.data = obj;
14+
15+
if (lastNode != null) {
16+
lastNode.next = node;
17+
lastNode = node;
18+
} else {
19+
lastNode = node;
20+
}
21+
22+
if (header == null) {
23+
header = node;
24+
}
25+
}
26+
27+
public void removeObject(Object obj) {
28+
LYNode lastNode = null;
29+
LYNode node = header;
30+
Object data = null;
31+
while (node != null) {
32+
data = node.data;
33+
if (data == obj) {
34+
if (lastNode != null) {
35+
lastNode.next = node.next;
36+
} else {
37+
// ÒƳýµÚÒ»¸öÔªËØ
38+
header = node.next;
39+
}
40+
41+
currentCount--;
42+
} else {
43+
lastNode = node;
44+
}
45+
node = node.next;
46+
}
47+
}
48+
49+
public void removeAtIndex(int index) {
50+
if (header == null) return; // error: out of bounces
51+
52+
LYNode lastNode = null;
53+
LYNode node = header;
54+
55+
for (int i = 0; i < index; i++) {
56+
if (node != null) {
57+
lastNode = node;
58+
node = node.next;
59+
} else {
60+
return; // error: out of bounces
61+
}
62+
}
63+
64+
if (index == 0) {
65+
header = node.next;
66+
} else {
67+
lastNode.next = node.next;
68+
}
69+
currentCount--;
70+
}
71+
72+
public Object get(int index) {
73+
if (header == null) return null; // error: out of bounces
74+
LYNode node = header;
75+
for (int i = 0; i < index; i++) {
76+
node = node.next;
77+
if (node == null) {
78+
return null;
79+
}
80+
}
81+
return node.data;
82+
}
83+
84+
public int size() {
85+
return currentCount;
86+
}
87+
88+
private static class LYNode {
89+
Object data;
90+
LYNode next;
91+
92+
}
93+
}

‎group07/396868934/DataStructure/src/com/louisly/java/LYArrayList.java

Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
package com.louisly.java;
2+
import com.louisly.java.LYIterator;
3+
4+
public class LYArrayList {
5+
private Object[] elementData = new Object[10];
6+
private int currentCount = 0;
7+
public void addObject(Object obj) {
8+
if (currentCount >= elementData.length) {
9+
grow();
10+
}
11+
elementData[currentCount] = obj;
12+
currentCount++;
13+
}
14+
15+
public boolean removeObject(Object obj) {
16+
boolean existObj = false;
17+
int removeIndex = -1;
18+
int index = currentCount;
19+
for (int i = 0; i < index; i++) {
20+
Object element = elementData[i];
21+
boolean remove = false;
22+
if (element != null && element.equals(obj)) {
23+
elementData[i] = null;
24+
existObj = true;
25+
remove = true;
26+
// 以防存在一样的第二个元素
27+
if (removeIndex == -1) {
28+
removeIndex = i;
29+
}
30+
currentCount--;
31+
}
32+
// 将元素往前移动
33+
if (!remove) {
34+
elementData[removeIndex] = element;
35+
elementData[i] = null;
36+
removeIndex++;
37+
}
38+
}
39+
return existObj;
40+
}
41+
42+
public boolean removeAtIndex(int index) {
43+
if (index > currentCount) {
44+
return false;
45+
}
46+
elementData[index] = null;
47+
48+
for (int i = index+1; i < currentCount; i++) {
49+
elementData[i-1] = elementData[i];
50+
elementData[i] = null;
51+
}
52+
currentCount--;
53+
return true;
54+
}
55+
56+
public void grow() {
57+
Object[] target = new Object[elementData.length*2];
58+
System.arraycopy(elementData, 0, target, 0, elementData.length);
59+
elementData = target;
60+
}
61+
62+
public Object get(int index) {
63+
if (index > currentCount) {
64+
return null;
65+
}
66+
return elementData[index];
67+
}
68+
69+
public int size() {
70+
return currentCount;
71+
}
72+
73+
public LYIterator iterator() {
74+
return new LYArrayListIterator(this);
75+
}
76+
private class LYArrayListIterator implements LYIterator {
77+
LYArrayList arrayList = null;
78+
int position = 0;
79+
public LYArrayListIterator(LYArrayList arrayList) {
80+
this.arrayList = arrayList;
81+
}
82+
83+
@Override
84+
public boolean hasNext() {
85+
86+
return false;
87+
}
88+
@Override
89+
public Object next() {
90+
return elementData[position];
91+
}
92+
public void remove() {
93+
94+
}
95+
}
96+
}

‎group07/396868934/DataStructure/src/com/louisly/java/LYArrayListTest.java

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
package com.louisly.java;
2+
3+
import static org.junit.Assert.*;
4+
5+
import java.util.ArrayList;
6+
7+
import org.junit.After;
8+
import org.junit.Before;
9+
import org.junit.Test;
10+
11+
import junit.framework.Assert;
12+
13+
public class LYArrayListTest {
14+
15+
@Before
16+
public void setUp() throws Exception {
17+
}
18+
19+
@After
20+
public void tearDown() throws Exception {
21+
}
22+
23+
@Test
24+
public void testAddObject() {
25+
LYArrayList list = new LYArrayList();
26+
list.addObject(new Integer(10));
27+
Assert.assertEquals(10, ((Integer)list.get(0)).intValue());
28+
}
29+
30+
@Test
31+
public void testRemoveObject() {
32+
fail("Not yet implemented");
33+
}
34+
35+
@Test
36+
public void testRemoveAtIndex() {
37+
fail("Not yet implemented");
38+
}
39+
40+
@Test
41+
public void testGet() {
42+
fail("Not yet implemented");
43+
}
44+
45+
@Test
46+
public void testSize() {
47+
fail("Not yet implemented");
48+
}
49+
50+
}

‎group07/396868934/DataStructure/src/com/louisly/java/LYBinaryTree.java

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package com.louisly.java;
2+
import com.louisly.java.LYObject;
3+
4+
public class LYBinaryTree {
5+
6+
private LYBinaryTreeNode headerNode;
7+
8+
public void addObject(LYObject obj) {
9+
10+
if (headerNode == null) {
11+
LYBinaryTreeNode node = new LYBinaryTreeNode();
12+
node.data = obj;
13+
headerNode = node;
14+
return;
15+
}
16+
17+
this.appendObject(headerNode, obj);
18+
}
19+
20+
private void appendObject(LYBinaryTreeNode toNode, LYObject obj) {
21+
if (obj.i > toNode.data.i) {
22+
if (toNode.right != null) {
23+
this.appendObject(toNode.right, obj);
24+
} else {
25+
LYBinaryTreeNode node = new LYBinaryTreeNode();
26+
node.data = obj;
27+
toNode.right = node;
28+
}
29+
} else {
30+
if (toNode.left != null) {
31+
this.appendObject(toNode.left, obj);
32+
} else {
33+
LYBinaryTreeNode node = new LYBinaryTreeNode();
34+
node.data = obj;
35+
toNode.left = node;
36+
}
37+
}
38+
}
39+
40+
public static class LYBinaryTreeNode {
41+
private LYObject data;
42+
private LYBinaryTreeNode left;
43+
private LYBinaryTreeNode right;
44+
}
45+
}

‎group07/396868934/DataStructure/src/com/louisly/java/LYIterator.java

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
package com.louisly.java;
2+
3+
public interface LYIterator {
4+
public boolean hasNext();
5+
public Object next();
6+
}

‎group07/396868934/DataStructure/src/com/louisly/java/LYObject.java

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
package com.louisly.java;
2+
3+
public class LYObject extends Object {
4+
int i = 0;
5+
public LYObject(int i) {
6+
this.i = i;
7+
}
8+
}

‎group07/396868934/DataStructure/src/com/louisly/java/LYQueue.java

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package com.louisly.java;
2+
import com.louisly.java.LYArrayList;
3+
4+
public class LYQueue {
5+
LYArrayList list = null;
6+
public LYQueue() {
7+
list = new LYArrayList();
8+
}
9+
10+
public void enQueue(Object obj) {
11+
list.addObject(obj);
12+
}
13+
14+
public Object deQueue() {
15+
if (list.size() != 0) {
16+
return list.get(0);
17+
}
18+
return null;
19+
}
20+
21+
public boolean isEmpty() {
22+
return list.size() == 0;
23+
}
24+
25+
public int size() {
26+
return list.size();
27+
}
28+
}

0 commit comments

Comments
 (0)