1、数据结构研究的是数据如何在计算机中进行组织和存储,使得我们可以高效的获取数据或者修改数据。
数据结构包含三种结构,线性结构,树结构,图结构。其中,线性结构包含数组,栈,队列,链表,哈希表等等。树结构包含二叉树,二分搜索树,AVL树,红黑树,Treap,Splay,堆,Tril,K-D树,并查集,哈夫曼树等等。图结构包含邻接矩阵,邻接表。
2、时间复杂度O(1), O(n), O(logn), O(nlogn),O(n^2),其中,大O描述的是算法的运行时间和输入数据之间的关系,n是指数据元素的个数。O后面的括号中有一个函数,指明某个算法的耗时/耗空间与数据增长量之间的关系。其中的n代表输入数据的量。
3、数据结构之数组。数据的查询,修改,删除,增加,动态扩容以及数组的缩容。
3.1、添加元素的时间复杂度分析。 1)、addLast(e),时间复杂度O(1),直接在数组最后赋值即可,和数组的容量无关。如果是进行了扩容reszie操作,那么时间复杂度是O(n)。 2)、addFirst(e),时间复杂度O(n),在数组头部添加元素,需要将所有元素后移一位。 3)、add(index,e),按照概率论,时间复杂度近似O(n),在该索引index位置插入一个元素e,和index的值有关的,比如index的值等于0或者index等于size。 3.2、删除元素的时间复杂度分析。 1)、removeFirst(e),时间复杂度是O(1),如果是进行了缩容reszie操作,那么时间复杂度是O(n)。 2)、removeLast(e),时间复杂度是O(n)。 3)、remove(index,e),时间复杂度是O(n)。 3.3、修改元素的时间复杂度分析。 1)、set(index,e),时间复杂度是O(1),数组支持随机访问哦。 3.4、查询元素的时间复杂度分析。 1)、get(index),时间复杂度是O(1)。 2)、contains(e),时间复杂度是O(n)。 3)、find(e),时间复杂度是O(n)。 3.5、综上所述,增加的时间复杂度是O(n)。删除的时间复杂度是O(n)。修改的时间复杂度是,如果已知索引O(1),未知索引O(n)。查找的时间复杂度是,如果已知索引O(1),未知索引O(n)。
1 package com.company;
2
3
4 /**
5 *
6 */
7 public class Array<E> {
8
9 private E[] data;//定义数组
10 private int size;//数组实际的长度
11
12 /**
13 * 构造函数,传入数组的容量capacity构造Array
14 *
15 * @param capacity 初始化数据的容量长度
16 */
17 public Array(int capacity) {
18 // 使用泛型,可以创建任意类型的数组类型
19 data = (E[]) new Object[capacity];
20 // 初始化数组的实际内容的长度为0
21 size = 0;
22 }
23
24 /**
25 * 无参数的构造函数,默认数组的容量capacity=10
26 */
27 public Array() {
28 // 无参构造函数,指定初始化数组容量长度为0
29 this(10);
30 }
31
32 /**
33 * 获取数组中的元素个数
34 *
35 * @return
36 */
37 public int getSize() {
38 // 获取到数组中的元素个数
39 return size;
40 }
41
42 /**
43 * 获取数组的容量
44 *
45 * @return
46 */
47 public int getCapacity() {
48 // 获取到数组的容量
49 return data.length;
50 }
51
52 /**
53 * 返回数组是否为空
54 *
55 * @return
56 */
57 public boolean isEmpty() {
58 // 判断数组的长度是否为空
59 return size == 0;
60 }
61
62
63 /**
64 * 向所有元素后添加一个新元素
65 *
66 * @param e
67 */
68 public void addLast(E e) {
69 // if (size == data.length) {
70 // throw new IllegalArgumentException("AddLast failed,Array is full......");
71 // } else {
72 // 在数组的末尾添加一个元素
73 // data[size] = e;
74 // 添加元素以后数组长度加一
75 // size++;
76 // }
77
78 // 调用公共的方法,其实就是在数组的实际长度后面添加指定的元素的。
79
80 // 调用添加数组的方法,参数一,传入数组实际的长度,参数二,添加的元素
81 add(size, e);
82 }
83
84 /**
85 * 在第一个位置添加元素,在所有元素前添加一个新元素
86 *
87 * @param e
88 */
89 public void addFirst(E e) {
90 // 在数组的第一个位置添加元素
91 add(0, e);
92 }
93
94
95 /**
96 * 在第index个位置插入一个新元素e
97 *
98 * @param index 在第index个位置
99 * @param e 添加的元素内容
100 */
101 public void add(int index, E e) {
102 // 判断位置index是否小于0或者索引index是否大于数组的实际长度size
103 if (index < 0 || index > size) {
104 throw new IllegalArgumentException("add failed,Require index >= 0 and index <= size.......");
105 }
106
107 // 判断实际长度size是否等于数组的长度
108 if (size == data.length) {
109 // 可以直接抛出异常
110 // throw new IllegalArgumentException("add failed,Array is full......");
111 // 调用数组扩容的方法,扩容的长度为元数组长度的2倍
112 resize(2 * data.length);
113 }
114
115 // 添加元素,就是在最后一个位置,将元素添加进去,即size的位置
116 // 从后向前移动,从后面的元素向后移动
117 // 如果传入的index是size,则初始化的位置是size-1,那么i的值大于等于传入的index(即size的值),i递减
118
119 // int i = size - 1是数组的实际长度的,即最后一个位置的元素
120 // i >= index,是在指定索引位置添加索引
121 // i--是为了将前面的元素向后面移动的。
122 for (int i = size - 1; i >= index; i--) {
123 // 后一个索引位置赋予前一个索引位置的值
124 data[i + 1] = data[i];
125 }
126 // 将元素的内容插入到数组的index索引位置
127 data[index] = e;
128 // 数组的size递增
129 size++;
130 }
131
132 /**
133 * 私用扩容,扩容数组的长度
134 *
135 * @param newCapacity
136 */
137 private void resize(int newCapacity) {
138 // 使用泛型创建对象,使用new Object的方法创建泛型的对象
139 E[] newData = (E[]) new Object[newCapacity];
140 // 循环,将原数组里面的内容放入到新数组里面,新数组的长度为元素组的2倍
141 for (int i = 0; i < size; i++) {
142 // 将原数组的值赋值给新数组的值
143 newData[i] = data[i];
144 }
145 // 将原数组的值指向新数组,此操作,不影响原数组的正常使用
146 data = newData;
147 }
148
149 /**
150 * 获取Index索引位置的元素
151 *
152 * @param index
153 * @return
154 */
155 public E get(int index) {
156 // 如果索引index小于0或者索引的长度大于等于实际长度size,则抛出异常
157 if (index < 0 || index >= size) {
158 throw new IllegalArgumentException("add failed,Index is illegal......");
159 }
160 // 返回指定索引位置的数组元素
161 return data[index];
162 }
163
164 /**
165 * 修改index索引位置的元素e
166 *
167 * @param index
168 */
169 public void set(int index, E e) {
170 // 如果索引index小于0或者索引的长度大于等于实际长度size,则抛出异常
171 if (index < 0 || index >= size) {
172 throw new IllegalArgumentException("add failed,Index is illegal......");
173 }
174 // 则将元素放入到数组的索引index位置
175 data[index] = e;
176 }
177
178
179 /**
180 * @return
181 */
182 @Override
183 public String toString() {
184 // 封装数组遍历的内容
185 StringBuilder sb = new StringBuilder();
186 sb.append(String.format("Array : size = %d,capacity = %d\n", size, data.length));
187 sb.append('[');
188 for (int i = 0; i < size; i++) {
189 sb.append(data[i]);
190 if (i != size - 1) {
191 sb.append(", ");
192 }
193 }
194 sb.append(']');
195 return sb.toString();
196 }
197
198 /**
199 * 查找数据中是否包含元素e
200 *
201 * @param e
202 * @return
203 */
204 public boolean contains(E e) {
205 // 查看是否包含元素,进行遍历
206 for (int i = 0; i < size; i++) {
207 // 如果数组元素等于传入的元素e
208 if (data[i].equals(e)) {
209 // 返回true
210 return true;
211 }
212 }
213 return false;
214 }
215
216 /**
217 * 查找数组中元素e所在的索引,如果不存在元素e,则返回-1
218 *
219 * @param e
220 * @return
221 */
222 public int find(E e) {
223 // 查看是否包含元素,进行遍历
224 for (int i = 0; i < size; i++) {
225 // 如果数组元素等于传入的元素e
226 if (data[i].equals(e)) {
227 // 返回该索引位置的索引
228 return i;
229 }
230 }
231 return -1;
232 }
233
234 /**
235 * 从数组中删除index位置的元素,返回删除的元素
236 *
237 * @param index 此参数是索引参数
238 * @return
239 */
240 public E remove(int index) {
241 // 如果索引位置小于等于0或者索引位置大于等于数组的实际长度size
242 if (index < 0 || index >= size) {
243 throw new IllegalArgumentException("remove failed,Index is illegal......");
244 }
245
246 // 返回删除的元素,先获取到要删除的元素
247 E result = data[index];
248 System.out.println(result);
249
250 // 初始化值是要删除索引的位置加1,且i的值小于实际size的大小,i递减
251
252 // int i = index + 1,传入进去的删除索引位置的元素
253 // i < size,i小于数组的实际长度
254 // i++,i递增
255 for (int i = index + 1; i < size; i++) {
256 // 将数组元素的值赋值被删除元素的位置上面
257 // 即将数组元素向前移动,即第i位置的索引的数据移动到第i-1位置索引的数据
258 data[i - 1] = data[i];
259 }
260 // 删除元素以后,数组长度size递减1
261 size--;
262 // 将不可访问的位置置空
263 data[size] = null;
264
265 // 避免出现复杂度震荡
266 // 删除数组长度,缩小容量
267 // data.length / 2 != 0,避免出现创建数组长度为0的数组
268 if (size == data.length / 4 && data.length / 2 != 0) {
269 // 缩容数组的长度
270 resize(data.length / 2);
271 }
272 return result;
273 }
274
275 /**
276 * 删除数组的第一个元素的值
277 * <p>
278 * 从删除中删除第一个元素,返回删除的元素
279 *
280 * @return
281 */
282 public E removeFirst() {
283 // 删除数组的第一个位置的元素
284 return remove(0);
285 }
286
287 /**
288 * 从数组中删除最后一个元素,返回删除的元素。
289 *
290 * @return
291 */
292 public E removeLast() {
293 // 删除数组最后一个位置的元素
294 return remove(size - 1);
295 }
296
297 /**
298 * 从数组中删除元素e
299 *
300 * @param e
301 */
302 public void removeElement(E e) {
303 // 查看数组里面是否有该元素
304 int index = find(e);
305 // 如果查找到存在该元素
306 if (index != -1) {
307 // 调用删除数组元素的方法
308 remove(index);
309 }
310 }
311
312 public static void main(String[] args) {
313 // 数组添加元素
314 Array<Integer> array = new Array<>(20);
315 for (int i = 0; i < 10; i++) {
316 array.addLast(i);
317 }
318
319 System.out.println(array.toString());
320
321 // 在指定位置添加元素
322 array.add(1, 110);
323 System.out.println(array.toString());
324
325 // 在第一个位置添加元素
326 array.addFirst(-1);
327 System.out.println(array.toString());
328
329 // 修改index索引位置的元素e
330 array.set(1, 120);
331 System.out.println(array.toString());
332
333 // 是否包含某个元素
334 boolean contains = array.contains(9);
335 System.out.println(contains);
336
337 // 删除指定索引位置的元素
338 array.remove(2);
339 System.out.println(array);
340
341 // 删除第一个索引位置的元素
342 array.removeFirst();
343 System.out.println(array);
344
345 // 删除最后一个位置的元素
346 array.removeLast();
347 System.out.println(array);
348
349 // 从数组中删除元素e
350 array.removeElement(110);
351 System.out.println(array);
352 }
353
354 }
4、数组,就是把数据码成一排进行存放的。数组的最大优点,就是可以快速查询,如果知道了索引,可以根据索引直接获取到元素的值。
5、二次封装属于我们自己的数组,制作属于我们自己的数组类Array,对Java数组的二次开发。
5.1、数组元素的添加,向数组添加元素,最简单的是向数组的末尾添加元素。
将元素一放入到data[0]以后,维护size的大小,size自增一,此时size为1。维护的size的大小,同时也是指数组中有多少个元素。
此时,如果再添加一个元素,将元素二添加到数组中。同理,此时size为1,1这个索引的位置就是数组中第一个没有元素的位置。我们向数组的末尾添加一个元素,就是让data[1]等于我们要添加的元素。维护size的大小,size自增一,此时size为2。
5.2、向数组中的指定位置添加元素。如何将元素77插入到指定的索引为1的位置。
将当前索引为1的这个位置的元素以及索引为1之后的所有元素向后移动一个位置。此时,将索引为1这个位置腾给77这个元素,但是索引为1的位置的元素此时还是88。
具体移动的时候,需要从后向前移动,先把最后一个元素向后移动一个位置,然后依次移动前一个位置的元素。具体移动的时候,是将size-1这个位置的元素,移动到size这个位置上。
然后依次移动,从后向前,依次将元素向后移动一个位置,直到索引为1的时候。
此时将元素88向后移动一个位置,但是此刻需要注意,原来88元素所在的位置上面,元素88还依旧存在,比如这里元素88还依旧存在在索引为1的位置上面。只不过此时可以将你需要插入的元素覆盖掉之前的元素了,因为你已经将元素放到了正确的位置上。
注意:从指定索引的位置以及指定索引的位置的后面,每一个元素都向后移动一个位置,也就是后一个索引位置赋予前一个索引位置的元素,直到移动到索引index这个位置的元素,移动到索引index这个位置以后,相应的就把index这个位置腾出来了,这里需要注意的是,我们说腾出来这个位置,不是说data[index]这个位置没有元素了,是空的,此时data[index]这个位置还是存放的原来的那个元素,只不过现在我可以放心的将这个位置上原来的那个元素给覆盖掉了,因为相应的副本已经正确的放到了这个索引的下一个位置。
最后将元素77放入到索引为1的位置上面,完成元素在指定位置的插入。
最后维护size的大小,size++。
5.3、删除指定位置的元素。删除索引为1的元素,删除掉元素77。
要删除索引为1的元素,那么就要从索引为2的元素开始,将索引为2这个元素移动到索引为1的这个元素位置中。
让索引2位置的这个元素等于索引3位置的这个元素。
让索引3位置的这个元素等于索引4位置的这个元素。依次循环,直到最后一个元素。
此时,已经将元素77从数组中删除掉了,删除任务已经结束了,然后维护size的大小,size--就行了。
注意,数组中的size既表示数组中有多少元素,也表示指向了第一个没有元素的位置。如果此时我们向数组的末尾添加一个元素的话,需要向数组的data[size]这个索引的位置添加元素的。但是,此时将元素77删除以后,data[size]的位置指向了元素100,此时会存在问题吗,其实是不会存在问题的,用户访问数组来说,最多只能访问到data[size -1]这个位置的索引的,如果想使用某一个索引拿到某一个元素,会判断该索引的合法性,size必须大于等于零且小于size的,用户永远看不到data[size]的值是多少的。
创建数组的时候会开辟空间,数组所有的位置都有一个默认值的,具体默认值看数组类型而定的,默认值对用户来说也是不可见的。
如果可以的话,可以将data[size]这个位置置空的。
5.4、数组的动态扩容。动态数组,是区别于静态数组的,静态数组的容量是有限的。
此时,可以新创建一个2倍于原来数组长度的数组。将旧数组的元素依次赋值到新数组的元素。
将旧数组的元素依次赋值到新数组的元素。实际上,是需要进行循环的,循环遍历原数组的所有元素,把这些元素依次赋值到新数组中。
此时,对于整个数组来说,我们是希望新数组newData取代旧数组data的,换句话说,对于现在这个数组newData来说,容量capacity增大了一倍,与此同时,size的值是不变的,只不过新数组newData的这个size后面有了新的空间,可以容纳更多的元素了, 而对于整个旧数组data来说,它本身是一个引用,之前是指向四个容量的数组,现在让它指向了8个容量的数组,就可以了。
此时,类的成员变量data,和新创建的newData这个变量都指向了同样的空间,由于整个过程是封装在一个方法中的,所以对于newData来说这个变量在我们这个方法执行完成以后就失效了,而我们的这个data是整个类的成员变量,和整个类的生命周期是一致的,只要类还在使用,这个data就是有效的,它指向了新的含有二倍于元素组容量大小的新数组。对于原来的只有四个空间的数组,由于没有变量指向它了,Java的垃圾回收机制就将它回收了。此时就完成了扩容操作。
对于原来的只有四个空间的数组,由于没有变量指向它了,Java的垃圾回收机制就将它回收了。此时就完成了扩容操作。
此时就完成了扩容操作。
数组的动态缩容,避免出现数组空间浪费,和数组的动态扩容反过来,自己可以理解一下的。