数组的初识

桃扇骨 2023-09-26 20:36 64阅读 0赞

**目录**

1.初识数组

2.数组的简单操作

2.1读取元素

2.2更新元素

2.3插入元素

2.4删除元素

--------------------

## **1.初识数组** ##

**数组是有限个相同类型的变量所组成的有序集合**，数组中的每一个变量被称为元素。数组是*最简单，最为常用*的数据结构。

以整型数组为例：数组的存储形式如下：

元素：3 1 6 4 8 7 6

下标：0 1 2 3 4 5 6

由上，数组中的每一个元素都拥有自己的下标，只不过这个下标从0开始，一直到数组大小-1.

数组的另外一个特点，是**在内存中顺序存储**，因此可以很好地实现逻辑上的顺序表。

*数组在内存中的存储，具体是什么样子呢?*

内存是由一个个连续的内存单元组成的，每一个内存单元都拥有自己的地址。在这些内存单元中，有些被其他数据占用了，有些是空闲的。

数组中的每一个元素，都存储在小小的内存单元中，并且元素之间紧密排列，既不能打乱存储顺序，也不能跳过存储单元进行存储。如下表表示一段内存空间中数组的存储方式：

(注：\*表示该内存单元不存储任何东西，\#表示该内存单元存储除数组外的其他内容）

不同类型的数组，每个元素所占的字节数也不同，该表格只是简单举例.

## **2.数组的简单操作** ##

### **2.1读取元素** ###

对于数组来说，读取元素是最简单的操作。由于数组在内存空间中的存储方式是顺序存储，所以**只要得到数组下标，就能获得对应元素。**

假设有一个名字叫arr的数组，若要获取到下标为一的元素，就写作arr\[1\]。注意：输入的下标必须在数组长度范围之内，否则会出现数组越界。

像这种根据下标获取元素的方式叫做**随机读取**。

简单的代码示例如下：

int[] array = new int[]{3,1,6,4,8,7};
    //输出数组中下标为三的元素
    System.out.println(array[3]);

### **2.2更新元素** ###

要把数组中的某一个元素的值替换为另一个新值，**只需要利用数组下标直接赋值即可**。

简单代码示例如下：

//初始化数组
    int[] arr = new int[]{3,1,6,4,8,7};
    //给下标为1的元素重新赋值
    arr[1] = 10;
    //输出下标为1的元素
    System.out.println(arr[1]);

根据上次我们学习的时间复杂度和空间复杂度的有关知识，我们可以得知读取元素和更新元素的时间复杂度为O（1），空间复杂度为O（n）。

### **2.3插入元素** ###

在介绍该操作之前，我们首先需要知道一个概念：那就是**数组的实际元素数量还可能小于数组的长度**。例如：

因此，插入数组元素的操作存在3种情况。

1.尾部插入

2.中间插入

3.超范围插入

1.尾部插入，最简单的情况，**直接把插入的元素放在数组尾部的空闲位置**，等同于更新元素的操作。

2.中间插入，稍微复杂一些。由于数组的每一个元素都有其固定下标，**所以先把插入位置及后面的元素向后移动，腾出地方，再把要插入的元素放入该位置**。

譬如在下标为1的位置插入元素6：

![41fe3cff7a96424b8205f0f2e9be92a9.jpeg][]

（注意：**移动元素的步骤一定是从后往前**，如上图步骤，若为从前向后，则会一直只挪动一个元素）

挪动后得到：

完整代码如下：

private int[] array;
    private int size;
    
    //创建大小为capacity的数组
    public Arrayinsert(int capacity){
        this.array = new int[capacity];
        size = 0;
    }
    
    /*index-插入的位置；element-插入的元素*/
    
    public void insert(int index, int element) throws Exception{
        //判断访问下标是否超出范围
        if(index<0 || index>size){
            throw new IndexOutOfBoundsException("超出数组实际范围！");
        }
        //从右向左循环，将元素逐个向右挪动一位
        for(int i=size-1; i>=index; i--){
            array[i+1] = array[i];
        }
        //腾出的位置放置新元素
        array[index] = element;
        size++;
    }
    
    //输出数组
    
    public void output(){
        for(int i=0; i<size; i++){
            System.out.println(array[i]);
        }
    }
    
    public static void main(String[] args) throws Exception{
       Arrayinsert myArray = new Arrayinsert[8];
       myArray.insert(0,3);
       myArray.insert(1,1);
       myArray.insert(2,6);
       myArray.insert(3,4);
       myArray.insert(4,8);
       myArray.insert(5,7);
       myArray.insert(1,6);
       myArray.output():
    }

代码中成员变量size是数组实际元素的数量。如果插入元素在数组尾部，则size=index,如果插入在中间则index<size。

如果传入的是下标参数大于size或者小于零，会认为是非法输入，会直接抛出异常。

到现在，我们已经大致了解了插入操作，但现在仍存在一个问题：**如果不断插入元素，元素数量就会大于数组长度**，这怎么办？

这就涉及了**超范围插入**。

比如现在有一个数组长度为6的数组，已经装满了元素，还想要添加一个新元素，这就涉及了数组的**扩容**。

如图，我们可以知道该数组的大小在一开始就确定了，无法随意的变长变短。那么此时，我们就可以考虑**创建一个新数组，**长度是旧数组的二倍，再**把旧数组的内容复制过来**，这就实现了数组的扩容。

如此一来，我们插入数组的方式也改变了，部分代码如下：

public void insert(int index, int element){
        //判断下标是否超出范围
        if(index<0 || index>size){
            throw new IndexOutOfBoundsException("超出数组的实际范围！");
        }
        //从右向左逐一移动数组元素
        for(int i=size-1; i>=index; i--){
            array[i+1] = array[i];
        }
        //如果数组实际长度大于等于数组长度，则引入扩容函数resize
        if(size >= array.length){
            resize();
        }
        array[index] = element;
        size++;
    }
    
    public void resize(){
        //创建一个新数组，大小是旧数组长度的两倍
        int[] arrayNew = new int[array.length*2];
        //利用arraycopy函数将旧数组内容复制到新数组内
        //附：arraycopy函数用法：arraycopy(arr1, a, arr2, b, c);
        //即在arr1数组内从下标为a的元素开始，放在arr2下标为b的元素开始，复制元素为c个
        System.arraycopy(array, 0, arrayNew, 0, size);
        array = arrayNew;
    }

这样就完成了数组扩容的操作。

### **2.4删除元素** ###

数组的删除操作和插入操作相反，如果删除的元素在中间，其**之后的元素都会向前移动一位**。

（其之后的元素的移动位次与插入操作相反，应该为**从右向左**的元素逐向前移动一位）

由于不涉及数组的扩容操作，因此比插入操作要更简单。

代码如下：

public void deleted(int index){
        //判断是否超出数组范围
        if(index<0 || index>size)
            throw new IndexOutOfBoundsException("超出数组实际范围!");
        int deletedElement = array[index];
        //从右向左循环，将元素逐个向左移动一位
        for(int i=index; i<size-1; i++){
            array[i] = array[i+1];
        }
        size--;
        return deletedElemet;
    }

相信各位对数组的概念及其操作有了一定的理解，希望该文章对大家有帮助，谢谢大家支持哦

![2c878e623db942a6bfbcbb6c172fbb25.jpeg][]

[41fe3cff7a96424b8205f0f2e9be92a9.jpeg]: https://img-blog.csdnimg.cn/41fe3cff7a96424b8205f0f2e9be92a9.jpeg
[2c878e623db942a6bfbcbb6c172fbb25.jpeg]: https://img-blog.csdnimg.cn/2c878e623db942a6bfbcbb6c172fbb25.jpeg