算法与数据结构之数组（Java）

目录

1、数组的定义

2、线性结构与非线性结构

3、数组的表现形式

3.1 一维数组

3.2 多维数组

4、重要特性：随机访问

5、ArrayList和数组

6、堆内存和栈内存

7、数组的增删查改

7.1 插入数据

7.2 删除一个数据

7.3 修改数组

7.4 查找数据

8、总结

什么是数组？

1、数组的定义

所谓数组，是有序的元素序列。如将有限个类型相同的变量的集合命名，那么这个名称就是数组名。

数组是用于存储多个相同类型数据的集合。通常用Array表示，也称之为线性表。

数组的特点：

（1）数组是相同数据类型的元素的集合（int的数组不能存float，float也不能存double）

（2） 数组中各元素的存储是有先后顺序的，它们在内存中按照这个顺序连续存放到一起。内存地址（连续存储）

（3）数组元素用整个数组的名字和它自己在数组中的顺序位置来表示。例如a[0]表示名字为a的数组中的第一个元素。a[1]表示名字为a的数组中的第二个元素，以此类推。

2、线性结构与非线性结构

3、数组的表现形式

3.1 一维数组

int a[],String b[];

3.2 多维数组

int a[][],String b[][][];//int a[m][n]:内存空间是多少？mxn

4、重要特性：随机访问

数组是连续的内存空间和相同类型的数据。正是因为这两个限制，它才有了这个重要的特性：随机访问。

优势：查找效率高（随机访问的应用）

缺点：删除、插入（效率相对低，因为要根据插入和删除的位置决定；效率低的原因：为了保证连续性，需要做大量的数据搬移工作）

比如往数组中插入一个数据：

删除数组中的某个数据：

使用数组注意事项：使用数组一定要注意访问越界的问题。要多加判断，尤其是开始和结束，测试的时候也要注意头尾。

5、ArrayList和数组

本质上是一样的，都是数组。ArrayList是JDK封装了。不需要管扩容等操作。

数组的话就是要你全部操作。

两者之间如何选择？

1、不知道数据大小的肯定选ArrayList（不需要管理扩容操作）

2、如果知道数据大小且非常关注性能的就选数组

6、堆内存和栈内存

Java分为堆栈两种内存（C语言同理）

什么是堆内存？（FIFO）

存放new 创建的对象和数组。

什么是栈内存？

引用变量（FILO）

堆栈区别：

栈：为编译器自动分配和释放，如函数参数、局部变量、临时变量等等

堆：为成员分配和释放，有程序员自己申请、自己释放。否则发生内存泄漏。（java自动管理（gc））

1、栈的速度要快

2、栈内存的数据可以共享，主要存一些基本数据类型。

int a = 3; //在栈中创建变量a然后给a赋值，先不会创建一个3，而是先在栈中找有没有3，如果有直接指向。
//如果没有就加一个3进来

int b = 3; //首先也要创建一个变量b

7、数组的增删查改

private int index;//数组已存在数据的大小

private int size;//数组大小

private int data[];//数组定义

7.1 插入数据

    public void insert(int loc, int n) {

        if (index++ < size) {
            //从后开始遍历，遍历到需要插入的位置，开始后移数据
            for (int i = size - 1; i > loc; i--) {
                //数据往后移动
                data[i] = data[i - 1];
            }
            //在loc位置插入n值
            data[loc] = n;
        } else {//扩容
            this.size = size * 2 + 1;
            int[] newData = new int[this.size];
            for (int i = 0; i < data.length; i++) {
                newData[i] = data[i];
            }
            this.data = newData;
            //从后开始遍历，遍历到需要插入的位置，开始后移数据
            for (int i = size - 1; i > loc; i--) {
                //数据往后移动
                data[i] = data[i - 1];
            }
            //在loc位置插入n值
            data[loc] = n;
        }
    }

7.2 删除一个数据

    public void delete(int loc) {
        //O(n)
        for (int i = loc; i < size - 1; i++) {
            //判断不是最后一个,如果是组后一个则把最后一个数据置为默认值0，就是没存数据
            if (i != size - 1) {
                //后面的数据要向前移动，确保连续性
                data[i] = data[i + 1];
            } else {
                data[i] = 0;
            }
        }
        index--;
    }

7.3 修改数组

public void update(int loc, int n) {//O(1)
  data[loc] = n;
}

7.4 查找数据

public int get(int loc) {//随机访问O(1)

return data[loc];

}

8、总结

数组是一个最简单的数据结构。它存储相同类型的一组数据，最大的特点就是下标和随机访问，缺点就是插入和删除都很慢，时间复杂度为O(n)。

思考：1、为什么数组的下标是从0开始呢？（连续存储）

如果不从0开始：就需要操作减法运算，计算机减法操作起来比加法复杂很多，以此优先考虑使用加法进行计算

一维数组的寻址公式：init_loc(初始内存地址) + index(数组下标)*size(数组长度)

loc = init_loc +index * size

2、二维数组的内存地址是怎样的？写出寻址公式？

二维数组的内存地址：

二维转一维：

1 2 3

4 5 6

》1 2 3 4 5 6

=》 4的下标是在二维里面是（1,0）

=》在一维里面是第3个

=》i *n(一维的长度) + j(在列)

==》1 * 3 + 0 = 3

a[i][j]: (i< n, j<n)

loc = init_loc + (i *n + j) * size