Skip to content

Commit 9ad7f68

Browse files
yangdd1205yangdd1205
committed
basic data structure
1 parent d4a25d6 commit 9ad7f68

File tree

15 files changed

+1074
-0
lines changed

15 files changed

+1074
-0
lines changed

‎group18/1049843090/.classpath

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,10 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<classpath>
3+
<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER"/>
4+
<classpathentry kind="src" path="src"/>
5+
<classpathentry kind="src" path="test"/>
6+
<classpathentry kind="con" path="org.eclipse.jdt.junit.JUNIT_CONTAINER/.jar"/>
7+
<classpathentry kind="lib" path="lib/junit-4.12.jar"/>
8+
<classpathentry kind="lib" path="lib/hamcrest-core-1.3.jar"/>
9+
<classpathentry kind="output" path="out/production/1049843090"/>
10+
</classpath>

‎group18/1049843090/.gitignore

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
*.idea
2+
*.iml
3+
*.eml
4+
.settings/
5+
target/
6+
build/
7+
out/

‎group18/1049843090/.project

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

‎group18/1049843090/src/com/coding/basic/ArrayList.java

Lines changed: 148 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,148 @@
1+
package com.coding.basic;
2+
3+
import java.util.Arrays;
4+
5+
/**
6+
* A Simple ArrayList
7+
*/
8+
public class ArrayList<E> implements List<E> {
9+
10+
/**
11+
* 当前list的元素个数
12+
*/
13+
private int size;
14+
15+
/**
16+
* 默认数组大小
17+
*/
18+
private static final int DEFAULT_CAPACITY = 10;
19+
20+
/**
21+
* 存储元素的数组
22+
*/
23+
private Object[] elementData;
24+
25+
/**
26+
* 追加一个元素
27+
*
28+
* @param e
29+
*/
30+
public void add(E e) {
31+
grow();
32+
elementData[size++] = e;
33+
}
34+
35+
private void grow() {
36+
if (elementData.length == size) {
37+
elementData = Arrays.copyOf(elementData, size + 10);
38+
}
39+
}
40+
41+
/**
42+
* 插入一个元素到指定位置
43+
*
44+
* @param index
45+
* @param e
46+
*/
47+
public void add(int index, E e) {
48+
if (index < 0 || index > size) {
49+
throw new IndexOutOfBoundsException("下标越界");
50+
}
51+
grow();
52+
int movedNum = size - index;
53+
if (movedNum > 0) {
54+
System.arraycopy(elementData, index, elementData, index + 1, movedNum);
55+
}
56+
elementData[index] = e;
57+
size++;
58+
}
59+
60+
/**
61+
* 获取指定位置的元素
62+
*
63+
* @param index
64+
* @return
65+
*/
66+
public E get(int index) {
67+
checkIndex(index);
68+
return getElement(index);
69+
}
70+
71+
72+
/**
73+
* 删除指定位置的元素
74+
*
75+
* @param index
76+
* @return
77+
*/
78+
public E remove(int index) {
79+
checkIndex(index);
80+
E delEle = getElement(index);
81+
int movedNum = size - index - 1;//是不是最后一个元素
82+
if (movedNum > 0) {
83+
System.arraycopy(elementData, index + 1, elementData, index, movedNum);
84+
}
85+
elementData[--size] = null;
86+
return delEle;
87+
}
88+
89+
private void checkIndex(int index) {
90+
if (index < 0 || index >= size) {
91+
throw new IndexOutOfBoundsException("下标越界");
92+
}
93+
}
94+
95+
private E getElement(int index) {
96+
return (E) elementData[index];
97+
}
98+
99+
/**
100+
* list中元素的个数
101+
*
102+
* @return
103+
*/
104+
public int size() {
105+
return this.size;
106+
}
107+
108+
109+
public ArrayList() {
110+
this.elementData = new Object[DEFAULT_CAPACITY];
111+
}
112+
113+
public Iterator<E> iterator() {
114+
return new ArrayListIterator();
115+
}
116+
117+
private class ArrayListIterator<E> implements Iterator<E> {
118+
119+
private int cursor;//游标
120+
121+
private int lastRet = -1;//可被删除元素下标
122+
123+
124+
@Override
125+
public boolean hasNext() {
126+
return cursor != size;
127+
}
128+
129+
@Override
130+
public E next() {
131+
int i = cursor;
132+
cursor++;
133+
return (E) elementData[lastRet = i];
134+
}
135+
136+
@Override
137+
public void remove() {
138+
if (lastRet < 0) {
139+
throw new IllegalStateException();
140+
}
141+
cursor = lastRet;//游标等于当前删除元素的下标 或者 cursor--;
142+
ArrayList.this.remove(lastRet);
143+
lastRet = -1;//重置可删元素下标
144+
145+
}
146+
}
147+
148+
}

‎group18/1049843090/src/com/coding/basic/BinaryTree.java

Lines changed: 95 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,95 @@
1+
package com.coding.basic;
2+
3+
4+
/**
5+
*
6+
*/
7+
public class BinaryTree {
8+
9+
private Node root;
10+
11+
public boolean insert(int data) {
12+
Node newNode = new Node(data);
13+
if (root == null) {
14+
root = newNode;
15+
return true;
16+
}
17+
18+
return add(data);
19+
//return add(root,new Node(data));
20+
}
21+
22+
private boolean add(Node currentNode,Node newNode) {
23+
if (currentNode.data == newNode.data) {
24+
return false;
25+
}
26+
if (currentNode.data < newNode.data) {
27+
if (currentNode.right == null) {
28+
currentNode.right = newNode;
29+
return true;
30+
} else {
31+
return add(currentNode.right, newNode);
32+
}
33+
}
34+
if (currentNode.left == null) {
35+
currentNode.left = newNode;
36+
return true;
37+
} else {
38+
return add(currentNode.left, newNode);
39+
}
40+
}
41+
42+
private boolean add(int data) {
43+
Node newNode = new Node(data);
44+
boolean result = false;
45+
Node cursorNode = root;
46+
Node parentNode = null;
47+
while (true) {
48+
parentNode = cursorNode;
49+
if (cursorNode.data == data) {
50+
break;
51+
}
52+
if (cursorNode.data < data) {
53+
cursorNode = cursorNode.right;
54+
if (cursorNode == null) {
55+
parentNode.right = newNode;
56+
result = true;
57+
break;
58+
}
59+
} else {
60+
cursorNode = cursorNode.left;
61+
if (cursorNode == null) {
62+
parentNode.left = newNode;
63+
result = true;
64+
break;
65+
}
66+
}
67+
}
68+
return result;
69+
}
70+
71+
72+
private static class Node {
73+
int data;
74+
Node left, right;
75+
76+
public Node(int data) {
77+
this.data = data;
78+
this.left = null;
79+
this.right = null;
80+
}
81+
}
82+
83+
public static void main(String[] args) {
84+
BinaryTree binaryTree = new BinaryTree();
85+
binaryTree.insert(5);
86+
binaryTree.insert(6);
87+
binaryTree.insert(4);
88+
binaryTree.insert(8);
89+
binaryTree.insert(7);
90+
binaryTree.insert(3);
91+
92+
System.out.println("finsh");
93+
}
94+
95+
}

‎group18/1049843090/src/com/coding/basic/BinaryTreeNode.java

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
package com.coding.basic;
2+
3+
/**
4+
* Binary Tree
5+
*/
6+
public class BinaryTreeNode {
7+
8+
/**
9+
* 节点数据
10+
*/
11+
private Object data;
12+
/**
13+
* 左节点
14+
*/
15+
private BinaryTreeNode left;
16+
/**
17+
* 右节点
18+
*/
19+
private BinaryTreeNode right;
20+
21+
public Object getData() {
22+
return data;
23+
}
24+
25+
public void setData(Object data) {
26+
this.data = data;
27+
}
28+
29+
public BinaryTreeNode getLeft() {
30+
return left;
31+
}
32+
33+
public void setLeft(BinaryTreeNode left) {
34+
this.left = left;
35+
}
36+
37+
public BinaryTreeNode getRight() {
38+
return right;
39+
}
40+
41+
public void setRight(BinaryTreeNode right) {
42+
this.right = right;
43+
}
44+
45+
public BinaryTreeNode insert(Object o) {
46+
BinaryTreeNode newNode = new BinaryTreeNode(o);
47+
if ((int)data<(int)o) {
48+
this.right = newNode;
49+
} else {
50+
this.left = newNode;
51+
}
52+
return newNode;
53+
}
54+
55+
public BinaryTreeNode(Object o){
56+
this.setData(o);
57+
}
58+
59+
60+
61+
public static void main(String[] args) {
62+
BinaryTreeNode binaryTreeNode = new BinaryTreeNode(1);
63+
binaryTreeNode.insert(2);
64+
System.out.println(binaryTreeNode.getRight().getData());
65+
}
66+
67+
}

‎group18/1049843090/src/com/coding/basic/Iterator.java

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package com.coding.basic;
2+
3+
/**
4+
* Iterator
5+
*/
6+
public interface Iterator<E> {
7+
8+
/**
9+
* 可迭代对象是否还有值
10+
*
11+
* @return
12+
*/
13+
boolean hasNext();
14+
15+
/**
16+
* 返回迭代对象的下一个元素
17+
*
18+
* @return
19+
*/
20+
E next();
21+
22+
/**
23+
* 移除当前元素
24+
*/
25+
void remove();
26+
}

0 commit comments

Comments
 (0)