【数据结构与算法之线性结构】数组

你的名字 2024-03-25 10:14 49阅读 0赞

#### 【数据结构与算法之线性结构】数组 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之线性结构】数组
         *   *   *  1 数组的基本概念
                 *  2 数组的定义
                 *  3 数组的基本操作
                 *   *  向数组中插入元素
                     *  从数组中删除元素
                 *  4 数组性能分析
                 *  5 其他案例
                 *   *  数组元素逆置
                     *  删除数组中的重复元素

###### 1 数组的基本概念 ######

数组Array是最简单的数据结构，是由有限个`相同类型`的变量(或对象)组成的有序集合。

![在这里插入图片描述][3017a2021d1e4cc7aa5990849f759990.png_pic_center]

【数组的特征】

*  数组用唯一的名字标识，通过数组名可以数组中的元素进行引用，例如arr\[0\] 表示数组arr 中的第一个元素。
 *  数组中的元素类型必须相同。
 *  数组的内存单元是连续的。
 *  数组中的数据元素都是顺序存放的。有先后关系，且元素之间没有空隙

总之，数组是一种物理空间和逻辑形式都连续的线性数据结构。

###### 2 数组的定义 ######

package 数组的定义;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: ArrayDefine
     * @Author: Ding Jiaxiong
     * @Data:2023/3/12 17:58
     */
    
    public class ArrayDefine {
        
    
        public static void main(String[] args) {
        
            
            int[] array1; // 【推荐】
            int array2[];
    
        }
    }

当然这样只是声明了一个引用变量，其本质是一个指针，要使用该数组，需要进行初始化。

package 数组的定义;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: ArrayInitialization
     * @Author: Ding Jiaxiong
     * @Data:2023/3/12 18:01
     */
    
    public class ArrayInitialization {
        
    
        public static void main(String[] args) {
        
    
            // 静态初始化
            // ①
            int[] array1 = {
        1, 2, 3, 4, 5, 6};
            // ②
            int[] array2;
            array2 = new int[]{
        1, 2, 3, 4, 5, 6};
    
            // 动态初始化
            // ①
            int[] array3 = new int[6]; // 不指定元素值
    
            // ②
            int[] array4;
            array4 = new int[6];
    
        }
    }

【定义我们自己的数组类】对数组的属性和操作进行封装。

package 数组的定义;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: MyArray
     * @Author: Ding Jiaxiong
     * @Data:2023/3/12 18:05
     */
    
    public class MyArray {
        
    
        int[] array;  // 数组本身
        int elemNumber; // 记录数组中的元素个数
    
        public MyArray(int capacity) {
        
            array = new int[capacity]; // 动态初始化数组，长度为capacity
            elemNumber = capacity;
        }
    
        public boolean insertElem(int elem, int index) {
        
            // 在数组的第index索引处插入elem元素
        }
    
        public boolean deleteElem(int index) {
        
            // 删除数组index索引处的元素
        }
    }

###### 3 数组的基本操作 ######

###### 向数组中插入元素 ######

在数组的index 索引位置插入elem元素，意为原index 索引以及之后位置上的元素都要向后移动一个位置。

主要就分为两步：

① 将数组中index 索引上以及之后的所有元素都向后移动一个位置，把数组的index 位置空出。

② 将新的元素插到数组的index 索引位置。

运行结果

![在这里插入图片描述][5fbc7f6441934fc5b319ec642b124743.png_pic_center]

> 这里没有严格的写清楚index，它不是索引，它不是索引，它不是索引。

模拟一下数组越界。

![在这里插入图片描述][c20203a5111f4f3abfc4202a8d9d7550.png_pic_center]

因为容量只有5，想再插入第6个元素，就不行了。

来一个扩容机制。

package 数组的基本操作;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: MyArray
     * @Author: Ding Jiaxiong
     * @Data:2023/3/12 18:14
     */
    
    public class MyArray {
        
    
        int[] array;  // 数组本身
        int elemNumber; // 记录数组中的元素个数
    
        public MyArray(int capacity) {
        
            array = new int[capacity]; // 动态初始化数组，长度为capacity
            elemNumber = 0;
        }
    
        public boolean insertElem(int elem, int index) {
        
            // 在数组的第index个位置处插入elem元素【不是索引位置】
            // 判断index是否合法
            if (index < 1 || index > elemNumber + 1) {
        
                System.out.println("插入位置错误");
                return false;
            }
    
            // 当数组元素数量等于数组容量时，对其进行扩容
            if (elemNumber == array.length) {
        
                increaseCapacity();
            }
    
            // 将index上元素及之后所有元素全部往后移动
            for (int i = elemNumber - 1; i >= index - 1; i--) {
        
                array[i + 1] = array[i];
            }
            // 将新元素插入空的array[index]
            array[index - 1] = elem; // array[index - 1] 就是数组的第index 个元素
            elemNumber++; // 数组元素数量 + 1
            return true;
        }
    
        private void increaseCapacity() {
        
            // 初始化一个新数组，容量是array容量的2倍
            int[] arrayTmp = new int[array.length * 2];
    
            // 将原数组array的内容拷贝到新数组
            System.arraycopy(array, 0, arrayTmp, 0, array.length);
            array = arrayTmp;  // 让array指向这个数组
        }
    
        public void printArray() {
        
            // 打印数组内容
            for (int i = 0; i < elemNumber; i++) {
        
                System.out.print(array[i] + " ");
            }
            System.out.println(); // 换行
        }
    
        public static void main(String[] args) {
        
            MyArray array = new MyArray(5);
    
            array.insertElem(3, 1);
            array.insertElem(5, 2);
            array.insertElem(2, 3);
            array.insertElem(7, 4);
            array.insertElem(8, 5);
    
            array.printArray();
            array.insertElem(0, 3);
            array.printArray();
    
        }
    
    }

再试一次【再说一次，index 为 3，是第3个元素，不是索引为3的元素。】

![在这里插入图片描述][fab1772372b7498b9513e071c48563f6.png_pic_center]

这次就过去了。

###### 从数组中删除元素 ######

与插入相反，只需要将index 位置之后的元素，不含index本身，顺序向前移动一个位置，并将数组元素的数量 - 1，即可完成删除操作。

package 数组的基本操作;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: MyArray
     * @Author: Ding Jiaxiong
     * @Data:2023/3/12 18:14
     */
    
    public class MyArray {
        
    
        int[] array;  // 数组本身
        int elemNumber; // 记录数组中的元素个数
    
        public MyArray(int capacity) {
        
            array = new int[capacity]; // 动态初始化数组，长度为capacity
            elemNumber = 0;
        }
    
        public boolean insertElem(int elem, int index) {
        
            // 在数组的第index个位置处插入elem元素【不是索引位置】
            // 判断index是否合法
            if (index < 1 || index > elemNumber + 1) {
        
                System.out.println("插入位置错误");
                return false;
            }
    
            // 当数组元素数量等于数组容量时，对其进行扩容
            if (elemNumber == array.length) {
        
                increaseCapacity();
            }
    
            // 将index上元素及之后所有元素全部往后移动
            for (int i = elemNumber - 1; i >= index - 1; i--) {
        
                array[i + 1] = array[i];
            }
            // 将新元素插入空的array[index]
            array[index - 1] = elem; // array[index - 1] 就是数组的第index 个元素
            elemNumber++; // 数组元素数量 + 1
            return true;
        }
    
        private void increaseCapacity() {
        
            // 初始化一个新数组，容量是array容量的2倍
            int[] arrayTmp = new int[array.length * 2];
    
            // 将原数组array的内容拷贝到新数组
            System.arraycopy(array, 0, arrayTmp, 0, array.length);
            array = arrayTmp;  // 让array指向这个数组
        }
    
        // 删除第index个位置上的元素【index非索引下标】
        public boolean deleteElem(int index) {
        
            // 判断index是否合法
            if (index < 1 || index > elemNumber) {
        
                System.out.println("删除元素位置错误");
                return false;
            }
            // 将index 位置之后的元素向前移动
            for (int i = index; i < elemNumber; i++) {
        
                array[i - 1] = array[i];
            }
            // 数组元素数量 - 1
            elemNumber--;
            return true;
        }
    
        public void printArray() {
        
            // 打印数组内容
            for (int i = 0; i < elemNumber; i++) {
        
                System.out.print(array[i] + " ");
            }
            System.out.println(); // 换行
        }
    
        public static void main(String[] args) {
        
            MyArray array = new MyArray(5);
    
            array.insertElem(3, 1);
            array.insertElem(5, 2);
            array.insertElem(2, 3);
            array.insertElem(7, 4);
            array.insertElem(8, 5);
    
            array.printArray();
            array.deleteElem(3);
            array.printArray();
    
        }
    
    }

运行结果【注意是删第3个元素，不是索引为3的元素】

![在这里插入图片描述][9c5d374d7873462b855ee0546e867500.png_pic_center]

###### 4 数组性能分析 ######

*   O ( 1 ) O(1) O(1) 时间复杂度直接定位元素
 *  插入、删除元素时间复杂度都是 O ( n ) O(n) O(n)

###### 5 其他案例 ######

###### 数组元素逆置 ######

> 当然Arrays 工具类谁都会用，搞算法直接调方法就没必要了

编写函数reverseArray()，将数组中的元素逆置。

// 逆置
    public void reverseArray() {
        
        int temElem; // 数据缓冲【实现数据交换】
        int low = 0, high = elemNumber - 1;  //low指向数组第一个元素arr[0], high指向最后一个元素arr[elemNumber - 1]
    
        while (low < high) {
        
            temElem = array[low];
            array[low] = array[high];
            array[high] = temElem;
            low++;
            high--;
        }
    }

测试

public static void main(String[] args) {
        
        MyArray array = new MyArray(5);
        for (int i = 0; i < 5; i++) {
        
            array.insertElem(i + 1, i + 1);
        }
    
        array.printArray();
        array.reverseArray();
        array.printArray();
    
    }

运行结果

![在这里插入图片描述][9d6750c6df274ac4ac73ef9cfb92c890.png_pic_center]

###### 删除数组中的重复元素 ######

实现有很多种方法：

1.  定位一个数组元素，从前往后扫描，如果发现与定位元素相同的元素，就删除它。不断调整定位，直到删除所有重复元素。
    
        void purge() {
              
            int i = 0, j;
            while (i < elemNumber) {
              
                j = i + 1; // 从arr[i + 1]开始逐个比较
                while (j < elemNumber) {
              
                    if (array[i] == array[j]) {
              
                        deleteElem(j + 1);
                    } else {
              
                        j++;
                    }
                }
                i++; // 定位下一个元素
            }
        }
        
        public static void main(String[] args) {
              
            MyArray array = new MyArray(10);
            // [1,1,3,5,2,3,1,5,6,8]
            array.insertElem(1, 1);
            array.insertElem(1, 2);
            array.insertElem(3, 3);
            array.insertElem(5, 4);
            array.insertElem(2, 5);
            array.insertElem(3, 6);
            array.insertElem(1, 7);
            array.insertElem(5, 8);
            array.insertElem(6, 9);
            array.insertElem(8, 10);
        
            array.printArray();
            array.purge();
            array.printArray();
        
        }
    
    运行结果
    
    ![在这里插入图片描述][f32cb5981647448a9921117631d54299.png_pic_center]
    
    功能是实现了，但是时间复杂度已经来到了 O ( n 3 ) O(n^3) O(n3) 【 两次 w h i l e 循环 ∗ 删除元素 两次while循环 \* 删除元素 两次while循环∗删除元素】
2.  稍微优化一下第一种方法，当找到重复元素后，不立马进行删除，而是做个标记，扫描完毕后，整体删除，这样就只需要执行一次二重循环找到重复元素，再加上一次循环删除就OK了，时间复杂度  O ( n 2 ) + O ( n ) → O ( n 2 ) O(n^2) + O(n) → O(n^2) O(n2)\+O(n)→O(n2)
    
        void purge2() {
              
            int i, j;
            int FLAG = -111;
        
            int number = elemNumber;
            // 将重复元素用FLAG覆盖
            for (i = 0; i < number; i++) {
              
                if (array[i] != FLAG) {
              
                    for (j = i + 1; j < elemNumber; j++) {
              
                        if (array[i] == array[j]) {
              
                            array[j] = FLAG;
                        }
                    }
                }
            }
            // 找到第一个FLAG标记
            for (i = 0; array[i] != FLAG; i++) ;
        
            for (j = i + 1; j < number; ) {
              
                if (array[j] != FLAG) {
              
                    // 若array[j] 不是FLAG，则用array[j] 覆盖array[i],并且向后走
                    array[i++] = array[j++];
                } else {
               // 若array[j] 是FLAG，则j 直接向后走,寻找下一个非FLAG的有效值
                    j++;
                }
                elemNumber = i;
            }
        
        }
    
    测试
    
    ![在这里插入图片描述][e84bd0070b0a4e8d9fef8b57230f5d76.png_pic_center]
3.  使用哈希表。
    
        void purge3() {
              
            int i, j;
            int FLAG = -111;
            int number = elemNumber;
        
            HashSet<Integer> set = new HashSet<Integer>();
            for (i = 0; i < number; i++) {
              
                if (!set.add(array[i])) {
              
                    // 如果不能存储到集合中，则说明array[i]与set 中的元素有重复
                    array[i] = FLAG;
                }
            }
            for (i = 0; array[i] != FLAG; i++) ;  // 找到第一个FLAG
            for (j = i + 1; j < number; ) {
              
                if (array[j] != FLAG) {
              
                    array[i++] = array[j++];
                } else {
              
                    j++;
                }
                elemNumber = i;
            }
        }
    
    测试
    
    ![在这里插入图片描述][fc9f6150306540978efff434c580d10b.png_pic_center]
    
    利用HashSet 查找重复元素时间复杂度为 O ( n ) O(n) O(n)，将数组中的FLAG全部删除  O ( n ) O(n) O(n)，所以整个算法时间复杂度 O ( n ) O(n) O(n)，代价就是需要一个HashSet 额外开了空间。
    
    之所以标记FLAG其实是为了维持原本数组的顺序(稳定)，如果不在意数组元素顺序，只考虑删除重复元素就完事儿的话，可以直接将HashSet 中的元素读出，但也就是因为HashSet 中数据无序，所以从其中读出的元素可能与原数组元素顺序不一致。

[3017a2021d1e4cc7aa5990849f759990.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/256cf3aae87c47df8d75f3b9923c6697.png
[5fbc7f6441934fc5b319ec642b124743.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/293f4ef6f640400bb7fd2c4e53d51d44.png
[c20203a5111f4f3abfc4202a8d9d7550.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/381eba367dcd4ed4abf9ad887c9dbd28.png
[fab1772372b7498b9513e071c48563f6.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/ee081bd058bc4c8d9fd399b6e8bcee59.png
[9c5d374d7873462b855ee0546e867500.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/8d94b35fb9914f009f39390e5cbe254e.png
[9d6750c6df274ac4ac73ef9cfb92c890.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/4332f8550e42468297a6593b38cc1124.png
[f32cb5981647448a9921117631d54299.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/9515f005c8d5410bb5bb0182043217a8.png
[e84bd0070b0a4e8d9fef8b57230f5d76.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/032c5c25827e47d7b3cf985925bc2214.png
[fc9f6150306540978efff434c580d10b.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/ffb0d12543e143beaf82d98bb8d6e30e.png