数据结构系列 -- 手撸数组
数组在开发中是必不可少、不可或缺的重要组成元素。在 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
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-01-09，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录