Skip to content

Commit bf5dbbd

Browse files
mingming-lumingming-lu
committed
2-26 assignment
1 parent 54fe271 commit bf5dbbd

File tree

9 files changed

+355
-0
lines changed

9 files changed

+355
-0
lines changed

‎group08/729770920/.gitignore

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
*.class

‎group08/729770920/2-26/resource/report.txt

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
CPU是计算机的大脑，由运算器和寄存器组成。可以储存指令和数据，并执行指令进行简单的计算。
2+
指令是CPU可以直接执行的命令。
3+
内存是所谓的RAM，读写速度较快。常用来作为CPU和硬盘之间数据交换的缓存。
4+
硬盘容量极大，但是读写速度比内存慢很多。用来存放程序的二进制码，音频，视频等等数据资源。
5+
程序运行时，数据由硬盘拷贝到内存，CPU再从内存里加载包含指令的数据，逐一执行。

‎group08/729770920/2-26/src/com/coding/basic/ArrayList.java

Lines changed: 111 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,111 @@
1+
package com.coding.basic;
2+
3+
public class ArrayList<E> implements List<E> {
4+
5+
private int size;
6+
7+
private E[] data;
8+
9+
public void add(E e){
10+
add(size, e);
11+
}
12+
13+
public ArrayList() {
14+
clear();
15+
}
16+
17+
public ArrayList(int capacity) {
18+
clear();
19+
ensureCapacity(capacity);
20+
}
21+
22+
public void add(int index, E e){
23+
if (index < 0 || index > size) {
24+
throw new IndexOutOfBoundsException(Integer.toString(index));
25+
}
26+
if (data.length == size) {
27+
ensureCapacity(size * 2 + 1);
28+
}
29+
for (int i = size++; i > index; --i) {
30+
data[i] = data[i - 1];
31+
}
32+
data[index] = e;
33+
}
34+
35+
public E get(int index){
36+
return data[index];
37+
}
38+
39+
public E remove(int index){
40+
if (index < 0 || index >= size) {
41+
throw new IndexOutOfBoundsException(Integer.toString(index));
42+
}
43+
E copy = data[index];
44+
--size;
45+
for (int i = index; i < size; ++i) {
46+
data[i] = data[i + 1];
47+
}
48+
return copy;
49+
}
50+
51+
public boolean contains(E e) {
52+
for (int i = 0; i < size; ++i) {
53+
if (data[i] == e) {
54+
return true;
55+
}
56+
}
57+
return false;
58+
}
59+
60+
public void clear() {
61+
size = 0;
62+
data = (E[]) new Object[0];
63+
}
64+
65+
public int size(){
66+
return size;
67+
}
68+
69+
public boolean isEmpty() {
70+
return size == 0;
71+
}
72+
73+
public Iterator<E> iterator(){
74+
return new ArrayListIterator();
75+
}
76+
77+
public void ensureCapacity(int capacity) {
78+
E[] newData = (E[]) new Object[capacity];
79+
for (int i = 0; i < size; ++i) {
80+
newData[i] = data[i];
81+
}
82+
data = newData;
83+
}
84+
85+
public void trimToSize() {
86+
E[] newData = (E[]) new Object[size];
87+
for (int i = 0; i < size; ++i) {
88+
newData[i] = data[i];
89+
}
90+
data = newData;
91+
}
92+
93+
private class ArrayListIterator implements Iterator<E> {
94+
int current = 0;
95+
96+
public boolean hasNext() {
97+
return current < size;
98+
}
99+
100+
public E next() {
101+
if (!hasNext()) {
102+
throw new java.util.NoSuchElementException();
103+
}
104+
return data[current++];
105+
}
106+
107+
public void remove() {
108+
ArrayList.this.remove(current);
109+
}
110+
}
111+
}

‎group08/729770920/2-26/src/com/coding/basic/Iterator.java

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,9 @@
1+
package com.coding.basic;
2+
3+
public interface Iterator<E> {
4+
boolean hasNext();
5+
6+
E next();
7+
8+
void remove();
9+
}

‎group08/729770920/2-26/src/com/coding/basic/LinkedList.java

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

‎group08/729770920/2-26/src/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+
public interface List<E> {
4+
void add(E e);
5+
6+
void add(int index, E e);
7+
8+
void clear();
9+
10+
E get(int index);
11+
12+
E remove(int index);
13+
14+
int size();
15+
16+
boolean contains(E e);
17+
18+
Iterator<E> iterator();
19+
}

‎group08/729770920/2-26/src/com/coding/basic/Queue.java

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
package com.coding.basic;
2+
3+
public class Queue<E> {
4+
private LinkedList<E> data = new LinkedList<>();
5+
6+
public void enQueue(E e){
7+
data.addFirst(e);
8+
}
9+
10+
public Object deQueue() {
11+
return data.removeLast();
12+
}
13+
14+
public boolean isEmpty() {
15+
return data.size() == 0;
16+
}
17+
18+
public int size(){
19+
return data.size();
20+
}
21+
}

‎group08/729770920/2-26/src/com/coding/basic/Stack.java

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package com.coding.basic;
2+
3+
public class Stack<E> {
4+
private LinkedList<E> data = new LinkedList<>();
5+
6+
public void push(E e) {
7+
data.addFirst(e);
8+
}
9+
10+
public Object pop() {
11+
return data.removeFirst();
12+
}
13+
14+
public Object peek() {
15+
return data.get(0);
16+
}
17+
18+
public boolean isEmpty() {
19+
return data.size() == 0;
20+
}
21+
22+
public int size() {
23+
return data.size();
24+
}
25+
}

‎group08/729770920/729770920.md renamed to ‎group08/729770920/README.md

File renamed without changes.

0 commit comments

Comments
 (0)