Skip to content

Commit d9c0269

Browse files
onlyliuxinonlyliuxin
authored
Merge pull request onlyliuxin#16 from gaodekui/master
20170226作业提交
2 parents 8f29473 + f9b9208 commit d9c0269

File tree

110 files changed

+5310
-0
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

110 files changed

+5310
-0
lines changed

‎.gitignore

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -7,15 +7,25 @@
77
*.war
88
*.ear
99

10+
*.iml
11+
*.idea
12+
13+
1014
# virtual machine crash logs, see http://www.java.com/en/download/help/error_hotspot.xml
1115
hs_err_pid*
1216

1317
#ide config
1418
.metadata
1519
.recommenders
20+
21+
22+
#macOS
23+
.DS_Store
24+
1625
.idea/
1726
*.iml
1827
rebel.*
1928
.rebel.*
2029

2130
target
31+

‎group16/1012075117/DataStructure219/.classpath

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<classpath>
3+
<classpathentry kind="src" path="src"/>
4+
<classpathentry kind="con" path="org.eclipse.jdt.launching.JRE_CONTAINER/org.eclipse.jdt.internal.debug.ui.launcher.StandardVMType/JavaSE-1.8"/>
5+
<classpathentry kind="output" path="bin"/>
6+
</classpath>

‎group16/1012075117/DataStructure219/.project

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

‎group16/1012075117/DataStructure219/.settings/org.eclipse.jdt.core.prefs

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
eclipse.preferences.version=1
2+
org.eclipse.jdt.core.compiler.codegen.inlineJsrBytecode=enabled
3+
org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.8
4+
org.eclipse.jdt.core.compiler.codegen.unusedLocal=preserve
5+
org.eclipse.jdt.core.compiler.compliance=1.8
6+
org.eclipse.jdt.core.compiler.debug.lineNumber=generate
7+
org.eclipse.jdt.core.compiler.debug.localVariable=generate
8+
org.eclipse.jdt.core.compiler.debug.sourceFile=generate
9+
org.eclipse.jdt.core.compiler.problem.assertIdentifier=error
10+
org.eclipse.jdt.core.compiler.problem.enumIdentifier=error
11+
org.eclipse.jdt.core.compiler.source=1.8

‎group16/1012075117/DataStructure219/src/com/stackwei/DataStructure/ArrayList.java

Lines changed: 94 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,94 @@
1+
package com.stackwei.DataStructure;
2+
3+
/**
4+
*
5+
* @author stackwei -2017.2.25
6+
*
7+
*/
8+
public class ArrayList implements List {
9+
10+
private int flag = -1;
11+
private static final int DEFAULT_CAPACITY = 1;
12+
private Object[] elementData = new Object[DEFAULT_CAPACITY];
13+
14+
@Override
15+
public void add(Object element) {
16+
// 当要添加数据的位置已经超过数组长度时，增长数组长度
17+
if (size() + 1 == elementData.length) {
18+
grow();
19+
}
20+
elementData[flag + 1] = element;
21+
flag++;
22+
}
23+
24+
@Override
25+
public void add(int index, Object element) {
26+
if (index < 0 || index > getFlag() + 1) {
27+
System.out.println("在--" + index + "--添加的--" + element + "--无效，因为越界了！");
28+
return;
29+
}
30+
// 数组长度永远比已存数据大一个。
31+
if (size() + 1 == elementData.length) {
32+
grow();
33+
}
34+
elementData[index] = element;
35+
if (index > getFlag()) {
36+
flag++;
37+
}
38+
}
39+
40+
@Override
41+
public Object get(int index) {
42+
if (index < 0 || index > getFlag()) {
43+
System.out.print("在--" + index + "--的get无效,因为越界了！");
44+
return null;
45+
}
46+
return elementData[index];
47+
}
48+
49+
@Override
50+
public Object remove(int index) {
51+
if (index < 0 || index > getFlag()) {
52+
System.out.println("在--" + index + "--的remove无效,因为越界了！");
53+
return null;
54+
}
55+
Object oldValue = elementData[index];
56+
elementData[index] = null;
57+
// 将删除处后面的数据往前移一格。
58+
Object[] data2 = new Object[elementData.length - 1];
59+
System.arraycopy(elementData, 0, data2, 0, getFlag());
60+
elementData = data2;
61+
flag--;
62+
return oldValue;
63+
}
64+
65+
@Override
66+
public int size() {
67+
return getFlag() + 1;
68+
}
69+
70+
public int getFlag() {
71+
return flag;
72+
}
73+
74+
private void grow() {
75+
Object[] data2 = new Object[elementData.length + 1];
76+
System.arraycopy(elementData, 0, data2, 0, getFlag() + 2);// 最后一个参数是需要复制的数据的数量。
77+
elementData = data2;
78+
}
79+
80+
/**
81+
* 测试用例
82+
*
83+
* @param args
84+
*/
85+
public static void main(String[] args) {
86+
ArrayList al = new ArrayList();
87+
al.add(0, 99);
88+
al.add(1, 100);
89+
System.out.println(al.get(1));
90+
al.remove(1);
91+
System.out.println(al.get(1));
92+
System.out.println(al.size());
93+
}
94+
}

‎group16/1012075117/DataStructure219/src/com/stackwei/DataStructure/LinkedList.java

Lines changed: 194 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,194 @@
1+
package com.stackwei.DataStructure;
2+
3+
/**
4+
*
5+
* @author stackwei -2017.2.25
6+
*
7+
*/
8+
public class LinkedList implements List {
9+
10+
private Node head = null;
11+
private Node last = null;
12+
private int size = 0;
13+
14+
private static class Node {
15+
Object item;
16+
Node prev;
17+
Node next;
18+
19+
public Node(Node prev, Object item, Node next) {
20+
this.prev = prev;
21+
this.item = item;
22+
this.next = next;
23+
}
24+
}
25+
26+
@Override
27+
public void add(Object element) {
28+
addLast(element);
29+
}
30+
31+
@Override
32+
public void add(int index, Object element) {
33+
if (index < 0 || index > size) {
34+
System.out.println("操作无效,越界了");
35+
return;
36+
}
37+
if (index == 0) {
38+
addFirst(element);
39+
return;
40+
}
41+
if (index == size) {
42+
addLast(element);
43+
return;
44+
}
45+
Node indexNode = node(index);
46+
Node newNode = new Node(indexNode.prev, element, indexNode);
47+
indexNode.prev.next = newNode;
48+
indexNode.prev = newNode;
49+
size++;
50+
}
51+
52+
@Override
53+
public Object get(int index) {
54+
if (index < 0 || index >= size) {
55+
System.out.println("查询无效,越界了");
56+
return null;
57+
}
58+
if (index == 0) {
59+
return head.item;
60+
}
61+
return node(index).item;
62+
}
63+
64+
@Override
65+
public Object remove(int index) {
66+
if (index < 0 || index > size) {
67+
System.out.println("是空的，无法删除");
68+
return null;
69+
}
70+
if (index == 0) {
71+
return removeFirst();
72+
}
73+
if (index == size - 1) {
74+
return removeLast();
75+
}
76+
Node x = node(index);
77+
final Object element = x.item;
78+
final Node next = x.next;
79+
final Node prev = x.prev;
80+
81+
if (prev == null) {
82+
head = next;
83+
} else {
84+
prev.next = next;
85+
x.prev = null;
86+
}
87+
88+
if (next == null) {
89+
last = prev;
90+
} else {
91+
next.prev = prev;
92+
x.next = null;
93+
}
94+
95+
x.item = null;
96+
size--;
97+
return element;
98+
}
99+
100+
@Override
101+
public int size() {
102+
return size;
103+
}
104+
105+
private void addFirst(Object element) {
106+
final Node f = head;
107+
Node newNode = new Node(null, element, f);
108+
head = newNode;
109+
if (f == null)
110+
last = newNode;
111+
else
112+
f.prev = newNode;
113+
size++;
114+
}
115+
116+
public void addLast(Object element) {
117+
if (head == null) {
118+
addFirst(element);
119+
} else {
120+
Node newNode = new Node(last, element, null);
121+
last.next = newNode;
122+
last = newNode;
123+
size++;
124+
}
125+
}
126+
127+
public Object removeFirst() {
128+
if (head == null) {
129+
System.out.println("是空的，无法删除");
130+
return null;
131+
} else {
132+
Node x = head;
133+
Node next = head.next;
134+
Object element = x.item;
135+
x.item = null;
136+
x.next = null;
137+
head = next;
138+
if (next == null)
139+
last = null;
140+
else
141+
x.prev = null;
142+
size--;
143+
return element;
144+
}
145+
}
146+
147+
public Object removeLast() {
148+
if (last == null) {
149+
System.out.println("是空的，无法删除");
150+
return null;
151+
} else {
152+
final Node l = last;
153+
final Object element = l.item;
154+
final Node p = l.prev;
155+
l.item = null;
156+
l.prev = null;
157+
last = p;
158+
if (p == null)
159+
head = null;
160+
else
161+
p.next = null;
162+
size--;
163+
return element;
164+
}
165+
}
166+
167+
Node node(int index) {
168+
if (index < (size >> 1)) {
169+
Node x = head;
170+
for (int i = 0; i < index; i++)
171+
x = x.next;
172+
return x;
173+
} else {
174+
Node x = last;
175+
for (int i = size - 1; i > index; i--)
176+
x = x.prev;
177+
return x;
178+
}
179+
}
180+
181+
/**
182+
* 测试用例
183+
*
184+
* @param args
185+
*/
186+
public static void main(String[] args) {
187+
LinkedList ll = new LinkedList();
188+
ll.add(0, "xxx");
189+
ll.add(1, 111);
190+
System.out.println(ll.size());
191+
System.out.println(ll.get(2));
192+
193+
}
194+
}

‎group16/1012075117/DataStructure219/src/com/stackwei/DataStructure/List.java

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
package com.stackwei.DataStructure;
2+
3+
public interface List {
4+
public void add(Object o);
5+
6+
public void add(int index, Object o);
7+
8+
public Object get(int index);
9+
10+
public Object remove(int index);
11+
12+
public int size();
13+
}

0 commit comments

Comments
 (0)