Skip to content

Commit 19eb0d2

Browse files
huaerhlyhuaerhly
committed
基本数据结构实现
1 parent 7e634ec commit 19eb0d2

17 files changed

+816
-0
lines changed

‎group01/932573198/20170220/.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/org.eclipse.jdt.internal.debug.ui.launcher.StandardVMType/JavaSE-1.8"/>
5+
<classpathentry kind="con" path="org.eclipse.jdt.junit.JUNIT_CONTAINER/4"/>
6+
<classpathentry kind="output" path="bin"/>
7+
</classpath>

‎group01/932573198/20170220/.gitignore

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

‎group01/932573198/20170220/.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>20170220</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>

‎group01/932573198/20170220/.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.8
4+
org.eclipse.jdt.core.compiler.codegen.unusedLocal=preserve
5+
org.eclipse.jdt.core.compiler.compliance=1.8
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.8

‎group01/932573198/20170220/src/com/coding/basic/ArrayList.java

Lines changed: 92 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,92 @@
1+
package com.coding.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[10];
10+
11+
/**
12+
* 扩容
13+
*/
14+
private void expansion() {
15+
if (elementData.length <= size)
16+
elementData = Arrays.copyOf(elementData, elementData.length * 3 / 2 + 1);
17+
}
18+
19+
/**
20+
* 越界
21+
*/
22+
private void outOfBoundsForAdd(int index) {
23+
if (index > size || index < 0)
24+
throw new IndexOutOfBoundsException("数组下标越界");
25+
}
26+
27+
private void outOfBoundsForOther(int index) {
28+
if (index >= size || index < 0)
29+
throw new IndexOutOfBoundsException("数组下标越界");
30+
}
31+
32+
public void add(Object o) {
33+
expansion();
34+
elementData[size++] = o;
35+
}
36+
37+
public void add(int index, Object o) {
38+
outOfBoundsForAdd(index);
39+
expansion();
40+
for (int i = size - 1; i >= index; i--) {
41+
elementData[i + 1] = elementData[i];
42+
}
43+
elementData[index] = o;
44+
size++;
45+
}
46+
47+
public Object get(int index) {
48+
outOfBoundsForOther(index);
49+
return elementData[index];
50+
}
51+
52+
public Object remove(int index) {
53+
outOfBoundsForOther(index);
54+
Object re = elementData[index];
55+
for (int i = index; i < size - 1; i++) {
56+
elementData[i] = elementData[i + 1];
57+
}
58+
elementData[size - 1] = null;
59+
size--;
60+
return re;
61+
}
62+
63+
public int size() {
64+
return size;
65+
}
66+
67+
@Override
68+
public String toString() {
69+
return Arrays.toString(elementData);
70+
}
71+
72+
public Iterator iterator() {
73+
return new ArrayIterator();
74+
}
75+
76+
private class ArrayIterator implements Iterator {
77+
78+
int pos = -1;
79+
80+
@Override
81+
public boolean hasNext() {
82+
return size > ++pos ? true : false;
83+
}
84+
85+
@Override
86+
public Object next() {
87+
return elementData[pos];
88+
}
89+
90+
}
91+
92+
}

‎group01/932573198/20170220/src/com/coding/basic/BinaryTree.java

Lines changed: 77 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,77 @@
1+
package com.coding.basic;
2+
3+
public class BinaryTree {
4+
5+
private BinaryTreeNode tNode;
6+
7+
@Override
8+
public String toString() {
9+
return tNode + "";
10+
}
11+
12+
public void insert(Object o) {
13+
tNode = insert(o, tNode);
14+
}
15+
16+
public BinaryTreeNode insert(Object o, BinaryTreeNode node) {
17+
if (node == null) {
18+
node = new BinaryTreeNode(o);
19+
} else {
20+
int result = o.toString().compareTo(node.getData().toString());
21+
if (result < 0)
22+
node.setLeft(insert(o, node.getLeft()));
23+
if (result > 0)
24+
node.setRight(insert(o, node.getRight()));
25+
}
26+
return node;
27+
}
28+
29+
private static class BinaryTreeNode {
30+
31+
private BinaryTreeNode left;
32+
33+
private Object data;
34+
35+
private BinaryTreeNode right;
36+
37+
public BinaryTreeNode() {
38+
}
39+
40+
public BinaryTreeNode(Object data) {
41+
this.left = null;
42+
this.data = data;
43+
this.right = null;
44+
}
45+
46+
public BinaryTreeNode getLeft() {
47+
return left;
48+
}
49+
50+
public void setLeft(BinaryTreeNode left) {
51+
this.left = left;
52+
}
53+
54+
public Object getData() {
55+
return data;
56+
}
57+
58+
public void setData(Object data) {
59+
this.data = data;
60+
}
61+
62+
public BinaryTreeNode getRight() {
63+
return right;
64+
}
65+
66+
public void setRight(BinaryTreeNode right) {
67+
this.right = right;
68+
}
69+
70+
@Override
71+
public String toString() {
72+
return "[" + left + ", " + data + ", " + right + "]";
73+
}
74+
75+
}
76+
77+
}

‎group01/932573198/20170220/src/com/coding/basic/Iterator.java

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

‎group01/932573198/20170220/src/com/coding/basic/LinkedList.java

Lines changed: 144 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,144 @@
1+
package com.coding.basic;
2+
3+
import java.util.NoSuchElementException;
4+
5+
public class LinkedList implements List {
6+
7+
private int size = 0;
8+
9+
private Node head;
10+
11+
12+
public Node getHead() {
13+
return head;
14+
}
15+
16+
public LinkedList() {
17+
this.head = new Node();
18+
}
19+
20+
@Override
21+
public String toString() {
22+
return "[" + head + "]";
23+
}
24+
25+
private void outOfBoundsForAdd(int index) {
26+
if (index > size || index < 0)
27+
throw new IndexOutOfBoundsException("数组下标越界");
28+
}
29+
30+
private void outOfBoundsForOther(int index) {
31+
if (index >= size || index < 0)
32+
throw new IndexOutOfBoundsException("数组下标越界");
33+
}
34+
35+
public void add(Object o) {
36+
Node node = head;
37+
while (node.next != null) {
38+
node = node.next;
39+
}
40+
node.next = new Node(o);
41+
size++;
42+
}
43+
44+
public void add(int index, Object o) {
45+
outOfBoundsForAdd(index);
46+
if(size == index)
47+
add(o);
48+
else{
49+
Node prevNode = head;
50+
for (int i = 0; i < index; i++) {
51+
prevNode = prevNode.next;
52+
}
53+
Node nextNode = prevNode.next;
54+
Node node = new Node(o);
55+
prevNode.next = node;
56+
node.next = nextNode;
57+
size++;
58+
}
59+
}
60+
61+
public Object get(int index) {
62+
outOfBoundsForOther(index);
63+
Node node = head;
64+
for (int i = 0; i <= index; i++) {
65+
node = node.next;
66+
}
67+
return node.data;
68+
}
69+
70+
public Object remove(int index) {
71+
outOfBoundsForOther(index);
72+
Node prevNode = head;
73+
for (int i = 0; i < index; i++) {
74+
prevNode = prevNode.next;
75+
}
76+
Node node = prevNode.next;
77+
prevNode.next = node.next;
78+
size--;
79+
return node.data;
80+
}
81+
82+
public int size() {
83+
return size;
84+
}
85+
86+
public void addFirst(Object o) {
87+
Node newNode = new Node(o);
88+
Node node = head.next;
89+
head.next = newNode;
90+
newNode.next = node;
91+
size++;
92+
}
93+
94+
public void addLast(Object o) {
95+
Node node = head;
96+
while (node.next != null) {
97+
node = node.next;
98+
}
99+
node.next = new Node(o);
100+
size++;
101+
}
102+
103+
private void noSuchEle() {
104+
if (head.next == null)
105+
throw new NoSuchElementException("没有这个元素");
106+
}
107+
108+
public Object removeFirst() {
109+
noSuchEle();
110+
Node node = head.next;
111+
head.next = node.next;
112+
size--;
113+
return node.data;
114+
}
115+
116+
public Object removeLast() {
117+
noSuchEle();
118+
Node node = head;
119+
for(int i=0;i<size-1;i++){
120+
node = node.next;
121+
}
122+
Node reNode = node.next;
123+
node.next = null;
124+
size--;
125+
return reNode.data;
126+
}
127+
128+
public static class Node {
129+
Object data;
130+
Node next;
131+
132+
@Override
133+
public String toString() {
134+
return data + ", " + next;
135+
}
136+
137+
public Node() {
138+
}
139+
140+
public Node(Object data) {
141+
this.data = data;
142+
}
143+
}
144+
}

‎group01/932573198/20170220/src/com/coding/basic/List.java

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package com.coding.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+
}

0 commit comments

Comments
 (0)