Skip to content

Commit 7f7243d

Browse files
tchenjxtchenjx
committed
week01
1 parent 0e84a06 commit 7f7243d

File tree

8 files changed

+337
-0
lines changed

8 files changed

+337
-0
lines changed

‎group09/277123057/Week01/ArrayList.java

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
package Week01;
2+
/*
3+
* time:2017-2-20 21:51 created
4+
*
5+
*/
6+
public class ArrayList implements List{
7+
8+
private int size = 0;
9+
//开辟的空间只有100个
10+
private Object[] elementData = new Object[100];
11+
12+
//向末位插入
13+
public void add(Object o){
14+
elementData[size++] = o;
15+
}
16+
17+
//当前位置有元素，就向右移动当前位于该位置的元素及所有后续元素
18+
public void add(int index, Object o){
19+
System.arraycopy(elementData, index, elementData, index+1, size-index);
20+
elementData[index] = o;
21+
size++;
22+
}
23+
24+
public Object get(int index){
25+
return elementData[index];
26+
}
27+
//移除此链表上指定的元素,右边元素左移
28+
public Object remove(int index){
29+
int numMoved = size - index - 1;
30+
if (numMoved > 0)
31+
System.arraycopy(elementData, index+1, elementData, index, numMoved);
32+
elementData[--size] = null;
33+
return elementData[index];
34+
}
35+
36+
public int size(){
37+
return size;
38+
}
39+
40+
public Iterator iterator(){
41+
return new ArrayListIterator();
42+
}
43+
44+
private class ArrayListIterator implements Iterator{
45+
private int pos = 0;
46+
47+
public boolean hashNext() {
48+
return pos < size();
49+
}
50+
51+
public Object next() {
52+
return elementData[pos++];
53+
}
54+
}
55+
}

‎group09/277123057/Week01/BinaryTreeNode.java

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package Week01;
2+
//
3+
/*
4+
*»¹Ã»ÓÐÍê
5+
* */
6+
public class BinaryTreeNode {
7+
private Object data;
8+
private BinaryTreeNode left;
9+
private BinaryTreeNode right;
10+
11+
public Object getData(){
12+
return data;
13+
}
14+
15+
public void setData(Object data){
16+
this.data = data;
17+
}
18+
19+
public BinaryTreeNode getLeft() {
20+
return left;
21+
}
22+
23+
public void setLeft(BinaryTreeNode left){
24+
this.left = left;
25+
}
26+
}

‎group09/277123057/Week01/Iterator.java

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

‎group09/277123057/Week01/LinkedList.java

Lines changed: 173 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,173 @@
1+
package Week01;
2+
3+
import java.util.NoSuchElementException;
4+
5+
/*
6+
* time:2017-2-22 13:00
7+
* 参考：http://blog.csdn.net/jianyuerensheng/article/details/51204598
8+
* http://www.jianshu.com/p/681802a00cdf
9+
* jdk1.8源码
10+
* */
11+
12+
//这里采用的是双向链表，jdk1.6中linkedList基于双向循环链表实现
13+
public class LinkedList implements List {
14+
15+
private int size = 0;
16+
private Node first; //指向头结点
17+
private Node last; //指向尾节点
18+
19+
//在链表的end添加元素，调用自己的addLast()方法
20+
public void add(Object o){
21+
addLast(o);
22+
}
23+
24+
//加在index后面,这段代码参考同组同学 spike
25+
public void add(int index, Object o){
26+
if (index < 0 || index > size)
27+
throw new IllegalArgumentException();
28+
size++;
29+
if (index == size){
30+
addLast(o);
31+
}else{
32+
Node target = findIndex(index);
33+
Node newNode = new Node(o, target,target.next);
34+
if (last == target){
35+
last = newNode;
36+
}else{
37+
//target.next = newNode;这行要不要加
38+
target.next.prev = newNode;//有点疑问
39+
}
40+
}
41+
size++;
42+
}
43+
44+
public Object get(int index){
45+
if ( index < 0 || index > size){
46+
throw new IllegalArgumentException();
47+
}
48+
return findIndex(index).data;
49+
}
50+
//删除index指定的元素
51+
public Object remove(int index){
52+
if (index < 0 || index > size){
53+
throw new IllegalArgumentException();
54+
}
55+
56+
Node target = findIndex(index);
57+
if (target == first){
58+
first = first.next;
59+
first.prev = null;
60+
}else if(target == last){
61+
last = last.prev;
62+
last.next = null;
63+
}else{
64+
target.prev.next = target.next;
65+
target.next.prev = target.prev;
66+
}
67+
return target.data;
68+
}
69+
70+
public int size(){
71+
return size;
72+
}
73+
74+
public void addFirst(Object o){
75+
76+
Node f = first;
77+
Node newNode = new Node(o,null,f);
78+
first = newNode;
79+
if (f == null)
80+
last = newNode; //如果f为null，说明只有last可以指向
81+
else
82+
f.prev = newNode;
83+
size++;
84+
}
85+
86+
public void addLast(Object o){
87+
Node l = last;
88+
Node newNode = new Node(o, l, null);
89+
last = newNode;
90+
if (l == null)
91+
first = newNode;
92+
else
93+
l.next = newNode;
94+
size++;
95+
}
96+
97+
98+
public Object removeFirst() {
99+
if ( first == null)
100+
throw new NoSuchElementException();
101+
Node f = first;
102+
Object data = f.data;
103+
Node next = f.next;
104+
//去除的元素指为null
105+
f.data = null;
106+
f.next = null;
107+
first = next;
108+
if (next == null)
109+
last = null;
110+
else
111+
next.prev = null;
112+
size--;
113+
return data;
114+
}
115+
116+
public Object removeLast(){
117+
if (last == null)
118+
throw new NoSuchElementException();
119+
Node l = last;
120+
Object data = l.data;
121+
Node previous = l.prev;
122+
l.data = null;
123+
l.prev = null;
124+
last = previous;
125+
if (previous == null)
126+
first = null;
127+
else
128+
previous.next = null;
129+
size--;
130+
return data;
131+
}
132+
133+
public Iterator iterator(){
134+
return new LinkedListIterator();
135+
}
136+
137+
private class LinkedListIterator implements Iterator {
138+
Node curNode = first;
139+
public boolean hashNext() {
140+
return curNode != null;
141+
}
142+
public Object next() {
143+
if (!hashNext())
144+
throw new NoSuchElementException();
145+
Object data = curNode.data;
146+
curNode = curNode.next;
147+
return data;
148+
}
149+
}
150+
private Node findIndex(int index) {
151+
Node target = first;
152+
int i = 0;
153+
while(i < index){
154+
target = target.next;
155+
i++;
156+
}
157+
return target;
158+
}
159+
160+
//定义结点
161+
private static class Node{
162+
private Object data;
163+
//默认也是null
164+
private Node prev = null; //上一个元素节点
165+
private Node next = null;//下一个元素节点
166+
167+
public Node(Object data, Node pre, Node next){
168+
this.data = data;
169+
this.prev = pre;
170+
this.next = next;
171+
}
172+
}
173+
}

‎group09/277123057/Week01/List.java

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package Week01;
2+
//time:
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+
}

‎group09/277123057/Week01/Queue.java

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package Week01;
2+
/*
3+
* time:2017-2-25 13:46 created by Doen
4+
*
5+
* */
6+
public class Queue {
7+
private LinkedList elementData = new LinkedList();
8+
//½ø¶ÓÁÐ
9+
10+
public void enQueue(Object o){
11+
elementData.add(o);
12+
}
13+
14+
//³ö¶ÓÁÐ
15+
public Object deQueue(){
16+
if (isEmpty())
17+
throw new UnsupportedOperationException();
18+
return elementData.remove(0);
19+
}
20+
21+
public boolean isEmpty(){
22+
return elementData.size() == 0;
23+
}
24+
25+
public int size(){
26+
return elementData.size();
27+
}
28+
29+
}

‎group09/277123057/Week01/Stack.java

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
package Week01;
2+
3+
import java.util.NoSuchElementException;
4+
5+
/*
6+
* time:2017-2-25 13:19 created by Doen
7+
* change
8+
* */
9+
public class Stack {
10+
11+
private ArrayList elementData = new ArrayList();
12+
13+
public void push(Object o){
14+
elementData.add(o);
15+
}
16+
17+
public Object pop(){
18+
if (isEmpty())
19+
throw new NoSuchElementException();
20+
return elementData.remove(elementData.size()-1);
21+
}
22+
23+
public boolean isEmpty(){
24+
return elementData.size() == 0;
25+
}
26+
27+
public int size(){
28+
return elementData.size();
29+
}
30+
}

‎group09/277123057/Week01/Test.java

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package Week01;
2+
//time
3+
public class Test {
4+
public static void main(String[] args){
5+
ArrayList arraylist = new ArrayList();
6+
arraylist.add(1);
7+
arraylist.add("A");
8+
}
9+
}

0 commit comments

Comments
 (0)