数据结构之数组详解

蔚落 2023-01-22 14:50 19阅读 0赞

**一.简介**  
数组(Array)是由相同类型的元素(element)集合组成的固定长度(Size)的一种数据结构。在内存中是连续存储的，因此可以通过索引(Index)计算出某个元素的地址。

**二.基础**  
**1.定义**  
ype arrayName\[\] 或者 type\[\] arrayName。  
如：

int arrInt[] 或者 int[] arrInt

声明过程，只是告诉编译器: arrInt变量保存了一个int类型的数组。这个过程并没有分配内存  
**2.分配内存**  
分配内存需要通过new完成，同时指明类型和数组大小。  
如：

int[] arrInt = new int[4];

数组中元素通过new分配后自动完成初始化，一般有几种：数字类型初始化为0(如：int/byte/short/long初始化为0，float/double初始化为0.0)，布尔型初始化为false(boolean初始化为false),String或者其他对象类型初始化为null。  
数组赋值也有两种

int[] arrInt = { 1,3,5,7};
    或
    int[] arrInt = new int[4];
    arrInt[0] = 1;
    arrInt[1] = 3;
    arrInt[2] = 5;
    arrInt[3] = 7;

示意图如下：  
![在这里插入图片描述][20210520132510560.png]  
**3.多维数组**  
多维数组类似，即数组中的元素也是数组。如

int[][] arrInt = { { 1,3,5},{ 2,4,6},{ 0,10,20}};

示意图如下：  
![在这里插入图片描述][20210520132600512.png]  
**4.数组的特点**  
（1）索引(即下标) 一般从0开始，如java, C/C++。  
（2）长度固定，在申请时长度固定。内存连续，在内存中则是申请一块连续的固定大小的空间。  
（3）数组有一维数组和多维数组，数组元素可以是基本数据类型(Primitive)，也可以是对象引用(Reference)。  
（4）随机访问，能够根据位置(下标)直接访问到元素。

**注：**  
**基本数据类型和对象引用数据类型**  
Primitive类型在java中有八种(具体内容后续整理)，Primitive类型在内存位置直接存入实际的值，引用对象的内存分配是在堆上(Heap)。  
Primitive类型： boolean、char、byte、short、int、long、float、double  
**数组下标从0开始**  
数组变量引用 指向了数组实际分配的连续内存的开始地址 即第一个元素的地址(firstAdrr)，数组下标(index)即偏移量。假使每个元素大小为size.  
那么数组元素位置计算：firstAdrr+index\*size。  
所以大部分语言数组下标是0开始。如果从1开始，计算位置时偏移量要减1操作，多了一步运算。

**数组关联的Class对象**  
每个数组有一个关联的Class对象，与其他相同类型数组共享。  
如：JNI中传递的参数经常看到：I表示int类型，\[ 表示一个数组，\[I 即int数组。

System.out.println("int array:" + new int[3].getClass());
    System.out.println("int array:" + new int[3].getClass().getSuperclass());
    System.out.println("String array:" + new String[3].getClass());
    System.out.println("boolean array:" + new boolean[3].getClass());

结果为：

int array:class [I
    int array super:class java.lang.Object
    String array:class [Ljava.lang.String;
    boolean array:class [Z

**三.数组的拷贝**  
一维数组拷贝  
一维数组的clone()是 深度拷贝，拷贝了数组内的原始数据到新数组，而不是引用的复制。  
如：

int arrInt[] = { 1,2,3};
     
    int arrClone[] = arrInt.clone();
    arrClone[1] = 5;
      
    System.out.println(arrInt == arrClone);
      
    for (int i = 0; i < arrClone.length; i++) { 
        System.out.println(arrInt[i]+" "+arrClone[i]);
    }

结果为：

false
    1 1
    2 5
    3 3

示意图如下：  
![在这里插入图片描述][20210520132934875.png]  
多维数组拷贝  
但多维数组则不是这样。如：

int arrInt[][] = { { 1,2,3},{ 4,5,6}};
            
    int[][] arrClone = arrInt.clone();
    arrClone[0][1] = 50;
    arrInt[0][1] = 100;
      
    System.out.println(arrInt == arrClone);
    System.out.println(arrInt[0] == arrClone[0]);
      
    for (int i = 0; i < arrInt.length; i++) { 
        for (int j = 0; j < arrInt[i].length; j++) { 
            System.out.println(arrInt[i][j]+" "+arrClone[i][j]);
        }
        
    }

结果为：

false
    true
    1 1
    100 100
    3 3
    4 4
    5 5
    6 6

示意图如下：  
![在这里插入图片描述][20210520133051834.png]  
**四.数组操作**  
插入  
如图，向数组中插入一个元素，插入位置及之后的所有元素都需要向后挪动一位来完成插入操作。  
如果数组已经满了(或者保证数组长度与元素个数一致),则只能创建一个新的数组(长度增加的)来完成插入操作。  
时间复杂度上，最好的是数组未满插入到最后 只需直接插入，操作一次(O(1))。最坏是插入到第一位，需要操作N次。  
平均时间复杂度，(1 + 2 + … + n) / n ~= O(n)  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwODQ0Nw_size_16_color_FFFFFF_t_70]  
这是一个简单的插入示例。在现有数组的position位置插入value值，首先创建了一个新数组(长度+1)，依次填入数据。

private int[] insertArr(int[] srcArr, int position, int value) { 
        if (position < 0 || position >= srcArr.length) return null;
        int[] desArr = new int[srcArr.length+1];
        System.arraycopy(srcArr, 0, desArr, 0, position);
        desArr[position] = value;
        System.arraycopy(srcArr, position, desArr, position+1, srcArr.length-position);
        return desArr;
    }

**删除**  
类似插入的反向操作，删除某个元素，该位置及之后的所有元素 向前挪一位。  
如果要保证数组长度与数组元素个数一致，则也需要重新创建一个(长度减小的)数组来完成。  
示意图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwODQ0Nw_size_16_color_FFFFFF_t_70 1]  
**查找**  
查找某一元素位置，只能一位位的遍历查找了

**访问**  
对于某位置的元素，直接读取或修改 就可以了。数组是随机访问的。

**五.时间复杂度总结**  
最后整理个表格，上述操作的时间复杂度大致如下，很容易理解就不详细解释了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwODQ0Nw_size_16_color_FFFFFF_t_70 2]

[20210520132510560.png]: /images/20221020/57694e0215484b03ae1669e8a6e43801.png
[20210520132600512.png]: /images/20221020/8f82f610e1cb44b396d2cb37e14bc9e9.png
[20210520132934875.png]: /images/20221020/b292cab259ab4e868a0dfa01884ce97e.png
[20210520133051834.png]: /images/20221020/d1589b66d04249fcb569e5788c3403d9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwODQ0Nw_size_16_color_FFFFFF_t_70]: /images/20221020/908e3b40a2ce456a974478a7b86c4650.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwODQ0Nw_size_16_color_FFFFFF_t_70 1]: /images/20221020/a5c8a7262a16432482cfebc5eab77495.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjQwODQ0Nw_size_16_color_FFFFFF_t_70 2]: /images/20221020/7a3dc0de208e4c87b65424f947e68b8d.png