动态数组实现(支持泛型)

雨点打透心脏的1/2处 2022-05-23 05:36 210阅读 0赞

# ** 动态数组实现(支持泛型) ** #

# **一、简单介绍** #

**    为了复习下数据结构，java框架搞多了，突然觉得数据结构的乐趣。就在这个月，每周会更新自己对以前数据结构的代码的优化，****本次，先写了支持泛型的动态数组，所以如果要测试，请使用除八大基本数据类型之外的类型进行测试，也可以使用八大基本数据类型的****包装类进行测试(****byte -----Byte short-----Short char---Char boolean----Boolean int ---- Integer long-----Long double----Double float-----Float****)。**

**    本代码进行了较为详细的注解，在这里就不讲解了，推荐学习方法---看思路再手撸。**

**二、源代码**

## (1)泛型的动态数组实现代码(Java): ##

package com.atlihao.array;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /**
     * author lihao
     * time  2018-6-2 23:25
     * @param <E>
     */
    public class Array <E>{
        private E [] data;
        private int size;
    
        //数组构造器
        public Array(int capacity){
            data=(E[])new Object[capacity];
            size=0;
        }
        public Array(){
           this(10);
        }
    
        //数组的大小
        public int getSize() {
           return size;
        }
        //数组的容量
        public int getCapacity(){
            return data.length;
        }
        //数组是否为空
        public Boolean isEmpty(){
            return size==0;
        }
        //添加到最后
        public void addLast(E e){
            add(size,e);
        }
    
        //根据数组下标获得对应的value
        public E get(int index){
            if(index<0||index>=size){
                throw new IllegalArgumentException("Get failed .Require index<0 or index>=size");
            }
            return data[index];
        }
    
        public E getFirst(){
            return get(0);
        }
    
        public E getLast(){
            return get(size-1);
        }
    
        //根据数组下标修改为对应的值
        public void set(int index,E e){
            if(index<0||index>=size){
                throw new IllegalArgumentException("Get failed .Require index<0 or index>=size");
            }
            data[index]=e;
        }
    
        //数组中是否包含该元素
        public Boolean contains(E e){
            for(int i=0;i<size;i++){
                if(data[i]==e){
                    return true;
                }
            }
            return false;
        }
    
        //找到为该元素的第一个下标
        public int find(E e){
            for(int i=0;i<size;i++){
                if(data[i]==e){
                    return i;
                }
            }
            return -1;
        }
    
        //找到为该元素的所有下标
        public List<Integer> findAll(E e){
            List<Integer> list=new ArrayList<>();
            for(int i=0;i<size;i++){
                if(data[i]==e){
                    list.add(i);
                }
            }
            return list;
        }
    
        //增加到数组的第一个
        public void addFirst(E e){
            add(0,e);
        }
    
        //任意位置增加
        public void add(int index,E e){
            if(index<0||index>size){
                throw new IllegalArgumentException("Remove failed .Require index <0 and index >size");
            }
            if(size==getCapacity()){
                resize( Math.multiplyExact(2,getCapacity()));
            }
            for(int i=size-1;i>=index;i--){
                data[i+1]=data[i];
            }
            data[index]=e;
            size++;
        }
    
        //动态改变数组大小
        private void resize(int newCapacity){
            E[] newData=(E[]) new Object[newCapacity];
            for(int i=0;i<size;i++){
                newData[i]=data[i];
            }
            data=newData;
        }
    
        //从数组中删除index下标的元素,返回删除的元素
        public E remove(int index){
            //判断是否超出了数组的容量
            if(size==0){
                //向方法传递了一个不合法或不正确的参数异常-----就当做一个运行时异常即可
                throw new IllegalArgumentException("Remove failed .Array is empty.");
            }
            if(index<0||index>=size){
                throw new IllegalArgumentException("Remove failed .Require index <0 and index >=size");
            }
            E ret=data[index];
            for(int i=index;i<size;i++){
                data[i]=data[i+1];
            }
            size--;
            data[size]=null;
            //防止频繁的动态缩小数组-----造成资源的浪费
            if(size==Math.floorDiv(getCapacity(),4) && Math.floorDiv(getCapacity(),2)!=0){
                resize( Math.floorDiv(getCapacity(),2));
            }
            return ret;
        }
    
        //从数组中删除第一个元素,返回删除的元素
        public E removeFirst(){
           return remove(0);
        }
    
        //从数组中删除最后一个元素,返回删除的元素
        public E removeLast(){
           return remove(size-1);
        }
    
        //从数组中删除元素
        public void removeElement(E e){
            int index=find(e);
            if(index!=-1){
                remove(index);
            }
        }
        //从数组中移除所有的某个元素
        public void removeAll(E e){
            List<Integer> list=findAll(e);
            for(int i=0;i<list.size();i++) {
                Integer index=getMaxMath(list);
                if (index != -1) {
                    remove(index);
                }
            }
        }
        //先删除下标大的位置
        private Integer getMaxMath(List<Integer> list){
            Integer max=-1;
            Integer target=-1;
            for(int i=0;i<list.size();i++){
                if(max<list.get(i)){
                    max=list.get(i);
                    target=i;
                }
            }
            list.set(target,-1);
            return max;
        }
    
        //重写Object类的toString()方法
        @Override
        public String toString() {
            //线程安全的StringBuffer
            StringBuilder res=new StringBuilder();
            res.append(String.format("Array:size=%d,capacity=%d [",size,getCapacity()));
            for(int i=0;i<size;i++){
                res.append(data[i]);
                if(i!=size-1) {
                    res.append(",");
                }
            }
            res.append("]");
            return res.toString();
        }
    }

## (2)测试代码: ##

package com.atlihao;
    
    import com.atlihao.array.Array;
    
    import java.util.List;
    
    //自定义数组的测试类
    
    /**
     * author lihao
     * time  2018-6-2 23:25
     */
    public class Main {
    
        public static void main(String[] args) {
            Array<Integer> arr=new Array<>(20);
            for(int i=0;i<9;i++){
                arr.addLast(i);
            }
            System.out.println(arr);
    
            arr.add(3,77);
            arr.add(3,77);
            System.out.println(arr);
    
            arr.addFirst(88);
            System.out.println(arr);
            arr.addLast(77);
            System.out.println(arr);
            arr.remove(1);
            arr.removeFirst();
            arr.removeLast();
            arr.removeElement(4);
            System.out.println(arr);
            Boolean hav=arr.contains(77);
            System.out.println("contains():"+hav);
            Integer s=arr.find(77);
            System.out.println("find():"+s);
            List<Integer> sign=arr.findAll(77);
            System.out.println("findAll():"+sign);
            System.out.println(arr);
            arr.removeAll(77);
            System.out.println(arr);
        }
    }

(3)测试截图:

![70][]

[70]: /images/20220523/a66870d269724913b4a79094c63b26e5.png