Skip to content

Commit 16b99fe

Browse files
onlyliuxinonlyliuxin
authored
Merge pull request onlyliuxin#107 from heyucool/master
14组第三周作业推送
2 parents 15da018 + d6299dd commit 16b99fe

Some content is hidden

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

42 files changed

+2041
-515
lines changed

‎group14/296933284/Note/README.md

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,4 +2,5 @@
22
---
33

44
1. [漫谈计算机组成 -- 微型计算机的硬件组成 2017-02-26](http://tennyson.ren/2017/02/25/%E6%BC%AB%E8%B0%88%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%B3%BB%E7%BB%9F%E7%BB%84%E6%88%90%20--%20%E5%BE%AE%E5%9E%8B%E8%AE%A1%E7%AE%97%E6%9C%BA%E7%9A%84%E7%A1%AC%E4%BB%B6%E7%BB%84%E6%88%90/)
5-
2. [Java中解析XML的方法 2017-03-04](http://tennyson.ren/2017/03/04/Java%E4%B8%AD%E8%A7%A3%E6%9E%90XML%E7%9A%84%E6%96%B9%E6%B3%95/#more)
5+
2. [Java中解析XML的方法 2017-03-04](http://tennyson.ren/2017/03/04/Java%E4%B8%AD%E8%A7%A3%E6%9E%90XML%E7%9A%84%E6%96%B9%E6%B3%95/#more)
6+
3. [Java多线程下载 2017-03-12](http://tennyson.ren/2017/03/12/Java%E5%A4%9A%E7%BA%BF%E7%A8%8B%E4%B8%8B%E8%BD%BD/)

‎group14/296933284/coding/src/com/coderising/LinkList/LinkedList.java

Lines changed: 355 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,355 @@
1+
package com.coderising.LinkList;
2+
3+
import com.coding.basic.Iterator;
4+
import com.coding.basic.List;
5+
6+
import java.util.Collection;
7+
8+
9+
/**
10+
* LinkedList (单链表) 第14小组 296933284
11+
*
12+
* @author Tonnyson
13+
*
14+
*/
15+
public class LinkedList<T extends Comparable> implements List<T> {
16+
17+
private Node<T> head;
18+
private int size;
19+
20+
public LinkedList() {
21+
super();
22+
this.head = new Node<T>(null);
23+
}
24+
25+
public Node<T> getHead() {
26+
return head;
27+
}
28+
29+
@Override
30+
public boolean add(T element) {
31+
addLast(element);
32+
return true;
33+
}
34+
35+
@Override
36+
public void add(int index, T element) {
37+
38+
if (index == size) {
39+
addLast(element);
40+
} else {
41+
Node<T> r = getPreNode(index);
42+
Node<T> node = new Node<>(element);
43+
node.next = r.next;
44+
r.next = node;
45+
size++;
46+
47+
}
48+
}
49+
50+
public void addFirst(T element) {
51+
Node<T> node = new Node<>(element);
52+
node.next = head.next;
53+
head.next = node;
54+
size++;
55+
}
56+
57+
public void addLast(T element) {
58+
59+
Node<T> node = new Node<>(element);
60+
61+
Node<T> r = head;
62+
while (r.next != null) r = r.next;
63+
64+
r.next = node;
65+
66+
size++;
67+
68+
}
69+
70+
public void addAll(Collection<T> c) {
71+
72+
Iterator<T> iter = (Iterator<T>) c.iterator();
73+
74+
while (iter.hasNext()) {
75+
addLast(iter.next());
76+
}
77+
}
78+
79+
@Override
80+
public T get(int index) {
81+
82+
rangCheck(index);
83+
84+
return (T) getPreNode(index).next.data;
85+
}
86+
87+
@Override
88+
public T remove(int index) {
89+
90+
rangCheck(index);
91+
92+
Node<T> r = getPreNode(index);
93+
94+
T result = (T) r.next.data;
95+
96+
r.next = r.next.next;
97+
size--;
98+
99+
return result;
100+
}
101+
102+
public T removeFirst() {
103+
return remove(0);
104+
}
105+
106+
public T removeLast() {
107+
return remove(size - 1);
108+
}
109+
110+
private Node<T> getPreNode(int index) {
111+
112+
rangCheck(index);
113+
114+
if (index == 0) {
115+
return head;
116+
} else {
117+
Node<T> r = head;
118+
119+
for (int i = 0; i < index; i++)
120+
r = r.next;
121+
122+
return r;
123+
}
124+
125+
}
126+
127+
@Override
128+
public int size() {
129+
return size;
130+
}
131+
132+
@Override
133+
public boolean isEmpty() {
134+
return size == 0;
135+
}
136+
137+
@Override
138+
public Iterator<T> iterator() {
139+
return new Iter<>();
140+
}
141+
142+
private class Iter<T> implements Iterator<T> {
143+
int current = 0;
144+
145+
@Override
146+
public boolean hasNext() {
147+
return current != size;
148+
}
149+
150+
@Override
151+
public T next() {
152+
int i = current;
153+
154+
rangCheck(i);
155+
156+
current++;
157+
158+
return (T) get(i);
159+
}
160+
161+
}
162+
163+
private void rangCheck(int index) {
164+
if ( index < 0 || index >= size)
165+
throw new IndexOutOfBoundsException();
166+
}
167+
168+
private static class Node<T> {
169+
T data;
170+
Node<T> next;
171+
172+
Node(T data) {
173+
super();
174+
this.data = data;
175+
this.next = null;
176+
}
177+
}
178+
179+
/**
180+
* 把该链表逆置
181+
* 例如链表为 3->7->10 , 逆置后变为 10->7->3
182+
*/
183+
public void reverse() {
184+
Node<T> r = head.next;
185+
Node<T> p = null;
186+
head.next = null;
187+
188+
while (r != null) {
189+
p = r;
190+
r = r.next;
191+
p.next = head.next;
192+
head.next = p;
193+
}
194+
}
195+
196+
/**
197+
* 删除一个单链表的前半部分
198+
* 例如：list = 2->5->7->8 , 删除以后的值为 7->8
199+
* 如果list = 2->5->7->8->10 ,删除以后的值为7,8,10
200+
*
201+
*/
202+
public void removeFirstHalf() {
203+
int len = (int) Math.ceil(size / 2.0);
204+
205+
remove(0, len);
206+
}
207+
208+
/**
209+
* 从第i个元素开始， 删除length 个元素 ， 注意i从0开始
210+
* @param i
211+
* @param length
212+
*/
213+
public void remove(int i, int length) {
214+
215+
rangCheck(i);
216+
217+
if (i + length - 1 > size - i) {
218+
throw new IndexOutOfBoundsException();
219+
}
220+
221+
Node<T> preFirst = getPreNode(i);
222+
Node<T> preLast = getPreNode(i + length - 1).next;
223+
224+
preFirst.next = preLast.next;
225+
preLast = null;
226+
size -= length;
227+
228+
}
229+
/**
230+
* 假定当前链表和list均包含已升序排列的整数
231+
* 从当前链表中取出那些list所指定的元素
232+
* 例如当前链表 = 11->101->201->301->401->501->601->701
233+
* listB = 1->3->4->6
234+
* 返回的结果应该是[101,301,401,601]
235+
* @param list
236+
*/
237+
public int[] getElements(LinkedList<Integer> list) {
238+
int[] elements = new int[list.size()];
239+
240+
for (int i = 0; i < list.size(); i++) {
241+
elements[i] = (Integer) get((int) list.get(i));
242+
}
243+
244+
return elements;
245+
}
246+
247+
/**
248+
* 已知链表中的元素以值递增有序排列，并以单链表作存储结构。
249+
* 从当前链表中中删除在list中出现的元素
250+
*
251+
* @param list
252+
*/
253+
public void subtract(LinkedList<T> list) {
254+
int len;
255+
for (int i = 0; i < list.size(); i++) {
256+
Node<T> p = head;
257+
Node<T> r = null;
258+
259+
T value = list.get(i);
260+
261+
while (p.next != null) {
262+
263+
if (p.next.data.equals(value)) {
264+
r = p.next;
265+
p.next = r.next;
266+
r.next = null;
267+
size--;
268+
} else {
269+
p = p.next;
270+
}
271+
272+
273+
}
274+
}
275+
}
276+
277+
/**
278+
* 已知当前链表中的元素以值递增有序排列，并以单链表作存储结构。
279+
* 删除表中所有值相同的多余元素（使得操作后的线性表中所有元素的值均不相同）
280+
*/
281+
public void removeDuplicateValues() {
282+
Node<T> p = head;
283+
Node<T> r = head.next;
284+
285+
while (p.next != null && r.next != null) {
286+
if (p.next.data.compareTo(r.next.data) == 0) {
287+
p.next = r.next;
288+
r.next = p.next.next;
289+
size--;
290+
} else {
291+
p = p.next;
292+
r = r.next;
293+
}
294+
}
295+
}
296+
297+
/**
298+
* 已知链表中的元素以值递增有序排列，并以单链表作存储结构。
299+
* 试写一高效的算法，删除表中所有值大于min且小于max的元素（若表中存在这样的元素）
300+
* @param min
301+
* @param max
302+
*/
303+
public void removeRange(int min, int max) {
304+
Node<T> p = head;
305+
306+
while (p.next!= null) {
307+
if (p.next.data.compareTo(min) > 0 && p.next.data.compareTo(max) < 0) {
308+
Node<T> r = p.next;
309+
p.next = r.next;
310+
r.next = null;
311+
size--;
312+
} else {
313+
p = p.next;
314+
}
315+
}
316+
}
317+
318+
/**
319+
* 假设当前链表和参数list指定的链表均以元素依值递增有序排列（同一表中的元素值各不相同）
320+
* 现要求生成新链表C，其元素为当前链表和list中元素的交集，且表C中的元素有依值递增有序排列
321+
* @param list
322+
*/
323+
public LinkedList<T> intersection(LinkedList<T> list){
324+
LinkedList<T> newList = new LinkedList<T>();
325+
326+
Node<T> p1 = head;
327+
328+
while (p1.next != null) {
329+
Node<T> p2 = list.getHead();
330+
while (p2.next != null && p1.next.data.compareTo(p2.next.data) != 0) {
331+
p2 = p2.next;
332+
}
333+
334+
if (p2.next != null) {
335+
newList.add(p2.next.data);
336+
}
337+
p1 = p1.next;
338+
}
339+
340+
return newList;
341+
}
342+
}
343+
344+
345+
346+
347+
348+
349+
350+
351+
352+
353+
354+
355+

0 commit comments

Comments
 (0)