Skip to content

Commit 478e4c4

Browse files
miniyk2012miniyk2012
committed
数据结构部分第一次提交，尚未完成二叉树
1 parent d4a25d6 commit 478e4c4

File tree

15 files changed

+630
-0
lines changed

15 files changed

+630
-0
lines changed

‎group02/812350401/.gitignore

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

‎group02/812350401/src/com/github/miniyk2012/coding2017/basic/ArrayList.java

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
package com.github.miniyk2012.coding2017.basic;
2+
3+
import java.util.Arrays;
4+
5+
6+
public class ArrayList implements List {
7+
8+
private int size = 0;
9+
private int DEFAULT_LENGTH = 10;
10+
11+
private Object[] elementData = new Object[DEFAULT_LENGTH];
12+
13+
public void add(Object o){
14+
ensureCapcacity();
15+
elementData[size++] = o;
16+
}
17+
public void add(int index, Object o){
18+
ensurnPosition(index);
19+
ensureCapcacity();
20+
System.arraycopy(elementData, index, elementData, index + 1,
21+
size - index);
22+
elementData[index] = o;
23+
size++;
24+
}
25+
26+
public Object get(int index){
27+
ensureIndex(index);
28+
return elementData[index];
29+
}
30+
31+
public Object remove(int index){
32+
ensureIndex(index);
33+
Object temp = elementData[index];
34+
System.arraycopy(elementData, index+1, elementData, index,
35+
size - index);
36+
size--;
37+
return temp;
38+
}
39+
40+
public void clear() {
41+
elementData = new Object[DEFAULT_LENGTH];
42+
size = 0;
43+
}
44+
45+
public int size(){
46+
return size;
47+
}
48+
49+
public Iterator iterator(){
50+
Iterator iterator = new IteratorImp(this);
51+
return iterator;
52+
}
53+
54+
private void ensureCapcacity() {
55+
int oldLength = elementData.length;
56+
if (size+1 > oldLength) {
57+
elementData = Arrays.copyOf(elementData, 2*oldLength);
58+
}
59+
}
60+
61+
private void ensureIndex(int index) {
62+
if (index >= size || index < 0)
63+
throw new ArrayIndexOutOfBoundsException(String.format("index %d out of bounds [0-%d)", index, size));
64+
}
65+
66+
private void ensurnPosition(int index) {
67+
if (index <0 || index>size)
68+
throw new ArrayIndexOutOfBoundsException(String.format("position %d out of position [0-%d)", index, size));
69+
}
70+
71+
@Override
72+
public String toString() {
73+
Object[] tempArray = Arrays.copyOf(elementData, size);
74+
return Arrays.toString(tempArray);
75+
}
76+
77+
}

‎group02/812350401/src/com/github/miniyk2012/coding2017/basic/BinaryTreeNode.java

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package com.github.miniyk2012.coding2017.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+
}

‎group02/812350401/src/com/github/miniyk2012/coding2017/basic/Iterator.java

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

‎group02/812350401/src/com/github/miniyk2012/coding2017/basic/IteratorImp.java

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
package com.github.miniyk2012.coding2017.basic;
2+
3+
public class IteratorImp implements Iterator {
4+
5+
private List aList;
6+
private int cursor = 0;
7+
8+
@Override
9+
public boolean hasNext() {
10+
return cursor != aList.size();
11+
}
12+
13+
@Override
14+
public Object next() {
15+
int i = cursor;
16+
Object next = aList.get(i);
17+
cursor = i+1;
18+
return next;
19+
}
20+
21+
public IteratorImp(List aList) {
22+
this.aList = aList;
23+
}
24+
}

‎group02/812350401/src/com/github/miniyk2012/coding2017/basic/LinkedList.java

Lines changed: 103 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,103 @@
1+
package com.github.miniyk2012.coding2017.basic;
2+
3+
public class LinkedList implements List {
4+
5+
private Node head;
6+
private int size = 0;
7+
8+
/**
9+
* node接收的index一定是范围内的值，不可能越界
10+
* @param index
11+
* @return a Node
12+
*/
13+
Node node(int index) {
14+
Node x = head;
15+
for (int i=0; i<index; i++) {
16+
x = x.next;
17+
}
18+
return x;
19+
}
20+
21+
public void add(Object o){
22+
add(size, o);
23+
}
24+
25+
public void add(int index , Object o){
26+
checkPositionIndex(index);
27+
Node after = node(index);
28+
Node newNode = new Node(o, after);
29+
if (index == 0) {
30+
head = newNode;
31+
}
32+
else {
33+
Node before = node(index-1);
34+
before.next = newNode;
35+
}
36+
size++;
37+
}
38+
39+
public Object get(int index){
40+
checkElementIndex(index);
41+
Node thisNode = node(index);
42+
return thisNode.data;
43+
}
44+
45+
public Object remove(int index){
46+
checkElementIndex(index);
47+
Node toRemove = node(index);
48+
if (index == 0)
49+
head = toRemove.next;
50+
else {
51+
Node before = node(index-1);
52+
before.next = toRemove.next;
53+
}
54+
size--;
55+
return toRemove.data;
56+
}
57+
58+
public int size(){
59+
return size;
60+
}
61+
62+
public void addFirst(Object o){
63+
add(0, o);
64+
}
65+
66+
public void addLast(Object o){
67+
add(o);
68+
}
69+
70+
public Object removeFirst(){
71+
return remove(0);
72+
}
73+
74+
public Object removeLast(){
75+
return remove(size-1);
76+
}
77+
78+
public Iterator iterator(){
79+
Iterator iterator = new IteratorImp(this);
80+
return iterator;
81+
}
82+
83+
private static class Node{
84+
Object data;
85+
Node next;
86+
87+
Node(){}
88+
Node(Object data, Node next) {
89+
this.data = data;
90+
this.next = next;
91+
}
92+
}
93+
94+
private void checkElementIndex(int index) {
95+
if (index < 0 || index >= size)
96+
throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
97+
}
98+
99+
private void checkPositionIndex(int index) {
100+
if (index < 0 || index > size)
101+
throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
102+
}
103+
}

‎group02/812350401/src/com/github/miniyk2012/coding2017/basic/List.java

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
package com.github.miniyk2012.coding2017.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+
public Iterator iterator();
10+
}

‎group02/812350401/src/com/github/miniyk2012/coding2017/basic/Queue.java

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package com.github.miniyk2012.coding2017.basic;
2+
3+
public class Queue {
4+
5+
// 队列入口 -》1，2，3，4 -》队列出口
6+
private LinkedList aList = new LinkedList();
7+
8+
public void enQueue(Object o){
9+
aList.addFirst(o);
10+
}
11+
12+
public Object deQueue(){
13+
return aList.removeLast();
14+
}
15+
16+
public boolean isEmpty(){
17+
return aList.size() == 0;
18+
}
19+
20+
public int size(){
21+
return aList.size();
22+
}
23+
}

‎group02/812350401/src/com/github/miniyk2012/coding2017/basic/Stack.java

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

‎group02/812350401/src/com/github/miniyk2012/coding2017/basic/test/ArrayListTest.java

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
package com.github.miniyk2012.coding2017.basic.test;
2+
3+
import org.junit.Before;
4+
import com.github.miniyk2012.coding2017.basic.ArrayList;
5+
6+
7+
public class ArrayListTest extends ListTest {
8+
9+
@Before
10+
public void setUpArrayList() {
11+
aList = new ArrayList();
12+
}
13+
14+
}

‎group02/812350401/src/com/github/miniyk2012/coding2017/basic/test/BinaryTreeNodeTest.java

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
package com.github.miniyk2012.coding2017.basic.test;
2+
3+
import static org.junit.Assert.assertEquals;
4+
5+
import org.junit.Before;
6+
import org.junit.Test;
7+
import com.github.miniyk2012.coding2017.basic.BinaryTreeNode;
8+
9+
public class BinaryTreeNodeTest {
10+
11+
private BinaryTreeNode binaryTreeNode;
12+
13+
@Before
14+
public void setUpBinaryTreeNode() {
15+
binaryTreeNode = new BinaryTreeNode();
16+
}
17+
18+
@Test
19+
public void testBinaryTreeNodeFunctional() {
20+
binaryTreeNode.insert(4);
21+
binaryTreeNode.insert(1);
22+
binaryTreeNode.insert(3);
23+
binaryTreeNode.insert(5);
24+
binaryTreeNode.insert(2);
25+
assertEquals(4, binaryTreeNode.getData());
26+
assertEquals(1, binaryTreeNode.getLeft().getData());
27+
assertEquals(5, binaryTreeNode.getRight().getData());
28+
assertEquals(3, binaryTreeNode.getLeft().getRight().getData());
29+
assertEquals(2, binaryTreeNode.getLeft().getRight().getLeft().getData());
30+
// binaryTreeNode.print();
31+
}
32+
33+
}

0 commit comments

Comments
 (0)