算法与数据结构之数组(Java)

2024-01-03 12:20:00

目录

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

文章来源:https://blog.csdn.net/m0_58476313/article/details/135356611
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。