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

梦里梦外; 2024-03-25 12:35 190阅读 0赞

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

文章目录

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

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

在这里插入图片描述

【数组的特征】

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

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

2 数组的定义
  1. package 数组的定义;
  3. /**
  4.  * @Projectname: JavaData_StructureAndAlgorithm
  5.  * @Classname: ArrayDefine
  6.  * @Author: Ding Jiaxiong
  7.  * @Data:2023/3/12 17:58
  8.  */
  10. public class ArrayDefine {
  13.     public static void main(String[] args) {
  16.         int[] array1; // 【推荐】
  17.         int array2[];
  19.     }
  20. }

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

  1. package 数组的定义;
  3. /**
  4.  * @Projectname: JavaData_StructureAndAlgorithm
  5.  * @Classname: ArrayInitialization
  6.  * @Author: Ding Jiaxiong
  7.  * @Data:2023/3/12 18:01
  8.  */
  10. public class ArrayInitialization {
  13.     public static void main(String[] args) {
  16.         // 静态初始化
  17.         // ①
  18.         int[] array1 = {
  19.     1, 2, 3, 4, 5, 6};
  20.         // ②
  21.         int[] array2;
  22.         array2 = new int[]{
  23.     1, 2, 3, 4, 5, 6};
  25.         // 动态初始化
  26.         // ①
  27.         int[] array3 = new int[6]; // 不指定元素值
  29.         // ②
  30.         int[] array4;
  31.         array4 = new int[6];
  33.     }
  34. }

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

  1. package 数组的定义;
  3. /**
  4.  * @Projectname: JavaData_StructureAndAlgorithm
  5.  * @Classname: MyArray
  6.  * @Author: Ding Jiaxiong
  7.  * @Data:2023/3/12 18:05
  8.  */
  10. public class MyArray {
  13.     int[] array;  // 数组本身
  14.     int elemNumber; // 记录数组中的元素个数
  16.     public MyArray(int capacity) {
  18.         array = new int[capacity]; // 动态初始化数组，长度为capacity
  19.         elemNumber = capacity;
  20.     }
  22.     public boolean insertElem(int elem, int index) {
  24.         // 在数组的第index索引处插入elem元素
  25.     }
  27.     public boolean deleteElem(int index) {
  29.         // 删除数组index索引处的元素
  30.     }
  31. }
3 数组的基本操作
向数组中插入元素

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

主要就分为两步：

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

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

在这里插入图片描述

  1. package 数组的基本操作;
  3. /**
  4.  * @Projectname: JavaData_StructureAndAlgorithm
  5.  * @Classname: MyArray
  6.  * @Author: Ding Jiaxiong
  7.  * @Data:2023/3/12 18:14
  8.  */
  10. public class MyArray {
  13.     int[] array;  // 数组本身
  14.     int elemNumber; // 记录数组中的元素个数
  16.     public MyArray(int capacity) {
  18.         array = new int[capacity]; // 动态初始化数组，长度为capacity
  19.         elemNumber = 0;
  20.     }
  22.     public boolean insertElem(int elem, int index) {
  24.         // 在数组的第index个位置处插入elem元素【不是索引位置】
  25.         // 判断index是否合法
  26.         if (index < 1 || index > elemNumber + 1) {
  28.             System.out.println("插入位置错误");
  29.             return false;
  30.         }
  31.         // 将index上元素及之后所有元素全部往后移动
  32.         for (int i = elemNumber - 1; i >= index - 1; i--) {
  34.             array[i + 1] = array[i];
  35.         }
  36.         // 将新元素插入空的array[index]
  37.         array[index - 1] = elem; // array[index - 1] 就是数组的第index 个元素
  38.         elemNumber++; // 数组元素数量 + 1
  39.         return true;
  40.     }
  42.     public void printArray() {
  44.         // 打印数组内容
  45.         for (int i = 0; i < elemNumber; i++) {
  47.             System.out.print(array[i] + " ");
  48.         }
  49.         System.out.println(); // 换行
  50.     }
  52.     public static void main(String[] args) {
  54.         MyArray array = new MyArray(8);
  56.         array.insertElem(3, 1);
  57.         array.insertElem(5, 2);
  58.         array.insertElem(2, 3);
  59.         array.insertElem(7, 4);
  60.         array.insertElem(8, 5);
  62.         array.printArray();
  63.         array.insertElem(0, 3);
  64.         array.printArray();
  66.     }
  68. }

运行结果

在这里插入图片描述

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

模拟一下数组越界。

在这里插入图片描述

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

来一个扩容机制。

  1. package 数组的基本操作;
  3. /**
  4.  * @Projectname: JavaData_StructureAndAlgorithm
  5.  * @Classname: MyArray
  6.  * @Author: Ding Jiaxiong
  7.  * @Data:2023/3/12 18:14
  8.  */
  10. public class MyArray {
  13.     int[] array;  // 数组本身
  14.     int elemNumber; // 记录数组中的元素个数
  16.     public MyArray(int capacity) {
  18.         array = new int[capacity]; // 动态初始化数组，长度为capacity
  19.         elemNumber = 0;
  20.     }
  22.     public boolean insertElem(int elem, int index) {
  24.         // 在数组的第index个位置处插入elem元素【不是索引位置】
  25.         // 判断index是否合法
  26.         if (index < 1 || index > elemNumber + 1) {
  28.             System.out.println("插入位置错误");
  29.             return false;
  30.         }
  32.         // 当数组元素数量等于数组容量时，对其进行扩容
  33.         if (elemNumber == array.length) {
  35.             increaseCapacity();
  36.         }
  38.         // 将index上元素及之后所有元素全部往后移动
  39.         for (int i = elemNumber - 1; i >= index - 1; i--) {
  41.             array[i + 1] = array[i];
  42.         }
  43.         // 将新元素插入空的array[index]
  44.         array[index - 1] = elem; // array[index - 1] 就是数组的第index 个元素
  45.         elemNumber++; // 数组元素数量 + 1
  46.         return true;
  47.     }
  49.     private void increaseCapacity() {
  51.         // 初始化一个新数组，容量是array容量的2倍
  52.         int[] arrayTmp = new int[array.length * 2];
  54.         // 将原数组array的内容拷贝到新数组
  55.         System.arraycopy(array, 0, arrayTmp, 0, array.length);
  56.         array = arrayTmp;  // 让array指向这个数组
  57.     }
  59.     public void printArray() {
  61.         // 打印数组内容
  62.         for (int i = 0; i < elemNumber; i++) {
  64.             System.out.print(array[i] + " ");
  65.         }
  66.         System.out.println(); // 换行
  67.     }
  69.     public static void main(String[] args) {
  71.         MyArray array = new MyArray(5);
  73.         array.insertElem(3, 1);
  74.         array.insertElem(5, 2);
  75.         array.insertElem(2, 3);
  76.         array.insertElem(7, 4);
  77.         array.insertElem(8, 5);
  79.         array.printArray();
  80.         array.insertElem(0, 3);
  81.         array.printArray();
  83.     }
  85. }

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

在这里插入图片描述

这次就过去了。

从数组中删除元素

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

在这里插入图片描述

  1. package 数组的基本操作;
  3. /**
  4.  * @Projectname: JavaData_StructureAndAlgorithm
  5.  * @Classname: MyArray
  6.  * @Author: Ding Jiaxiong
  7.  * @Data:2023/3/12 18:14
  8.  */
  10. public class MyArray {
  13.     int[] array;  // 数组本身
  14.     int elemNumber; // 记录数组中的元素个数
  16.     public MyArray(int capacity) {
  18.         array = new int[capacity]; // 动态初始化数组，长度为capacity
  19.         elemNumber = 0;
  20.     }
  22.     public boolean insertElem(int elem, int index) {
  24.         // 在数组的第index个位置处插入elem元素【不是索引位置】
  25.         // 判断index是否合法
  26.         if (index < 1 || index > elemNumber + 1) {
  28.             System.out.println("插入位置错误");
  29.             return false;
  30.         }
  32.         // 当数组元素数量等于数组容量时，对其进行扩容
  33.         if (elemNumber == array.length) {
  35.             increaseCapacity();
  36.         }
  38.         // 将index上元素及之后所有元素全部往后移动
  39.         for (int i = elemNumber - 1; i >= index - 1; i--) {
  41.             array[i + 1] = array[i];
  42.         }
  43.         // 将新元素插入空的array[index]
  44.         array[index - 1] = elem; // array[index - 1] 就是数组的第index 个元素
  45.         elemNumber++; // 数组元素数量 + 1
  46.         return true;
  47.     }
  49.     private void increaseCapacity() {
  51.         // 初始化一个新数组，容量是array容量的2倍
  52.         int[] arrayTmp = new int[array.length * 2];
  54.         // 将原数组array的内容拷贝到新数组
  55.         System.arraycopy(array, 0, arrayTmp, 0, array.length);
  56.         array = arrayTmp;  // 让array指向这个数组
  57.     }
  59.     // 删除第index个位置上的元素【index非索引下标】
  60.     public boolean deleteElem(int index) {
  62.         // 判断index是否合法
  63.         if (index < 1 || index > elemNumber) {
  65.             System.out.println("删除元素位置错误");
  66.             return false;
  67.         }
  68.         // 将index 位置之后的元素向前移动
  69.         for (int i = index; i < elemNumber; i++) {
  71.             array[i - 1] = array[i];
  72.         }
  73.         // 数组元素数量 - 1
  74.         elemNumber--;
  75.         return true;
  76.     }
  78.     public void printArray() {
  80.         // 打印数组内容
  81.         for (int i = 0; i < elemNumber; i++) {
  83.             System.out.print(array[i] + " ");
  84.         }
  85.         System.out.println(); // 换行
  86.     }
  88.     public static void main(String[] args) {
  90.         MyArray array = new MyArray(5);
  92.         array.insertElem(3, 1);
  93.         array.insertElem(5, 2);
  94.         array.insertElem(2, 3);
  95.         array.insertElem(7, 4);
  96.         array.insertElem(8, 5);
  98.         array.printArray();
  99.         array.deleteElem(3);
  100.         array.printArray();
  102.     }
  104. }

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

在这里插入图片描述

4 数组性能分析
  • O ( 1 ) O(1) O(1) 时间复杂度直接定位元素
  • 插入、删除元素时间复杂度都是 O ( n ) O(n) O(n)
5 其他案例
数组元素逆置

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

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

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

测试

  1. public static void main(String[] args) {
  3.     MyArray array = new MyArray(5);
  4.     for (int i = 0; i < 5; i++) {
  6.         array.insertElem(i + 1, i + 1);
  7.     }
  9.     array.printArray();
  10.     array.reverseArray();
  11.     array.printArray();
  13. }

运行结果

在这里插入图片描述

删除数组中的重复元素

实现有很多种方法：

  1. 定位一个数组元素，从前往后扫描，如果发现与定位元素相同的元素，就删除它。不断调整定位，直到删除所有重复元素。

    1. void purge() {
    3.     int i = 0, j;
    4.     while (i < elemNumber) {
    6.         j = i + 1; // 从arr[i + 1]开始逐个比较
    7.         while (j < elemNumber) {
    9.             if (array[i] == array[j]) {
    11.                 deleteElem(j + 1);
    12.             } else {
    14.                 j++;
    15.             }
    16.         }
    17.         i++; // 定位下一个元素
    18.     }
    19. }
    21. public static void main(String[] args) {
    23.     MyArray array = new MyArray(10);
    24.     // [1,1,3,5,2,3,1,5,6,8]
    25.     array.insertElem(1, 1);
    26.     array.insertElem(1, 2);
    27.     array.insertElem(3, 3);
    28.     array.insertElem(5, 4);
    29.     array.insertElem(2, 5);
    30.     array.insertElem(3, 6);
    31.     array.insertElem(1, 7);
    32.     array.insertElem(5, 8);
    33.     array.insertElem(6, 9);
    34.     array.insertElem(8, 10);
    36.     array.printArray();
    37.     array.purge();
    38.     array.printArray();
    40. }

    运行结果

    在这里插入图片描述

    功能是实现了，但是时间复杂度已经来到了 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)

    1. void purge2() {
    3.     int i, j;
    4.     int FLAG = -111;
    6.     int number = elemNumber;
    7.     // 将重复元素用FLAG覆盖
    8.     for (i = 0; i < number; i++) {
    10.         if (array[i] != FLAG) {
    12.             for (j = i + 1; j < elemNumber; j++) {
    14.                 if (array[i] == array[j]) {
    16.                     array[j] = FLAG;
    17.                 }
    18.             }
    19.         }
    20.     }
    21.     // 找到第一个FLAG标记
    22.     for (i = 0; array[i] != FLAG; i++) ;
    24.     for (j = i + 1; j < number; ) {
    26.         if (array[j] != FLAG) {
    28.             // 若array[j] 不是FLAG，则用array[j] 覆盖array[i],并且向后走
    29.             array[i++] = array[j++];
    30.         } else {
    31.        // 若array[j] 是FLAG，则j 直接向后走,寻找下一个非FLAG的有效值
    32.             j++;
    33.         }
    34.         elemNumber = i;
    35.     }
    37. }

    测试

    在这里插入图片描述

  3. 使用哈希表。

    1. void purge3() {
    3.     int i, j;
    4.     int FLAG = -111;
    5.     int number = elemNumber;
    7.     HashSet<Integer> set = new HashSet<Integer>();
    8.     for (i = 0; i < number; i++) {
    10.         if (!set.add(array[i])) {
    12.             // 如果不能存储到集合中，则说明array[i]与set 中的元素有重复
    13.             array[i] = FLAG;
    14.         }
    15.     }
    16.     for (i = 0; array[i] != FLAG; i++) ;  // 找到第一个FLAG
    17.     for (j = i + 1; j < number; ) {
    19.         if (array[j] != FLAG) {
    21.             array[i++] = array[j++];
    22.         } else {
    24.             j++;
    25.         }
    26.         elemNumber = i;
    27.     }
    28. }

    测试

    在这里插入图片描述

    利用HashSet 查找重复元素时间复杂度为 O ( n ) O(n) O(n)，将数组中的FLAG全部删除 O ( n ) O(n) O(n)，所以整个算法时间复杂度 O ( n ) O(n) O(n)，代价就是需要一个HashSet 额外开了空间。

    之所以标记FLAG其实是为了维持原本数组的顺序(稳定)，如果不在意数组元素顺序，只考虑删除重复元素就完事儿的话，可以直接将HashSet 中的元素读出，但也就是因为HashSet 中数据无序，所以从其中读出的元素可能与原数组元素顺序不一致。

发表评论

表情：
评论列表 （有 0 条评论，190人围观）

还没有评论，来说两句吧...

相关阅读