Skip to content

Commit bf7313a

Browse files
conf1102conf1102
authored
Merge pull request onlyliuxin#6 from honokaBiu/master
Sync
2 parents 358bed9 + 7436f62 commit bf7313a

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

63 files changed

+2697
-252
lines changed

‎group05/351592484/.gitignore

+9
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
/bin/
2+
*.class
3+
*.settings
4+
*.project
5+
*.classpath
6+
*/.settings
7+
*.iml
8+
/.idea
9+
/**/target/**/*

‎group05/351592484/src/com/github/zhanglifeng/coding2017/basic/ArrayList.java

+132
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,132 @@
1+
package com.github.zhanglifeng.coding2017.basic;
2+
3+
import java.util.*;
4+
5+
/**
6+
* 功能：实现ArrayList.
7+
* @author zhanglifeng.
8+
*/
9+
public class ArrayList implements List {
10+
private int size = 0; //当前数组大小
11+
12+
private Object[] elementData = new Object[5]; //初始数组
13+
14+
/**
15+
* 将对象o添加到ArrayList中.
16+
* @param o:需要添加的对象.
17+
*/
18+
public void add(Object o) {
19+
ensureCapacity(size + 1); //确保数组的容量可以装的下size + 1个元素，如果不够则扩容
20+
21+
elementData[size] = o; //将o添加到数组中
22+
size++; //数组大小增加1
23+
}
24+
25+
/**
26+
* 将对象o添加到ArrayList的指定位置.
27+
* @param index: 指定位置.
28+
* @param o: 需要添加的对象.
29+
*/
30+
public void add(int index, Object o) {
31+
rangeCheck(index); //判断指定的位置index是否合法
32+
33+
ensureCapacity(size + 1); //确保数组的容量可以装的下size + 1个元素，如果不够则扩容
34+
35+
System.arraycopy(elementData, index, elementData, index + 1, size - index); //将index位置到结束位置所有的数组往后移动一个位置
36+
elementData[index] = o; //将对象o添加到index位置
37+
size++;//数组大小增加1
38+
}
39+
40+
public Object get(int index) {
41+
rangeCheck(index);
42+
return elementData[index];
43+
}
44+
45+
public Object remove(int index) {
46+
rangeCheck(index);
47+
48+
if (index != elementData.length - 1) {
49+
System.arraycopy(elementData, index + 1, elementData, index, size - 1 - index);
50+
}
51+
52+
size--;
53+
return elementData;
54+
}
55+
56+
public int size() {
57+
return size;
58+
}
59+
60+
public Iterator iterator() {
61+
return new ArrayListIterator(this);
62+
}
63+
64+
private void ensureCapacity(int number) {
65+
if (number > elementData.length) {
66+
elementData = grow(elementData, 1);
67+
}
68+
}
69+
70+
public Object[] grow(Object[] src, int step) {
71+
Object[] target = new Object[src.length + step];
72+
System.arraycopy(src, 0, target, 0, src.length);
73+
return target;
74+
}
75+
76+
public void rangeCheck(int index){
77+
if (index > size || index < 0) {
78+
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
79+
}
80+
}
81+
82+
private class ArrayListIterator implements Iterator {
83+
ArrayList arrayList = null;
84+
int current = 0;
85+
86+
private ArrayListIterator(ArrayList arrayList) {
87+
this.arrayList = arrayList;
88+
}
89+
90+
@Override
91+
public boolean hasNext() {
92+
current++;
93+
return current > arrayList.size() ? false : true;
94+
}
95+
96+
@Override
97+
public Object next() {
98+
return elementData[current];
99+
}
100+
101+
}
102+
103+
public static void main(String[] args) {
104+
ArrayList arrayList = new ArrayList();
105+
arrayList.add("s1");
106+
arrayList.add("s2");
107+
arrayList.add("s3");
108+
arrayList.add("s4");
109+
arrayList.add(3, "s33");
110+
arrayList.add("s5");
111+
112+
System.out.println(arrayList.size());
113+
114+
System.out.println(arrayList.get(2));
115+
116+
arrayList.remove(3);
117+
118+
System.out.println(arrayList.size());
119+
120+
arrayList.add("s1");
121+
System.out.println(arrayList.size());
122+
arrayList.remove(5);
123+
System.out.println(arrayList.size());
124+
125+
Iterator it = arrayList.iterator();
126+
while(it.hasNext()){
127+
System.out.print(it.next() + " ");
128+
}
129+
System.out.println();
130+
}
131+
132+
}

‎group05/351592484/src/com/github/zhanglifeng/coding2017/basic/BinaryTreeNode.java

+37
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
package com.github.zhanglifeng.coding2017.basic;
2+
3+
public class BinaryTreeNode {
4+
private Object data;
5+
private BinaryTreeNode left;
6+
private BinaryTreeNode right;
7+
8+
public BinaryTreeNode(Object data) {
9+
this.data = data;
10+
left = null;
11+
right = null;
12+
}
13+
14+
public Object getData() {
15+
return this.data;
16+
}
17+
public void setData(Object data) {
18+
this.data = data;
19+
}
20+
public BinaryTreeNode getLeft() {
21+
return this.left;
22+
}
23+
public void setLeft(BinaryTreeNode left) {
24+
this.left = left;
25+
}
26+
public BinaryTreeNode getRight() {
27+
return this.right;
28+
}
29+
public void setRight(BinaryTreeNode right) {
30+
this.right = right;
31+
}
32+
33+
public BinaryTreeNode insert(Object o){
34+
return null;
35+
}
36+
37+
}

‎group05/351592484/src/com/github/zhanglifeng/coding2017/basic/Iterator.java

+7
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
package com.github.zhanglifeng.coding2017.basic;
2+
3+
public interface Iterator {
4+
public boolean hasNext();
5+
public Object next();
6+
7+
}

‎group05/351592484/src/com/github/zhanglifeng/coding2017/basic/LinkedList.java

+168
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,168 @@
1+
package com.github.zhanglifeng.coding2017.basic;
2+
3+
import java.util.NoSuchElementException;
4+
5+
/**
6+
* 功能：实现LinkedList.
7+
* @author zhanglifeng.
8+
*/
9+
public class LinkedList implements List {
10+
private Node head, tail;
11+
private int size;
12+
13+
private Node getNodeByIndex(int index) {
14+
if (index < 0 || index > size - 1) {
15+
throw new IndexOutOfBoundsException("线性表索引越界");
16+
}
17+
Node current = head;
18+
for (int i = 0; i < size && current != null; i++, current = current.next) {
19+
if (i == index) {
20+
return current;
21+
}
22+
}
23+
return null;
24+
}
25+
26+
public void add(Object o) {
27+
addLast(o);
28+
}
29+
30+
public void add(int index, Object o) {
31+
if (index < 0 || index > size) {
32+
throw new IndexOutOfBoundsException("线性表索引越界");
33+
}
34+
35+
if (0 == index) {
36+
addFirst(o);
37+
}else{
38+
Node node = getNodeByIndex(index - 1);
39+
node.next = new Node(o, node.next);
40+
size ++;
41+
}
42+
}
43+
44+
public Object get(int index) {
45+
return getNodeByIndex(index).data;
46+
}
47+
48+
public Object remove(int index) {
49+
if (index < 0 || index > size - 1) {
50+
throw new IndexOutOfBoundsException("线性表索引越界");
51+
}
52+
53+
if(0 == index){
54+
return removeFirst();
55+
}else if(size - 1 == index){
56+
return removeLast();
57+
}else{
58+
Node node = getNodeByIndex(index);
59+
Node preNode = getNodeByIndex(index - 1);
60+
preNode.next = node.next;
61+
size --;
62+
return node.data;
63+
}
64+
}
65+
66+
public int size() {
67+
return size;
68+
}
69+
70+
public void addFirst(Object o) {
71+
Node currentHead = head;
72+
Node newNode = new Node(o, currentHead);
73+
head = newNode;
74+
if(currentHead == null){
75+
tail = newNode;
76+
}
77+
78+
size++;
79+
}
80+
81+
public void addLast(Object o) {
82+
Node currentTail = tail;
83+
Node newNode = new Node(o, null);
84+
tail = newNode;
85+
if(currentTail == null){
86+
head = newNode;
87+
}else {
88+
currentTail.next = newNode;
89+
}
90+
size++;
91+
}
92+
93+
public Object removeFirst() {
94+
if(head == null){
95+
throw new NoSuchElementException();
96+
}
97+
Node node = new Node(head.data, null);
98+
head = head.next;
99+
size --;
100+
return node.data;
101+
}
102+
103+
public Object removeLast() {
104+
if(tail == null){
105+
throw new NoSuchElementException();
106+
}
107+
Node node = getNodeByIndex(size - 1);
108+
node.next = null;
109+
size --;
110+
return node.data;
111+
}
112+
113+
public Iterator iterator() {
114+
return new LinkedListIterator(this);
115+
}
116+
117+
private static class Node {
118+
Object data;
119+
Node next;
120+
121+
public Node(Object data, Node next) {
122+
this.data = data;
123+
this.next = next;
124+
}
125+
}
126+
127+
private class LinkedListIterator implements Iterator {
128+
LinkedList linkedList = null;
129+
private int current = 0;
130+
131+
public LinkedListIterator(LinkedList linkedList) {
132+
this.linkedList = linkedList;
133+
}
134+
135+
@Override
136+
public boolean hasNext() {
137+
return current < size;
138+
}
139+
140+
@Override
141+
public Object next() {
142+
return linkedList.get(current ++);
143+
}
144+
}
145+
146+
public static void main(String[] args) {
147+
LinkedList linkedList = new LinkedList();
148+
linkedList.add("s1");
149+
linkedList.add("s2");
150+
linkedList.add("s3");
151+
linkedList.addFirst("s0");
152+
linkedList.addLast("s4");
153+
154+
Iterator it = linkedList.iterator();
155+
while(it.hasNext()){
156+
System.out.print(it.next() + " ");
157+
}
158+
System.out.println();
159+
System.out.println("第3个元素：" + linkedList.get(3));
160+
161+
System.out.println(linkedList.removeFirst());
162+
System.out.println(linkedList.size());
163+
System.out.println("Last element:" + linkedList.removeLast());
164+
System.out.println(linkedList.size());
165+
System.out.println("第2个元素：" + linkedList.remove(2));
166+
System.out.println(linkedList.size());
167+
}
168+
}

‎group05/351592484/src/com/github/zhanglifeng/coding2017/basic/List.java

+9
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package com.github.zhanglifeng.coding2017.basic;
2+
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+
}

‎group05/351592484/src/com/github/zhanglifeng/coding2017/basic/Queue.java

+25
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package com.github.zhanglifeng.coding2017.basic;
2+
3+
import java.util.EmptyStackException;
4+
5+
public class Queue {
6+
private LinkedList elementData = new LinkedList();
7+
public void enQueue(Object o){
8+
elementData.add(o);
9+
}
10+
11+
public Object deQueue(){
12+
if (elementData.size() == 0) {
13+
throw new EmptyStackException();
14+
}
15+
return elementData.removeFirst();
16+
}
17+
18+
public boolean isEmpty(){
19+
return elementData.size() == 0;
20+
}
21+
22+
public int size(){
23+
return elementData.size();
24+
}
25+
}

0 commit comments

Comments
 (0)