数组是一种常用的数据结构，数组具有不可变性，创建后的数组的长度固定，通过索引访问数组中的元素，访问速度快，删除添加效率低。
通过面向对象模拟数组，模拟的数组具有以下功能：
- 添加新元素
- 展示
- 查找元素所在位置
- 根据索引获取元素
- 根据索引删除元素
- 修改指定位置的元素
同时使用两个算法对数组进行操作：
- 有序添加元素
- 二分查找法
1.创建数组类 MyArray.java
数据如何存储呢？在类中添加一个数组类型的私有属性用来保存数据，同时添加一个变量存储有效数据的长度（也就是元素的个数）
创建数组的时候需要指定数组的长度，所以要添加两个构造方法：
1.无参构造方法设置数组默认长度
2.有参构造方法指定数组长度
public class MyArray {
//存储元素
private long[] arr;
//表示有效数据的长度
private int elements;
//无参构造默认50个长度
public MyArray() {
arr=new long[50];
}
public MyArray(int maxsize) {
arr=new long[maxsize];
}
}
2.编写添加数据的方法
elements 属性的默认值是 0，第一次向对象中添加元素也是添加到索引为0 的元素中，添加后将 elements 的长度加1，就能一直向数组中添加元素了，添加元素的个数取决于 arr 的长度。
public void insert(long value) {
arr[elements]=value;
elements++;
}
3.编写展示数据的方法
简单的展示数组中的元素即可，使用 for 循环遍历
public void display() {
System.out.print("[");
for (int i = 0; i < elements; i++) {
System.out.print(arr[i]+" ");
}
System.out.println("]");
}
4.编写查找数据的方法
思路：使用循环遍历数组 arr ，将要查找的数据和 arr 中每个元素进行比较。如果相等，则跳出循环。循环结束后，如果循环次数等于元素个数说明没有找到数据，返回-1。否则返回循环次数（即找到的索引）。
public int search(long value) {
int i ;
for (i = 0; i < elements; i++) {
if(value==arr[i]) {
break;
}
}
//遍历到末尾说明没有找到
if (i==elements) {
return -1;
}else {
return i;
}
}
5.根据索引获取元素
思路：这相对比较简单了，直接给 arr 索引就能获取到元素。但是要注意传入的索引必须可用，不能用的索引可以抛出异常。
public long get(int index) {
//如果索引大于可用，或索引小于0 都是无效的索引
if (index>=elements||index<0) {
//抛出数组越界异常
throw new ArrayIndexOutOfBoundsException();
}else {
return arr[index];
}
}
6.根据索引删除元素
思路：和获取元素时一样，先检查索引是否可用。如果可用，就从要删除元素的位置开始向后遍历，每次都将下一个元素的值赋值给当前元素。也就相当于要删除的元素被下一个元素覆盖，下一个元素被下下一个元素覆盖，以此类推。元素移动完成后，将可用元素长度 elements 减1。
public void delete(int index) {
//如果索引大于可用，或索引小于0 都是无效的索引
if (index>=elements||index<0) {
throw new ArrayIndexOutOfBoundsException();
}else {
for(int i=index;i<elements;i++) {
arr[index]=arr[i+1];
}
elements--;
}
}
7.修改指定位置的元素
思路：和获取差不多，就是把获取改为修改
public void change(int index,int newValue) {
//如果索引大于可用，或索引小于0 都是无效的索引
if (index>=elements||index<0) {
throw new ArrayIndexOutOfBoundsException();
}else {
arr[index]=newValue;
}
}
8.完整代码
public class MyArray {
private long[] arr;
//表示有效数据的长度
private int elements;
public MyArray() {
arr=new long[50];
}
public MyArray(int maxsize) {
arr=new long[maxsize];
}
/**
* 添加数据
* @param value
*/
public void insert(long value) {
arr[elements]=value;
elements++;
}
/**
* 显示数据
*/
public void display() {
System.out.print("[");
for (int i = 0; i < elements; i++) {
System.out.print(arr[i]+" ");
}
System.out.println("]");
}
/**
* 查找数据
*/
public int search(long value) {
int i ;
for (i = 0; i < elements; i++) {
if(value==arr[i]) {
break;
}
}
//遍历到末尾说明没有找到
if (i==elements) {
return -1;
}else {
return i;
}
}
/**
* 查找数据，根据索引来查
*/
public long get(int index) {
//如果索引大于可用，或索引小于0 都是无效的索引
if (index>=elements||index<0) {
throw new ArrayIndexOutOfBoundsException();
}else {
return arr[index];
}
}
/**
* 删除数据
*/
public void delete(int index) {
//如果索引大于可用，或索引小于0 都是无效的索引
if (index>=elements||index<0) {
throw new ArrayIndexOutOfBoundsException();
}else {
for(int i=index;i<elements;i++) {
arr[index]=arr[i+1];
}
elements--;
}
}
/**
* 更新数据
*/
public void change(int index,int newValue) {
//如果索引大于可用，或索引小于0 都是无效的索引
if (index>=elements||index<0) {
throw new ArrayIndexOutOfBoundsException();
}else {
arr[index]=newValue;
}
}
}
9.有序添加元素
思路：修改 insert 方法，遍历 arr 数组，如果当前元素大于添加的数据，当前的位置就要存入的位置。从最后一个元素开始，逐个将元素向后位移，空出要存入的位置。存入要添加的元素后，将有效数据长度加1。
public void insert(long value) {
int i;
for(i=0;i<elements;i++) {
if(arr[i]>value) {
break;
}
}
for (int j = elements; j > i; j--) {
arr[j]=arr[j-1];
}
arr[i]=value;
elements++;
}
10.二分查找法
思路：数据必须是有序的，才能使用二分查找法！可以结合有序添加元素一块使用，这里的序列是升序（从小到大）。二分查找是每次和一组数中间的数进行比较，如果大于就再和右边的数最中间的数比较，如果小于就和左边的数最中间的数比较。直到中间的数和要查找的数相等，否则就是没有这个数。
public int binarySearch(long value) {
int mid=0;//中间值
int low=0;
int high = elements;
while(true) {
mid=(high+low)/2;
if(arr[mid]==value) {
return mid;
}else if(low>high) {
return -1;
}else {
if (value>arr[mid]) {
high=mid+1;
}else {
high=mid-1;
}
}
}
}
二分查找法图示
网友评论