Skip to content

Commit 733e95e

Browse files
author
he
committed
第一周编程作业
1 parent bb45e5a commit 733e95e

File tree

9 files changed

+413
-0
lines changed

9 files changed

+413
-0
lines changed

‎group14/775857669/.gitignore

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

‎group14/775857669/src/com/coding/basic/ArrayList.java

Lines changed: 86 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,86 @@
1+
package com.coding.basic;
2+
3+
import java.util.Arrays;
4+
5+
public class ArrayList implements List {
6+
7+
private int size = 0;
8+
9+
private static final int MIN_EXTEND = 10;
10+
11+
private Object[] elementData = new Object[100];
12+
/**
13+
*
14+
* @Author: yuhe
15+
* @Description: 确保数组的容量
16+
* @param next 要插入的位置
17+
*/
18+
private void ensureCapacity(int capacity) {
19+
if (capacity < elementData.length) {
20+
return;
21+
} else {
22+
int newLength = capacity + MIN_EXTEND;
23+
elementData = Arrays.copyOf(elementData, newLength);
24+
}
25+
26+
}
27+
28+
private void rangeCheckForAdd(int index) {
29+
if (index < 0 || index > size) {
30+
throw new ArrayIndexOutOfBoundsException(index);
31+
}
32+
}
33+
34+
private void rangeCheck(int index) {
35+
if (index < 0 || index >= size) {
36+
throw new ArrayIndexOutOfBoundsException(index);
37+
}
38+
}
39+
40+
public void add(Object o){
41+
ensureCapacity(size+1);
42+
elementData[size++] = o;
43+
}
44+
45+
public void add(int index, Object o){
46+
rangeCheckForAdd(index);
47+
ensureCapacity(size +1);
48+
System.arraycopy(elementData, index, elementData, index+1, size - index);
49+
elementData[index] = o;
50+
size++;
51+
}
52+
53+
public Object get(int index){
54+
rangeCheck(index);
55+
return elementData[index];
56+
}
57+
58+
public Object remove(int index){
59+
rangeCheck(index);
60+
Object ret = elementData[index];
61+
int numToRemove = size-index-1;
62+
if (numToRemove > 0)
63+
System.arraycopy(elementData, index+1, elementData, index, numToRemove);
64+
elementData[size--] = null;
65+
return ret;
66+
}
67+
68+
public int size(){
69+
return size;
70+
}
71+
72+
public Iterator iterator(){
73+
return new Iterator() {
74+
private int index = 0;
75+
@Override
76+
public Object next() {
77+
return elementData[index++];
78+
}
79+
80+
@Override
81+
public boolean hasNext() {
82+
return index < size;
83+
}
84+
};
85+
}
86+
}

‎group14/775857669/src/com/coding/basic/BinaryTreeNode.java

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

‎group14/775857669/src/com/coding/basic/Iterator.java

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

‎group14/775857669/src/com/coding/basic/JUnitTest.java

Lines changed: 69 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,69 @@
1+
package com.coding.basic;
2+
3+
import static org.junit.Assert.*;
4+
5+
6+
import org.junit.Test;
7+
8+
public class JUnitTest {
9+
@Test
10+
public void testArrayList() {
11+
ArrayList list = new ArrayList();
12+
for (int i = 0; i < 300; i++) {
13+
list.add(i);
14+
}
15+
assertTrue(list.size() == 300);
16+
list.add(3, 3);
17+
assertTrue( (int)list.get(3) == 3 );
18+
assertTrue( (int)list.get(2) == 2 );
19+
assertTrue( (int)list.get(4) == 3 );
20+
assertTrue( (int)list.get(299) == 298 );
21+
assertTrue( (int)list.get(300) == 299 );
22+
assertTrue(list.size() == 301);
23+
list.remove(3);
24+
assertTrue( (int)list.get(3) == 3 );
25+
assertTrue( (int)list.get(2) == 2 );
26+
assertTrue( (int)list.get(4) == 4 );
27+
assertTrue( (int)list.get(299) == 299 );
28+
assertTrue(list.size() == 300);
29+
Iterator iterator = list.iterator();
30+
while(iterator.hasNext()) {
31+
System.out.print(iterator.next() + " ");
32+
}
33+
System.out.println();
34+
LinkedList linkedList = new LinkedList();
35+
for(int i=0 ; i<10 ; i++){
36+
linkedList.add(i);
37+
}
38+
assertTrue(linkedList.size() == 10);
39+
Iterator iterator2 = linkedList.iterator();
40+
while(iterator2.hasNext()) {
41+
System.out.print(iterator2.next() + " ");
42+
}
43+
linkedList.add(0, -1);
44+
linkedList.add(11,10);
45+
46+
assertTrue(linkedList.size() == 12);
47+
assertTrue((int)linkedList.removeFirst() == -1);
48+
49+
assertTrue((int)linkedList.removeLast() == 10);
50+
assertTrue((int)linkedList.remove(5) == 5);
51+
assertTrue(linkedList.size() == 9);
52+
53+
Stack stack = new Stack();
54+
for (int i = 0; i < 10; i++) {
55+
stack.push(i);
56+
}
57+
assertTrue(stack.size() == 10);
58+
assertFalse(stack.isEmpty());
59+
assertTrue((int)stack.peek() == 9);
60+
assertTrue((int)stack.pop() == 9);
61+
assertTrue(stack.size() == 9);
62+
System.out.println();
63+
for (int i=0 ; i<9 ; i++){
64+
System.out.print(stack.pop() + " ");
65+
}
66+
assertTrue(stack.isEmpty());
67+
}
68+
69+
}

‎group14/775857669/src/com/coding/basic/LinkedList.java

Lines changed: 140 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,140 @@
1+
package com.coding.basic;
2+
3+
import java.util.NoSuchElementException;
4+
5+
public class LinkedList implements List {
6+
7+
private int size = 0;
8+
9+
private Node head;
10+
11+
public LinkedList() {
12+
head = new Node();
13+
}
14+
15+
public void add(Object o){
16+
Node temp = head;
17+
for (int i=0 ; i<size ; i++){
18+
temp = temp.next;
19+
}
20+
temp.next = new Node(o, null);
21+
size++;
22+
}
23+
24+
public void add(int index , Object o){
25+
checkRangeForAdd(index);
26+
Node before = head;
27+
Node after = null;
28+
for (int i=0 ; i <index ; i++){
29+
before = before.next;
30+
}
31+
after = before.next;
32+
Node newNode = new Node(o, after);
33+
before.next = newNode;
34+
size++;
35+
}
36+
37+
public Object get(int index){
38+
checkRange(index);
39+
Node tmp = head.next;
40+
for (int i=0 ; i<index ; i++) {
41+
tmp = tmp.next;
42+
}
43+
return tmp.data;
44+
}
45+
46+
public Object remove(int index){
47+
Node before = head;
48+
for(int i=0 ; i<index ; i++) {
49+
before = before.next;
50+
}
51+
Node after = before.next;
52+
Node target = before.next;
53+
before.next = after;
54+
size--;
55+
return target.data;
56+
}
57+
58+
public int size(){
59+
return size;
60+
}
61+
62+
public void addFirst(Object o){
63+
Node after = head.next;
64+
Node newNode = new Node(o, after);
65+
head.next = newNode;
66+
size++;
67+
}
68+
public void addLast(Object o){
69+
Node tail = head;
70+
for(int i=0 ; i<size ; i++){
71+
tail = tail.next;
72+
}
73+
tail.next = new Node(o, null);
74+
size++;
75+
}
76+
public Object removeFirst(){
77+
if (size < 1) {
78+
throw new ArrayIndexOutOfBoundsException(0);
79+
}
80+
Node first = head.next;
81+
Node second = first.next;
82+
head.next = second;
83+
size--;
84+
return first.data;
85+
}
86+
public Object removeLast(){
87+
if (size == 0)
88+
throw new NoSuchElementException();
89+
Node beforeLast = head;
90+
for (int i=0 ; i<size-1 ; i++){
91+
beforeLast = beforeLast.next;
92+
}
93+
Node tail = beforeLast.next;
94+
beforeLast.next = null;
95+
size--;
96+
return tail.data;
97+
}
98+
public Iterator iterator(){
99+
return new Iterator() {
100+
Node index = head;
101+
@Override
102+
public Object next() {
103+
index = index.next;
104+
return index.data;
105+
}
106+
107+
@Override
108+
public boolean hasNext() {
109+
return index.next!=null;
110+
}
111+
};
112+
}
113+
114+
private void checkRangeForAdd(int index) {
115+
if (index < 0 || index > size) {
116+
throw new ArrayIndexOutOfBoundsException(index);
117+
}
118+
}
119+
120+
private void checkRange(int index) {
121+
if (index < 0 || index >= size) {
122+
throw new ArrayIndexOutOfBoundsException(index);
123+
}
124+
}
125+
126+
private static class Node{
127+
public Node() {
128+
}
129+
130+
public Node(Object data, Node next) {
131+
super();
132+
this.data = data;
133+
this.next = next;
134+
}
135+
136+
private Object data;
137+
private Node next;
138+
139+
}
140+
}

‎group14/775857669/src/com/coding/basic/List.java

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

‎group14/775857669/src/com/coding/basic/Queue.java

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

0 commit comments

Comments
 (0)