Skip to content

Commit 7d1ed27

Browse files
luoziyihaoluoziyihao
authored
Merge pull request onlyliuxin#10 from williamgx8/master
2月26作业，除文章
2 parents c230748 + f83c004 commit 7d1ed27

File tree

12 files changed

+543
-0
lines changed

12 files changed

+543
-0
lines changed

‎group17/785396327/binarytree/BinaryTree.java

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
package binarytree;
2+
3+
/**
4+
* Created by william on 2017/2/16.
5+
*/
6+
public class BinaryTree {
7+
private Node root;
8+
9+
class Node {
10+
private Node left;
11+
private Node right;
12+
private Comparable data;
13+
14+
public Node(Node left, Node right, Comparable data) {
15+
this.left = left;
16+
this.right = right;
17+
this.data = data;
18+
}
19+
20+
private void add(Comparable data) {
21+
if (this.data.compareTo(data) >= 0)
22+
if (this.left == null)
23+
this.left = new Node(null, null, data);
24+
else
25+
left.add(data);
26+
else if (this.data.compareTo(data) < 0)
27+
if (this.right == null)
28+
this.right = new Node(null, null, data);
29+
else
30+
this.right.add(data);
31+
}
32+
33+
public Comparable getData() {
34+
return this.data;
35+
}
36+
37+
public Node getLeft() {
38+
return this.left;
39+
}
40+
41+
public Node getRight() {
42+
return this.right;
43+
}
44+
}
45+
46+
public void add(Comparable data) {
47+
if (this.root == null)
48+
root = new Node(null, null, data);
49+
else this.root.add(data);
50+
}
51+
52+
public void printByType(SearchType<Node> type) {
53+
type.printByType(this.root);
54+
}
55+
}

‎group17/785396327/binarytree/DLRSearchType.java

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
package binarytree;
2+
3+
/**
4+
* Created by william on 2017/2/18.
5+
*/
6+
public class DLRSearchType implements SearchType<BinaryTree.Node> {
7+
8+
@Override
9+
public void printByType(BinaryTree.Node root) {
10+
if (root != null) {
11+
System.out.print(root.getData()+" ");
12+
printByType(root.getLeft());
13+
printByType(root.getRight());
14+
}
15+
}
16+
}

‎group17/785396327/binarytree/LDRSearchType.java

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
package binarytree;
2+
3+
/**
4+
* Created by william on 2017/2/18.
5+
*/
6+
public class LDRSearchType implements SearchType<BinaryTree.Node> {
7+
@Override
8+
public void printByType(BinaryTree.Node root) {
9+
if (root != null) {
10+
printByType(root.getLeft());
11+
System.out.print(root.getData() + " ");
12+
printByType(root.getRight());
13+
}
14+
}
15+
}

‎group17/785396327/binarytree/LFSearchType.java

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package binarytree;
2+
3+
import java.util.LinkedList;
4+
5+
/**
6+
* Created by william on 2017/2/18.
7+
*/
8+
public class LFSearchType implements SearchType<BinaryTree.Node> {
9+
private LinkedList<BinaryTree.Node> queue = new LinkedList<>();
10+
11+
@Override
12+
public void printByType(BinaryTree.Node root) {
13+
if (root == null)
14+
return;
15+
queue.offer(root);
16+
while (!queue.isEmpty()) {
17+
BinaryTree.Node curNode = queue.poll();
18+
System.out.print(curNode.getData() + " ");
19+
if (curNode.getLeft() != null)
20+
queue.offer(curNode.getLeft());
21+
if (curNode.getRight() != null)
22+
queue.offer(curNode.getRight());
23+
}
24+
25+
}
26+
27+
}

‎group17/785396327/binarytree/LRDSearchType.java

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
package binarytree;
2+
3+
/**
4+
* Created by william on 2017/2/18.
5+
*/
6+
public class LRDSearchType implements SearchType<BinaryTree.Node> {
7+
@Override
8+
public void printByType(BinaryTree.Node root) {
9+
if (root != null) {
10+
printByType(root.getLeft());
11+
printByType(root.getRight());
12+
System.out.print(root.getData() + " ");
13+
}
14+
}
15+
}

‎group17/785396327/binarytree/SearchType.java

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package binarytree;
2+
3+
/**
4+
* Created by william on 2017/2/18.
5+
*/
6+
public interface SearchType<T> {
7+
8+
void printByType(T root);
9+
}

‎group17/785396327/list/ArrayList.java

Lines changed: 135 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,135 @@
1+
package list;
2+
3+
import java.util.Arrays;
4+
import java.util.NoSuchElementException;
5+
6+
/**
7+
* Created by william on 2017/2/25.
8+
*/
9+
public class ArrayList<T> implements List<T> {
10+
private static final int DEFAULT_CAPACITY = 10;
11+
private int size;
12+
private Object[] elementData;
13+
14+
public ArrayList() {
15+
elementData = new Object[DEFAULT_CAPACITY];
16+
}
17+
18+
public ArrayList(int initialCapacity) {
19+
if (initialCapacity < 0)
20+
throw new RuntimeException("非法初始化大小参数!");
21+
elementData = new Object[initialCapacity];
22+
}
23+
24+
public boolean add(T ele) {
25+
grow();
26+
elementData[size] = ele;
27+
size++;
28+
return true;
29+
}
30+
31+
public T get(int index) {
32+
checkBounds(index);
33+
return (T) elementData[index];
34+
}
35+
36+
public T remove(int index) {
37+
checkBounds(index);
38+
T removeEle = (T) elementData[index];
39+
System.arraycopy(elementData, index + 1, elementData, index, size - index);
40+
size--;
41+
return removeEle;
42+
}
43+
44+
public boolean add(int index, T ele) {
45+
checkBounds(index);
46+
size++;//有效元素内容先加，保证长度极限情况grow在添加前生效
47+
grow();
48+
//将原本数组从待插入的index截取，将原本index后的有效值，复制到原本数组index+1之后
49+
System.arraycopy(elementData, index, elementData, index + 1, size - index);
50+
elementData[index] = ele;
51+
return true;
52+
}
53+
54+
@Override
55+
public boolean remove(T ele) {
56+
int index;
57+
if ((index = indexOf(ele)) == -1)
58+
return false;
59+
remove(index);
60+
return true;
61+
}
62+
63+
private void checkBounds(int index) {
64+
if (index < 0 || index >= size)
65+
throw new IndexOutOfBoundsException("index : " + index + ", size : [ 0 - " + size + " ]");
66+
}
67+
68+
public int size() {
69+
return size;
70+
}
71+
72+
private void grow() {
73+
if (size >= elementData.length) {
74+
int curLen = elementData.length;
75+
int newLen = curLen + (curLen >> 1) > Integer.MAX_VALUE ? Integer.MAX_VALUE : curLen + (curLen >> 1);
76+
elementData = Arrays.copyOf(elementData, newLen);
77+
}
78+
}
79+
80+
public boolean isEmpty() {
81+
return size == 0;
82+
}
83+
84+
@Override
85+
public boolean contains(T ele) {
86+
return indexOf(ele) != -1;
87+
}
88+
89+
public int indexOf(T ele) {
90+
for (int i = 0; i < size; i++) {
91+
if (ele == null)
92+
if (null == elementData[i])
93+
return i;
94+
else if (ele.equals(elementData[i]))
95+
return i;
96+
}
97+
return -1;
98+
}
99+
100+
public Iterator<T> iterator() {
101+
return new Itr<T>();
102+
}
103+
104+
private class Itr<T> implements Iterator<T> {
105+
int cursor;//待遍历元素的下标
106+
107+
@Override
108+
public boolean hasNext() {
109+
return cursor != size;
110+
}
111+
112+
@Override
113+
public T next() {
114+
if (cursor >= size)
115+
throw new NoSuchElementException();
116+
return (T) elementData[cursor++];
117+
}
118+
119+
@Override
120+
public void remove() {
121+
if (cursor >= size)
122+
throw new NoSuchElementException();
123+
ArrayList.this.remove(cursor--);
124+
}
125+
}
126+
127+
@Override
128+
public String toString() {
129+
StringBuilder sb = new StringBuilder("[ ");
130+
for (Object ele : elementData) {
131+
sb.append(ele).append(" ");
132+
}
133+
return sb.append("]").toString();
134+
}
135+
}

‎group17/785396327/list/Iterator.java

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
package list;
2+
3+
/**
4+
* Created by IBM on 2017/2/25.
5+
*/
6+
public interface Iterator<T> {
7+
8+
boolean hasNext();
9+
10+
T next();
11+
12+
void remove();
13+
}

0 commit comments

Comments
 (0)