Skip to content

Commit 957bb91

Browse files
PigTSPigTS
committed
Basic Data Structure Test---Version 1.0
1 parent 764c5b0 commit 957bb91

File tree

17 files changed

+735
-0
lines changed

17 files changed

+735
-0
lines changed

‎group01/1814014897/zhouhui/.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>

‎group01/1814014897/zhouhui/.gitignore

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

‎group01/1814014897/zhouhui/.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>2017Learning</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>

‎group01/1814014897/zhouhui/.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

‎group01/1814014897/zhouhui/src/BasicDataStructure/ArrayList.java

Lines changed: 74 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,74 @@
1+
package BasicDataStructure;
2+
3+
import java.util.Arrays;
4+
5+
public class ArrayList implements List {
6+
7+
private int size = 0;
8+
9+
private Object[] elementData = new Object[100];
10+
11+
public void add(Object o){
12+
ensureCapacity(size + 1); //size increase,in order to have enough capacity.
13+
elementData[size++] = o; //similar to: elementData[size]=o; size++;
14+
}
15+
16+
private void ensureCapacity(int minCapacity){
17+
if(minCapacity > elementData.length){
18+
grow(minCapacity);
19+
}
20+
}
21+
22+
private void grow(int minCapacity){
23+
int oldCapacity = elementData.length;
24+
int newCapacity = oldCapacity + ( oldCapacity >> 1 );
25+
if(newCapacity < minCapacity){
26+
newCapacity = minCapacity;
27+
}
28+
elementData = Arrays.copyOf(elementData, newCapacity);
29+
30+
}
31+
32+
public void add(int index, Object o){
33+
if(index < 0 || index > size) throw new IndexOutOfBoundsException("Index:"+index+",Size:"+size);
34+
ensureCapacity(size+1);
35+
System.arraycopy(elementData, index, elementData, index + 1, size - index);
36+
elementData[index] = o;
37+
size++;
38+
}
39+
40+
public Object get(int index){
41+
if(index < 0 || index >= size) throw new IndexOutOfBoundsException("Index:"+index+",Size:"+size);
42+
return elementData[index];
43+
}
44+
45+
public Object remove(int index){
46+
if(index < 0 || index >= size) throw new IndexOutOfBoundsException("Index:"+index+",Size:"+size);
47+
System.arraycopy(elementData, index + 1, elementData, index, size - index - 1);
48+
elementData[size - 1] = null;
49+
size--;
50+
return elementData;
51+
}
52+
53+
public int size(){
54+
return size;
55+
}
56+
57+
public Iterator iterator(){
58+
return new ArrayListIterator();
59+
}
60+
61+
private class ArrayListIterator implements Iterator{
62+
63+
private int pos = 0;
64+
65+
public boolean hasNext() {
66+
return pos < size;
67+
}
68+
69+
public Object next() {
70+
return elementData[pos++];
71+
}
72+
}
73+
74+
}

‎group01/1814014897/zhouhui/src/BasicDataStructure/BinaryTreeNode.java

Lines changed: 56 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,56 @@
1+
package BasicDataStructure;
2+
3+
public class BinaryTreeNode{
4+
5+
private Object data;
6+
private BinaryTreeNode left;
7+
private BinaryTreeNode right;
8+
9+
public BinaryTreeNode(Object data){
10+
this.data = data;
11+
left = null;
12+
right = null;
13+
}
14+
15+
public Object getData() {
16+
return data;
17+
}
18+
public void setData(Object data) {
19+
this.data = data;
20+
}
21+
public BinaryTreeNode getLeft() {
22+
return left;
23+
}
24+
public void setLeft(BinaryTreeNode left) {
25+
this.left = left;
26+
}
27+
public BinaryTreeNode getRight() {
28+
return right;
29+
}
30+
public void setRight(BinaryTreeNode right) {
31+
this.right = right;
32+
}
33+
34+
public BinaryTreeNode insert(Object o){
35+
if((Integer)o < (Integer)this.data)
36+
{
37+
if(this.left == null){
38+
BinaryTreeNode node = new BinaryTreeNode(o);
39+
this.setLeft(node);
40+
return node;
41+
}else{
42+
return this.left.insert(o);
43+
}
44+
}else{
45+
if(this.right == null){
46+
BinaryTreeNode node = new BinaryTreeNode(o);
47+
this.setRight(node);
48+
return node;
49+
}else{
50+
return this.right.insert(o);
51+
}
52+
}
53+
}
54+
}
55+
56+

‎group01/1814014897/zhouhui/src/BasicDataStructure/Iterator.java

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

‎group01/1814014897/zhouhui/src/BasicDataStructure/LinkedList.java

Lines changed: 113 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,113 @@
1+
package BasicDataStructure;
2+
3+
public class LinkedList implements List {
4+
5+
private Node head;
6+
private int size = 0;
7+
8+
public void add(Object o){
9+
if(head == null){
10+
head = new Node(o);
11+
}else{
12+
Node pos = head;
13+
while(pos.next != null){
14+
pos = pos.next;
15+
}
16+
pos.next = new Node(o);
17+
}
18+
size++;
19+
}
20+
21+
public void add(int index , Object o){
22+
if(index < 0 || index >size ) throw new IndexOutOfBoundsException("Index:"+index+",Size"+size);
23+
if(index == 0) {
24+
Node node = new Node(o);
25+
node.next = head;
26+
head = node;
27+
}
28+
else{
29+
Node pos = head;
30+
for(int i = 0;i < index-1;i++){
31+
pos = pos.next;
32+
}
33+
Node node = new Node(o);
34+
node.next = pos.next;
35+
pos.next = node;
36+
}
37+
size++;
38+
}
39+
40+
public Object get(int index){
41+
if(index < 0 || index >=size ) throw new IndexOutOfBoundsException("Index:"+index+",Size"+size);
42+
Node pos = head;
43+
for(int i = 0;i < index;i++){
44+
pos = pos.next;
45+
}
46+
return pos.data;
47+
}
48+
49+
public Object remove(int index){
50+
if(index < 0 || index >=size ) throw new IndexOutOfBoundsException("Index:"+index+",Size:"+size);
51+
Node element = head;
52+
if(index == 0){
53+
head = head.next;
54+
}else{
55+
Node pos = head;
56+
for(int i = 0;i < index - 1;i++){
57+
pos = pos.next;
58+
}
59+
element = pos.next;
60+
pos.next = pos.next.next;
61+
}
62+
size--;
63+
return element.data;
64+
}
65+
66+
public int size(){
67+
return size;
68+
}
69+
70+
public void addFirst(Object o){
71+
add(0,o);
72+
}
73+
public void addLast(Object o){
74+
add(size,o);
75+
}
76+
public Object removeFirst(){
77+
return remove(0);
78+
}
79+
public Object removeLast(){
80+
return remove(size-1);
81+
}
82+
public Iterator iterator(){
83+
return new LinkedListIterator();
84+
}
85+
86+
class LinkedListIterator implements Iterator{
87+
88+
private Node node = head;
89+
private int pos = 0;
90+
@Override
91+
public boolean hasNext() {
92+
return pos < size;
93+
}
94+
95+
@Override
96+
public Object next() {
97+
pos++;
98+
if(pos != 1){
99+
node = node.next;
100+
}
101+
return node.data;
102+
}
103+
}
104+
105+
private static class Node{
106+
Object data;
107+
Node next;
108+
public Node(Object data){
109+
this.data = data;
110+
next = null;
111+
}
112+
}
113+
}

‎group01/1814014897/zhouhui/src/BasicDataStructure/List.java

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package BasicDataStructure;
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+
}

‎group01/1814014897/zhouhui/src/BasicDataStructure/Queue.java

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

‎group01/1814014897/zhouhui/src/BasicDataStructure/Stack.java

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

‎group01/1814014897/zhouhui/src/BasicDataStructureTest/AllTest.java

Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
package BasicDataStructureTest;
2+
3+
import org.junit.runner.RunWith;
4+
import org.junit.runners.Suite;
5+
import org.junit.runners.Suite.SuiteClasses;
6+
7+
@RunWith(Suite.class)
8+
@SuiteClasses({
9+
ArrayListTest.class,
10+
BinaryTreeNodeTest.class,
11+
LinkedListTest.class,
12+
QueueTest.class,
13+
StackTest.class
14+
})
15+
16+
public class AllTest {
17+
18+
}

0 commit comments

Comments
 (0)