Skip to content

Commit a641738

Browse files
jodie-zssjodie-zss
authored
Merge pull request onlyliuxin#1 from jy97799/master
2.26作业
2 parents 480b655 + 3888ae8 commit a641738

File tree

7 files changed

+297
-0
lines changed

7 files changed

+297
-0
lines changed

‎group15/1507_977996067/README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
### qq 977996067 的作业文件夹

‎group15/1507_977996067/src/task1/MyArrayList.java

Lines changed: 95 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,95 @@
1+
package task1;
2+
3+
import java.util.Arrays;
4+
import java.util.Iterator;
5+
6+
/**
7+
* ArrayList实现
8+
*/
9+
public class MyArrayList<T> implements MyList<T> {
10+
11+
//列表元素的个数
12+
private int size;
13+
//列表存放的元素
14+
private Object[] elements;
15+
//初始容量10
16+
private static final int DEFAULT_CAPACITY = 10;
17+
18+
public MyArrayList() {
19+
elements = new Object[DEFAULT_CAPACITY];
20+
}
21+
22+
public MyArrayList(int capacity) {
23+
elements = new Object[capacity <= DEFAULT_CAPACITY ? DEFAULT_CAPACITY : capacity];
24+
}
25+
26+
@Override
27+
public void add(T o) {
28+
add(size, o);
29+
}
30+
31+
@Override
32+
public void add(int index, T o) {
33+
if (index < 0 || index > size)
34+
throw new IndexOutOfBoundsException("index " + index + " 不合法");
35+
if (size >= elements.length)
36+
ensureCapacity((size >> 1) + size);
37+
elements[index] = o;
38+
size++;
39+
}
40+
41+
@Override
42+
@SuppressWarnings("unchecked")
43+
public T get(int index) {
44+
if (index < 0 || index >= size)
45+
throw new IndexOutOfBoundsException("index " + index + " 越界");
46+
return (T) elements[index];
47+
}
48+
49+
@Override
50+
@SuppressWarnings("unchecked")
51+
public T remove(int index) {
52+
if (index < 0 || index >= size)
53+
throw new IndexOutOfBoundsException("index " + index + " 越界");
54+
T removeElement = (T) elements[index];
55+
System.arraycopy(elements, index + 1, elements, index, elements.length - index - 1);
56+
size--;
57+
return removeElement;
58+
}
59+
60+
@Override
61+
public int size() {
62+
return size;
63+
}
64+
65+
public Iterator<T> iterator() {
66+
return new MyItr();
67+
}
68+
69+
private void ensureCapacity(int newCapacity) {
70+
elements = Arrays.copyOf(elements, newCapacity);
71+
}
72+
73+
private class MyItr implements Iterator<T> {
74+
75+
private int current = 0;
76+
77+
@Override
78+
public boolean hasNext() {
79+
return current < size;
80+
}
81+
82+
@Override
83+
@SuppressWarnings("unchecked")
84+
public T next() {
85+
return (T) elements[current++];
86+
}
87+
88+
@Override
89+
public void remove() {
90+
if (current == 0)
91+
throw new IllegalStateException("先调用next后才能再调用remove");
92+
MyArrayList.this.remove(--current);
93+
}
94+
}
95+
}

‎group15/1507_977996067/src/task1/MyLinkedList.java

Lines changed: 130 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,130 @@
1+
package task1;
2+
3+
import java.util.Iterator;
4+
5+
/**
6+
* LinkedList 实现
7+
*/
8+
public class MyLinkedList<T> implements MyList<T> {
9+
10+
//存放的元素数量
11+
private int size;
12+
13+
private Node<T> head;
14+
15+
public MyLinkedList() {
16+
head = new Node<>(null, null);
17+
}
18+
19+
@Override
20+
public void add(T o) {
21+
add(size, o);
22+
}
23+
24+
@Override
25+
public void add(int index, T o) {
26+
if (index < 0 || index > size)
27+
throw new IndexOutOfBoundsException("index " + index + " 不合法");
28+
Node<T> targetNode = new Node<>(null, o);
29+
Node<T> targetPrevNode = getPrevNode(index);
30+
targetNode.next = targetPrevNode.next;
31+
targetPrevNode.next = targetNode;
32+
size++;
33+
}
34+
35+
@Override
36+
public T get(int index) {
37+
checkIndexRange(index);
38+
return getPrevNode(index).next.data;
39+
}
40+
41+
42+
@Override
43+
public T remove(int index) {
44+
checkIndexRange(index);
45+
Node<T> prevNode = getPrevNode(index);
46+
Node<T> nodeToRemove = prevNode.next;
47+
prevNode.next = nodeToRemove.next;
48+
size--;
49+
return nodeToRemove.data;
50+
}
51+
52+
@Override
53+
public int size() {
54+
return size;
55+
}
56+
57+
public void addFirst(T o) {
58+
add(0, o);
59+
60+
}
61+
62+
public void addLast(T o) {
63+
add(size, o);
64+
}
65+
66+
public T removeFirst() {
67+
return remove(0);
68+
}
69+
70+
public T removeLast() {
71+
return remove(size - 1);
72+
}
73+
74+
75+
public Iterator<T> iterator() {
76+
return new MyLinkedItr();
77+
}
78+
79+
/**
80+
* 找到位置为index的前一个node
81+
*
82+
* @param index 索引值
83+
*/
84+
85+
private Node<T> getPrevNode(int index) {
86+
Node<T> targetPrevNode = head;
87+
for (int i = 0; i < index; i++) {
88+
targetPrevNode = targetPrevNode.next;
89+
}
90+
return targetPrevNode;
91+
}
92+
93+
/**
94+
* 检查索引是否越界
95+
*
96+
* @param index 索引值
97+
*/
98+
private void checkIndexRange(int index) {
99+
if (index < 0 || index >= size)
100+
throw new IndexOutOfBoundsException("index " + index + " 越界");
101+
}
102+
103+
private static class Node<T> {
104+
private Node<T> next;
105+
private T data;
106+
107+
private Node(Node<T> next, T data) {
108+
this.next = next;
109+
this.data = data;
110+
}
111+
}
112+
113+
private class MyLinkedItr implements Iterator<T> {
114+
115+
private Node<T> currentNode = head;
116+
117+
@Override
118+
public boolean hasNext() {
119+
return currentNode.next != null;
120+
}
121+
122+
@Override
123+
public T next() {
124+
Node<T> nextNode = currentNode.next;
125+
T data = nextNode.data;
126+
currentNode = nextNode;
127+
return data;
128+
}
129+
}
130+
}

‎group15/1507_977996067/src/task1/MyList.java

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
package task1;
2+
3+
/**
4+
* List 接口
5+
*/
6+
public interface MyList<T> {
7+
public void add(T o);
8+
9+
public void add(int index, T o);
10+
11+
public T get(int index);
12+
13+
public T remove(int index);
14+
15+
public int size();
16+
}

‎group15/1507_977996067/src/task1/MyQueue.java

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package task1;
2+
3+
/**
4+
* Queue 实现
5+
*/
6+
public class MyQueue<T> {
7+
private MyLinkedList<T> elementData = new MyLinkedList<T>();
8+
9+
public void enQueue(T o) {
10+
elementData.addFirst(o);
11+
}
12+
13+
public T deQueue() {
14+
return elementData.removeLast();
15+
}
16+
17+
public boolean isEmpty() {
18+
return elementData.size() == 0;
19+
}
20+
21+
public int size() {
22+
return elementData.size();
23+
}
24+
25+
}

‎group15/1507_977996067/src/task1/MyStack.java

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package task1;
2+
3+
/**
4+
* Stack 实现
5+
*/
6+
public class MyStack<T> {
7+
private MyLinkedList<T> elementData = new MyLinkedList<T>();
8+
9+
public void push(T o) {
10+
elementData.addFirst(o);
11+
}
12+
13+
public T pop() {
14+
return elementData.removeFirst();
15+
}
16+
17+
public T peek() {
18+
return elementData.get(0);
19+
}
20+
21+
public boolean isEmpty() {
22+
return elementData.size() == 0;
23+
}
24+
25+
public int size() {
26+
return elementData.size();
27+
}
28+
29+
}

‎group15/1507_977996067/src/task1/README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
###2.26作业：实现简单的数据结构

0 commit comments

Comments
 (0)