Skip to content

Commit a598a5d

Browse files
author
kaitao.li
committed
第一次数据结构作业
1 parent e316a06 commit a598a5d

File tree

15 files changed

+685
-0
lines changed

15 files changed

+685
-0
lines changed

‎group01/280646174/.gitignore

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
# Created by .ignore support plugin (hsz.mobi)
2+
### Java template
3+
*.class
4+
5+
# Log file
6+
*.log
7+
8+
# BlueJ files
9+
*.ctxt
10+
11+
# Mobile Tools for Java (J2ME)
12+
.mtj.tmp/
13+
14+
# Package Files #
15+
*.jar
16+
*.war
17+
*.ear
18+
*.zip
19+
*.tar.gz
20+
*.rar
21+
22+
# virtual machine crash logs, see http://www.java.com/en/download/help/error_hotspot.xml
23+
hs_err_pid*
24+
25+
# Idea Files #
26+
.idea
27+
*.iml

‎group01/280646174/280646174.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
# dutekt's home

‎group01/280646174/basic/pom.xml

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<project xmlns="http://maven.apache.org/POM/4.0.0"
3+
xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
4+
xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
5+
<parent>
6+
<artifactId>root</artifactId>
7+
<groupId>com.coding2017</groupId>
8+
<version>1.0-SNAPSHOT</version>
9+
</parent>
10+
<modelVersion>4.0.0</modelVersion>
11+
12+
<artifactId>basic</artifactId>
13+
14+
<dependencies>
15+
<!--test-->
16+
<dependency>
17+
<groupId>junit</groupId>
18+
<artifactId>junit</artifactId>
19+
</dependency>
20+
<dependency>
21+
<groupId>junit</groupId>
22+
<artifactId>junit-dep</artifactId>
23+
</dependency>
24+
</dependencies>
25+
26+
27+
</project>

‎group01/280646174/basic/src/main/java/com/coding2017/basic/ArrayList.java

Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
1+
package com.coding2017.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[4];
10+
11+
public void add(Object o) {
12+
if (noSpace()) {
13+
extendSpace();
14+
}
15+
16+
elementData[size++] = o;
17+
}
18+
19+
private void extendSpace() {
20+
elementData = Arrays.copyOf(elementData, elementData.length * 2);
21+
}
22+
23+
private boolean noSpace() {
24+
return size == elementData.length;
25+
}
26+
27+
public void add(int index, Object o) {
28+
if (index < 0 || index > size) {
29+
throw new IndexOutOfBoundsException();
30+
}
31+
if (noSpace()) {
32+
extendSpace();
33+
}
34+
35+
if (index == size) {
36+
add(o);
37+
return;
38+
}
39+
40+
System.arraycopy(elementData, index, elementData, index + 1, size - index);
41+
elementData[index] = o;
42+
size++;
43+
}
44+
45+
public Object get(int index) {
46+
if (index < 0 || index >= size) {
47+
throw new IndexOutOfBoundsException();
48+
}
49+
return elementData[index];
50+
}
51+
52+
public Object remove(int index) {
53+
if (index < 0 || index >= size) {
54+
throw new IndexOutOfBoundsException();
55+
}
56+
if (index == size - 1) {
57+
return elementData[--size];
58+
}
59+
60+
Object removed = elementData[index];
61+
System.arraycopy(elementData, index + 1, elementData, index, size - index - 1);
62+
size--;
63+
return removed;
64+
}
65+
66+
public int size() {
67+
return size;
68+
}
69+
70+
@Override
71+
public String toString() {
72+
StringBuilder builder = new StringBuilder("[");
73+
if (size > 0) {
74+
builder.append(get(0));
75+
}
76+
for (int i = 1; i < size; i++) {
77+
builder.append(", ").append(get(i));
78+
}
79+
builder.append("]");
80+
return builder.toString();
81+
}
82+
83+
public Iterator iterator() {
84+
return new ArrayListIterator();
85+
}
86+
87+
private class ArrayListIterator implements Iterator {
88+
private int pos;
89+
90+
@Override
91+
public boolean hasNext() {
92+
return pos < size();
93+
}
94+
95+
@Override
96+
public Object next() {
97+
return ArrayList.this.get(pos++);
98+
}
99+
}
100+
}

‎group01/280646174/basic/src/main/java/com/coding2017/basic/BinaryTreeNode.java

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

‎group01/280646174/basic/src/main/java/com/coding2017/basic/Iterator.java

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

‎group01/280646174/basic/src/main/java/com/coding2017/basic/LinkedList.java

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

0 commit comments

Comments
 (0)