Java 杂谈数据结构与算法

数据结构(1):使用面向对象模拟数组

2019-08-07  本文已影响3人  要成为王的男人

数组是一种常用的数据结构,数组具有不可变性,创建后的数组的长度固定,通过索引访问数组中的元素,访问速度快,删除添加效率低。

通过面向对象模拟数组,模拟的数组具有以下功能:

  1. 添加新元素
  2. 展示
  3. 查找元素所在位置
  4. 根据索引获取元素
  5. 根据索引删除元素
  6. 修改指定位置的元素

同时使用两个算法对数组进行操作:

  1. 有序添加元素
  2. 二分查找法

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;
            }
        }
    }
    
}
二分查找法图示
上一篇 下一篇

猜你喜欢

热点阅读