Skip to content

Commit 3c803ac

Browse files
KilienKilien
committed
week01
1 parent 28621ba commit 3c803ac

File tree

6 files changed

+449
-0
lines changed

6 files changed

+449
-0
lines changed

‎group09/790466157/src/com/coding/basic/Iterator.java

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

‎group09/790466157/src/com/coding/basic/List.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 List {
4+
public void add(Object o);
5+
public void add(int index, Object o);
6+
public Object get(int index);
7+
public Object remove(int index);
8+
public int size();
9+
}

‎group09/790466157/src/com/coding/basic/MyArrayList.java

Lines changed: 133 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,133 @@
1+
package com.coding.basic;
2+
import java.util.Arrays;
3+
import java.util.NoSuchElementException;
4+
5+
import com.coding.basic.List;
6+
import com.coding.basic.Iterator;
7+
8+
public class MyArrayList implements List {
9+
10+
private int size = 0;
11+
12+
private Object[] elementData = new Object[100];
13+
14+
private final static int MAX_ARRAY_LENGTH = Integer.MAX_VALUE;
15+
16+
private static final int DEFAULT_CAPACITY = 10;
17+
18+
19+
//无常构造函数
20+
public MyArrayList(){
21+
this(DEFAULT_CAPACITY);
22+
}
23+
24+
public MyArrayList(int size){
25+
if (size < 0){
26+
throw new IllegalArgumentException("默认的大小" + size);
27+
}
28+
else{
29+
elementData = new Object[size];
30+
}
31+
}
32+
33+
public void add(Object o){
34+
isCapacityEnough(size+1);
35+
elementData[size++] = o;
36+
}
37+
38+
private void isCapacityEnough(int size){
39+
//判断是否超过初始容量，是否需要扩容
40+
if (size > DEFAULT_CAPACITY){
41+
explicitCapacity(size);
42+
}
43+
if (size < 0){
44+
throw new OutOfMemoryError();
45+
}
46+
}
47+
48+
private void explicitCapacity(int capacity){
49+
int oldCapacity = elementData.length;
50+
//新容量=旧容量 + （旧容量/2） 扩容1.5倍【右移操作符相当于除以2】
51+
int newLength = oldCapacity + (oldCapacity >> 1);
52+
if (newLength - capacity < 0){
53+
newLength = capacity;
54+
}
55+
//判断newLength的长度
56+
//如果超过上面定义的数组最大长度则判断要需要的扩容空间是否大于数组最大长度
57+
//如果大于则newLength为 MAX_VALUE ，否则为 MAX_ARRAY_LENGTH。
58+
if (newLength > (MAX_ARRAY_LENGTH)){
59+
newLength = (capacity > MAX_ARRAY_LENGTH ? Integer.MAX_VALUE : MAX_ARRAY_LENGTH);
60+
}
61+
//调用copyof进行扩容
62+
elementData = Arrays.copyOf(elementData, newLength);
63+
}
64+
65+
public void add(int index, Object o){
66+
67+
checkRangeForAdd(index);
68+
isCapacityEnough(size +1);
69+
// 将 elementData中从Index位置开始、长度为size-index的元素，
70+
// 拷贝到从下标为index+1位置开始的新的elementData数组中。
71+
// 即将当前位于该位置的元素以及所有后续元素右移一个位置。
72+
System.arraycopy(elementData, index, elementData, index + 1, size - index);
73+
elementData[index] = o;
74+
size++;
75+
}
76+
77+
//判断是否越界
78+
private void checkRangeForAdd(int index){
79+
if (index < 0 || index > size){
80+
throw new IndexOutOfBoundsException("指定的index越界");
81+
}
82+
}
83+
84+
// 返回此列表中指定位置上的元素。
85+
public Object get(int index){
86+
checkRange(index);
87+
return elementData[index];
88+
}
89+
90+
//判断是否越界
91+
private void checkRange(int index){
92+
if (index >= size || index < 0){
93+
throw new IndexOutOfBoundsException("指定的index越界");
94+
}
95+
}
96+
97+
public Object remove(int index){
98+
Object value = get(index);
99+
int moveSize = size - index -1;
100+
if (moveSize >0){
101+
System.arraycopy(elementData, index +1, elementData, index, size - index -1);
102+
103+
}
104+
elementData[--size] = null;
105+
return value;
106+
}
107+
108+
public int size(){
109+
return size;
110+
}
111+
112+
//迭代器
113+
public Iterator iterator(Object o){
114+
return new ArrayListIterator();
115+
}
116+
117+
118+
private class ArrayListIterator implements Iterator{
119+
private int currentIndex=0;
120+
121+
public boolean hasNext() {
122+
return currentIndex < size();
123+
}
124+
125+
public Object next() {
126+
if (!hasNext()){
127+
throw new NoSuchElementException();
128+
}
129+
return new Object[currentIndex + 1];
130+
}
131+
}
132+
133+
}

‎group09/790466157/src/com/coding/basic/MyLinkedList.java

Lines changed: 159 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,159 @@
1+
package com.coding.basic;
2+
3+
public class MyLinkedList<E> {
4+
5+
private int size;
6+
7+
private Node<E> first;
8+
9+
private Node<E> last;
10+
11+
12+
public boolean add(E element) {
13+
addAtLast(element);
14+
return true;
15+
}
16+
17+
private void addAtLast(E element) {
18+
Node<E> l = last;
19+
Node<E> node = new Node<E>(element, null, l);
20+
last = node;
21+
if (l == null) {
22+
first = node;
23+
} else {
24+
l.next = node;
25+
}
26+
size++;
27+
}
28+
29+
public void add(int index, E element) {
30+
checkRangeForAdd(index);
31+
if (index == size) {
32+
addAtLast(element);
33+
} else {
34+
Node<E> l = node(index);
35+
addBeforeNode(element, l);
36+
}
37+
}
38+
39+
private void addBeforeNode(E element, Node<E> specifiedNode) {
40+
Node<E> preNode = specifiedNode.prev;
41+
Node<E> newNode = new Node<E>(element, specifiedNode, preNode);
42+
if (preNode == null) {
43+
first = newNode;
44+
} else {
45+
preNode.next = newNode;
46+
}
47+
specifiedNode.prev = newNode;
48+
size++;
49+
}
50+
51+
52+
private Node<E> node(int index) {
53+
if (index < (size << 1)) {
54+
Node<E> cursor = first;
55+
for (int i = 0; i < index; i++) {
56+
cursor = cursor.next;
57+
}
58+
return cursor;
59+
} else {
60+
Node<E> cursor = last;
61+
for (int i = size - 1; i > index; i--) {
62+
cursor = cursor.prev;
63+
}
64+
return cursor;
65+
}
66+
}
67+
68+
private void checkRangeForAdd(int index) {
69+
if (index > size || index < 0) {
70+
throw new IndexOutOfBoundsException("指定的index超过界限");
71+
}
72+
}
73+
74+
public E get(int index) {
75+
checkRange(index);
76+
return node(index).item;
77+
}
78+
79+
private void checkRange(int index) {
80+
if (index >= size || index < 0) {
81+
throw new IndexOutOfBoundsException("指定index超过界限");
82+
}
83+
}
84+
85+
public int indexOf(Object element) {
86+
Node<E> cursor = first;
87+
int count = 0;
88+
while (cursor != null) {
89+
if (element != null) {
90+
if (element.equals(cursor.item)) {
91+
return count;
92+
}
93+
}else{
94+
if (cursor.item == null) {
95+
return count;
96+
}
97+
}
98+
count ++;
99+
cursor = cursor.next;
100+
}
101+
return -1;
102+
}
103+
104+
public E remove(int index) {
105+
checkRange(index);
106+
return deleteLink(index);
107+
}
108+
109+
public boolean remove(Object o) {
110+
int index = indexOf(o);
111+
if (index < 0){
112+
return false;
113+
}
114+
deleteLink(index);
115+
return true;
116+
}
117+
118+
private E deleteLink(int index) {
119+
Node<E> l = node(index);
120+
E item = l.item;
121+
Node<E> prevNode = l.prev;
122+
Node<E> nextNode = l.next;
123+
124+
if (prevNode == null) {
125+
first = nextNode;
126+
}else{
127+
prevNode.next = nextNode;
128+
l.next = null;
129+
}
130+
131+
if (nextNode == null) {
132+
last = prevNode;
133+
}else{
134+
nextNode.prev = prevNode;
135+
l.prev = null;
136+
}
137+
size--;
138+
l.item = null;
139+
return item;
140+
}
141+
142+
143+
144+
public int size(){
145+
return size;
146+
}
147+
private static class Node<E> {
148+
E item;
149+
Node<E> next;
150+
Node<E> prev;
151+
152+
public Node(E item, Node<E> next, Node<E> prev) {
153+
this.item = item;
154+
this.next = next;
155+
this.prev = prev;
156+
157+
}
158+
}
159+
}

‎group09/790466157/src/com/coding/basic/Queue.java

Lines changed: 68 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,68 @@
1+
package com.coding.basic;
2+
import java.util.Arrays;
3+
4+
public class Queue {
5+
private static final int CAPACITY = 10;
6+
private static int capacity;
7+
private static int front;
8+
private static int tail;
9+
private static Object[] array;
10+
11+
public Queue(){
12+
this.capacity = CAPACITY;
13+
array = new Object[capacity];
14+
front = tail = 0;
15+
}
16+
17+
public void enQueue(Object o) throws ExceptionQueueFull {
18+
if (size() == capacity -1)
19+
throw new ExceptionQueueFull("Queue is full");
20+
array[tail] = o;
21+
tail = (tail +1) % capacity;
22+
}
23+
24+
public Object deQueue() throws ExceptionQueueEmpty{
25+
Object o;
26+
if (isEmpty())
27+
throw new ExceptionQueueEmpty("Queue is empty");
28+
o = array[front];
29+
front = (front + 1) % capacity;
30+
return o;
31+
}
32+
33+
public boolean isEmpty(){
34+
return (front == tail);
35+
}
36+
37+
public int size(){
38+
if (isEmpty())
39+
return 0;
40+
else
41+
return (capacity + tail - front) % capacity;
42+
}
43+
44+
public class ExceptionQueueEmpty extends Exception {
45+
// Constructor
46+
public ExceptionQueueEmpty() {
47+
48+
}
49+
50+
// Constructor with parameters
51+
public ExceptionQueueEmpty(String mag) {
52+
System.out.println(mag);
53+
}
54+
}
55+
56+
public class ExceptionQueueFull extends Exception {
57+
58+
// Constructor
59+
public ExceptionQueueFull() {
60+
61+
}
62+
63+
// Constructor with parameters
64+
public ExceptionQueueFull(String mag) {
65+
System.out.println(mag);
66+
}
67+
}
68+
}

0 commit comments

Comments
 (0)