二次封装属于我们自己的数组

最近在学习数据结构与算法收获颇深,做一点笔记记录一下学习过程。

在学习数据结构的过程中,我们都会从增删改查开始,我们这里基于java的数组,二次封装属于我们自己的数组类。

一. 定义一个数组类

  1.  数组本身是静态,我们一开始需要设置最多装多少个元素(Capacity)
  2.  我们使用size来记录数组中的元素个数

 

二. 向数组中添加元素

  1. 向数组末尾添加元素(向数组末尾添加元素,就是在size添加元素,添加完以后我们需要将size加1)
  2. 向指定位置添加元素(向索引为2的位置添加元素99,从索引为2的位置起将所有元素往后移,然后将99插入到索引为2的位置,插入以后我们需要将size加1

三. 向数组中查询元素(根据下标查询相应的元素,查询下标为index的元素)

    返回 data[index]即可

四. 向数组中修改元素(修改对应下标index下面的元素,修改值为value)

   data[index] = value

五. 从数组中删除指定位置的元素(删除索引为2的元素)

六 . 使用泛型

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

七. 将我们的数组封装为动态数组 (重新开一个空间,将之前的元素赋值到现在的空间中,我们这里叫resize操作)

扩容以后,当我们的数据删除到一定的程度以后,我们可以将我们的数组进行缩小,一样的使用resize方法进行缩容。

八. 分析动态数组的时间复杂

  1. 添加操作  O(n)

             addLast(e)          O(1)

             addFirst(e)          O(n)                       

             add(index,e)       O(n/2)

             最坏情况:O(n), resize:O(n)

       2.  修改操作         O(1)

             set(index,e)   O(1)

        3.  查找操作

             get(index)    O(1)

             contains(e)  O(n)

             find(e)         O(n)

        总结:

              改和查,已知索引为O(1),未知索引为O(n)

              增和删,为O(n),由于在我们的动态数组中有resize操作,那么我们在操作最后一个元素时还是O(n)的时间复杂度?

九. 使用均摊复杂度分析resize操作

      我们知道进行resize操作时,需要将原数组中的元素复制到新的数组中。假如我们数组中的元素是n,那么我们需要进行n次复制,那么resize时间复杂度为O(n) 

      假设当前 capacity = 8,   并且每一次添加操作都使用addLast

       

        9次addLast操作,触发resize,总共进行了17次基本操作,平均每次addLast操作,进行2次基本操作。

       假设capacity = n,n+1次addLast,触发resize,总共进行2n+1次基本操作,平均每次addLast操作进行2次基本操作,这样均摊计算,时间复杂度是O(1)的!

       在这里,其实这样均摊计算,比计算最坏情况更加有意义。

       addLast的均摊复杂度为O(1)

      同理:removeLast的均摊复杂为O(1)

     其实相对一个比较耗时的操作,只要我们不是每一次都进行计算,其实这样子的运行效率还是比较可观的。

 十. 防止resize的复杂度震荡

 我们会发现,当每次扩容增加一倍和缩容一半时,可能会同时不断触发addLast和removeLast操作

此时会出现复杂度震荡,出现的问题:removeLast时resize过于着急(Eager)

解决方案:Lazy

                                              当 size == capacity / 4 时,才将capacity 减半

具体代码实现:

// 为了简洁,我们都使用//进行注释

public class Array<E> { 
    private E[] data;
    private int size; 
    private int capacity = 10;

    // 有参数的构造函数
    public Array(int capacity){
        data = (E[])new Object[capacity];  // 我们new 一个泛型类型的数组,需要绕一个弯
        size = 0;
    }
    
    // 无参数的构造函数,默认数组的容量capacity=10
    public Array(){
        data = (E[])new Object[capacity];
        size = 0;
    }
    
    // 获取数组中的元素个数
    public int getSize(){
        return size;
    }

    
    // 返回数组是否为空
    public boolean isEmpty(){
        return size==0;
    }
    
    // 获取数组的容量
    public int getCapacity(){
        return data.length;
    }
    
    // 向数组末尾添加一个新的元素,我们复用add方法,在索引为size的位置添加元素
    public void addLast(E e){
        add(size,e);
    }
    

    // 向数组的第一个位置添加一个新的元素,我们复用add方法,在索引为0的位置添加元素
    public void addFirst(E e){
        add(0,e);
    }

    // 在索引为index的位置插入一个新的元素e
    public void add(int index, E e){
        if(size == data.length)
            // 这里扩容1倍,扩容的量与当前的数据是有关系的
            resize(2 * data.length);
        // index<0 是非法的,index>size 说明插入的不是紧密的,不是我们要的结果
        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索引位置的元素,get 无法读取使用的空间的
    public E get(int index){
        if(index<0 ||index>=size)
            throw new IllegalArgumentException(“Get failed. Index is illegal.”);
        return data[index];
    }
    

   // 获取数组中最后一个元素
    public E getLast(){
        return get(size-1);
    }
    

  // 获取数组中第一个元素
    public E getFirst(){
        return get(0);
    }
    

   // 修改数组中索引为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))      //这里是比较两个类对象的值是否相等需要使用equals  ==为引用比较
              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;  // 由于这里是泛型,还存在对象的引用,垃圾回收机制就不会去删除,我们将其置为null
        
        if(size == data.length/4 && data.length /2 != 0)
          resize(data.length/2);
        return ret;
    }
    
    // 从数组中删除第一个元素,返回删除的元素
    public E removeFirst(){
        return remove(0);
    }
    
    // 从数组中删除最后一个元素,返回删除的元素
    public E removeLast(){
        return remove(size-1);
    }
    
    // 从数组中删除元素e,这里只删除一个元素e
    public void removeElement(E e){
        int index = find(e);
        if(index !=-1)
            remove(index);
    }
    
    //重写 toString 定义打印输出的方法
    @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();
    }
    // 为动态数组的扩容和缩容操作
    private void resize(int newCapacity) {
        E[] newData = (E[])new Object[newCapacity];
        for(int i=0 ; i<size ; i++)
             newData[i] = data[i];
        data = newData;
    }
}

转载自:https://blog.csdn.net/qq_22230709/article/details/81298241

You may also like...

退出移动版