java学习之数据结构：一、数组

主要是对数组所有的东西进行总结，整理

适合小白~

目录

1.什么是数组

1.1数组定义

1.2数组创建

1）静态创建

2）动态创建

 1.3数组遍历

1）for和while遍历

2）foreach遍历

2.数组越界问题及解决

2.1数组越界问题

2.2越界问题解决----数组拷贝扩容

1）防止发生：

2）发生后解决：

3）采用List list = new ArrayList<>();

3.数组算法

3.1插入算法

1）尾插法

2）指定位置插入法

2.删除

1）删除第一个符合条件的数据

2）删除所有符合条件的数据

3）使用快慢指针删除元素

3.查找算法

1）二分查找法

---

1.什么是数组

1.1数组定义

数组是一种用于存储固定大小的同类型元素的集合，是一种数据结构。

        int[] arr = {1,2,3,4,5,6,7,8,9,10};char[] chars = {'a','b','c','d','e','f','g','h','i','j'};String[] strings = {"hello","world","java","python","c++"};double[] doubles = {1.1,2.2,3.3,4.4,5.5,6.6,7.7,8.8,9.9,10.10};

1.2数组创建

有两种方式。[两者相比后者灵活性更高，区别不大，针对需求选择格式使用]

1）静态创建

在创建数组时就明确地指定数组中的元素，数组的长度由指定的元素个数决定。

// 基本数据类型数组
int[] staticArray1 = {1, 2, 3, 4, 5};
// 对象数组
String[] staticArray2 = {"apple", "banana", "cherry"};

2）动态创建

在创建数组时只指定数组的长度，而不具体给出数组元素的初始值。后续可以再对数组元素进行赋值操作。

// 基本数据类型数组
int[] dynamicArray1 = new int[5];List<Integer> list = new ArrayList<>();

 1.3数组遍历

java中数组有两种常见的遍历方式

1）for和while遍历

2）foreach遍历

这种方式不能修改数组值和单独访问下标索引。形式为for( int name : names)表示对数组names中的每个元素都复制给name然后执行

        int[] arr = {1,2,3,4,5,6,7,8,9,10};
//        for遍历for (int i = 0; i < arr.length; i++) {System.out.println(arr[i]);}
//        while遍历int i = 0;while (i< arr.length){System.out.println(arr[i]);}
//        foreach遍历for (int i : arr) {System.out.println(i);}

2.数组越界问题及解决

2.1数组越界问题

数组越界：访问的索引值超过了数组的最大长度-1[因为数组下标从0开始]。或者是添加元素超过了数组最大长度-1、删除数组中没有的元素

越界异常提示实例如下：

        int[] arr = {1,2,3,4,5,6,7,8,9,10};System.out.println(arr[10]);

提示为：

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 10 out of bounds for length 10
    at com.weimeng.test.array.main(array.java:25)

2.2越界问题解决----数组拷贝扩容

发生越界后有以下解决方法：

1）防止发生：

仔细检查索引计算：在编写代码时，要确保索引的计算不会超出数组的有效范围。

进行边界检查：在访问数组元素之前，先检查索引是否在有效范围内。可以编写一个if辅助方法来进行边界检查，避免越界访问。

2）发生后解决：

数组扩容：就是创建新数组再拷贝原数组元素，新数组的长度更长。先创建新数组，再将原数组元素复制过来，最后替换引用。如下：

        int[] arr = {1,2,3,4,5,6,7,8,9,10};
//        数组扩容
//先创建新数组，再将原数组元素复制过来，最后替换引用int len=arr.length;double factor=1.5;//扩大因子int[] brr=new int[(int) (len*factor)];//新数组for(int i=0;i<len;i++){brr[i]=arr[i];}arr=brr;System.out.println(arr[10]);

3）采用List<Integer> list = new ArrayList<>();

这种方法可以防止添加元素越界，访问越界和删除越界可以再结合1）方式。

3.数组算法

3.1插入算法

数组的插入算法是指在数组的特定位置插入一个新元素的操作。由于数组的特性（元素在内存中连续存储，长度固定），插入元素可能需要移动其他元素来腾出空间。

1）尾插法

尾插法过程：判断数组满没满，没满就直接放入数组最后元素的下一个位置；满了就进行扩容再插入。整个过程通过size控制，代码如下：

public class Array1 {int size=0;int len=10;double factor=1.5;//扩大因子int arr[]=new int[len];//        目标：实现尾插法public static void main(String[] args) {Array1 list=new Array1();list.add(1);list.add(2);list.add(3);System.out.println(list.toString());}public void add(int data){if(size==len){len=(int)(len*factor);int[] brr=new int[len];for(int i=0;i<size;i++){brr[i]=arr[i];}arr=brr;}arr[size]=data;size++;}public String toString(){String str="[";for(int i=0;i<size;i++){str+=arr[i];if(i!=size-1){str+=",";}}str+="]";return str;}
}

2）指定位置插入法

算法原理：先判断插入位置是否合理，保证代码合法性；再判断数组是否满；插入时反向循环，先将size++，然后arr[i]=size[i-1]进行循环，如下图所示：

//    指定位置插入public void addAtIndex(int index,int data){//保证数组访问安全if(index<0||index>size){System.out.println("超出范围");return;}//扩容if(size==len){len=(int)(len*factor);int[] brr=new int[len];for(int i=0;i<size;i++){brr[i]=arr[i];}arr=brr;}size++;for(int i=size;i>index;i--){arr[i]=arr[i-1];}arr[index]=data;}public String toString(){String str="[";for(int i=0;i<size;i++){str+=arr[i];if(i!=size-1){str+=",";}}str+="]";return str;}

2.删除

1）删除第一个符合条件的数据

原理：从前向后遍历，找删除的数据。找不到直接输出“不存在该元素”；找到则记录该位置，通过循环从该位置开始，arr[i]=arr[i+1]覆盖掉，size--,输出“删除完成"

 public void remove(int data) {for (int i = 0; i < size; i++) {if (arr[i] == data) {// 移动元素覆盖要删除的元素for (int j = i; j < size - 1; j++) {arr[j] = arr[j + 1];}// 最后一个有效位置置为默认值arr[size - 1] = 0;size--;System.out.println("删除成功");return;}}System.out.println("不存在该元素");}

2）删除所有符合条件的数据

即通过循环遍历元素，遇到arr[i]==data就进行删除，如下：

    public void delete(int data) {for(int i=0;i<size;i++){if(arr[i]==data){for(int j=i+1;j<size;j++){arr[j-1]=arr[j];}size--;i--;}}}

3）使用快慢指针删除元素

• 慢指针（slow）：用于记录删除特定元素后数组的有效长度，它指向的位置是下一个非data元素应该存放的位置。
• 快指针（fast）：用于遍历数组中的每一个元素。

具体步骤：

1.初始化两个指针：slow 和 fast，都指向arr的起始位置（索引为 0）。

2.使用 fast 指针遍历数组：如果 fast 指针指向的元素不等于data，则将该元素赋值给 slow 指针指向的位置，然后 slow 指针向后移动一位。如果 fast 指针指向的元素等于data，则跳过该元素，slow 指针保持不动。

重复步骤 2，直到 fast 指针遍历完整个数组。最终 slow 指针的值就是删除特定元素后数组的新长度。

代码：

//    使用快慢指针删除元素public void delete2(int data){int slow=0;int fast=0;while(fast<size){if(arr[fast]!=data){arr[slow]=arr[fast];slow++;}fast++;}size=slow;}

3.查找算法

1）二分查找法

二分查找适合有序数组，它的核心思想是不断将查找区间缩小一半，以此减少查找范围，从而快速定位目标元素。

算法内容：

1.先设置左右边界，左边界 left 初始化为数组的第一个元素的索引（通常为 0），右边界 right 初始化为数组最后一个元素的索引（即数组长度减 1）。

2.再计算当前查找区间的中间元素的索引 mid，计算公式为 mid = left + (right - left) / 2。

3.比较中间元素跟目标元素：若中间元素等于目标元素，表明找到了目标元素，返回中间元素的索引。若中间元素大于目标元素，说明目标元素在左半部分区间，更新右边界 right = mid - 1。若中间元素小于目标元素，说明目标元素在右半部分区间，更新左边界 left = mid + 1。

4.重复2、3步，持续缩小查找区间，直到左边界大于右边界，此时表示目标元素不存在于数组中，返回 -1。

代码：

public int binarySearch(int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = (right + left) / 2;if (arr[mid] == target) {return mid;} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return-1;}