专栏首页极客慕白的成长之路算法学习之动态数组类

算法学习之动态数组类

算法学习之动态数组

一、整型动态数组类

数组操作逻辑代码实现

public class Array {

    private int[] data;
    private int size;


    //构造函数,传入数组的容量capacity构造Array
    public Array(int capacity){
        data = new int[capacity];
        size = 0;
    }
    //无参构造函数,默认数组的容量capacity=10
    public Array() {
        this(10);
    }
    // 获取数组的容量
    public int getCapacity(){
        return data.length;
    }
    // 获取数组中的元素个数
    public int getSize(){
        return size;
    }
    // 返回数组是否为空
    public boolean isEmpty(){
        return size == 0;
    }

    // 向所有元素后添加一个新元素
    public void addLast(int e){

        // if(size == data.length)
        //     throw new IllegalArgumentException("AddLast failed. Array is full.");
        //
        // data[size] = e;
        // size ++;
        add(size, e);  //代码的复用
    }
    // 在所有元素前添加一个新元素
    public void addFirst(int e){
        add(0, e);
    }

    // 在index索引的位置插入一个新元素e
    public void add(int index, int e){
        //合法性检测
        if(size == data.length)
            throw new IllegalArgumentException("Add failed. Array is full.");
        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");

        for(int i = size - 1; i >= index ; i --)  //将索引位置之后的所有元素向后移一个位置
            data[i + 1] = data[i];
        data[index] = e;
        size ++;
    }

    //获取index索引位置的元素
    public int get(int index){
        if (index<0 || index>=size)
            throw new IllegalArgumentException("Get failed. Index is illegal.");
        return data[index];
    }
    // 修改index索引位置的元素为e
    public void set(int index, int e){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Set failed. Index is illegal.");
        data[index] = e;
    }

    // 查找数组中是否有元素e
    public boolean contains(int e){
        for(int i = 0 ; i < size ; i ++){
            if(data[i] == e)
                return true;
        }
        return false;
    }

    // 查找数组中元素e所在的索引,如果不存在元素e,则返回-1
    public int find(int e){
        for(int i = 0 ; i < size ; i ++){
            if(data[i] == e)
                return i;
        }
        return -1;
    }

    // 从数组中删除index位置的元素, 返回删除的元素
    public int remove(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");

        int ret = data[index];
        for(int i = index + 1 ; i < size ; i ++)
            data[i - 1] = data[i];
        size --;
        return ret;
    }

    // 从数组中删除第一个元素, 返回删除的元素
    public int removeFirst(){
        return remove(0);
    }

    // 从数组中删除最后一个元素, 返回删除的元素
    public int removeLast(){
        return remove(size - 1);
    }

    // 从数组中删除元素e
    public void removeElement(int e){
        int index = find(e);
        if(index != -1)
            remove(index);
    }

    //方法重写,数组内容的输出
    @Override
    public String toString(){

        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
        res.append("[");
        for (int i=0;i<size;i++){
            res.append(data[i]);
            if (i!=size-1)
                res.append(",");
        }
        res.append("]");
        return  res.toString();
    }
}

数组操作测试

public class Main {

    public static void main(String[] args) {

//        int[] arr = new int[20];
//        for (int i = 0; i < arr.length; i++) {   //arr.length可变
//            arr[i] = i;
//        }
//
//        int[] scores = new int[]{100, 99, 98};
//        for (int score : scores)   // foreach循环的实现
//            System.out.println(score);

        Array arr = new Array(20);
        for(int i = 0 ; i < 10 ; i ++)
            arr.addLast(i);
        System.out.println(arr);

        arr.add(1, 100);
        System.out.println(arr);

        arr.addFirst(-1);
        System.out.println(arr);

        arr.remove(2);
        System.out.println(arr);

        arr.removeElement(4);
        System.out.println(arr);

        arr.removeFirst();
        System.out.println(arr);
    }
}

二、使用泛型

让我们的数据结构可以放置“任何”数据类型 不可以是基本数据类型,只能是类对象 boolean,byte , char,short,int,long,float,double 每个基本数据类型都有对应的包装类 Boolean,Byte,Char,Short , Int , Long,Float,Double

需要改动的地方: 1、声明数组的方式,不再只是int

public class Array<E>{ private E[] data; ... //创建类数组 data = (E[])new Object[capacity]; }

1234567

public class Array<E>{    private E[] data;    ...    //创建类数组    data = (E[])new Object[capacity];}

2、传入参数类型改变

public void addLast(E e){ //不再是int e add(size, e); }

1234

public void addLast(E e){ //不再是int e        add(size, e);    }

3、值比较与引用比较

判断相等的时候不能用==,改为equals()方法 // 查找数组中是否有元素e public boolean contains(E e){ for(int i = 0 ; i < size ; i ++){ if(data[i].equals(e)) //data[i] == e return true; } return false; }

12345678910

判断相等的时候不能用==,改为equals()方法// 查找数组中是否有元素e    public boolean contains(E e){        for(int i = 0 ; i < size ; i ++){            if(data[i].equals(e))  //data[i] == e                return true;        }        return false;    }

4、声明存放数据类型

Array<Integer> arr = new Array<>(20); int类型的包装类 //下面是原来的 Array arr = new Array(20);

1234

Array<Integer> arr = new Array<>(20); int类型的包装类//下面是原来的Array arr = new Array(20);

修改后的泛型数组代码

public class Array<E> {

    private E[] data;
    private int size;

    // 构造函数,传入数组的容量capacity构造Array
    public Array(int capacity){
        data = (E[])new Object[capacity];
        size = 0;
    }

    // 无参数的构造函数,默认数组的容量capacity=10
    public Array(){
        this(10);
    }

    // 获取数组的容量
    public int getCapacity(){
        return data.length;
    }

    // 获取数组中的元素个数
    public int getSize(){
        return size;
    }

    // 返回数组是否为空
    public boolean isEmpty(){
        return size == 0;
    }

    // 在index索引的位置插入一个新元素e
    public void add(int index, E e){

        if(size == data.length)
            throw new IllegalArgumentException("Add failed. Array is full.");

        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");

        for(int i = size - 1; i >= index ; i --)
            data[i + 1] = data[i];

        data[index] = e;

        size ++;
    }

    // 向所有元素后添加一个新元素
    public void addLast(E e){
        add(size, e);
    }

    // 在所有元素前添加一个新元素
    public void addFirst(E e){
        add(0, e);
    }

    // 获取index索引位置的元素
    public E get(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Get failed. Index is illegal.");
        return data[index];
    }

    // 修改index索引位置的元素为e
    public void set(int index, E e){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Set failed. Index is illegal.");
        data[index] = e;
    }

    // 查找数组中是否有元素e
    public boolean contains(E e){
        for(int i = 0 ; i < size ; i ++){
            if(data[i].equals(e))
                return true;
        }
        return false;
    }

    // 查找数组中元素e所在的索引,如果不存在元素e,则返回-1
    public int find(E e){
        for(int i = 0 ; i < size ; i ++){
            if(data[i].equals(e))
                return i;
        }
        return -1;
    }

    // 从数组中删除index位置的元素, 返回删除的元素
    public E remove(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");

        E ret = data[index];
        for(int i = index + 1 ; i < size ; i ++)
            data[i - 1] = data[i];
        size --;
        data[size] = null; // loitering objects != memory leak
        return ret;
    }

    // 从数组中删除第一个元素, 返回删除的元素
    public E removeFirst(){
        return remove(0);
    }

    // 从数组中删除最后一个元素, 返回删除的元素
    public E removeLast(){
        return remove(size - 1);
    }

    // 从数组中删除元素e
    public void removeElement(E e){
        int index = find(e);
        if(index != -1)
            remove(index);
    }

    @Override
    public String toString(){

        StringBuilder res = new StringBuilder();
        res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
        res.append('[');
        for(int i = 0 ; i < size ; i ++){
            res.append(data[i]);
            if(i != size - 1)
                res.append(", ");
        }
        res.append(']');
        return res.toString();
    }
}

泛型数组操作代码

public class Student {

    private String name;
    private int score;

    public Student(String studentName, int studentScore){
        name = studentName;
        score = studentScore;
    }

    @Override
    public String toString(){
        return String.format("Student(name: %s, score: %d)", name, score);
    }

    public static void main(String[] args) {

        Array<Student> arr = new Array<>();
        arr.addLast(new Student("Alice", 100));
        arr.addLast(new Student("Bob", 66));
        arr.addLast(new Student("Charlie", 88));
        System.out.println(arr);
    }
}

三、动态数组

当数组的长度大于数组实际的个数的时候,多余的空间就会浪费,可以自动调用方法使数组长度变小。 一般采取2倍的操作,扩容2倍或者缩小2倍。

// 在index索引的位置插入一个新元素e
    public void add(int index, E e){

        if(index < 0 || index > size)
            throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");

        if(size == data.length)
            resize(2 * data.length);

        for(int i = size - 1; i >= index ; i --)
            data[i + 1] = data[i];

        data[index] = e;

        size ++;
    }

// 从数组中删除index位置的元素, 返回删除的元素
    public E remove(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");

        E ret = data[index];
        for(int i = index + 1 ; i < size ; i ++)
            data[i - 1] = data[i];
        size --;
        data[size] = null; // loitering objects != memory leak

        if(size == data.length / 2)
            resize(data.length / 2);
        return ret;
    }


// 将数组空间的容量变成newCapacity大小
    private void resize(int newCapacity){

        E[] newData = (E[])new Object[newCapacity];
        for(int i = 0 ; i < size ; i ++)
            newData[i] = data[i];
        data = newData;
    }

四、复杂度震荡

当长度刚好是数组长度时,增加一个和删除一个末尾的元素都需要扩容,时间复杂度都是O(n),在这个极端情况下产生的复杂度变化称为复杂度震荡。解决的方式就是懒处理,当元素在原来的1/4时缩小一半。

// 从数组中删除index位置的元素, 返回删除的元素
    public E remove(int index){
        if(index < 0 || index >= size)
            throw new IllegalArgumentException("Remove failed. Index is illegal.");

        E ret = data[index];
        for(int i = index + 1 ; i < size ; i ++)
            data[i - 1] = data[i];
        size --;
        data[size] = null; // loitering objects != memory leak

        if(size == data.length / 4 && data.length / 2 != 0)
            resize(data.length / 2);
        return ret;
    }

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C++上机考试试题解析

    慕白
  • 算法学习之栈与队列

    Stack<E> void push(E) //入栈 E pop() //出栈 E peek() //查看 int getSize() //长度 bool...

    慕白
  • 网站服务器修改SSH默认22端口

    慕白
  • 搞定数据结构-数组结构

    从数组存储的内存模型来看,“下标”最确切的定义应该是”偏移”,如果用a来表示数组的首地址,a0 就是偏移为0的位置,也就是首地址,a k就表示偏移k个type_...

    用户3045442
  • 封装数组之改进为泛型数组

    前言:通过上一节我们对我们需要封装的数组,进行了基本的增删改查的封装,但只局限于int类型的操作,为了能提供多种类型数组的操作,我们可以将其进一步封装为泛型数组...

    wfaceboss
  • [算法题] 使用数组实现栈和队列

    CoderJed
  • Array数组

    数组(Array)是一种线性表数据结构。它用一组连续的内存空间,来存储一组具有相同类型的数据。 查找元素快:通过索引,可以快速访问指定位置的元素

    羊羽shine
  • 看得见的数据结构Android版之表的数组实现(数据结构篇)

    张风捷特烈
  • Java实现基本数据结构(一)——数组

    首先,我们先设计一个静态的数组,以int数组为例。不考虑扩容,先从最简单的类来理解数组的基本功能。 数组可以表示为下图:

    星如月勿忘初心
  • 学好R语言绘图,你只需这样一个网站就够了

    话不多说,上网址: https://www.r-graph-gallery.com/ r-garp-gallery收入了大量利用R语言绘制的图形,这些图形包...

    不温卜火

扫码关注云+社区

领取腾讯云代金券