Skip to content

Commit 7dfc9d3

Browse files
nusubmarine01nusubmarine01
authored
Merge pull request onlyliuxin#15 from cmhello88/master
basic data structure
2 parents bf45542 + 70235df commit 7dfc9d3

File tree

12 files changed

+625
-0
lines changed

12 files changed

+625
-0
lines changed

‎group03/345943980/2017Learning/src/com/coding/basic/ArrayList.java

Lines changed: 91 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,91 @@
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+
* (non-Javadoc)
13+
*
14+
* @see com.coding.basic.List#add(java.lang.Object)
15+
*/
16+
public void add(Object o) {
17+
if (size > elementData.length) { // size大于数组初始长度，需要对原数组进行扩容
18+
grow(elementData, 10);
19+
}
20+
this.elementData[size++] = o;
21+
}
22+
23+
/*
24+
* 在指定下标位置插入元素 (non-Javadoc)
25+
*
26+
* @see com.coding.basic.List#add(int, java.lang.Object)
27+
*/
28+
public void add(int index, Object o) {
29+
if (size > elementData.length) { // size大于数组初始长度，需要对原数组进行扩容
30+
grow(elementData, 10);
31+
}
32+
if (index > size || index < 0)
33+
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
34+
System.arraycopy(elementData, index, elementData, index + 1, size - index);
35+
elementData[index] = o;
36+
size++;
37+
}
38+
39+
public Object get(int index) {
40+
// 1、先要判断index所在处有无值，没有则返回null
41+
Object o = elementData[index];
42+
if (null == o)
43+
throw new IndexOutOfBoundsException();
44+
return o;
45+
}
46+
47+
public Object remove(int index) {
48+
Object oldVal = elementData[index]; // 保留要删除的元素
49+
int numMoved = size - index - 1;
50+
if (numMoved > 0) {
51+
System.arraycopy(elementData, index + 1, elementData, index, numMoved);// 讲移除位置之后的元素向前 挪动
52+
}
53+
elementData[--size] = null; // 将数组末尾元素置为空
54+
return oldVal;
55+
}
56+
57+
/**
58+
* 获取数组元素个数
59+
*/
60+
public int size() {
61+
return this.size;
62+
}
63+
64+
public Object[] grow(Object[] src, int size) {
65+
// Arrays.copyOf(src, src.length+size);
66+
Object[] target = new Object[src.length + size];
67+
System.arraycopy(src, 0, target, 0, src.length);
68+
return target;
69+
}
70+
71+
public Iterator iterator() {
72+
73+
return new ArrayListIterator();
74+
}
75+
76+
private class ArrayListIterator implements Iterator {
77+
78+
private int cursor=0;
79+
@Override
80+
public boolean hasNext() {
81+
return size != cursor;
82+
}
83+
84+
@Override
85+
public Object next() {
86+
return elementData[cursor++];
87+
}
88+
89+
}
90+
91+
}

‎group03/345943980/2017Learning/src/com/coding/basic/BinaryTree.java

Lines changed: 132 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,132 @@
1+
package com.coding.basic;
2+
3+
/**
4+
* 二叉树
5+
*
6+
* @author cm
7+
*/
8+
public class BinaryTree {
9+
10+
private BinaryTreeNode root;
11+
12+
public BinaryTreeNode insert(Object o) {
13+
BinaryTreeNode binaryTreeNode = new BinaryTreeNode(o);
14+
if (null == root) {
15+
root = new BinaryTreeNode(o);
16+
} else {
17+
boolean flag = false;
18+
BinaryTreeNode cursorNode = root;
19+
while (!flag) {
20+
if (binaryTreeNode.compareTo(cursorNode) < 0) {
21+
if (cursorNode.getLeft() == null) {
22+
cursorNode.setLeft(binaryTreeNode);
23+
flag = true;
24+
} else {
25+
cursorNode = cursorNode.getLeft();
26+
}
27+
} else {
28+
if (cursorNode.getRight() == null) {
29+
cursorNode.setRight(binaryTreeNode);
30+
flag = true;
31+
} else {
32+
cursorNode = cursorNode.getRight();
33+
}
34+
}
35+
}
36+
}
37+
return binaryTreeNode;
38+
}
39+
40+
public LinkedList inOrder() {
41+
LinkedList linkedList = new LinkedList();
42+
sortLeft(linkedList, root);
43+
sortRight(linkedList, root);
44+
return linkedList;
45+
}
46+
47+
private void sortRight(LinkedList linkedList, BinaryTreeNode binaryTreeNode) {
48+
Queue queue = getRightList(binaryTreeNode);
49+
while (!queue.isEmpty()) {
50+
BinaryTreeNode queueNode = (BinaryTreeNode) queue.deQueue();
51+
sortLeft(linkedList, queueNode);
52+
}
53+
}
54+
55+
private void sortLeft(LinkedList linkedList, BinaryTreeNode binaryTreeNode) {
56+
Stack stack = getLeftList(binaryTreeNode);
57+
while (!stack.isEmpty()) {
58+
BinaryTreeNode stackNode = (BinaryTreeNode) stack.pop();
59+
linkedList.add(stackNode.getData());
60+
Queue queue = getRightList(stackNode);
61+
while (!queue.isEmpty()) {
62+
BinaryTreeNode queueNode = (BinaryTreeNode) queue.deQueue();
63+
sortLeft(linkedList, queueNode);
64+
}
65+
}
66+
linkedList.add(binaryTreeNode.getData());
67+
}
68+
69+
private Stack getLeftList(BinaryTreeNode binaryTreeNode) {
70+
Stack stack = new Stack();
71+
while (binaryTreeNode.getLeft() != null) {
72+
binaryTreeNode = binaryTreeNode.getLeft();
73+
stack.push(binaryTreeNode);
74+
}
75+
return stack;
76+
}
77+
78+
private Queue getRightList(BinaryTreeNode binaryTreeNode) {
79+
Queue queue = new Queue();
80+
while (binaryTreeNode.getRight() != null) {
81+
binaryTreeNode = binaryTreeNode.getRight();
82+
queue.enQueue(binaryTreeNode);
83+
}
84+
return queue;
85+
}
86+
87+
private class BinaryTreeNode implements Comparable<BinaryTreeNode> {
88+
private Object data;
89+
private BinaryTreeNode left;
90+
private BinaryTreeNode right;
91+
92+
public Object getData() {
93+
return data;
94+
}
95+
96+
public void setData(Object data) {
97+
this.data = data;
98+
}
99+
100+
public BinaryTreeNode getLeft() {
101+
return left;
102+
}
103+
104+
public void setLeft(BinaryTreeNode left) {
105+
this.left = left;
106+
}
107+
108+
public BinaryTreeNode getRight() {
109+
return right;
110+
}
111+
112+
public void setRight(BinaryTreeNode right) {
113+
this.right = right;
114+
}
115+
116+
public BinaryTreeNode(Object o) {
117+
setData(o);
118+
}
119+
120+
@Override
121+
public int compareTo(BinaryTreeNode binaryTreeNode) {
122+
Integer currVal = (Integer) root.getData();
123+
Integer compVal = (Integer) binaryTreeNode.getData();
124+
if (currVal < compVal)
125+
return -1;
126+
else if (currVal == compVal)
127+
return 0;
128+
else
129+
return 1;
130+
}
131+
}
132+
}

‎group03/345943980/2017Learning/src/com/coding/basic/Iterator.java

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

‎group03/345943980/2017Learning/src/com/coding/basic/LinkedList.java

Lines changed: 129 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,129 @@
1+
package com.coding.basic;
2+
3+
/**
4+
* 单向链表
5+
*
6+
* @author Administrator
7+
*
8+
*/
9+
public class LinkedList implements List {
10+
11+
private Node head = new Node(null, null);
12+
private int size = 0;
13+
14+
public LinkedList() {
15+
head.next = head;
16+
}
17+
18+
public void add(Object o) {
19+
addLast(o);
20+
}
21+
22+
public void add(int index, Object o) {
23+
// 1、检查是否在合理范围内
24+
if (index > size || index < 0)
25+
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
26+
Node currNode = findNodeByIndex(index);
27+
Node newNode = new Node(o, currNode);
28+
if (index == 0) { // 直接插入到第一个位置
29+
head = newNode;
30+
} else {
31+
Node preNode = findNodeByIndex(index - 1);
32+
preNode.next = newNode;
33+
}
34+
size++;
35+
}
36+
37+
public Object get(int index) {
38+
return findNodeByIndex(index).data;
39+
}
40+
41+
public Object remove(int index) {
42+
if (index > size || index < 0)
43+
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
44+
Node targetNode = this.findNodeByIndex(index);
45+
Object obj = targetNode.data;
46+
if (index == 0) {
47+
targetNode.data = null;
48+
head = targetNode.next;
49+
} else {
50+
Node preNode = findNodeByIndex(index - 1);
51+
preNode.next = targetNode.next;
52+
}
53+
// targetNode.data = null;
54+
size--;
55+
return obj;
56+
}
57+
58+
public int size() {
59+
return this.size;
60+
}
61+
62+
public void addFirst(Object o) {
63+
Node nextNode = head;
64+
Node newNode = new Node(o, nextNode);
65+
head = newNode;
66+
size++;
67+
}
68+
69+
public void addLast(Object o) {
70+
Node subNode = new Node(o, null);
71+
if (size == 0) {
72+
head = subNode;
73+
} else {
74+
Node lastNode = findNodeByIndex(size - 1);
75+
lastNode.next = subNode;
76+
}
77+
size++;
78+
}
79+
80+
public Object removeFirst() {
81+
return this.remove(0);
82+
}
83+
84+
public Object removeLast() {
85+
return this.remove(size - 1);
86+
}
87+
88+
private Node findNodeByIndex(int index) {
89+
Node lastNode = head;
90+
for (int i = 0; i < index; i++) {
91+
lastNode = lastNode.next;
92+
}
93+
return lastNode;
94+
}
95+
96+
public Iterator iterator() {
97+
return new LinkedListIterator();
98+
}
99+
100+
private static class Node {
101+
Object data;
102+
Node next;
103+
104+
Node(Object data, Node next) {
105+
this.data = data;
106+
this.next = next;
107+
}
108+
}
109+
110+
private class LinkedListIterator implements Iterator {
111+
112+
private int cursor = 0;
113+
private Node cursorNode = head;
114+
115+
@Override
116+
public boolean hasNext() {
117+
return size != cursor;
118+
}
119+
120+
@Override
121+
public Object next() {
122+
Object obj = cursorNode.data;
123+
cursorNode = cursorNode.next;
124+
cursor++;
125+
return obj;
126+
}
127+
128+
}
129+
}

‎group03/345943980/2017Learning/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)