Skip to content

Commit dea377e

Browse files
gabywonggabywong
committed
version v1.0
2.26前需要提交的作业 实现List，Stack，Queue
1 parent d4a25d6 commit dea377e

File tree

11 files changed

+468
-0
lines changed

11 files changed

+468
-0
lines changed

‎group15/1513_121469918/HomeWork01/.classpath

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<classpath>
3+
<classpathentry kind="src" path="src"/>
4+
<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER/org.eclipse.jdt.internal.debug.ui.launcher.StandardVMType/JavaSE-1.7"/>
5+
<classpathentry kind="output" path="bin"/>
6+
</classpath>

‎group15/1513_121469918/HomeWork01/.gitignore

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

‎group15/1513_121469918/HomeWork01/.project

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<projectDescription>
3+
<name>HomeWork01</name>
4+
<comment></comment>
5+
<projects>
6+
</projects>
7+
<buildSpec>
8+
<buildCommand>
9+
<name>org.eclipse.jdt.core.javabuilder</name>
10+
<arguments>
11+
</arguments>
12+
</buildCommand>
13+
</buildSpec>
14+
<natures>
15+
<nature>org.eclipse.jdt.core.javanature</nature>
16+
</natures>
17+
</projectDescription>

‎group15/1513_121469918/HomeWork01/.settings/org.eclipse.jdt.core.prefs

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
eclipse.preferences.version=1
2+
org.eclipse.jdt.core.compiler.codegen.inlineJsrBytecode=enabled
3+
org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.7
4+
org.eclipse.jdt.core.compiler.codegen.unusedLocal=preserve
5+
org.eclipse.jdt.core.compiler.compliance=1.7
6+
org.eclipse.jdt.core.compiler.debug.lineNumber=generate
7+
org.eclipse.jdt.core.compiler.debug.localVariable=generate
8+
org.eclipse.jdt.core.compiler.debug.sourceFile=generate
9+
org.eclipse.jdt.core.compiler.problem.assertIdentifier=error
10+
org.eclipse.jdt.core.compiler.problem.enumIdentifier=error
11+
org.eclipse.jdt.core.compiler.source=1.7

‎group15/1513_121469918/HomeWork01/src/coding/ArrayList.java

Lines changed: 118 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,118 @@
1+
package coding;
2+
3+
import java.util.NoSuchElementException;
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+
int len = size + 1;
13+
// 判断list的长度是否大于容器长度
14+
if (len > elementData.length) {
15+
// 创建新容器
16+
Object[] newElemDate = new Object[elementData.length + 1];
17+
// 复制旧容器所有元素到新容器
18+
System.arraycopy(elementData, 0, newElemDate, 0, elementData.length);
19+
elementData = newElemDate;
20+
}
21+
elementData[size] = o;
22+
size++;
23+
}
24+
25+
public void add(int index, Object o) {
26+
// 检查是否越界
27+
if (index < 0 || index > size) {
28+
throw new IndexOutOfBoundsException("index:" + index + "size:" + size);
29+
}
30+
// 插入元素到末尾直接调用add方法
31+
if (index == size) {
32+
add(o);
33+
} else {
34+
// 创建新容器
35+
Object[] newElemData = new Object[elementData.length + 1];
36+
// 复制index以前的所有元素到新容器
37+
System.arraycopy(elementData, 0, newElemData, 0, index);
38+
newElemData[index] = o;
39+
// 复制index 及以后的元素到新容器
40+
System.arraycopy(elementData, index, newElemData, index + 1, size - index);
41+
42+
elementData = newElemData;
43+
size++;
44+
}
45+
}
46+
47+
public Object get(int index) {
48+
if (index < 0 || index >= size) {
49+
throw new IndexOutOfBoundsException("index:" + index + "size:" + size);
50+
}
51+
return elementData[index];
52+
}
53+
54+
public Object remove(int index) {
55+
if (index >= size) {
56+
throw new IndexOutOfBoundsException("index:" + index + "size:" + size);
57+
}
58+
Object removeElement = elementData[index];
59+
//不是最后一个元素的索引值才需要操作
60+
if(index != (size-1)){
61+
// 创建新容器
62+
Object[] newElemData = new Object[elementData.length];
63+
// 复制index以前的所有元素到新容器
64+
System.arraycopy(elementData, 0, newElemData, 0, index);
65+
// 复制index 以后的元素到新容器
66+
System.arraycopy(elementData, index+1, newElemData, index, size - index -1);
67+
}
68+
//最后一个元素的索引值直接减短list长度
69+
size--;
70+
return removeElement;
71+
}
72+
73+
public int size() {
74+
return size;
75+
}
76+
77+
public Iterator iterator() {
78+
return new MyIterator(this);
79+
}
80+
81+
private class MyIterator implements Iterator {
82+
private int poi = -1;
83+
private ArrayList array = null;
84+
85+
private MyIterator(ArrayList array) {
86+
this.array = array;
87+
}
88+
89+
@Override
90+
public boolean hasNext() {
91+
return (poi + 1) < array.size;
92+
}
93+
94+
@Override
95+
public Object next() {
96+
// TODO Auto-generated method stub
97+
poi++;
98+
if (poi >= array.size) {
99+
poi--;
100+
throw new IndexOutOfBoundsException();
101+
}
102+
103+
return array.get(poi);
104+
}
105+
106+
@Override
107+
public Object remove() {
108+
// TODO Auto-generated method stub
109+
if (poi < 0) {
110+
throw new NoSuchElementException();
111+
}
112+
Object val = array.remove(poi);
113+
poi--;
114+
return val;
115+
}
116+
117+
}
118+
}

‎group15/1513_121469918/HomeWork01/src/coding/BinaryTreeNode.java

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
package coding;
2+
3+
public class BinaryTreeNode {
4+
private Object data;
5+
private BinaryTreeNode left;
6+
private BinaryTreeNode right;
7+
8+
public Object getData() {
9+
return data;
10+
}
11+
12+
public void setData(Object data) {
13+
this.data = data;
14+
}
15+
16+
public BinaryTreeNode getLeft() {
17+
return left;
18+
}
19+
20+
public void setLeft(BinaryTreeNode left) {
21+
this.left = left;
22+
}
23+
24+
public BinaryTreeNode getRight() {
25+
return right;
26+
}
27+
28+
public void setRight(BinaryTreeNode right) {
29+
this.right = right;
30+
}
31+
32+
public BinaryTreeNode insert(Object o) {
33+
// 判断当前节点有无元素
34+
if (data == null) {
35+
setData(o);
36+
} else {
37+
Integer i = (Integer) o;
38+
// 当前节点有数据则判断左右节点
39+
if (i.compareTo((Integer) data) == -1) {
40+
if(right == null)
41+
right = new BinaryTreeNode();
42+
return right.insert(i);
43+
} else if (i.compareTo((Integer) data) == 1) {
44+
if(left == null)
45+
left = new BinaryTreeNode();
46+
return left.insert(i);
47+
}
48+
return null;
49+
}
50+
return null;
51+
}
52+
53+
}

‎group15/1513_121469918/HomeWork01/src/coding/Iterator.java

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

‎group15/1513_121469918/HomeWork01/src/coding/LinkedList.java

Lines changed: 170 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,170 @@
1+
package coding;
2+
3+
import java.util.NoSuchElementException;
4+
5+
public class LinkedList implements List {
6+
private Node head;
7+
private int size;
8+
9+
public void add(Object o) {
10+
// 判断头是否有数据
11+
if (head == null) {
12+
head = new Node(o, null);
13+
} else {
14+
Node newNode = head;
15+
while (newNode.next != null) {
16+
newNode = newNode.next;
17+
}
18+
newNode.next = new Node(o, null);
19+
}
20+
size++;
21+
}
22+
23+
public void add(int index, Object o) {
24+
if (index < 0 || index > size) {
25+
throw new IndexOutOfBoundsException("index:" + index + "size:" + size);
26+
}
27+
Node node = head;
28+
if (index != 0) {
29+
// 不是第一个索引值就找到索引值的前面一个节点
30+
for (int i = 1; i < index; i++) {
31+
node = node.next;
32+
}
33+
Node newNode = new Node(o, node.next);
34+
node.next = newNode;
35+
size++;
36+
} else {
37+
// 第一个索引值就将头节点指向它
38+
Node newNode = new Node(o, head);
39+
head = newNode;
40+
size++;
41+
}
42+
}
43+
44+
public Object get(int index) {
45+
indexCheck(index);
46+
Node node = head;
47+
for (int i = 1; i <= index; i++) {
48+
node = node.next;
49+
}
50+
return node.data;
51+
}
52+
53+
public Object remove(int index) {
54+
indexCheck(index);
55+
56+
Node node = head;
57+
Node removeNode;
58+
if (index == 0) {
59+
//删除第一个节点就把头节点指向原本的第二个节点
60+
removeNode = head;
61+
head = head.next;
62+
} else {
63+
//找到索引值的前一个节点
64+
for (int i = 1; i < index; i++) {
65+
node = node.next;
66+
}
67+
removeNode = node.next;
68+
//前一个节点指针，指向被删除节点所指向的节点
69+
node.next = removeNode.next;
70+
}
71+
size--;
72+
return removeNode.data;
73+
}
74+
75+
public int size() {
76+
return size;
77+
}
78+
79+
public void addFirst(Object o) {
80+
Node newNode = new Node(o, head.next);
81+
head.next = newNode;
82+
size++;
83+
}
84+
85+
public void addLast(Object o) {
86+
add(o);
87+
}
88+
89+
public Object removeFirst() {
90+
//没有元素就抛异常
91+
if (size <= 0) {
92+
throw new IndexOutOfBoundsException("size:" + size);
93+
}
94+
Object val = head.data;
95+
head = head.next;
96+
size--;
97+
return val;
98+
}
99+
100+
public Object removeLast() {
101+
if (size <= 0) {
102+
throw new IndexOutOfBoundsException("size:" + size);
103+
}
104+
Node node = head;
105+
while (node.next != null) {
106+
node = node.next;
107+
}
108+
Object val = node.data;
109+
node = null;
110+
size--;
111+
return val;
112+
}
113+
114+
public Iterator iterator() {
115+
return new MyIterator(this);
116+
}
117+
118+
private class MyIterator implements Iterator{
119+
private int poi = -1;
120+
private LinkedList list ;
121+
private MyIterator(LinkedList list) {
122+
this.list= list;
123+
}
124+
@Override
125+
public boolean hasNext() {
126+
// TODO Auto-generated method stub
127+
return (poi + 1) < list.size;
128+
}
129+
130+
@Override
131+
public Object next() {
132+
// TODO Auto-generated method stub
133+
poi++;
134+
if (poi >= list.size) {
135+
poi--;
136+
throw new IndexOutOfBoundsException();
137+
}
138+
139+
return list.get(poi);
140+
}
141+
142+
@Override
143+
public Object remove() {
144+
// TODO Auto-generated method stub
145+
if (poi < 0) {
146+
throw new NoSuchElementException();
147+
}
148+
Object val = list.removeLast();
149+
poi--;
150+
return val;
151+
}
152+
153+
}
154+
155+
private void indexCheck(int index) {
156+
if (index < 0 || index >= size) {
157+
throw new IndexOutOfBoundsException("index:" + index + "size:" + size);
158+
}
159+
}
160+
161+
private static class Node {
162+
Object data;
163+
Node next;
164+
165+
Node(Object data, Node next) {
166+
this.data = data;
167+
this.next = next;
168+
}
169+
}
170+
}

0 commit comments

Comments
 (0)