Skip to content

Commit 5e07f16

Browse files
author
dream
committed
homework
1 parent eed8301 commit 5e07f16

File tree

10 files changed

+961
-0
lines changed

10 files changed

+961
-0
lines changed

‎group03/763878069/.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"/>
5+
<classpathentry kind="output" path="bin"/>
6+
</classpath>

‎group03/763878069/.gitignore

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
/bin/

‎group03/763878069/.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>SimpleDataStructure</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>

‎group03/763878069/src/cmj/datastructure/list/ArrayList.java

Lines changed: 154 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,154 @@
1+
package cmj.datastructure.list;
2+
3+
import java.util.Arrays;
4+
import java.util.Collection;
5+
6+
public class ArrayList implements List {
7+
private transient Object[] elementData;
8+
private int size;
9+
10+
/**
11+
* ArrayList初始化无参数构造函数
12+
*/
13+
public ArrayList() {
14+
this(10);
15+
}
16+
17+
/**
18+
* ArrayList带容量的构造函数
19+
*
20+
* @param initialCapacity初始化容量
21+
*/
22+
public ArrayList(int initialCapacity) {
23+
super();
24+
if (initialCapacity < 0)
25+
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
26+
// 新建一个数组
27+
this.elementData = new Object[initialCapacity];
28+
}
29+
30+
/**
31+
* 检查数组的容量
32+
*
33+
* @param neededMinCapacity所需最小的容量
34+
*/
35+
public void ensureCapacity(int neededMinCapacity) {
36+
int currCapacity = elementData.length;// 获取当前数据的全部容量
37+
// 需要扩容的情况
38+
if (neededMinCapacity > currCapacity) {
39+
int newCapacity = (currCapacity * 3) / 2 + 1;// 计算新的容量
40+
elementData = Arrays.copyOf(elementData, newCapacity);
41+
}
42+
}
43+
44+
/**
45+
* 添加数据
46+
*
47+
* @param o要添加的元素
48+
* @return 是否添加成功
49+
*/
50+
public void add(Object o) {
51+
// 确定ArrayList的容量大小
52+
ensureCapacity(size + 1); // Increments modCount!!
53+
// 添加o到ArrayList中
54+
elementData[size++] = o;
55+
}
56+
57+
/**
58+
* 就是检查一下是不是超出数组界限了，超出了就抛出IndexOutBoundsException异常。
59+
*
60+
* @param index要用于检查的索引
61+
*/
62+
private void RangeCheck(int index) {
63+
if (index > size || index < 0)
64+
throw new IndexOutOfBoundsException("Index: " + index + " 超出访问范围");
65+
}
66+
67+
/**
68+
* 向指定的位置添加元素
69+
*
70+
* @param index
71+
* @param o
72+
*/
73+
public void add(int index, Object o) {
74+
RangeCheck(index);
75+
ensureCapacity(size + 1);// 检查容量
76+
77+
/* 将原数组从第index个位置复制到原数组第index+1个位置上，一共移动size-index（也就是后面剩下的）个元素 */
78+
System.arraycopy(elementData, index, elementData, index + 1, size - index);
79+
elementData[index] = o;
80+
size++;
81+
}
82+
83+
public boolean addAll(Collection<? extends Object> c) {
84+
Object[] a = c.toArray();
85+
int growthNum = a.length;
86+
ensureCapacity(size + growthNum); // Increments modCount
87+
System.arraycopy(a, 0, elementData, size, growthNum);
88+
size += growthNum;
89+
return growthNum != 0;
90+
}
91+
92+
public Object get(int index) {
93+
RangeCheck(index);
94+
return elementData[index];
95+
96+
}
97+
98+
public Object remove(int index) {
99+
RangeCheck(index);
100+
int numMoved = size - index - 1;// 删除后需要移动的对象
101+
Object RemovedValue = elementData[index];
102+
if (numMoved > 0)
103+
System.arraycopy(elementData, index + 1, elementData, index, numMoved);
104+
elementData[--size] = null;
105+
return RemovedValue;
106+
}
107+
108+
public int size() {
109+
return size;
110+
}
111+
112+
@Override
113+
public String toString() {
114+
String arraylist = "[";
115+
for (int i = 0; i < size; i++) {
116+
if (i == size - 1) {
117+
arraylist += elementData[i].toString() + "]";
118+
} else {
119+
arraylist += elementData[i].toString() + " ,";
120+
}
121+
}
122+
return arraylist;
123+
}
124+
125+
public static void main(String[] args) {
126+
ArrayList arrayList = new ArrayList(5);
127+
arrayList.add(1);
128+
arrayList.add(2);
129+
arrayList.add(3);
130+
arrayList.add(4);
131+
arrayList.add(5);
132+
arrayList.add(6);
133+
System.out.println(arrayList);
134+
arrayList.add(1, 1234);
135+
System.out.println(arrayList);
136+
arrayList.remove(1);
137+
System.out.println(arrayList);
138+
System.out.println(arrayList.get(5));
139+
140+
ArrayList stringArraylist = new ArrayList(3);
141+
stringArraylist.add("Hello ");
142+
stringArraylist.add("string ");
143+
stringArraylist.add("arraylist");
144+
System.out.println(stringArraylist);
145+
146+
ArrayList mixArraylist = new ArrayList(5);
147+
mixArraylist.add("String");
148+
mixArraylist.add(1);
149+
mixArraylist.add('f');
150+
mixArraylist.add(3.1f);
151+
mixArraylist.add(4L);
152+
System.out.println(mixArraylist);
153+
}
154+
}

‎group03/763878069/src/cmj/datastructure/list/LinkedList.java

Lines changed: 208 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,208 @@
1+
package cmj.datastructure.list;
2+
3+
public class LinkedList implements List {
4+
5+
private Node head;// 头结点
6+
private Node current;// 尾结点
7+
private int size;
8+
9+
public LinkedList() {
10+
// 头指针和尾指针都指向头结点
11+
head = new Node(null, null);
12+
current = head;
13+
}
14+
15+
/**
16+
* 添加元素
17+
*
18+
* @param o——用于添加的元素
19+
*/
20+
public void add(Object o) {
21+
Node node = new Node(o, null);// 新建一个结点
22+
current.next = node;// 尾指针指向它
23+
current = current.next;// 尾指针指向最后一个元素
24+
size++;
25+
}
26+
27+
/**
28+
* 在第index个位置插入元素
29+
*
30+
* @param index——要插入的位置
31+
* @param o——用于插入的对象
32+
*/
33+
public void add(int index, Object o) {
34+
Node node = new Node(o, null);// 新建一个结点
35+
if (index == 0) {
36+
addFirst(o);
37+
} else {
38+
Node curr = (Node) this.get(index - 1);// 获得前一个结点
39+
Node behind = (Node) this.get(index);// 获得后一个结点
40+
// 在这两个结点之间插入新的元素,修改引用指向
41+
curr.next = node;
42+
node.next = behind;
43+
size++;
44+
}
45+
46+
}
47+
48+
/**
49+
* 随机访问index位置上的元素
50+
*
51+
* @param index——元素的位置
52+
* @return——对应的元素
53+
*/
54+
public Object get(int index) {
55+
RangeCheck(index);// 检查索引是否越界
56+
Node curr = head;// 得到头结点的引用
57+
// 从头结点开始遍历到第index个元素
58+
for (int i = 0; i <= index; i++)
59+
curr = curr.next;
60+
return curr;
61+
}
62+
63+
/**
64+
* 删除第index个位置上的元素
65+
*
66+
* @param index
67+
* @return
68+
*/
69+
public Object remove(int index) {
70+
RangeCheck(index);// 检查索引是否越界
71+
if (0 == index) {
72+
return removeFirst();
73+
} else {
74+
Node toRemove = (Node) this.get(index);// 获得要删除的结点
75+
Node preRemove = (Node) this.get(index - 1);// 获得前一个结点
76+
preRemove.next = toRemove.next;// 将前一个结点指向要删除的结点的下一个结点
77+
size--;
78+
return toRemove;
79+
}
80+
81+
}
82+
83+
/**
84+
* 获取元素的大小
85+
*
86+
* @return
87+
*/
88+
public int size() {
89+
return size;
90+
}
91+
92+
/**
93+
* 在链表头部增加元素
94+
*
95+
* @param o——要增加的元素
96+
*/
97+
public void addFirst(Object o) {
98+
Node node = new Node(o, null);// 新建一个结点
99+
node.next = head.next;// 结点指向第一个元素
100+
head.next = node;// 将头结点指向它
101+
size++;
102+
}
103+
104+
/**
105+
* 在链表末尾添加元素
106+
*
107+
* @param o——要添加的元素
108+
*/
109+
public void addLast(Object o) {
110+
Node node = new Node(o, null);// 新建一个结点
111+
current.next.next = node;// 尾结点的next指向新建的结点
112+
current.next = node;// 尾结点引用指向向新结点
113+
size++;
114+
}
115+
116+
/**
117+
* 移除第一个元素
118+
*
119+
* @return——移除元素
120+
*/
121+
public Object removeFirst() {
122+
Node curr = head.next;// 新建一个引用记录第一个结点
123+
head.next = curr.next;// 头指针移动到原第二个元素上
124+
size--;
125+
return curr;
126+
}
127+
128+
/**
129+
* 移除最后一个元素
130+
*
131+
* @return——移除元素
132+
*/
133+
public Object removeLast() {
134+
Node remove = current.next;
135+
Node pre = (Node) this.get(size - 2);// 获得倒数第二个结点
136+
current.next = pre;
137+
pre.next = null;
138+
size--;
139+
return remove;
140+
}
141+
142+
/**
143+
* 就是检查一下是不是超出数组界限了，超出了就抛出IndexOutBoundsException异常。
144+
*
145+
* @param index要用于检查的索引
146+
*/
147+
private void RangeCheck(int index) {
148+
if (index > size || index < 0)
149+
throw new IndexOutOfBoundsException("Index: " + index + " 超出访问范围");
150+
}
151+
152+
/**
153+
* 重写toString()方法
154+
*/
155+
@Override
156+
public String toString() {
157+
String linkedlist = "[";
158+
Node visit = head;
159+
while (visit.next != null) {
160+
visit = visit.next;
161+
if (visit.next == null) {
162+
linkedlist += visit.data.toString() + "]";
163+
} else {
164+
linkedlist += visit.data.toString() + "--->";
165+
}
166+
}
167+
return linkedlist;
168+
}
169+
170+
/**
171+
* 结点内部类，主要要声明为static的
172+
*
173+
* @author think
174+
*
175+
*/
176+
private static class Node {
177+
Object data;
178+
Node next;
179+
180+
public Node(Object data, Node next) {
181+
this.data = data;
182+
this.next = next;
183+
}
184+
185+
}
186+
187+
public static void main(String[] args) {
188+
LinkedList list = new LinkedList();
189+
list.add("a");
190+
list.add("b");
191+
list.add("c");
192+
list.add("d");
193+
System.out.println(list);
194+
System.out.println(((Node) list.get(3)).data);
195+
list.add(4, "4");
196+
System.out.println(list);
197+
list.add(0, "0");
198+
System.out.println(list);
199+
list.addLast("last");
200+
System.out.println(list);
201+
System.out.println("Removed:" + ((Node) list.remove(1)).data);
202+
System.out.println(list);
203+
System.out.println("Removed:" + ((Node) list.removeFirst()).data);
204+
System.out.println(list);
205+
System.out.println("Removed:" + ((Node) list.removeLast()).data);
206+
System.out.println(list);
207+
}
208+
}

0 commit comments

Comments
 (0)