数据结构——数组

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

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

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)，直接通过下标就可以定位一个元素。一些算法，例如二分查找、双指针、前缀和、分差等都是用在数组这样的结构上的。图的关联关系存储使用邻接矩阵，邻接矩阵就是二维数组。下一篇将对另一个线性结构——链表，进行一个总结。