Skip to content

Commit 9554b78

Browse files
hackfengJamhackfengJam
committed
动态数组
1 parent c25d77a commit 9554b78

File tree

3 files changed

+354
-0
lines changed

3 files changed

+354
-0
lines changed

‎Array/src/Array.java‎

Lines changed: 173 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,173 @@
1+
public class Array<E> {
2+
3+
private E[] data;
4+
private int size;
5+
6+
/**
7+
* 构造函数，传入数组的容量 capacity 构造 Array
8+
*
9+
* @param capacity
10+
*/
11+
public Array(int capacity) {
12+
data = (E[]) new Object[capacity]; // new E[capacity] 不支持该语法，历史遗留问题
13+
size = 0;
14+
}
15+
16+
// 无参数的构造函数，默认数组的容量 capacity=10
17+
public Array() {
18+
this(10);
19+
}
20+
21+
// 获取数组中的元素个数
22+
public int getSize() {
23+
return size;
24+
}
25+
26+
// 获取数组的容量
27+
public int getCapacity() {
28+
return data.length;
29+
}
30+
31+
// 返回数组是否为空
32+
public boolean isEmpty() {
33+
return size == 0;
34+
}
35+
36+
// 向所有元素后添加一个新元素
37+
public void addLast(E e) {
38+
/*if (size == data.length) {
39+
throw new IllegalArgumentException("AddLast failed. Array is full.");
40+
}
41+
42+
data[size] = e;
43+
size++;*/
44+
add(size, e);
45+
}
46+
47+
// 在所有元素前添加一个新元素
48+
public void addFirst(E e) {
49+
add(0, e);
50+
}
51+
52+
// 在第 index 个位置插入一个新元素 e
53+
public void add(int index, E e) {
54+
55+
if (index < 0 || index > size) {
56+
throw new IllegalArgumentException("add failed. Require index >=0 and index < size.");
57+
}
58+
if (size == data.length) {
59+
resize(2 * data.length);
60+
}
61+
62+
63+
for (int i = size - 1; i >= index; i--) {
64+
data[i + 1] = data[i];
65+
}
66+
data[index] = e;
67+
size++;
68+
}
69+
70+
//获取 index 索引位置的元素
71+
public E get(int index) {
72+
if (index < 0 || index >= size) {
73+
throw new IllegalArgumentException("Get failed. Index is illegal.");
74+
}
75+
return data[index];
76+
}
77+
78+
// 修改 index 索引位置的元素
79+
public void set(int index, E e) {
80+
if (index < 0 || index >= size) {
81+
throw new IllegalArgumentException("Set failed. Index is illegal.");
82+
}
83+
data[index] = e;
84+
}
85+
86+
// 查找数组中是否有元素 e
87+
public boolean contains(E e) {
88+
for (int i = 0; i < size; i++) {
89+
if (data[i].equals(e)) {
90+
return true;
91+
}
92+
}
93+
return false;
94+
}
95+
96+
// 查找数组中元素 e 所在的索引，如果不存在元素 e，则返回 -1
97+
public int find(E e) {
98+
for (int i = 0; i < size; i++) {
99+
if (data[i].equals(e)) {
100+
return i;
101+
}
102+
}
103+
return -1;
104+
}
105+
106+
// 从数组中删除 index 位置的元素，返回删除的元素
107+
public E remove(int index) {
108+
109+
if (index < 0 || index > size) {
110+
throw new IllegalArgumentException("remove failed. Index is illegal.");
111+
}
112+
E ret = data[index];
113+
for (int i = index + 1; i < size; i++) {
114+
data[i - 1] = data[i];
115+
}
116+
size--;
117+
118+
// 该行可选
119+
data[size] = null; // loitering objects != memory leak
120+
121+
if (size == data.length / 2) {
122+
resize(data.length / 2);
123+
}
124+
125+
return ret;
126+
}
127+
128+
129+
// 从数组中删除第一个元素，返回删除的元素
130+
public E removeFirst(int index) {
131+
132+
return remove(0);
133+
}
134+
135+
// 从数组中删除最后元素，返回删除的元素
136+
public E removeLast(int index) {
137+
138+
return remove(size - 1);
139+
}
140+
141+
// 从数组中删除元素e
142+
public void removeElement(E e) {
143+
int index = find(e);
144+
if (index != -1) {
145+
remove(index);
146+
}
147+
}
148+
149+
150+
@Override
151+
public String toString() {
152+
StringBuilder res = new StringBuilder();
153+
res.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
154+
res.append("[");
155+
for (int i = 0; i < size; i++) {
156+
res.append(data[i]);
157+
if (i != size - 1) {
158+
res.append(", ");
159+
}
160+
}
161+
res.append("]");
162+
return res.toString();
163+
}
164+
165+
166+
private void resize(int newCapacity) {
167+
E[] newData = (E[]) new Object[newCapacity];
168+
for (int i = 0; i < size; i++) {
169+
newData[i] = data[i];
170+
}
171+
data = newData;
172+
}
173+
}

‎Array/src/Main.java‎

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
public class Main {
2+
public static void main(String[] args) {
3+
Array<Integer> arr = new Array<>();
4+
for (int i = 0; i < 10; i++) {
5+
arr.addLast(i);
6+
}
7+
System.out.println(arr);
8+
9+
arr.add(1, 100);
10+
System.out.println(arr);
11+
12+
arr.addFirst(-1);
13+
System.out.println(arr);
14+
15+
arr.remove(2);
16+
System.out.println(arr);
17+
18+
arr.remove(1);
19+
System.out.println(arr);
20+
}
21+
}

‎Array/src/StaticArray.java‎

Lines changed: 160 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,160 @@
1+
public class StaticArray<E> {
2+
3+
private E[] data;
4+
private int size;
5+
6+
/**
7+
* 构造函数，传入数组的容量 capacity 构造 Array
8+
*
9+
* @param capacity
10+
*/
11+
public StaticArray(int capacity) {
12+
data = (E[]) new Object[capacity]; // new E[capacity] 不支持该语法，历史遗留问题
13+
size = 0;
14+
}
15+
16+
// 无参数的构造函数，默认数组的容量 capacity=10
17+
public StaticArray() {
18+
this(10);
19+
}
20+
21+
// 获取数组中的元素个数
22+
public int getSize() {
23+
return size;
24+
}
25+
26+
// 获取数组的容量
27+
public int getCapacity() {
28+
return data.length;
29+
}
30+
31+
// 返回数组是否为空
32+
public boolean isEmpty() {
33+
return size == 0;
34+
}
35+
36+
// 向所有元素后添加一个新元素
37+
public void addLast(E e) {
38+
/*if (size == data.length) {
39+
throw new IllegalArgumentException("AddLast failed. Array is full.");
40+
}
41+
42+
data[size] = e;
43+
size++;*/
44+
add(size, e);
45+
}
46+
47+
// 在所有元素前添加一个新元素
48+
public void addFirst(E e) {
49+
add(0, e);
50+
}
51+
52+
// 在第 index 个位置插入一个新元素 e
53+
public void add(int index, E e) {
54+
55+
if (size == data.length) {
56+
throw new IllegalArgumentException("add failed. Array is full.");
57+
}
58+
59+
if (index < 0 || index > size) {
60+
throw new IllegalArgumentException("add failed. Array is full.");
61+
}
62+
63+
for (int i = size - 1; i >= index; i--) {
64+
data[i + 1] = data[i];
65+
}
66+
data[index] = e;
67+
size++;
68+
}
69+
70+
//获取 index 索引位置的元素
71+
public E get(int index) {
72+
if (index < 0 || index >= size) {
73+
throw new IllegalArgumentException("Get failed. Index is illegal.");
74+
}
75+
return data[index];
76+
}
77+
78+
// 修改 index 索引位置的元素
79+
public void set(int index, E e) {
80+
if (index < 0 || index >= size) {
81+
throw new IllegalArgumentException("Set failed. Index is illegal.");
82+
}
83+
data[index] = e;
84+
}
85+
86+
// 查找数组中是否有元素 e
87+
public boolean contains(E e) {
88+
for (int i = 0; i < size; i++) {
89+
if (data[i].equals(e)) {
90+
return true;
91+
}
92+
}
93+
return false;
94+
}
95+
96+
// 查找数组中元素 e 所在的索引，如果不存在元素 e，则返回 -1
97+
public int find(E e) {
98+
for (int i = 0; i < size; i++) {
99+
if (data[i].equals(e)) {
100+
return i;
101+
}
102+
}
103+
return -1;
104+
}
105+
106+
// 从数组中删除 index 位置的元素，返回删除的元素
107+
public E remove(int index) {
108+
109+
if (index < 0 || index > size) {
110+
throw new IllegalArgumentException("remove failed. Index is illegal.");
111+
}
112+
E ret = data[index];
113+
for (int i = index + 1; i < size; i++) {
114+
data[i - 1] = data[i];
115+
}
116+
size--;
117+
118+
// 该行可选
119+
data[size] = null; // loitering objects != memory leak
120+
121+
return ret;
122+
}
123+
124+
125+
// 从数组中删除第一个元素，返回删除的元素
126+
public E removeFirst(int index) {
127+
128+
return remove(0);
129+
}
130+
131+
// 从数组中删除最后元素，返回删除的元素
132+
public E removeLast(int index) {
133+
134+
return remove(size - 1);
135+
}
136+
137+
// 从数组中删除元素e
138+
public void removeElement(E e) {
139+
int index = find(e);
140+
if (index != -1) {
141+
remove(index);
142+
}
143+
}
144+
145+
146+
@Override
147+
public String toString() {
148+
StringBuilder res = new StringBuilder();
149+
res.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
150+
res.append("[");
151+
for (int i = 0; i < size; i++) {
152+
res.append(data[i]);
153+
if (i != size - 1) {
154+
res.append(", ");
155+
}
156+
}
157+
res.append("]");
158+
return res.toString();
159+
}
160+
}

0 commit comments

Comments
 (0)