Skip to content

Commit 47da352

Browse files
onlyliuxinonlyliuxin
authored
Merge pull request onlyliuxin#28 from nusubmarine01/master
第三组第一次作业
2 parents 5d17ba1 + dcac31c commit 47da352

File tree

151 files changed

+7717
-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.

151 files changed

+7717
-0
lines changed

‎group03/1196051822/2月26日作业的代码/src/ArrayList.java

Lines changed: 102 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,102 @@
1+
package com.byhieg.coding2017;
2+
3+
import java.util.Arrays;
4+
import java.util.NoSuchElementException;
5+
6+
public class ArrayList implements List {
7+
8+
private int size = 0;
9+
10+
private Object[] elementData = new Object[100];
11+
12+
13+
public void add(Object o) {
14+
isCapacityEnough(size + 1);
15+
elementData[size++] = o;
16+
}
17+
18+
public void add(int index, Object o) {
19+
checkForAdd(index);
20+
isCapacityEnough(size + 1);
21+
System.arraycopy(elementData,index,elementData,index + 1,size - index);
22+
elementData[index] = o;
23+
size++;
24+
}
25+
26+
private void checkForAdd(int index){
27+
if (index < 0 || index > size) {
28+
throw new IndexOutOfBoundsException("index不在指定范围内");
29+
}
30+
31+
}
32+
private void isCapacityEnough(int size) {
33+
if (size > 100) {
34+
explicitCapacity(size);
35+
}
36+
if (size < 0) {
37+
throw new OutOfMemoryError();
38+
}
39+
}
40+
41+
private final static int MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8;
42+
43+
public void explicitCapacity(int size) {
44+
int newLength = elementData.length * 2;
45+
if (newLength > (MAX_ARRAY_LENGTH)){
46+
newLength = (size > MAX_ARRAY_LENGTH ? Integer.MAX_VALUE : MAX_ARRAY_LENGTH);
47+
}
48+
elementData = Arrays.copyOf(elementData, newLength);
49+
50+
}
51+
52+
53+
public Object get(int index) {
54+
checkRange(index);
55+
return elementData[index];
56+
}
57+
58+
private void checkRange(int index){
59+
if (index < 0 || index >= size) {
60+
throw new IndexOutOfBoundsException("index不在范围内");
61+
}
62+
}
63+
64+
public Object remove(int index) {
65+
Object o = get(index);
66+
//要保证后面的 index + 1是有效的
67+
int moveSize = size - index - 1;
68+
if (moveSize > 0) {
69+
System.arraycopy(elementData,index + 1,elementData,index, size - index);
70+
}
71+
elementData[--size] = null;
72+
return o;
73+
}
74+
75+
public int size() {
76+
return size;
77+
}
78+
79+
public Iterator iterator() {
80+
return new MyIterator();
81+
}
82+
83+
private class MyIterator implements Iterator {
84+
85+
private int cursor = 0;
86+
87+
@Override
88+
public boolean hasNext() {
89+
return cursor != size;
90+
}
91+
92+
@Override
93+
public Object next() {
94+
if (cursor >= size) {
95+
throw new NoSuchElementException();
96+
}
97+
return elementData[cursor++];
98+
}
99+
}
100+
101+
102+
}

‎group03/1196051822/2月26日作业的代码/src/BinaryTree.java

Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
package com.byhieg.coding2017;
2+
3+
/**
4+
* Created by byhieg on 17/2/22.
5+
* Mail to byhieg@gmail.com
6+
*/
7+
8+
public class BinaryTree {
9+
10+
private BinaryTreeNode root = new BinaryTreeNode();
11+
12+
public BinaryTree(Object rootData){
13+
root = root.insert(rootData);
14+
}
15+
16+
17+
//左边的值小于等于父节点的值，右边的值大于父节点的值
18+
private void insertNode(BinaryTreeNode root, BinaryTreeNode node) {
19+
int value = (int)node.getData();
20+
int rootValue = (int)root.getData();
21+
if (value <= rootValue){
22+
insertLeft(root,node);
23+
}else {
24+
insertRight(root,node);
25+
}
26+
}
27+
28+
29+
public void insert(Object o) {
30+
BinaryTreeNode node = new BinaryTreeNode();
31+
node = node.insert(o);
32+
insertNode(root,node);
33+
}
34+
35+
private void insertLeft(BinaryTreeNode father, BinaryTreeNode node) {
36+
if (father.getLeft() == null) {
37+
father.setLeft(node);
38+
}else{
39+
insertNode(father.getLeft(),node);
40+
}
41+
}
42+
43+
private void insertRight(BinaryTreeNode father, BinaryTreeNode node) {
44+
if (father.getRight() == null) {
45+
father.setRight(node);
46+
} else {
47+
insertNode(father.getRight(),node);
48+
}
49+
}
50+
51+
//前序遍历输出书
52+
private void preOrder(BinaryTreeNode node) {
53+
if (node != null) {
54+
System.out.println(node.getData());
55+
preOrder(node.getLeft());
56+
preOrder(node.getRight());
57+
}
58+
}
59+
60+
61+
//打印树
62+
public void printTree(){
63+
preOrder(root);
64+
}
65+
66+
}

‎group03/1196051822/2月26日作业的代码/src/BinaryTreeNode.java

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package com.byhieg.coding2017;
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+
13+
public void setData(Object data) {
14+
this.data = data;
15+
}
16+
17+
public BinaryTreeNode getLeft() {
18+
return left;
19+
}
20+
21+
public void setLeft(BinaryTreeNode left) {
22+
this.left = left;
23+
}
24+
25+
public BinaryTreeNode getRight() {
26+
return right;
27+
}
28+
29+
public void setRight(BinaryTreeNode right) {
30+
this.right = right;
31+
}
32+
33+
public BinaryTreeNode insert(Object o) {
34+
BinaryTreeNode node = new BinaryTreeNode();
35+
int value = (int)o;
36+
node.setData(value);
37+
node.setRight(null);
38+
node.setLeft(null);
39+
return node;
40+
}
41+
42+
}

‎group03/1196051822/2月26日作业的代码/src/Iterator.java

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

‎group03/1196051822/2月26日作业的代码/src/LinkedList.java

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

‎group03/1196051822/2月26日作业的代码/src/List.java

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
package com.byhieg.coding2017;
2+
3+
public interface List {
4+
public void add(Object o);
5+
6+
public void add(int index, Object o);
7+
8+
public Object get(int index);
9+
10+
public Object remove(int index);
11+
12+
public int size();
13+
}

0 commit comments

Comments
 (0)