数据结构——数组

接下来将对现阶段所学习到的数据结构与算法进行一个总结,总结完后将重新恢复对算法刷题练习的文章。

数组有一维二维三维…n维?实际上我们用到的只有一维二维,三维用的也不多,因为维度越多越复杂。数组是一块连续的内存区域,使用下标表示其偏移地址,熟悉c语言的就知道,定义一个数组a[10],这个数组其a就是该数组的起始地址,a[0]访问数组的第一个元素,第一个元素的地址是a的初始地址加上偏移量0 * sizeof type,解释一下,就是说a[n]就是访问第n + 1个元素,其地址就是(n + 1) * 该类型的大小,在Java中,这些底层的问题都被隐藏起来了,但是在c语言中是可以通过指针+n表示偏移的,因此需要了解这些原理,数组是一个非常常见的数据结构,后面的很多算法都是依赖数组来实现性能的优化。下面就来看看基本的数组用法:

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
package top.devonte.structure.linear;

import java.util.Arrays;

public class ArrayStructure {

/**
* 一位数组,过于简单,懒得解释,如果不懂就是Java基础没学好
*/
public static void arrayOne() {
int[] arr = new int[10];
for(int i = 0; i < arr.length; i++) {
arr[i] = i;
}
System.out.println(Arrays.toString(arr));
}

/**
* 二维数组,二维数组在内存中实际上也是连续的
* 通常使用row和col来定位,我们也可以通过一维的方式自己计算索引下标来定位
* 在逻辑上是这样的:
* []
* []
* []
* []
* 后面使用到二维数组的算法有:动态规划、二维数组的旋转等
* 下面演示一下通过一维的方式计算索引,并且格式化输出矩阵
*/
public static void arrayTwo() {
int[][] arr = new int[10][10];
for(int i = 0; i < 10; i++) {
for(int j = 0; j < 10; j++) {
arr[i][j] = i * j;
}
}
for(int i = 0; i < 100; i++) {
System.out.print(arr[i / 10][i % 10] + "\t");
if(i % 10 == 9) {
System.out.println();
}
}
}

}

结语

数组是基本数据结构中最简单的一个,但是它的用处很大,后面的树、堆、图、散列表和堆栈基本上都可以用到它。最简单也是最灵活的,数组的随机访问时间复杂度是O(1),直接通过下标就可以定位一个元素。一些算法,例如二分查找、双指针、前缀和、分差等都是用在数组这样的结构上的。图的关联关系存储使用邻接矩阵,邻接矩阵就是二维数组。下一篇将对另一个线性结构——链表,进行一个总结。