Skip to content

Commit 7bc4437

Browse files
Viscaria233Viscaria233
committed
init
1 parent f21458d commit 7bc4437

File tree

13 files changed

+1324
-0
lines changed

13 files changed

+1324
-0
lines changed

‎group01/895457260/code/src/datastructure/basic/ArrayList.java

Lines changed: 85 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,85 @@
1+
package datastructure.basic;
2+
3+
public class ArrayList implements List {
4+
5+
private int size = 0;
6+
7+
Object[] elementData;
8+
9+
public ArrayList() {
10+
elementData = new Object[100];
11+
}
12+
13+
public ArrayList(int initCapacity) {
14+
elementData = new Object[initCapacity];
15+
}
16+
17+
public void add(Object o){
18+
autoGrow();
19+
elementData[size()] = o;
20+
size++;
21+
}
22+
23+
public void add(int index, Object o){
24+
autoGrow();
25+
System.arraycopy(elementData, index, elementData, index + 1, size() - index);
26+
elementData[index] = o;
27+
size++;
28+
}
29+
30+
public Object get(int index){
31+
checkIndex(index);
32+
return elementData[index];
33+
}
34+
35+
public Object remove(int index){
36+
checkIndex(index);
37+
Object removed = elementData[index];
38+
System.arraycopy(elementData, index + 1, elementData, index, size() - index);
39+
size--;
40+
return removed;
41+
}
42+
43+
public int size(){
44+
return size;
45+
}
46+
47+
public Iterator iterator(){
48+
return new Iterator() {
49+
int index = -1;
50+
@Override
51+
public boolean hasNext() {
52+
return index + 1 < size();
53+
}
54+
55+
@Override
56+
public Object next() {
57+
index++;
58+
return elementData[index];
59+
}
60+
};
61+
}
62+
63+
private void autoGrow() {
64+
if (size >= elementData.length) {
65+
Object[] newArray = new Object[nextCapacity()];
66+
System.arraycopy(elementData, 0, newArray, 0, elementData.length);
67+
elementData = newArray;
68+
}
69+
}
70+
71+
private int nextCapacity() {
72+
return elementData.length * 2;
73+
}
74+
75+
private void checkIndex(int index) {
76+
if (index >= size() || index < 0) {
77+
throw new IndexOutOfBoundsException(indexOutOfBoundMessage(index));
78+
}
79+
}
80+
81+
private String indexOutOfBoundMessage(int index) {
82+
return "index: " + index + ", size: " + size();
83+
}
84+
85+
}

‎group01/895457260/code/src/datastructure/basic/BinaryTreeNode.java

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

‎group01/895457260/code/src/datastructure/basic/Iterator.java

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

‎group01/895457260/code/src/datastructure/basic/LinkedList.java

Lines changed: 102 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,102 @@
1+
package datastructure.basic;
2+
3+
public class LinkedList implements List {
4+
5+
private Node head;
6+
private int size;
7+
8+
public LinkedList() {
9+
head = new Node();
10+
}
11+
12+
public void add(Object o){
13+
addLast(o);
14+
}
15+
16+
public void add(int index , Object o){
17+
Node pre = findNode(index - 1);
18+
Node node = new Node();
19+
node.data = o;
20+
addNode(node, pre);
21+
}
22+
23+
public Object get(int index){
24+
checkIndex(index);
25+
return findNode(index);
26+
}
27+
public Object remove(int index){
28+
checkIndex(index);
29+
Node pre = findNode(index - 1);
30+
Node removed = pre.next;
31+
removeNode(removed, pre);
32+
return removed.data;
33+
}
34+
35+
public int size(){
36+
return size;
37+
}
38+
39+
public void addFirst(Object o){
40+
Node node = new Node();
41+
node.data = o;
42+
addNode(node, head);
43+
}
44+
public void addLast(Object o){
45+
Node node = new Node();
46+
node.data = o;
47+
Node pre = findNode(size());
48+
addNode(node, pre);
49+
}
50+
public Object removeFirst(){
51+
Node removed = head.next;
52+
removeNode(head.next, head);
53+
return removed.data;
54+
}
55+
public Object removeLast(){
56+
return remove(size() - 1);
57+
}
58+
public Iterator iterator(){
59+
return null;
60+
}
61+
62+
63+
private static class Node{
64+
Object data;
65+
Node next;
66+
}
67+
68+
private Node findNode(int index) {
69+
if (index == -1) {
70+
return head;
71+
} else {
72+
checkIndex(index);
73+
}
74+
Node node = head.next;
75+
for (int i = 0; i < index; ++i) {
76+
node = node.next;
77+
}
78+
return node;
79+
}
80+
81+
private void checkIndex(int index) {
82+
if (index >= size() || index < 0) {
83+
throw new IndexOutOfBoundsException(indexOutOfBoundMessage(index));
84+
}
85+
}
86+
87+
private String indexOutOfBoundMessage(int index) {
88+
return "index: " + index + ", size: " + size();
89+
}
90+
91+
private void addNode(Node node, Node pre) {
92+
node.next = pre.next;
93+
pre.next = node;
94+
size++;
95+
}
96+
97+
private void removeNode(Node node, Node pre) {
98+
pre.next = node.next;
99+
node.next = null;
100+
size--;
101+
}
102+
}

‎group01/895457260/code/src/datastructure/basic/List.java

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

‎group01/895457260/code/src/datastructure/basic/Queue.java

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
package datastructure.basic;
2+
3+
public class Queue {
4+
//数组实现自增长的循环队列
5+
private Object[] array = new Object[10];
6+
private int head = 0;
7+
private int rear = 0;
8+
9+
public void enQueue(Object o){
10+
int target = mapIndex(rear);
11+
autoGrow();
12+
array[target] = o;
13+
rear++;
14+
}
15+
16+
public Object deQueue() {
17+
Object obj = array[mapIndex(head)];
18+
head++;
19+
return obj;
20+
}
21+
22+
public boolean isEmpty(){
23+
return head == rear;
24+
}
25+
26+
public int size(){
27+
return rear - head;
28+
}
29+
30+
private int capacity() {
31+
return array.length;
32+
}
33+
34+
private void autoGrow() {
35+
if (size() >= capacity()) {
36+
Object[] newArray = new Object[nextCapacity()];
37+
System.arraycopy(array, 0, newArray, 0, capacity());
38+
39+
int increase = nextCapacity() - capacity();
40+
int moveCount = size() - mapIndex(rear);
41+
System.arraycopy(newArray, mapIndex(head), newArray, mapIndex(head) + increase, moveCount);
42+
array = newArray;
43+
head += increase;
44+
rear += increase;
45+
}
46+
}
47+
48+
private int nextCapacity() {
49+
return capacity() * 2;
50+
}
51+
52+
private int mapIndex(int index) {
53+
return index >= capacity() ? index % capacity() : index;
54+
}
55+
56+
public static void main(String[] args) {
57+
Queue queue = new Queue();
58+
for (int i = 0; i < 22; ++i) {
59+
queue.enQueue(i);
60+
}
61+
for (int i = 0; i < 6; ++i) {
62+
System.out.print(queue.deQueue() + " ");
63+
}
64+
for (int i = 22; i < 41; ++i) {
65+
queue.enQueue(i);
66+
}
67+
while (!queue.isEmpty()) {
68+
System.out.print(queue.deQueue() + " ");
69+
}
70+
System.out.println();
71+
}
72+
}

‎group01/895457260/code/src/datastructure/basic/Stack.java

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
package datastructure.basic;
2+
3+
public class Stack {
4+
private ArrayList elementData = new ArrayList();
5+
6+
public void push(Object o){
7+
elementData.add(o);
8+
}
9+
10+
public Object pop(){
11+
Object peek = peek();
12+
elementData.remove(elementData.size() - 1);
13+
return peek;
14+
}
15+
16+
public Object peek(){
17+
return elementData.get(elementData.size() - 1);
18+
}
19+
20+
public boolean isEmpty(){
21+
return size() == 0;
22+
}
23+
24+
public int size(){
25+
return elementData.size();
26+
}
27+
28+
public static void main(String[] args) {
29+
Stack stack = new Stack();
30+
for (int i = 0; i < 6; ++i) {
31+
stack.push(i);
32+
}
33+
for (int i = 0; i < 4; ++i) {
34+
System.out.print(stack.pop() + " ");
35+
}
36+
for (int i = 6; i < 21; ++i) {
37+
stack.push(i);
38+
}
39+
while (!stack.isEmpty()) {
40+
System.out.print(stack.pop() + " ");
41+
}
42+
}
43+
}

0 commit comments

Comments
 (0)