Skip to content

Commit f999553

Browse files
BlankKellyBlankKelly
committed
基本数据结构作业
1 parent 988fb24 commit f999553

File tree

11 files changed

+522
-0
lines changed

11 files changed

+522
-0
lines changed

‎group08/769638826/pom.xml

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
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+
<modelVersion>4.0.0</modelVersion>
6+
7+
<groupId>com.coding2017</groupId>
8+
<artifactId>coding</artifactId>
9+
<version>1.0-SNAPSHOT</version>
10+
11+
<properties>
12+
<project.build.buildEncoding>UTF-8</project.build.buildEncoding>
13+
<java.version>1.7</java.version>
14+
</properties>
15+
16+
<dependencies>
17+
<dependency>
18+
<groupId>junit</groupId>
19+
<artifactId>junit</artifactId>
20+
<version>4.12</version>
21+
</dependency>
22+
</dependencies>
23+
24+
<build>
25+
<plugins>
26+
<plugin>
27+
<groupId>org.apache.maven.plugins</groupId>
28+
<artifactId>maven-compiler-plugin</artifactId>
29+
<configuration>
30+
<source>${java.version}</source>
31+
<target>${java.version}</target>
32+
<encoding>${project.build.buildEncoding}</encoding>
33+
</configuration>
34+
</plugin>
35+
</plugins>
36+
</build>
37+
</project>

‎group08/769638826/src/main/java/com/coding/basic/ArrayList.java

Lines changed: 102 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,102 @@
1+
package com.coding.basic;
2+
3+
import java.util.Arrays;
4+
import java.util.NoSuchElementException;
5+
6+
/**
7+
* Created by huitailang on 17/2/25.
8+
*
9+
* @author zhangkun
10+
* @date 2017年02月25日13:23:30
11+
*/
12+
public class ArrayList implements List {
13+
private int size = 0;
14+
private static final int DEFAULT_SIZE = 16;
15+
private Object[] elementData = null;
16+
private int index;
17+
18+
public ArrayList() {
19+
elementData = new Object[DEFAULT_SIZE];
20+
}
21+
22+
public ArrayList(final int size) {
23+
elementData = new Object[size];
24+
}
25+
26+
public void add(Object o) {
27+
//如果当前元素个数大于数组长度的2/3
28+
if (size() > elementData.length * 2 / 3) {
29+
raiseArray();
30+
}
31+
32+
elementData[index++] = o;
33+
size++;
34+
}
35+
36+
public void add(int index, Object o) {
37+
checkParam(index);
38+
39+
//如果当前元素个数大于数组长度的2/3
40+
if (size() > elementData.length * 2 / 3) {
41+
raiseArray();
42+
}
43+
44+
elementData[index] = o;
45+
size++;
46+
}
47+
48+
public Object get(int index) {
49+
checkParam(index);
50+
51+
return elementData[index];
52+
}
53+
54+
public Object remove(int index) {
55+
checkParam(index);
56+
57+
Object o = elementData[index];
58+
elementData[index] = null;
59+
size--;
60+
return o;
61+
}
62+
63+
private void raiseArray() {
64+
Object[] newElementData = Arrays.copyOf(elementData, size() * 2);
65+
elementData = newElementData;
66+
}
67+
68+
private void checkParam(int index) {
69+
if (index < 0 || index > elementData.length - 1) {
70+
throw new IndexOutOfBoundsException();
71+
}
72+
}
73+
74+
public int size() {
75+
return size;
76+
}
77+
78+
public Iterator iterator() {
79+
return null;
80+
}
81+
82+
private class ListIterator implements Iterator{
83+
@Override
84+
public boolean hasNext() {
85+
return size != 0;
86+
}
87+
88+
public void remove(){
89+
throw new UnsupportedOperationException();
90+
}
91+
92+
@Override
93+
public Object next() {
94+
if(!hasNext()){
95+
throw new NoSuchElementException();
96+
}
97+
98+
//TODO
99+
return null;
100+
}
101+
}
102+
}

‎group08/769638826/src/main/java/com/coding/basic/Iterator.java

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
package com.coding.basic;
2+
3+
/**
4+
* Created by huitailang on 17/2/25.
5+
*
6+
* @author zhangkun
7+
* @date 2017年02月25日16:25:42
8+
*/
9+
public interface Iterator {
10+
public boolean hasNext();
11+
12+
public Object next();
13+
}

‎group08/769638826/src/main/java/com/coding/basic/LinkedList.java

Lines changed: 190 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,190 @@
1+
package com.coding.basic;
2+
3+
import java.util.NoSuchElementException;
4+
5+
/**
6+
* Created by huitailang on 17/2/25.
7+
*
8+
* @author zhangkun
9+
* @date 2017年02月25日13:57:58
10+
*/
11+
public class LinkedList implements List {
12+
private Node head;
13+
private int size;
14+
15+
public LinkedList() {
16+
head = null;
17+
size = 0;
18+
}
19+
20+
@Override
21+
public void add(Object o) {
22+
if (head == null) {
23+
Node newNode = new Node();
24+
newNode.data = o;
25+
head = newNode;
26+
}
27+
28+
Node oldhead = head;
29+
head = new Node();
30+
head.data = o;
31+
head.next = oldhead;
32+
size++;
33+
}
34+
35+
@Override
36+
public void add(int index, Object o) {
37+
Node newNode = new Node();
38+
newNode.data = o;
39+
40+
if (head == null) {
41+
42+
}
43+
44+
if (index < 1 || index > size + 1) {
45+
throw new IllegalArgumentException("invalid index, it's should be 1 and" + size + 1);
46+
}
47+
48+
if (index == 1) {
49+
newNode.next = head;
50+
} else {
51+
Node currentNode = head;
52+
int count = 1;
53+
while (count < index - 1) {
54+
count++;
55+
currentNode = currentNode.next;
56+
}
57+
newNode.next = currentNode.next;
58+
currentNode.next = newNode;
59+
}
60+
}
61+
62+
@Override
63+
public Object get(int index) {
64+
if (head == null) {
65+
return null;
66+
}
67+
68+
if (index == 1) {
69+
return head.next.data;
70+
} else {
71+
Node currentNode = head;
72+
int count = 1;
73+
while (count < index - 1) {
74+
count++;
75+
currentNode = currentNode.next;
76+
}
77+
78+
return currentNode.next.data;
79+
}
80+
}
81+
82+
@Override
83+
public Object remove(int index) {
84+
Object result = null;
85+
86+
if (index < 1 || index > size) {
87+
throw new IllegalArgumentException("invalid index, it's should be 1 and " + size);
88+
}
89+
90+
if (index == 1) {
91+
Node currentNode = head.next;
92+
head = null;
93+
return currentNode;
94+
} else {
95+
Node prevNode = head;
96+
97+
int count = 1;
98+
while (count < index - 1) {
99+
prevNode = prevNode.next;
100+
count++;
101+
}
102+
Node currentNode = prevNode.next;
103+
prevNode.next = currentNode.next;
104+
result = currentNode.data;
105+
currentNode = null;
106+
}
107+
108+
return result;
109+
}
110+
111+
@Override
112+
public int size() {
113+
return size;
114+
}
115+
116+
public void addFirst(Object o) {
117+
add(1, o);
118+
}
119+
120+
public void addLast(Object o) {
121+
add(size + 1, o);
122+
}
123+
124+
public Object removeFirst() {
125+
return remove(1);
126+
}
127+
128+
public Object removeLast() {
129+
return remove(size);
130+
}
131+
132+
public Iterator iterator() {
133+
return new ListIterator();
134+
}
135+
136+
public void print() {
137+
if (head == null) {
138+
System.out.println("No elements in the list!");
139+
}
140+
141+
Node currentNode = head;
142+
while (currentNode != null) {
143+
System.out.println(currentNode.data + "->");
144+
currentNode = currentNode.next;
145+
}
146+
147+
System.out.println();
148+
}
149+
150+
public int length() {
151+
int count = 0;
152+
153+
Node currentNode = head;
154+
while (currentNode != null) {
155+
count++;
156+
currentNode = currentNode.next;
157+
}
158+
159+
return count;
160+
}
161+
162+
private static class Node {
163+
Object data;
164+
Node next;
165+
}
166+
167+
private class ListIterator implements Iterator {
168+
private Node current = head;
169+
170+
@Override
171+
public boolean hasNext() {
172+
return current != null;
173+
}
174+
175+
public void remove() {
176+
throw new UnsupportedOperationException();
177+
}
178+
179+
@Override
180+
public Object next() {
181+
if (!hasNext()) {
182+
throw new NoSuchElementException();
183+
}
184+
185+
Object o = current.data;
186+
current = current.next;
187+
return o;
188+
}
189+
}
190+
}

‎group08/769638826/src/main/java/com/coding/basic/List.java

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
package com.coding.basic;
2+
3+
/**
4+
* Created by huitailang on 17/2/25.
5+
*
6+
* @author zhangkun
7+
* @date 2017年02月25日13:54:33
8+
*/
9+
public interface List {
10+
public void add(Object o);
11+
12+
public void add(int index, Object o);
13+
14+
public Object get(int index);
15+
16+
public Object remove(int index);
17+
18+
public int size();
19+
}

‎group08/769638826/src/main/java/com/coding/basic/Queue.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+
* Created by huitailang on 17/2/25.
5+
* @author zhangkun
6+
* @date 2017年02月25日17:40:02
7+
*/
8+
public class Queue {
9+
private ArrayList elementData = new ArrayList();
10+
11+
public void enQueue(Object o){
12+
elementData.add(o);
13+
}
14+
15+
public Object deQueue(){
16+
return elementData.get(size());
17+
}
18+
19+
public boolean isEmpty(){
20+
return elementData.size() != 0;
21+
}
22+
23+
public int size(){
24+
return elementData.size();
25+
}
26+
}

0 commit comments

Comments
 (0)