专栏首页奔跑吧攻城狮数据结构系列 -- 手撸数组

数据结构系列 -- 手撸数组

数组在开发中是必不可少、不可或缺的重要组成元素。在 Java 数据结构中,数组也被赋予神圣的地位。但是你真的会数组吗?那今天换个姿势,我们来怼一怼数据结构中的数组。

一、数组定义

  • 数组的定义比较基础,在这就不展开了。(需要重温 Java 数组的可以参照菜鸟教程的 Java 数组模块)

二、数组基础用法

数组可以直接使用的方法不多,遍历便是最简单的一种使用。

1. 数组遍历

数组遍历比较简单,简单粗暴的使用 for 循环遍历是最简单的事情,当然也可以使用 foreach 遍历。如下:

public static void main(String[] args) {
    // 定义一个长度为3的数组,并初始化
    int[] arr = new int[] {9, 8, 7};
    // for 循环遍历该数组
    for(int i = 0; i < arr.length; i++) {
        newArr[i] = arr[i];
    }
    // 使用 java.util.Arrays.toString() 打印
    System.out.println(Arrays.toString(arr));
    // 使用forwach 遍历
    for (int i : newArr) {
        // 打印
        System.out.print(i + "\t");
    }
    System.out.println();
}

三、 数组进阶使用

学过数组的人都知道,数组的长度是固定的,初始化之后就不能再改变他的长度。但是在日常开发中,经常会对数组进行添加元素,删除元素,查找元素等等,这些 Java 数组都是没有方法实现的,但是 Java 中集合衍生出来的 ArrayList ,LinkList 这些可以是实现上述的功能。既然数组没有,那么下面就搞一下。

总体思路就是,封装一个数组的类,实现增删改查的功能。先实现必要的封装,如下:

/**
 * 创建 MyArray 类,定义原始数组,并初始化
 */
public class MyArray {
    // 定义一个数组
    private int[] elements;
    // 构造函数
    public MyArray() {
        super();
        // 初始化数组,长度为零
        this.elements = new int[0];
    }
}

1. 添加元素

元素的添加,这一块主要是在数组末尾添加一个元素,在指定位置插入一个元素。

1)在数组末尾添加一个元素
  • 实现思路: ① 创建一个全新的数组 newArr,长度为原始数组 elements.length + 1。 ② 把 elements 复制到 newArr 的 0 - elements.length 位置 ③ 把需要添加的元素添加到新的数组 newArr[elements.length] ④ 最后把原始数组 elements 指向新数组 newArr
  • 实现代码:
/***
 * 往数组中末尾添加一个元素
 * 
 * @param element 待添加的元素
 */
public void add(int element) {
    int[] newArr = new int[elements.length + 1];
    for (int i = 0; i < elements.length; i++) {
        newArr[i] = elements[i];
    }
    newArr[elements.length] = element;
    this.elements = newArr;
}
2)在数组指定位置插入一个元素
  • 实现思路: ① 创建一个全新的数组 newArr,长度为原始数组 elements.length + 1。 ② 把 elements[0]-elements[index-1] 复制到 newArr[0]-newArr[index-1]中 ③把elements[index] - elements[elements.length-1] 复制到 newArr[index+1]-newArr[elements.lemgth] 中 ④ 把需要添加的元素添加到新的数组 newArr[index] 中 ⑤ 最后把原始数组 elements 指向新数组 newArr
  • 实现代码:
/**
 * 指定位置插入元素
 * 
 * @param index   待位置
 * @param element 待插入元素
 */
public void insert(int index, int element) {
    // 健壮性检查
    if (index < 0 || index > elements.length) {
        // 抛出异常
        throw new RuntimeException("插入数组下标越界!");
    }
    int[] newArr = new int[elements.length + 1];
    for (int i = 0; i < elements.length; i++) {
        if (index > i) {
            newArr[i] = elements[i];
        } else {
            newArr[i + 1] = elements[i];
        }
    }
    newArr[index] = element;
    elements = newArr;
}

2. 删除元素

删这一部分,主要是删除指定下标位置上的元素功能

1)删除指定下标的元素
  • 实现思路: ① 创建一个全新的数组 newArr,长度为原始数组 elements.length - 1。 ② 把 elements[0]-elements[index-1] 复制到 newArr[0]-newArr[index-1]中 ③ 把 elements[index+1]-elements[elements.length-1] 复制到 newArr[index]-newArr[elements.lemgth-2] 中 ④ 最后把原始数组 elements 指向新数组 newArr
  • 实现代码:
/**
 * 删除数组中的元素
 * 
 * @param index 待删除元素的索引
 */
public void delete(int index) {
    if (index > elements.length - 1 || index < 0) {
        throw new RuntimeException("删除数组下标越界!");
    }
    int[] newArr = new int[elements.length - 1];
    for (int i = 0; i < elements.length; i++) {
        if (i < index) {
            newArr[i] = elements[i];
        }
        if (i > index) {
            newArr[i - 1] = elements[i];
        }
    }
    elements = newArr;
}

3. 查询元素

查询元素这一部分主要是由元素索引查询、线性查询、二分查询等功能。

1)元素索引查询
  • 实现思路:

这个功能十分简单,只需要把对应索引的值返回便可,就不展开阐述了,直接贴代码。

  • 代码实现:
/**
 * 返回对应下标的元素值
 * 
 * @param index 下标
 * @return 对应元素的值
 */
public int get(int index) {
    if (index > elements.length || index < 0) {
        throw new RuntimeException("获取数组下标越界!");
    }
    return elements[index];
}
2)线性查询
  • 实现思路 ① 遍历所有元素,如果相等,记录索引下标 ② 退出循环,返回对应下标值,如果没有该值,返回 -1
  • 代码实现:
/**
 * 线性查找
 * 
 * @param target 待查找的元素
 * @return 该元素的位置
 */
public int search(int target) {
    for (int i = 0; i < elements.length; i++) {
        if (target == elements[i]) {
            return i;
        }
    }
    return -1;
}
3)二分查找

二分查找有个特殊的要求,需要该数组的升序、降序排列的。这里使用升序。

  • 实现思路: ① 在升序的数组当中,去中间位值与目标值比较, 如果相等输出该下标。 ② 不相等则比较中间位值与目标值的大小, 在左边则说明目标值较小,需要把 end 设置为中间值-1 ③ 在右边则说明目标值较大,需要把 start 设置为中间值+1 ③ 跳回到步骤①,直到找到该元素,如果没有返回 -1
  • 代码实现:
/**
 * 二分查找 
 * 
 * @param target 查找元素的值
 * @return 对应元素的下标
 */
public int binarySearch(int target) {
    int begin = 1;
    int end = elements.length - 1;
    int mid = (begin + end) / 2;
    int index = -1;
    while (true) {
        if (target > elements[elements.length - 1] || target < elements[0]) {
            break;
        }
        if (target == elements[mid]) {
            index = mid;
            break;
        } else {
            if (target > elements[mid]) {
                begin = mid + 1;
            } else {
                end = mid - 1;
            }
            mid = (begin + end) / 2;
        }
    }
    return index;
}

4. 修改数组

修改数组这部分功能,主要包含替换元素值功能

1)替换元素值
  • 实现思路:

这个功能也是相对简单,直接给需要替换的元素对应的下标的的便可。直接贴代码。

  • 代码实现:
/**
 * 替换数组指定位置元素
 * 
 * @param index   位置
 * @param element 元素
 */
public void replace(int index, int element) {
    if (index < 0 || index > elements.length) {
        throw new RuntimeException("替换插入数组下标越界!");
    }
    elements[index] = element;
}

5. 其他功能

再写几个常用的工具,包括遍历所有元素、获取该数组的长度。这部分功能比较简单,不展开阐述了。详细见下。

1)遍历所有元素
  • 代码实现:
/**
 * 打印所有元素到控制台
 */
public void printAllElements() {
    System.out.println(Arrays.toString(elements));
}
2)获取该数组的长度
  • 代码实现:
/**
 * 获取数组长度
 * 
 * @return 数组长度
 */
public int size() {
    return elements.length;
}

四、总结

上述就是,Java 关于数组的主要内容了。总的来看,上述内容就是自己实现 ArrayLiat 这个类的常见功能,关键是重温下对数组的使用,还有部分的算法实现(二分查找)。

  • 关于数据结构的数组部分就到这里。

THE END

本文分享自微信公众号 - 奔跑吧攻城狮(runningdimple)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-01-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 工作日、工作小时的一种非常简单的计算方式

    有些业务流程复杂,环节多样。为了看清整个业务的进展,往往需要对各个环节设定预计完成时间开销,然后在用这个是时间去考核实际业务开展的效率。

    普通程序员
  • Java NIO 系列学习 03 - Channels

    Java NIO Channels 在很多地方都与 streams 相似,不同点有下面几个:

    许杨淼淼
  • Java NIO 系列学习 08 - FileChannel

    Java NIO FileChannel 是连接文件的channel。使用fileChannle可以实现从文件中读写数据。FileChannel是用来替代Jav...

    许杨淼淼
  • 现代C++之字面量、静态断言和成员函数说明符

    字面量(literal)是指在源代码中写出的固定常量,它们在 C++98 里只能是原生类型,如:

    公众号guangcity
  • CAS 和 ABA 问题浅析

    CAS, 现在有内存值V, 更改操作发生前的预期值A,要更改后的值B。当且仅当V==A时才进行更改操作。 原理很简单,这样真的是安全的么?

    许杨淼淼
  • Java NIO 系列学习 06 - Channel to Channel Transfers

    在Java NIO中,如果有两个Channel且其中一个是FileChannel时,我们可以传递数据从一个channel到另一个channel。FileChan...

    许杨淼淼
  • Java NIO 系列学习 10 - ServerSocketChannel

    ServerSocketChannel 可以监听传入的TCP连接,与Java标准库的ServerSocket类似。

    许杨淼淼
  • 探索JAVA并发 - 可重入锁和不可重入锁

    CAS操作需要输入两个数值,一个旧值(期望操作前的值)和一个新值,在操作期间先比较下旧值有没有发生变化,如果没有发生变化,才交换成新值,发生了变化则不交换。

    李红
  • Java NIO 系列学习 09 - SocketChannel

    Java NIO SocketChannel 是一个连接TCP网络socket的channel。与标准库的网络Socket是等效的。有两个办法可以来建立Sock...

    许杨淼淼
  • Java NIO 系列学习 05 - Scatter and Gather

    Java NIO 提供了内置的Scatter和Gather支持。Scatter和Gatter是用于读写Channel的概念。

    许杨淼淼

扫码关注云+社区

领取腾讯云代金券