Skip to content

Commit f8a1eb7

Browse files
haolipenghaolipeng
authored
Merge pull request onlyliuxin#11 from lulijie/master
Master
2 parents 067521b + c0fc221 commit f8a1eb7

File tree

14 files changed

+567
-0
lines changed

14 files changed

+567
-0
lines changed

‎group18/542330964/.classpath

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
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"/>
5+
<classpathentry kind="con" path="org.eclipse.jdt.junit.JUNIT_CONTAINER/4"/>
6+
<classpathentry kind="output" path="bin"/>
7+
</classpath>

‎group18/542330964/.gitignore

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

‎group18/542330964/.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>542330964learning</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>

‎group18/542330964/src/basicstruct/ArrayList.java

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
package basicstruct;
2+
3+
4+
5+
public class ArrayList implements List{
6+
7+
private int size = 0;
8+
9+
private Object[] elementData ;
10+
11+
private static final int DEFAULT_CAPACITY = 10;
12+
13+
public ArrayList() {
14+
elementData=new Object [DEFAULT_CAPACITY];
15+
}
16+
17+
public ArrayList(int initialCapacity) {
18+
if(initialCapacity>=0){
19+
elementData=new Object[initialCapacity];
20+
}else {
21+
throw new IllegalArgumentException("initialCapacity"+
22+
initialCapacity+"不能为负数");
23+
}
24+
}
25+
26+
public void add(Object o){
27+
ensureCapacity();
28+
elementData[size++] = o;
29+
}
30+
public void add(int index, Object o){
31+
if(index<0||index>size){
32+
throw new ArrayIndexOutOfBoundsException("index:"+index);
33+
}
34+
ensureCapacity();
35+
System.arraycopy(elementData, index, elementData, index + 1,size - index);
36+
elementData[index] = o;
37+
size++;
38+
}
39+
40+
private void rangeCheck(int index) {
41+
if(index<0||index>=size){
42+
throw new ArrayIndexOutOfBoundsException("index:"+index);
43+
}
44+
}
45+
private void ensureCapacity() {
46+
if(size == elementData.length) {
47+
Object[] newArray = new Object[size * 2 + 1];
48+
System.arraycopy(elementData, 0, newArray, 0, elementData.length);
49+
elementData = newArray;
50+
}
51+
}
52+
public Object get(int index){
53+
rangeCheck(index);
54+
return elementData[index];
55+
}
56+
57+
public Object remove(int index){
58+
rangeCheck(index);
59+
Object movedValue = elementData[index];
60+
//被删除元素后的元素数目
61+
int numMoved = size - index - 1;
62+
//后面有元素
63+
if (numMoved > 0){
64+
System.arraycopy(elementData, index+1, elementData, index,numMoved);
65+
}
66+
//恰为最后一个元素
67+
size--;
68+
elementData[size] = null; //垃圾回收
69+
return movedValue;
70+
}
71+
72+
public int size(){
73+
return size;
74+
}
75+
76+
public Iterator iterator(){
77+
return null;
78+
}
79+
80+
}

‎group18/542330964/src/basicstruct/BinaryTreeNode.java

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package basicstruct;
2+
public class BinaryTreeNode {
3+
4+
private Object data;
5+
private BinaryTreeNode left;
6+
private BinaryTreeNode right;
7+
8+
public Object getData() {
9+
return data;
10+
}
11+
public void setData(Object data) {
12+
this.data = data;
13+
}
14+
public BinaryTreeNode getLeft() {
15+
return left;
16+
}
17+
public void setLeft(BinaryTreeNode left) {
18+
this.left = left;
19+
}
20+
public BinaryTreeNode getRight() {
21+
return right;
22+
}
23+
public void setRight(BinaryTreeNode right) {
24+
this.right = right;
25+
}
26+
27+
public BinaryTreeNode insert(Object o){
28+
return null;
29+
}
30+
31+
}

‎group18/542330964/src/basicstruct/Iterator.java

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

‎group18/542330964/src/basicstruct/LinkedList.java

Lines changed: 175 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,175 @@
1+
package basicstruct;
2+
3+
import java.util.NoSuchElementException;
4+
5+
6+
public class LinkedList implements List {
7+
8+
private Node head;
9+
10+
private Node tail;
11+
12+
private int size=0;
13+
14+
public void add(Object o){
15+
addLast(o);
16+
}
17+
public void add(int index , Object o){
18+
if (index < 0 || index > size) {
19+
throw new IndexOutOfBoundsException("index: "+index);
20+
}
21+
if (index == size) {
22+
addLast(o);
23+
} else {
24+
Node temp = node(index);
25+
final Node pred = temp.previous;
26+
final Node newNode = new Node(o, temp, pred);
27+
temp.previous = newNode;
28+
if (pred == null){
29+
head = newNode;
30+
}
31+
else{
32+
pred.next = newNode;
33+
}
34+
size++;
35+
}
36+
}
37+
38+
public Node node(int index) {
39+
//二分法查找
40+
if (index < (size >> 1)) {
41+
Node temp = head;
42+
for (int i = 0; i < index; i++){
43+
temp = temp.next;
44+
}
45+
return temp;
46+
} else {
47+
Node temp = tail;
48+
for (int i = size - 1; i > index; i--){
49+
temp = temp.previous;
50+
}
51+
return temp;
52+
}
53+
}
54+
55+
public Object get(int index){
56+
if (index < 0 || index >=size) {
57+
throw new IndexOutOfBoundsException("index: "+index);
58+
}
59+
return node(index).data;
60+
}
61+
62+
public Object remove(int index){
63+
if (index < 0 || index >=size) {
64+
throw new IndexOutOfBoundsException("index: "+index);
65+
}
66+
return deleteElement(node(index));
67+
}
68+
69+
private Object deleteElement(Node node) {
70+
Object element = node.data;
71+
Node next = node.next;
72+
Node prev = node.previous;
73+
if (prev == null) {
74+
head = next;
75+
}else{
76+
prev.next = next;
77+
node.previous = null;
78+
}
79+
if(next == null) {
80+
tail = prev;
81+
}else {
82+
next.previous = prev;
83+
node.next = null;
84+
}
85+
node.data = null;
86+
size--;
87+
return element;
88+
}
89+
public int size(){
90+
return size;
91+
}
92+
93+
public void addFirst(Object o){
94+
Node h = head;
95+
Node newNode = new Node(o, h, null);
96+
head = newNode;
97+
if (h == null){
98+
tail = newNode;
99+
}else{
100+
h.previous = newNode;
101+
}
102+
size++;
103+
}
104+
105+
public void addLast(Object o){
106+
Node t = tail;
107+
Node node = new Node(o, null, t);
108+
tail = node;
109+
if (t == null) {
110+
head = node;
111+
} else {
112+
t.next = node;
113+
}
114+
size++;
115+
}
116+
117+
public Object removeFirst(){
118+
final Node h = head;
119+
if (h == null) {
120+
throw new NoSuchElementException("No such element");
121+
}
122+
final Object element = h.data;
123+
final Node next = h.next;
124+
h.data = null;
125+
h.next = null;
126+
head = next;
127+
if (next == null) {
128+
tail = null;
129+
} else {
130+
next.previous = null;
131+
}
132+
size--;
133+
return element;
134+
}
135+
136+
public Object removeLast(){
137+
Node t = tail;
138+
if (t == null){
139+
throw new NoSuchElementException("No such element");
140+
}
141+
final Object element = t.data;
142+
final Node prev = t.previous;
143+
t.data = null;
144+
t.previous = null;
145+
tail = prev;
146+
if (prev == null) {
147+
head = null;
148+
} else {
149+
prev.next = null;
150+
}
151+
size--;
152+
return element;
153+
}
154+
public boolean isEmpty(){
155+
return size==0;
156+
}
157+
public Iterator iterator(){
158+
return null;
159+
}
160+
161+
private static class Node{
162+
Object data;
163+
Node next;
164+
Node previous;
165+
public Node() {
166+
super();
167+
}
168+
public Node(Object data, Node next, Node previous) {
169+
super();
170+
this.data = data;
171+
this.next = next;
172+
this.previous = previous;
173+
}
174+
}
175+
}

‎group18/542330964/src/basicstruct/List.java

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

‎group18/542330964/src/basicstruct/Queue.java

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
package basicstruct;
2+
3+
public class Queue {
4+
5+
private LinkedList queue = new LinkedList();
6+
//进队列
7+
public void enQueue(Object o) {
8+
queue.addLast(o);
9+
}
10+
//出队列
11+
public Object deQueue() {
12+
return queue.removeFirst();
13+
}
14+
15+
public int size() {
16+
return queue.size();
17+
}
18+
19+
public boolean isEmpty() {
20+
return queue.isEmpty();
21+
}
22+
}

‎group18/542330964/src/basicstruct/Stack.java

Lines changed: 24 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
1+
package basicstruct;
2+
3+
public class Stack {
4+
5+
private ArrayList elementData = new ArrayList();
6+
7+
public void push(Object o){
8+
elementData.add(o);
9+
}
10+
//删除栈顶的值
11+
public Object pop(){
12+
return elementData.remove(elementData.size()-1);
13+
}
14+
//获取栈顶的值
15+
public Object peek(){
16+
return elementData.get(elementData.size()-1);
17+
}
18+
public boolean isEmpty(){
19+
return elementData.size()==0;
20+
}
21+
public int size(){
22+
return elementData.size();
23+
}
24+
}

0 commit comments

Comments
 (0)