Skip to content

Commit f3f4984

Browse files
AdministratorAdministrator
Administrator
authored and
Administrator
committed
第一周作业提交
1 parent d4a25d6 commit f3f4984

File tree

12 files changed

+755
-0
lines changed

12 files changed

+755
-0
lines changed

‎group02/1554421063/src/com/github/FelixCJF/coding2017/basic/ArrayList.java

Lines changed: 97 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,97 @@
1+
package com.github.FelixCJF.coding2017.basic;
2+
3+
import java.util.Arrays;
4+
5+
public class ArrayList implements List {
6+
7+
private int size = 0;
8+
9+
private Object[] elementData = new Object[100];
10+
11+
public void add(Object o){
12+
//容量增加
13+
ensureCapacity(size + 1);
14+
//添加
15+
elementData[size++] = o;
16+
}
17+
18+
public void add(int index, Object o){
19+
//容量增加
20+
ensureCapacity(size + 1);
21+
//临时变量
22+
Object[] elementData3 = new Object[size + 1];
23+
//将index前数据复制
24+
for (int i = 0; i < index + 1 ; i++) {
25+
elementData3[i] = elementData[i];
26+
}
27+
//插入的数据
28+
elementData3 [index + 1] = o;
29+
//插入数据之后的后半段复制
30+
for (int i = index + 2 ; i < elementData3.length; i++) {
31+
elementData3[i] = elementData[i-1];
32+
}
33+
elementData = elementData3;
34+
size++;
35+
}
36+
37+
public Object get(int index){
38+
if (index < 0 || index >= this.size) {
39+
throw new IndexOutOfBoundsException();
40+
}
41+
return elementData[index];
42+
}
43+
44+
public Object remove(int index){
45+
if (index < 0 || index >= this.size) {
46+
throw new IndexOutOfBoundsException();
47+
}
48+
Object oldValue = elementData[index];
49+
Object[] elementData4 = new Object[size - 1];
50+
for (int i = 0; i < index; i++) {
51+
elementData4[i] = elementData[i];
52+
}
53+
for (int i = index; i < elementData4.length; i++) {
54+
elementData4[i] = elementData[i + 1];
55+
}
56+
elementData = elementData4;
57+
size--;
58+
return oldValue;
59+
}
60+
61+
public int size(){
62+
return size;
63+
}
64+
65+
public Iterator iterator(){
66+
return new ArrayListIterator();
67+
}
68+
69+
//内部类，实现Iterator
70+
private class ArrayListIterator implements Iterator{
71+
72+
private int currentIndex = 0; //当前索引
73+
74+
public boolean hasNext() {
75+
if (currentIndex >= size) {
76+
return false;
77+
}
78+
return true;
79+
}
80+
81+
public Object next() {
82+
Object object = elementData[currentIndex];
83+
currentIndex ++ ;
84+
return object;
85+
}
86+
}
87+
public void ensureCapacity(int minCapacity) {
88+
int oldCapacity = elementData.length;
89+
if (minCapacity > oldCapacity) {
90+
int newCapacity = (oldCapacity * 3) / 2 + 1;
91+
if (newCapacity < minCapacity)
92+
newCapacity = minCapacity;
93+
elementData = Arrays.copyOf(elementData, newCapacity);
94+
}
95+
}
96+
97+
}

‎group02/1554421063/src/com/github/FelixCJF/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.FelixCJF.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/1554421063/src/com/github/FelixCJF/coding2017/basic/Iterator.java

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

‎group02/1554421063/src/com/github/FelixCJF/coding2017/basic/LinkedList.java

Lines changed: 214 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,214 @@
1+
package com.github.FelixCJF.coding2017.basic;
2+
3+
import java.util.NoSuchElementException;
4+
5+
public class LinkedList implements List {
6+
7+
private Node head;//头指针
8+
private Node last;//尾指针
9+
private int size = 0;
10+
11+
public void add(Object o){
12+
addLast(o);
13+
}
14+
15+
public void add(int index , Object o){
16+
//检查是否越界
17+
checkIndex(index);
18+
19+
Node indexNode = node(index);
20+
21+
if (index == size) {
22+
addLast(o);
23+
} else {
24+
final Node pred = indexNode.prv;
25+
26+
final Node newNode = new Node();
27+
newNode.data = o;
28+
newNode.next = indexNode;
29+
newNode.prv = pred;
30+
31+
indexNode.prv = newNode;
32+
33+
if (pred == null) {
34+
head = newNode;
35+
} else {
36+
pred.next = newNode;
37+
}
38+
}
39+
size ++;
40+
}
41+
public Object get(int index){
42+
//检查是否越界
43+
checkIndex(index);
44+
45+
Node indexNode = node(index);
46+
47+
return indexNode.data;
48+
}
49+
public Object remove(int index){
50+
//检查是否越界
51+
checkIndex(index);
52+
53+
Node indexNode = node(index);
54+
Object element = indexNode.data;
55+
Node pre = indexNode.prv;
56+
Node next = indexNode.next;
57+
58+
if (pre == null) {
59+
head = next;
60+
} else {
61+
pre.next = next;
62+
indexNode.prv = null;
63+
}
64+
65+
if (next == null) {
66+
last = pre;
67+
} else {
68+
next.prv = pre;
69+
indexNode.next = null;
70+
}
71+
72+
indexNode.data = null;
73+
74+
size --;
75+
76+
return element;
77+
}
78+
79+
public int size(){
80+
return size;
81+
}
82+
83+
public void addFirst(Object o){
84+
//节点变量存放原来的头指针
85+
final Node oldHead = head;
86+
//创建新的节点对象
87+
final Node newNode = new Node();
88+
newNode.data = o;
89+
newNode.next = head;
90+
newNode.prv = null;
91+
//判断oldhead是否为null
92+
if (oldHead == null) {
93+
last = newNode;
94+
}else {
95+
//头指针指向新创建的节点对象
96+
oldHead.prv = newNode;
97+
}
98+
//将newNode变为头指针
99+
head = newNode;
100+
size ++;
101+
}
102+
public void addLast(Object o){
103+
//节点新变量放原先的尾指针
104+
final Node oldLast = last;
105+
//创建新节点，加入要添加的对象
106+
final Node newNode = new Node();
107+
newNode.data = o;
108+
newNode.next = null;
109+
newNode.prv = oldLast;
110+
if (oldLast == null) {
111+
head = newNode;
112+
} else {
113+
//尾指针指向新创建的节点
114+
oldLast.next = newNode;
115+
}
116+
//newNode变为尾指针
117+
last = newNode;
118+
size++;
119+
}
120+
public Object removeFirst(){
121+
//通过头指针创建头节点
122+
final Node hNode = head;
123+
if (hNode == null) {
124+
throw new NoSuchElementException();
125+
}
126+
final Node next = hNode.next;
127+
final Object element = hNode.data;
128+
129+
//移除
130+
hNode.data = null;
131+
hNode.next = null;
132+
head = next;
133+
//判断是否为尾节点
134+
if (next == null) {
135+
last = null;
136+
}else {
137+
next.prv = null;
138+
}
139+
size --;
140+
return element;
141+
}
142+
public Object removeLast(){
143+
//通过尾指针创建节点
144+
final Node lastNode = last;
145+
if (lastNode == null) {
146+
throw new NoSuchElementException();
147+
}
148+
final Object element = lastNode.data;
149+
final Node prve = lastNode.prv;
150+
151+
//移除
152+
lastNode.data = null;
153+
lastNode.prv = null;
154+
last = prve;
155+
156+
if (prve == null) {
157+
head = null;
158+
} else {
159+
prve.next = null;
160+
}
161+
size --;
162+
return element;
163+
}
164+
public Iterator iterator(){
165+
return new LinkedListIterator();
166+
}
167+
168+
private class LinkedListIterator implements Iterator{
169+
170+
private Node currentNode = head;//当前节点
171+
172+
public boolean hasNext() {
173+
if (currentNode == null) {
174+
return false;
175+
}
176+
return true;
177+
}
178+
179+
public Object next() {
180+
Object element = currentNode.data;
181+
currentNode = currentNode.next;
182+
return element;
183+
}
184+
185+
}
186+
187+
//查找index节点,并返回该节点
188+
Node node(int index) {
189+
// assert isElementIndex(index);
190+
191+
if (index < (size >> 1)) {
192+
Node x = head;
193+
for (int i = 0; i < index; i++)
194+
x = x.next;
195+
return x;
196+
} else {
197+
Node x = last;
198+
for (int i = size - 1; i > index; i--)
199+
x = x.prv;
200+
return x;
201+
}
202+
}
203+
//检查索引
204+
private void checkIndex(int index){
205+
if (index < 0 || index > size) {
206+
throw new IndexOutOfBoundsException();
207+
}
208+
}
209+
private static class Node{
210+
Object data;
211+
Node next;
212+
Node prv;
213+
}
214+
}

‎group02/1554421063/src/com/github/FelixCJF/coding2017/basic/List.java

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

0 commit comments

Comments
 (0)