数据结构与算法——Java实现 4.数组

news/2024/10/4 0:24:05/文章来源:https://blog.csdn.net/m0_73983707/article/details/141969599

目录

一、数组 — 概述

1.定义

2.特点

 3.公式

小测试

二、数组的性能

1.空间占用

2.随机访问

三、动态数组

1.实现动态数组

2.新增元素(最后一个元素位置)

3.新增元素、数组扩容

4.检查数组容量

 5.类中定义的其他方法

① 按索引查找元素

② 返回数组长度

③ 遍历数组

④ 遍历泛型

⑤ 函数式接口遍历

⑥ 迭代器遍历

⑦ Java流的方式遍历

⑧ 删除元素值

⑨ 重写比较方法

 6.整体代码

① 类

② 测试类

7.插入或删除性能

四、二维数组

1.定义格式

2.内存分布及内存占用

五、数组的缓存与局部性原理

局部性原理


上帝,请赐予我平静,去接受我无法改变的;

给予我勇气,去改变我能改变的;

赐我智慧,分辨这两者的区别。

                                                        —— 24.9.8

一、数组 — 概述

1.定义

        在计算机科学中,数组是由一组元素(值或变量)组成的数据结构。每个元素有至少一个索引或键来标识(元素的类型必须一致

2.特点

        数组内的元素是连续存储的,所以数组中元素的地址,可以通过其索引计算出来,例如:

int[] arr = {1,2,3,4,5}
//           0 1 2 3 4

 3.公式

        知道了数组的数据起始地址BaseAddress,就可以由公式BaseAddress + i * size计算出索引 i 元素的地址

        ① i 即索引,在Java、C等语言中都是从 0 开始

        ② size 是每个元素占用的字节,例如 int 占 4 位,double 占 8 位 

小测试

byte[] array = {1,2,3,4,5};

已知array的数据的起始地址是0x7138f94c8,那么元素3的地址是什么?

        0x7138f94c8 + 2*1 = 0x7138f94ca

        16进制:0123456789abcdef

二、数组的性能

1.空间占用

Java 中数组结构为:

        8字节 markword(记录对象的哈希码、锁的信息等)
        4字节 class 指针(压缩类指针的情况)
        4字节 数组大小(决定了数组最大容量是 232)
        数组元素 + 对齐字节(java 中所有对象大小都是8字节的整数倍,不足的要用对齐字节补足)

例如:

int[] array = {1,2,3,4,5};

8 + 4 + 4 * 5 + 4(alignment)

markdown+指针+元素+对齐字节  

2.随机访问

即根据索引查找元素,与数据规模没有关系,时间复杂度是O(1)

三、动态数组

1.实现动态数组

size —— 逻辑大小,代表数组中有效的元素个数

capacity —— 数组的容量,代表数组中最大可以容纳的元素数

public class demo1ArrayVectorInsert implements Iterable<Integer> {// 准备三个属性private int size = 0;// 逻辑大小private int capacity = 8;// 容量// 懒惰初始化思想private int[] array = {};
}

2.新增元素(最后一个元素位置)

    public void addLast(int element){// size代表数组内有效元素个数// array[size] = element;// size++;add(size,element);}

3.新增元素、数组扩容

    // 数组增加元素,需要先进行数组扩容// index:插入元素的位置索引,element:插入的元素// 如果容量不够,需要先扩容public void add(int index,int element){// 容量的检查checkAndGrow();// System.arraycopy(array,index,array,index+1,size-index):实现数组间的元素复制if(index < size && index >= 0) { // 拷贝到0-size-1的区间内// 从原始数组array的index索引开始,拷贝到同一个数组array,向后移动一位,拷贝size-index个元素System.arraycopy(array, index, array, index + 1, size - index);} else if (index == size) {array[index] = element;size ++;} else{// 对插入位置合法性进行判断System.out.println("Index out of bounds");return;}}

4.检查数组容量

    private void checkAndGrow() {// 容量的检查if(size == 0){// 检查数组容量是否为8array = new int[capacity];} else if(size == capacity){// 数组容量已满,应进行扩容:1.5倍 1.618倍 2倍capacity = capacity + (capacity >> 1);// 复制到新数组int[] newArray = new int[capacity];System.arraycopy(array,0,newArray,0,size);array = newArray;}}

 5.类中定义的其他方法

① 按索引查找元素

    // 按索引查找元素public int get(int index) {return array[index];}

② 返回数组长度

    // 返回数组长度public int length(){return array.length;}

③ 遍历数组

    // 遍历数组public void forEach(){for(int i = 0; i < size; i++) {System.out.print(array[i]+" ");}System.out.println();}

④ 遍历泛型

    // 遍历泛型public void forEachGenirics(Consumer<Integer> consumer){for (int i = 0; i < size; i++) {consumer.accept(array[i]);}}

⑤ 函数式接口遍历

    // consumer函数式接口,consumer:一个参数,没有返回值public void Foreach(Consumer<Integer> consumer){for (int i = 0; i < size; i++) {//    System.out.print(array[i]+" ");// 提供 array[i]// 返回 voidconsumer.accept(array[i]);System.out.print(" ");}System.out.println();}

⑥ 迭代器遍历

    // 迭代器遍历@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {// 匿名内部类的写法int i = 0;@Override// 判断有没有下一个元素public boolean hasNext() {return i < size;}@Override// 返回当前元素,并移动到下一个元素public Integer next(){return array[i++];}};}

⑦ Java流的方式遍历

    // Java流的方式进行遍历public IntStream stream(){return IntStream.of(array);}

⑧ 删除元素值

   // 删除元素值public int remove(int index){if(index < size && index >= 0) {int removed = array[index];if(index < size - 1){System.arraycopy(array, index + 1, array, index, size - index - 1);}// arraycopy(原始数组,要移动的起始位置,目标数组,目标数组的起始位置),要移动的元素个数size--;return removed;}else {System.out.println("Index out of bounds");return 0;}}

⑨ 重写比较方法

    // 重写比较方法@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;demo1ArrayVectorInsert integers = (demo1ArrayVectorInsert) o;return size == integers.size && capacity == integers.capacity && Objects.deepEquals(array, integers.array);}@Overridepublic int hashCode() {return Objects.hash(size, capacity, Arrays.hashCode(array));}

 6.整体代码

① 类

package Day2Array;import java.util.Arrays;
import java.util.Iterator;
import java.util.Objects;
import java.util.function.Consumer;
import java.util.stream.IntStream;// Java自己实现ArrayList动态数组
// 迭代器遍历,实现一个接口Iterable
public class demo1ArrayVectorInsert implements Iterable<Integer> {// 准备三个属性private int size = 0;// 逻辑大小private int capacity = 8;// 容量// 懒惰初始化思想private int[] array = {};// 新增元素public void addLast(int element){// size代表数组内有效元素个数// array[size] = element;// size++;add(size,element);}// 数组增加元素,需要先进行数组扩容// index:插入元素的位置索引,element:插入的元素// 如果容量不够,需要先扩容public void add(int index,int element){// 容量的检查checkAndGrow();// System.arraycopy(array,index,array,index+1,size-index):实现数组间的元素复制if(index < size && index >= 0) { // 拷贝到0-size-1的区间内// 从原始数组array的index索引开始,拷贝到同一个数组array,向后移动一位,拷贝size-index个元素System.arraycopy(array, index, array, index + 1, size - index);} else if (index == size) {array[index] = element;size ++;} else{// 对插入位置合法性进行判断System.out.println("Index out of bounds");return;}}private void checkAndGrow() {// 容量的检查if(size == 0){// 检查数组容量是否为8array = new int[capacity];} else if(size == capacity){// 数组容量已满,应进行扩容:1.5倍 1.618倍 2倍capacity = capacity + (capacity >> 1);// 复制到新数组int[] newArray = new int[capacity];System.arraycopy(array,0,newArray,0,size);array = newArray;}}// 按索引查找元素public int get(int index) {return array[index];}// 返回数组长度public int length(){return array.length;}// 遍历数组public void forEach(){for(int i = 0; i < size; i++) {System.out.print(array[i]+" ");}System.out.println();}// 遍历泛型public void forEachGenirics(Consumer<Integer> consumer){for (int i = 0; i < size; i++) {consumer.accept(array[i]);}}// consumer函数式接口,consumer:一个参数,没有返回值public void Foreach(Consumer<Integer> consumer){for (int i = 0; i < size; i++) {//    System.out.print(array[i]+" ");// 提供 array[i]// 返回 voidconsumer.accept(array[i]);System.out.print(" ");}System.out.println();}// 迭代器遍历@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {// 匿名内部类的写法int i = 0;@Override// 判断有没有下一个元素public boolean hasNext() {return i < size;}@Override// 返回当前元素,并移动到下一个元素public Integer next(){return array[i++];}};}// Java流的方式进行遍历public IntStream stream(){return IntStream.of(array);}// 删除元素值public int remove(int index){if(index < size && index >= 0) {int removed = array[index];if(index < size - 1){System.arraycopy(array, index + 1, array, index, size - index - 1);}// arraycopy(原始数组,要移动的起始位置,目标数组,目标数组的起始位置),要移动的元素个数size--;return removed;}else {System.out.println("Index out of bounds");return 0;}}// 重写比较方法@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;demo1ArrayVectorInsert integers = (demo1ArrayVectorInsert) o;return size == integers.size && capacity == integers.capacity && Objects.deepEquals(array, integers.array);}@Overridepublic int hashCode() {return Objects.hash(size, capacity, Arrays.hashCode(array));}
}

② 测试类

package Day2Array;import org.junit.Test;
import org.junit.jupiter.api.DisplayName;public class test {@Test@DisplayName("删除遍历")public void test1() {demo1ArrayVectorInsert demo1ArrayVectorInsert = new demo1ArrayVectorInsert();demo1ArrayVectorInsert.addLast(1);demo1ArrayVectorInsert.addLast(2);demo1ArrayVectorInsert.addLast(3);demo1ArrayVectorInsert.addLast(4);demo1ArrayVectorInsert.addLast(5);int res = demo1ArrayVectorInsert.get(4);System.out.println(res);}@Test@DisplayName("删除遍历")public void test2() {demo1ArrayVectorInsert demo1ArrayVectorInsert = new demo1ArrayVectorInsert();demo1ArrayVectorInsert.addLast(1);demo1ArrayVectorInsert.addLast(2);demo1ArrayVectorInsert.addLast(3);demo1ArrayVectorInsert.addLast(4);demo1ArrayVectorInsert.addLast(5);// 遍历的方法// ① 自己写一个for循环,在类中写一个函数返回数组长度for (int i = 0; i < demo1ArrayVectorInsert.length(); i++) {System.out.print(demo1ArrayVectorInsert.get(i)+" ");}System.out.println(" ");// ② 在数组中写一个遍历的函数,调用函数demo1ArrayVectorInsert.forEach();// ③ 类定义一个接口,在数组中遍历的函数参数传递一个泛型,在调用函数时进行具体的实现demo1ArrayVectorInsert.forEach(element -> {demo1ArrayVectorInsert.forEach();System.out.print(element+" ");});// ④ 类定义一个接口,定义一个方法传递泛型类型,调用该方法时时进行具体的实现// 将来可以直接调用时修改函数,不需要再函数的定义内部进行代码的修改demo1ArrayVectorInsert.forEachGenirics(element -> {System.out.println(element);});// ⑤ 迭代器遍历:实现接口,用增强for循环使用demo1ArrayVectorInsert.Foreach(element->{demo1ArrayVectorInsert.forEach();System.out.print(element+" ");});}@Test@DisplayName("删除遍历")public void test3() {demo1ArrayVectorInsert demo1ArrayVectorInsert = new demo1ArrayVectorInsert();demo1ArrayVectorInsert.addLast(1);demo1ArrayVectorInsert.addLast(2);demo1ArrayVectorInsert.addLast(3);demo1ArrayVectorInsert.addLast(4);demo1ArrayVectorInsert.addLast(5);for (Integer element : demo1ArrayVectorInsert) {// hashNext() next()System.out.print(element+" ");}}@Test@DisplayName("删除遍历")public void test4() {demo1ArrayVectorInsert demo1ArrayVectorInsert = new demo1ArrayVectorInsert();demo1ArrayVectorInsert.addLast(1);demo1ArrayVectorInsert.addLast(2);demo1ArrayVectorInsert.addLast(3);demo1ArrayVectorInsert.addLast(4);demo1ArrayVectorInsert.addLast(5);demo1ArrayVectorInsert.stream().forEach(element->{System.out.print(element+" ");});}@Test@DisplayName("删除测试")public void test5() {demo1ArrayVectorInsert demo1ArrayVectorInsert = new demo1ArrayVectorInsert();demo1ArrayVectorInsert.addLast(1);demo1ArrayVectorInsert.addLast(2);demo1ArrayVectorInsert.addLast(3);demo1ArrayVectorInsert.addLast(4);demo1ArrayVectorInsert.addLast(5);// 删除第三位,索引为2的元素int removed = demo1ArrayVectorInsert.remove(2);demo1ArrayVectorInsert.forEach();// 验证期望删除值与返回值是否相等if(3 == removed){System.out.println("true");}else{System.out.println("false");}int removed2 = demo1ArrayVectorInsert.remove(3);demo1ArrayVectorInsert.forEach();// 验证期望删除值与返回值是否相等if(5 == removed){System.out.println("true");}else{System.out.println("false");}}@Test@DisplayName("扩容数组")public void test6() {demo1ArrayVectorInsert demo1ArrayVectorInsert = new demo1ArrayVectorInsert();for (int i = 0; i < 9; i++) {demo1ArrayVectorInsert.addLast(i+1);}demo1ArrayVectorInsert demo1ArrayVectorInsert1 = new demo1ArrayVectorInsert();demo1ArrayVectorInsert1.add(0,1);demo1ArrayVectorInsert1.add(1,2);demo1ArrayVectorInsert1.add(2,3);demo1ArrayVectorInsert1.add(3,4);demo1ArrayVectorInsert1.add(4,5);demo1ArrayVectorInsert1.add(5,6);demo1ArrayVectorInsert1.add(6,7);demo1ArrayVectorInsert1.add(7,8);demo1ArrayVectorInsert1.add(8,9);System.out.println("创建的新数组与目标数组是否相等:"+ demo1ArrayVectorInsert1.equals(demo1ArrayVectorInsert));}
}

7.插入或删除性能

① 头部位置,时间复杂度是 O(n)

② 中间位置,时间复杂度是 O(n)

③ 尾部位置,时间复杂度是 O(1) (均摊来说)

四、二维数组

1.定义格式

int[][] array = {{11,12,13,14,15},{21,22,23,24,25},{31,32,33,34,35}};

2.内存分布及内存占用

i:代表外层数组的索引位置

j:代表内层数组的索引位置

五、数组的缓存与局部性原理

局部性原理

这里只讨论空间局部性

       ① cpu读取内存(速度慢)数据后,会将其放入高速缓存(速度快)当中,如果后来的计算再用到此数据在缓存中能读到的话,就不必读内存了

        ② 缓存的最小存储单位是缓存行(cache line),一般是 64 bytes,一次读的数据少了不划算,因此最少读 64 bvtes 填满一个缓存行,因此读入某个数据时也会读取其临近的数据,这就是所谓空间局部性

        先行后列访问的是连续内存,先列后行访问的是非连续内存,相当于访问链表

先i后j:int[0][0] ——> [0][1] ——> [0][2]... ——> [0][j]int[1][0] ——> [1][1] ——> [1[2]... ——> [1][j]……int[i][0] ——> [i][1] ——> [i[2]... ——> [i][j]先j后i:int[0][0]int[1][0]int[2][0]…int[i][0]……int[][j]

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.ldbm.cn/p/440105.html

如若内容造成侵权/违法违规/事实不符,请联系编程新知网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【C语言】了解函数,认识函数

目录 一、函数的概念 函数特点 二、库函数 1.标准库和头文件 2.库函数的使用方法 常见的库函数总结 3.自定义函数 1.函数的形参和实参 2.数组做参数时&#xff1a; 四、 函数的嵌套调用和链式访问 1.嵌套调用 链式访问 五、函数的声明和定义 1.单个文件 多个文件&…

CodeFormer——卓越的AI照片修复工具,能够轻松消除图片以及视频中的马赛克,还原清晰画质。

CodeFormer是什么 CodeFormer是一款由南洋理工大学和商汤科技联合开发的AI照片和视频修复工具。融合了变分自动编码器&#xff08;VQGAN&#xff09;和Transformer技术&#xff0c;对模糊和马赛克的照片或视频进行高质量的修复。CodeFormer通过先进的算法优化图像细节&#xf…

SpringBoot学习(14)增删改查

快速上手 配置文件 pom 包配置 pom 包里面添加 Jpa 和 Thymeleaf 的相关包引用 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-web</artifactId> </dependency> <dependency><gr…

Android中SurfaceView的双缓冲机制和普通View叠加问题解决办法

本文首发于公众号“AntDream”&#xff0c;欢迎微信搜索“AntDream”或扫描文章底部二维码关注&#xff0c;和我一起每天进步一点点 SurfaceView 是 Android 平台上用于高效渲染图形的视图控件。它将内容绘制在一个独立的 Surface 上&#xff0c;可以直接由渲染线程访问&#x…

IBM中国撤出研发中心:对学生和行业的影响与反思

最近&#xff0c;IBM中国宣布关闭了其在中国的两大研发中心&#xff0c;这一决定迅速引发了IT行业的广泛关注和讨论。作为一个即将毕业的在校大学生&#xff0c;准备进入IT行业&#xff0c;这样的消息无疑让我们这些学生心中产生了许多疑问与担忧。跨国公司在中国的战略调整背后…

【STM32】呼吸灯实现

对应pwm概念可以去看我的博客51实现的呼吸灯 根据对应图我们可知预分频系数为999&#xff0c;重装载值为2000&#xff0c;因为设置内部时钟晶振频率为100MHZ &#xff0c;1s跳 100 000000次 &#xff0c;跳一次需要1/100 000000s 20ms0.02s 对应跳的次数为 我们使用通用定时器…

HTML 超链接

每一个网站都是由许多独立的网页组成&#xff0c;网页之家通常都是通过超链接来相互连接的。超链接可以让用户在各个独立的网页之间跳转。 <!DOCTYPE html> <html> <head><meta charset"utf-8" /><title>colspan属性</title>&l…

Acrobat Pro DC 2023 for Mac/Win:全能型PDF编辑器深度解析

Adobe Acrobat Pro DC 2023作为一款跨平台的PDF编辑器&#xff0c;无论是对于Mac还是Windows用户&#xff0c;都提供了极为全面且强大的PDF处理功能。该软件凭借其卓越的性能和丰富的特性&#xff0c;成为了全球范围内用户处理PDF文档的首选工具。 一、强大的编辑功能 Acroba…

表格多列情况下,loading不显示问题

问题描述&#xff1a; 用element plus 做得表格&#xff0c;如下图&#xff0c;列数较多&#xff0c;且部分表格内容显示比较复杂&#xff0c;数据量中等的情况下&#xff0c;有一个switch 按钮&#xff0c;切换部分列的显示和隐藏&#xff0c;会发现&#xff0c;切换为显示的时…

上交团队发布PathoDuet:面向HE和IHC病理切片的自监督学习基础模型|文献精析·24-09-09

小罗碎碎念 本期主题&#xff1a;HE&IHC 今天分享的文献于2024年7月31日发表于Medical Image Analysis&#xff0c;目前IF10.7&#xff0c;作者来自上海交大。 作者类型姓名单位单位翻译第一作者Shengyi HuaQing Yuan Research Institute, Shanghai Jiao Tong University, …

Qt工程实践_06_Qt MSVC2O17编译器下的程序添加VS2017生成的动态链接库方法

文章目录 1. 利用VS2017生成动态链接库1.1 创建C++空项目1.2 添加.h和.cpp内容:添加了一个减法运算1.3 设置动态链接库目标计算机类型1.4 设置项目属性为动态库1.5 生成项目,复制需要的文件2. Qt程序使用VS2017生成的动态链接库方法2.1 创建Widget程序2.2 链接动态库文件2.2.…

优化销售流程,领先市场趋势!企元数智赠送小程序合规分销系统!

在当今竞争激烈的商业环境中&#xff0c;企业要保持竞争力并领先市场趋势&#xff0c;关键在于不断优化销售流程和采用最新的营销工具。为满这一迫切需求&#xff0c;企元数智&#xff08;假设为一家虚构公司&#xff09;推出了一项创新举措&#xff1a;赠送小程序合规分销系统…

Ollama 本地运行大模型(LLM)完全指南

文章介绍了 Ollama 本地运行大模型&#xff08;LLM&#xff09;的方方面面&#xff0c; 包括安装运行、对话、自定义模型、系统提示配置、调试、开发、存储、如何作为服务、OpenAI 的兼容等。 这一年来&#xff0c;我已经习惯了使用线上大模型 API 来工作&#xff0c;只要网络…

2024年AMC10美国数学竞赛倒计时两个月:吃透1250道真题和知识点(持续)

根据通知&#xff0c;2024年AMC10美国数学竞赛的报名还有两周&#xff0c;正式比赛还有两个月就要开始了。计划参赛的孩子们要记好时间&#xff0c;认真备考&#xff0c;最后冲刺再提高成绩。 那么如何备考2024年AMC10美国数学竞赛呢&#xff1f;做真题&#xff0c;吃透真题和…

云计算和传统IT相比,有哪些优势?

云计算相比于传统的IT基础设施&#xff0c;具有以下一些显著的优势&#xff1a; 成本效益&#xff1a; 云计算通常采用按需付费模式&#xff0c;用户只需为实际使用的资源支付费用&#xff0c;避免了高昂的前期硬件投资和维护成本。 弹性计费方式使得企业可以根据业务需求灵活调…

【C++ Primer Plus习题】13.2

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream> #include "classic.h&quo…

【大数据分析与挖掘算法】matlab实现——Apriori关联规则算法

实验一 &#xff1a;Apriori关联规则算法 一、实验目的 掌握有关Apriori关联规则算法的理论知识&#xff0c;从中了解关联规则的数学模型、基本思想、方法及应用。 二、实验任务 根据某超市的五条客户购物清单记录&#xff0c;使用Apriori关联规则算法进行计算&#xff0c;…

【MySQL】MySQL表的操作

目录 创建表的语法创建表的示例查看表的结构进入数据库查看自己在哪个数据库查看自己所在数据库都有哪些表查看表的详细信息查看创建表时的详细信息 修改表修改表名修改表的内容插入几个数据增加一列修改一列的所有属性删除某一列修改列的名称 删除表 创建表的语法 CREATE TAB…

ML 系列:机器学习和深度学习的深层次总结(01)

​ 文章目录 一、说明二、人工智能和机器学习三、机器学习的类型四、结论 一、说明 欢迎学习机器学习系列。这门综合课程目前包括40个部分&#xff0c;指导您了解机器学习、统计和数据分析的基本概念和技术。以下是到目前为止涵盖的关键主题的简要概述&#xff1a; 1 机器学习…

汇舸环保从北交所转战港交所:狂分红超8000万,客户依赖度越来越高

《港湾商业观察》施子夫 7月31日&#xff0c;上海汇舸环保科技集团股份有限公司&#xff08;以下简称&#xff0c;汇舸环保&#xff09;递表港交所获受理&#xff0c;联席保荐机构中信证券和中国银河证券。 8月14日&#xff0c;公司披露公告称&#xff0c;另委任法国巴黎证券…