数据基础结构
数据结构研究的是数据如何在计算机中进行组织和存储，使得我们可以高效的获取数据或者修改数据。
在内存世界的增删改查
数据结构的分类
线性结构
树结构
- 二叉树、二分搜索树、AVL、红黑树、Treap、Splay、堆、Trie、线段树、K-D树、并查集、哈夫曼树
图结构
动态数组
Java中的数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| package demo.structure.array;
import demo.helper.model.Student;
public class ArrayMain {
public static void main(String[] args) {
int[] arr = new int[10];
for (int i = 0; i < arr.length; i++) {
arr[i] = i;
}
int[] scores = new int[]{100, 99, 66};
for (int i = 0; i < scores.length; i++) {
System.out.println(scores[i]);
}
for (int score : scores) {
System.out.println(score);
}
}
}
|
数组基础
- 把数据码成一排进行存放
- 索引，从0开始，最后一个元素n-1
- 索引：索引可以有语意（实际的意义，比如：学号），也可以没有语意（没有实际意义，只是进行数据存储）
- 数组最大的优点：快速查询。num[2]（数组[索引值]）
- 数组最好应用于”索引有语意”的情况
- 但并非所有有语意的索引都适用于数组（例如：身份证号，长度太大了，容易造成空间浪费）
- 数组也可以处理“索引没有语意”的情况
- 索引没有语意，如何表示没有的元素？
- 如何添加元素？如何删除元素？
- ……
- 基于Java的数组，二次封装属于我们自己的数组类
二次封装Java中的数组类
自定义数组类
- 获取数组信息
- 添加
- 向数组指定位置添加元素，将指定位置之后的元素都后（向右）移一位
- 向数组中添加元素（最后）
- 向数组中添加元素（最头）
- 获取
- 获取指定索引位置的元素
- 获取数组的头元素
- 获取数组的最后一个元素
- 修改
- 包含
- 搜索
- 删除
- 向数组指定位置删除元素，将指定位置之后的元素都前（向左）移一位
- 向数组中删除元素（最后）
- 向数组中删除元素（最头）
- 扩容
泛型类和动态数组
- 使用Java泛型类，支持多数据类型的数组存储
- 动态数组，是指数组的容量动态伸缩，数组在定义的时候是初始化容量，如果增加的数组元素的个数超过目前的数组容量，就会新生成一个新的数组（是当前数组的2倍的容量），将原有数组的元素复制到新的数组中，并将原数组指向性到新数组，原数组为空则会被Java垃圾回收机制回收
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
| package demo.structure.array;
public class Array<E> {
private E[] data;
private int size;
public Array(int capacity) {
data = (E[]) new Object[capacity];
size = 0;
}
public Array() {
this(10);
}
public int getSize() {
return size;
}
public int getCapacity() {
return data.length;
}
public boolean isEmpty() {
return size == 0;
}
public void add(int index, E e) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("AddLast failed.Array is full");
}
if (size == data.length) {
resize(2 * data.length);
}
for (int i = size - 1; i >= index; i--) {
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
public void addLast(E e) {
add(size, e);
}
public void addFirst(E e) {
add(0, e);
}
public E get(int index) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Get failed.Index is illegal");
}
return data[index];
}
public E getLast() {
return get(size - 1);
}
public E getFirst() {
return get(0);
}
public void set(int index, E e) {
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Get failed.Index is illegal");
}
data[index] = e;
}
public boolean contains(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return true;
}
}
return false;
}
public int find(E e) {
for (int i = 0; i < size; i++) {
if (data[i].equals(e)) {
return i;
}
}
return -1;
}
public E remove(int index) {
if (index < 0 || index > size) {
throw new IllegalArgumentException("Remove failed.Index is illegal");
}
E ret = data[index];
for (int i = index + 1; i < size; i++) {
data[i - 1] = data[i];
}
size--;
data[size] = null;
if (size == data.length / 4 && data.length / 2 != 0) {
resize(data.length / 2);
}
return ret;
}
public void removeElement(E e) {
int index = find(e);
if (index != -1) {
remove(index);
}
}
public E removeFirst() {
return remove(0);
}
public E removeLast() {
return remove(size - 1);
}
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newData[i] = data[i];
}
data = newData;
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("Array:size = %d, capacity = %d \n", size, data.length));
res.append('[');
for (int i = 0; i < size; i++) {
res.append(data[i]);
if (i != size - 1) {
res.append(",");
}
}
res.append(']');
return res.toString();
}
}
|
简单分析动态数组的时间复杂度
- 添加元素 – O(n) (考虑最坏的情况)
- addLast(e) – O(1)
- addFirst(e) – O(n)
- add(index, e) – 严格计算需要一些概率知识 O(n/2) = O(n)
- resize – O(n)
- 如果只对最后一个元素操作应是O(1)，因为引入了resize，resize是O(n)级别的，考虑最坏的情况，则成为O(n)
- 删除操作 – O(n) (考虑最坏的情况)
- removeLast(e) – O(1)
- removeFirst – O(n)
- remove(index, e) – O(n/2) = O(n)
- 如果只对最后一个元素操作应是O(1)，因为引入了resize，resize是O(n)级别的，考虑最坏的情况，则成为O(n)
- 修改操作：已知索引O(1)；未知索引O(n)
- 查询操作: 已知索引O(1)；未知索引O(n)
- get(index) – O(1)
- contains – O(n)
- find(e) – O(n)
- resize O(n)的复杂度分析
- 假设当前capacity=8，并且每一次添加操作都使用addLast
- 第9次addLast操作，触发resize，总共进行了17次操作
- 平均，每次addLast操作，进行2次基本操作
- 由此总结：
- 假设capacity=n，n+1次addLast，触发resize，总共进行2n+1次基本操作
- 平均，每次addLast操作，进行2次基本操作
- 这样均摊计算，时间复杂度是O(1)的
- 在这个例子里，这样均摊计算，比计算最坏情况又意义
均摊复杂度和防止复杂度的震荡
