Skip to content

Commit 5d17ba1

Browse files
onlyliuxinonlyliuxin
authored
Merge pull request onlyliuxin#21 from ChristopherYue/master
截至2017-02-26 23:08:45 ，10组提交的作业
2 parents 5ba95e7 + 06f8fd7 commit 5d17ba1

File tree

109 files changed

+5443
-0
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

109 files changed

+5443
-0
lines changed

‎group10/1363044717/第一次作业(数据结构)/ArrayList.java

Lines changed: 119 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,119 @@
1+
package com.coding.basic;
2+
3+
import java.lang.reflect.Array;
4+
import java.util.Arrays;
5+
import java.util.NoSuchElementException;
6+
7+
public class ArrayList<E> implements List<E> {
8+
9+
private int size = 0;
10+
11+
private Object[] elementData;
12+
13+
//默认容量
14+
private static final int DEFAULT_CAPACITY = 10;
15+
16+
public ArrayList(int capacity){
17+
if(capacity >= 0){
18+
elementData = new Object[capacity];
19+
}else {
20+
throw new IllegalArgumentException("Illegal Capacity: " +
21+
capacity);
22+
}
23+
24+
}
25+
public ArrayList(){
26+
this(DEFAULT_CAPACITY);
27+
}
28+
29+
/**
30+
* 保证集合容量
31+
* @param minCapacity
32+
*/
33+
private void ensureCapacity(int minCapacity){
34+
int oldCapacity = elementData.length;
35+
if(minCapacity > oldCapacity){
36+
//扩容
37+
int newCapacity = oldCapacity + (oldCapacity >> 1) + 1;
38+
if(minCapacity - newCapacity > 0){
39+
newCapacity = minCapacity;
40+
}
41+
elementData = Arrays.copyOf(elementData, newCapacity);
42+
}
43+
}
44+
private void checkIndexRange(int index)
45+
{
46+
if(index >= size || index < 0)
47+
{
48+
throw new IndexOutOfBoundsException("Index out of bounds, index : " + index);
49+
}
50+
}
51+
public void add(E o){
52+
ensureCapacity(size+1);
53+
elementData[size++] = o;
54+
}
55+
public void add(int index, E o){
56+
checkIndexRange(index);//检查下标
57+
ensureCapacity(size+1);//保证数组容量
58+
System.arraycopy(elementData,index,elementData,index + 1,size-index);//数组复制,把index后的元素全部向后移一位
59+
elementData[index] = o;//插入元素值
60+
size++;//元素size加一
61+
}
62+
63+
@Override
64+
public E get(int index) {
65+
checkIndexRange(index);//检查下标
66+
return (E)elementData[index];
67+
}
68+
69+
@Override
70+
public E remove(int index) {
71+
E e = this.get(index);
72+
int numMoved = size - index - 1;
73+
if(numMoved > 0)
74+
{
75+
System.arraycopy(elementData, index+1, elementData, index, numMoved);//数组复制,把index后的元素全部向前移一位
76+
}
77+
elementData[--size] = null;//最后一位赋值为null，size-1
78+
return e;
79+
}
80+
81+
82+
public int size(){
83+
return size;
84+
}
85+
86+
@Override
87+
public boolean isEmpty() {
88+
return size == 0;
89+
}
90+
91+
public Iterator iterator(){
92+
return new ArrayListIterator(this);
93+
}
94+
95+
private class ArrayListIterator<E> implements Iterator{
96+
97+
private Object [] array;
98+
private int endIndex = 0;
99+
private int index = 0;
100+
101+
public ArrayListIterator(ArrayList list){
102+
this.array=list.elementData;
103+
this.endIndex = list.size();
104+
}
105+
@Override
106+
public boolean hasNext() {
107+
return this.index < this.endIndex;
108+
}
109+
110+
@Override
111+
public E next() {
112+
if(!this.hasNext()) {
113+
throw new NoSuchElementException();//没有元素了
114+
} else {
115+
return (E)Array.get(this.array, this.index++);
116+
}
117+
}
118+
}
119+
}

‎group10/1363044717/第一次作业(数据结构)/BinaryTreeNode.java

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
package com.coding.basic;
2+
3+
4+
public class BinaryTreeNode implements Comparable<BinaryTreeNode> {
5+
public BinaryTreeNode(Object data) {
6+
this.data = data;
7+
}
8+
9+
private Object data;
10+
private BinaryTreeNode left;
11+
private BinaryTreeNode right;
12+
13+
public Object getData() {
14+
return data;
15+
}
16+
17+
public void setData(Object data) {
18+
this.data = data;
19+
}
20+
21+
public BinaryTreeNode getLeft() {
22+
return left;
23+
}
24+
25+
public void setLeft(BinaryTreeNode left) {
26+
this.left = left;
27+
}
28+
29+
public BinaryTreeNode getRight() {
30+
return right;
31+
}
32+
33+
public void setRight(BinaryTreeNode right) {
34+
this.right = right;
35+
}
36+
37+
public BinaryTreeNode insert(Object o) {
38+
//左子节点的值永远比父节点的值小
39+
//右子节点的值永远比父节点的值大
40+
BinaryTreeNode node = new BinaryTreeNode(o);
41+
insertNode(node);
42+
return node;
43+
}
44+
private void insertNode(BinaryTreeNode node){
45+
insertNode(this,node);
46+
}
47+
private void insertNode(BinaryTreeNode parentNode, BinaryTreeNode node) {
48+
if (parentNode.compareTo(node) <= 0) {//数字大于父节点
49+
if (parentNode.right == null) {
50+
parentNode.right = node;
51+
return;
52+
}
53+
insertNode(parentNode.right, node);
54+
} else {
55+
if (parentNode.left == null) {
56+
parentNode.left = node;
57+
return;
58+
}
59+
insertNode(parentNode.left, node);
60+
}
61+
}
62+
63+
@Override
64+
public int compareTo(BinaryTreeNode o) {
65+
Integer i = (Integer) this.data;
66+
return i.compareTo((Integer) o.data);
67+
}
68+
}

‎group10/1363044717/第一次作业(数据结构)/Iterator.java

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

‎group10/1363044717/第一次作业(数据结构)/JavaTest.java

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
package com.coding.basic;
2+
3+
import org.junit.Assert;
4+
import org.junit.Test;
5+
6+
/**
7+
* Created by Mori on 2017/2/21.
8+
*/
9+
public class JavaTest {
10+
@Test
11+
public void testBinaryTreeNode(){
12+
BinaryTreeNode node = new BinaryTreeNode(5);
13+
node.insert(4);//左
14+
node.insert(7);//右
15+
node.insert(2);//左左
16+
node.insert(6);//右左
17+
node.insert(5);//右左左
18+
node.insert(6);//右左右
19+
System.out.println(node.getData());
20+
System.out.println(node.getLeft().getData());
21+
System.out.println(node.getRight().getData());
22+
System.out.println(node.getLeft().getLeft().getData());
23+
System.out.println(node.getRight().getLeft().getData());
24+
System.out.println(node.getRight().getLeft().getLeft().getData());
25+
System.out.println(node.getRight().getLeft().getRight().getData());
26+
}
27+
@Test
28+
public void testArrayList(){
29+
ArrayList<Integer> list =new ArrayList<>();
30+
list.add(1);
31+
list.add(2);
32+
list.add(3);
33+
list.add(5);
34+
Assert.assertEquals((Object) list.get(2),3);
35+
Assert.assertEquals((Object) list.remove(2),3);
36+
Assert.assertEquals((Object) list.get(2),5);
37+
Iterator listIterator = list.iterator();
38+
while (listIterator.hasNext()){
39+
System.out.println(listIterator.next());
40+
}
41+
}
42+
@Test
43+
public void testLinkedList(){
44+
LinkedList<Integer> linkedList = new LinkedList<>();
45+
linkedList.add(1);
46+
linkedList.add(2);
47+
linkedList.add(5);
48+
linkedList.addFirst(10);
49+
linkedList.add(1,6);
50+
// linkedList.removeLast();
51+
//linkedList.removeFirst();
52+
Iterator linkedListIterator = linkedList.iterator();
53+
while (linkedListIterator.hasNext()){
54+
System.out.println(linkedListIterator.next());
55+
}
56+
System.out.println("----");
57+
System.out.println(linkedList.remove(0));
58+
System.out.println(linkedList.remove(2));
59+
//System.out.println(linkedList.get(3));
60+
//System.out.println(linkedList.get(4));
61+
}
62+
}

0 commit comments

Comments
 (0)