数据结构之——数组

数组

数据结构的基本类型之一,它可以构成其他数据结构,如栈、队列、哈希表、树、图、堆、矩阵、张量。
数组在内存中的存储方式为一片连续的内存空间,其基本操作与其他数据结构一致,即所谓的增删改查。废话不多说,上代码加以理解。

Java类型实现

class array {

  public static void main(String[] args) {    

      // 初始化数组
      Scanner in = new Scanner(System.in);
      int[] arr = new int [5];
      int[] nums = {1,3,2,5,4};

      System.out.println("访问的随机元素是:"+randomAccess(nums));


      System.out.print("输入要插入的索引和元素:");
      int index = in.nextInt();
      int n = in.nextInt();
      insert(nums,n,index);
      System.out.println("现在的nums数组为:");
      for (int i = 0; i < nums.length; i++) {
          System.out.print(nums[i]);
      }
      System.out.println();

      System.out.print("输入要删除的索引和元素:");
      index = in.nextInt();
      n = in.nextInt();
      delete(nums,n,index);
      System.out.println("现在的nums数组为:");
      for (int i = 0; i < nums.length; i++) {
          System.out.print(nums[i]);
      }
     // foreach遍历方式
     // for (int num: nums) {
     //   System.out.println(num);
     // }
      System.out.println();

      //查找元素
      System.out.println("请输入要查找的元素:");
      n = in.nextInt();
      System.out.println("查找的元素的下标为:"+find(nums,n));

      //扩展数组
      System.out.println("请输入扩展的大小:");
      n = in.nextInt();
      int[] a = extend(nums,n);
      System.out.println("新数组为:");
      for (int b:a) {
          System.out.print(b);
      }

  }
  //访问元素,在数组中随机抽取一个数
  public static int randomAccess(int[] nums){
      int randomIndex = ThreadLocalRandom.current().nextInt(0, nums.length);
      int randomNum = nums[randomIndex];
      return randomNum;
  }

  //插入元素
  public static void insert(int[] nums,int num,int index){
      for (int i = nums.length-1; i > index ; i--) {
          nums[i] = nums[i-1];
      }
      nums[index] = num;
  }

  //删除元素
  public static void delete(int[] nums,int num,int index){
      if (index == nums.length-1){
          nums[index] = 0;
          return ;
      }
      for (int i = index; i < nums.length - 1; i++) {
          nums[i] = nums[i+1];
      }
  }

  //查找元素,返回索引
  public static int find(int[] nums,int num){
      for (int i = 0 ; i < nums.length ; i++ ) {
          if (nums[i] == num) {
              return  i;
          }
      }
      return -1;
  }

  //扩展数组:思路——新建一个更大的数组,将原数组复制到新数组中
  public static int[] extend(int[] nums,int enlarge){
      int[] newArr = new int[nums.length+enlarge];
      for (int i = 0; i < nums.length; i++) {
          newArr[i] = nums[i];
      }
      return newArr;
  }
}

数组的优点与局限性:

    ·空间效率高:数组为数据分配了连续的内存块,无需额外的结构开销
    ·支持随机访问:允许在O(1)时间内访问任何元素
    ·缓存局部性:当访问数组元素时,计算机不仅会加载它,还会缓存其周围的其他数据,从而借助高速缓存来提升后续操作的执行速度

连续空间存储的局限性:

    ·插入与删除效率低:但数据量大时,该操作会移动大量数据
    ·长度不可变:数组在初始化后长度就固定了,扩容数组需要将所有数据复制到新数组,开销很大
    ·空间浪费:如果数组分配的空间大小超过实际所需,那么多余的空间就被浪费了

数组典型应用:

·随机访问
·排序和搜索
·查找表
·机器学习
·数据结构实现

本篇内容参考自Github krahets的hello算法,将其内容进行归纳整理

热门相关:唐朝贵公子   黑暗血时代   抗战老兵之不死传奇   惊艳人生   万古第一帝