【数据结构】数据

1. 内存连续性
   • 由于数组元素在内存中是连续存储的，这使得访问数组元素的速度非常快。当知道数组的起始地址（通常由数组名表示）和元素类型的大小后，就可以通过简单的计算来确定任何一个元素的内存地址。
   • 例如，对于一个int类型的数组（假设int类型占 4 个字节），如果数组的起始地址是base_address，那么第i个元素的地址可以用公式address(i)=base_address + i * sizeof(int)来计算。
2. 一维数组与多维数组
   • 一维数组：是最基本的形式，如上面所举的例子。它就像一条直线上排列的元素。
   • 二维数组：可以看作是一个表格，例如int[][] matrix = {{1, 2}, {3, 4}};。在内存中，二维数组也是按行（或按列，取决于编程语言的实现方式）连续存储的。实际上，二维数组可以理解为是一个一维数组，其中的每个元素又是一个一维数组。对于按行存储的二维数组，在访问matrix[i][j]时，首先找到第i行的起始地址（类似于访问一维数组），然后在该行中找到第j个元素。
   • 更高维的数组（如三维数组等）原理类似，不过其存储和访问方式更加复杂，但都是基于低维数组的概念扩展而来的。

1. 访问元素
   • 如前面所述，通过索引来访问元素是数组最基本的操作。在大多数编程语言中，这种访问操作的时间复杂度是 O (1)，这意味着无论数组有多大，访问单个元素的时间基本上是固定的。
   • 但是要注意，索引必须在合法的范围内，否则可能会导致程序出错，例如在一个长度为n的数组中，索引不能小于 0 或者大于等于n。
2. 插入元素
   • 在末尾插入：在大多数编程语言中，在数组末尾插入元素相对比较简单。如果数组还有足够的空间，直接将元素添加到最后一个位置即可。时间复杂度通常是 O (1)。
   • 在中间插入：这是比较复杂的操作。当要在数组中间插入一个元素时，需要将插入位置之后的所有元素向后移动一个位置，为新元素腾出空间。例如，在数组{1, 2, 3, 4, 5}中，如果要在索引为 2 的位置插入元素6，需要将3、4、5依次向后移动，得到{1, 2, 6, 3, 4, 5}。这种操作的时间复杂度是 O (n)，其中n是数组中元素的个数，因为在最坏的情况下，可能需要移动所有的元素。
3. 删除元素
   • 在末尾删除：通常比较简单，只需要将数组的长度减 1 即可，时间复杂度是 O (1)。
   • 在中间删除：和插入类似，需要将删除位置之后的元素向前移动来填补空缺。例如，在数组{1, 2, 3, 4, 5}中，如果要删除索引为 2 的元素，需要将4和5向前移动，得到{1, 2, 4, 5}。这种操作的时间复杂度也是 O (n)。

1. 优点
   • 访问速度快：由于内存连续和通过索引直接计算地址的方式，使得访问数组元素的速度非常快，这对于需要频繁访问数据的应用场景（如科学计算中的矩阵运算）非常重要。
   • 简单易用：数组的概念和操作相对比较简单，容易理解和掌握，对于初学者来说是很好的数据结构学习起点。
2. 缺点
   • 插入和删除操作复杂（除末尾外）：如前面所述，在数组中间插入或删除元素需要移动大量的元素，这在元素个数较多的情况下会消耗大量的时间和资源。
   • 大小固定（部分语言中）：在一些编程语言（如 C 和 C++）中，数组的大小在创建时就固定了，后续如果需要改变大小，需要进行复杂的操作（如重新分配内存等），而在一些高级语言（如 Java 和 Python）中，虽然有动态数组的概念可以一定程度上缓解这个问题，但本质上还是有性能损耗。

public class ArrayExample {
    public static void main(String[] args) {
        // 创建一个整数数组
        int[] arr = {1, 2, 3, 4, 5};

        // 访问数组元素
        System.out.println("第三个元素是：" + arr[2]);

        // 在末尾插入元素
        int[] newArr = new int[6];
        System.arraycopy(arr, 0, newArr, 0, arr.length);
        newArr[5] = 6;
        System.out.println("在末尾插入元素后的数组：");
        for (int i : newArr) {
            System.out.print(i + " ");
        }
        System.out.println();

        // 在中间插入元素
        int[] anotherArr = new int[7];
        System.arraycopy(newArr, 0, anotherArr, 0, 3);
        anotherArr[3] = 7;
        System.arraycopy(newArr, 3, anotherArr, 4, newArr.length - 3);
        System.out.println("在中间插入元素后的数组：");
        for (int i : anotherArr) {
            System.out.print(i + " ");
        }
        System.out.println();

        // 删除末尾元素
        int[] tempArr = new int[anotherArr.length - 1];
        System.arraycopy(anotherArr, 0, tempArr, 0, tempArr.length);
        System.out.println("删除末尾元素后的数组：");
        for (int i : tempArr) {
            System.out.print(i + " ");
        }
        System.out.println();

        // 删除中间元素
        int[] finalArr = new int[tempArr.length - 1];
        System.arraycopy(tempArr, 0, finalArr, 0, 3);
        System.arraycopy(tempArr, 4, finalArr, 3, tempArr.length - 4);
        System.out.println("删除中间元素后的数组：");
        for (int i : finalArr) {
            System.out.print(i + " ");
        }
    }
}