java实现数据结构01(数组详解代码之自定义数组)

╰+攻爆jí腚メ 2023-06-19 14:25 52阅读 0赞

## 自定义数组类 ##

/**
     * @description: 数组类,E为泛型，可以使用任意对象
     * @author: liangrui
     * @create: 2019-12-05 20:25
     **/
    public class Array<E> {
    
        //数据
        private E[] data;
        //实际数据个数
        private int size;
    
        /**
         * 有参构造函数
         * @param capacity 数据容量
         */
        public Array(int capacity){
            data=(E[]) new Object[capacity];
            size=0;
        }
    
        /**
         * 无参构造函数，this(10)代表调用有参构造函数，赋予容量10
         */
        public Array(){
            this(10);
        }
    
        /**
         * 重新设置数组容量，使数组具有可伸缩性
         * @param newCapacity 设置的容量大小
         */
        private void resetCapacity(int newCapacity){
            E[] newData=(E[]) new Object[newCapacity];
            for (int i = 0; i < size; i++) {
                newData[i]=data[i];
            }
            data=newData;
        }
    
        /**
         * @return 获取数组中元素个数
         */
        public int getSize(){
            return size;
        }
    
        /**
         * @return 获取数组的容量
         */
        public int getCapacity(){
            return data.length;
        }
    
        /**
         * @return 判断数组是否为空，为空返回true，不为空返回false
         */
        public boolean isEmpty(){
            return size==0;
        }
    
        /**
         * 指定数组位置添加数据
         * @param index 数组下标
         * @param e 添加的数据
         */
        public void add(int index,E e){
    
            //如果插入的位置下标小于0或者大于数组元素的数量，即不合法。抛出异常。
            if (index<0||index>size){
                throw new IllegalArgumentException("Add failed. Require index>=0 and index<=size.");
            }
    
            //如果数组元素等于数组容量，即数组已满,可以扩容2倍
            if(size==data.length){
                resetCapacity(2*data.length);
            }
    
            //从最后一个元素遍历到存储的下标，逐个把前一个的元素赋值到后一个，从而保证元素不丢失，且把要添加的index位置空出来
            for (int i = size-1; i >=index ; i--) {
                data[i+1]=data[i];
            }
    
            //把e赋值到index所在的数组位置
            data[index]=e;
            //元素数量+1。
            size++;
        }
    
        /**
         * 从最后面添加数据
         * @param e 添加的数据
         */
        public void addLast(E e){
            add(size,e);
        }
    
        /**
         * 在数组最前面添加数据
         * @param e 添加的数据
         */
        public void addFirst(E e){
            add(0,e);
        }
    
        /**
         * 查询数组信息
         * @return 返回数组信息
         */
        @Override
        public String toString(){
            //创建StringBuilder对象，实现字符串拼接
            StringBuilder sb=new StringBuilder();
            //第一行为数组的元素个数和数组的容量
            sb.append(String.format("Array Size:%d. Array Capacity:%d.\n",size,data.length));
            //第二行为数组的数据
            sb.append("[");
            for (int i = 0; i < size; i++) {
                sb.append(data[i]);
                //如果不是最后一个元素，拼接","
                if (i!=size-1){
                    sb.append(",");
                }
            }
            sb.append("]");
            //返回字符串
            return sb.toString();
        }
    
        /**
         * 获取指定下标的数据
         * @param index 下标
         * @return 返回对应数组中的数据
         */
        public E get(int index){
            //非法索引
            if (index<0||index>=size){
                System.out.println(index);
                throw new IllegalArgumentException("Get failed. Index is Illegal.");
            }
            return data[index];
        }
    
        /**
         * 修改指定下标的数据
         * @param index 下标
         * @param e 修改后的数据
         */
        public void set(int index,E e){
            //非法索引
            if (index<0||index>=size){
                throw new IllegalArgumentException("Set failed. Index is Illegal.");
            }
            data[index]=e;
        }
    
        /**
         * 查询数组中是否包含某元素
         * @param e 查询的元素
         * @return 存在返回true,不存在返回false
         */
        public boolean contains(E e){
            for (int i = 0; i < size; i++) {
                //包含
                if (data[i].equals(e)){
                    return true;
                }
            }
            //遍历结束，不包含
            return false;
        }
    
        /**
         * 查询某元素的索引
         * @param e 查询的元素
         * @return 返回元素索引，元素不存在返回-1
         */
        public int findIndex(E e){
            for (int i = 0; i < size; i++) {
                if (data[i].equals(e)){
                    return i;
                }
            }
            return -1;
        }
    
        /**
         * 查询所有相同元素的索引
         * @param e 元素
         */
        public void findAllIndex(E e){
            StringBuilder sb=new StringBuilder();
            sb.append("AllIndex:");
            for (int i = 0; i < size; i++) {
                if (data[i].equals(e)){
                    sb.append(i+" ");
                }
            }
            System.out.println(sb.toString());
        }
    
        /**
         * 删除指定索引的元素
         * @param index 索引
         */
        public E removeByIndex(int index){
            //非法索引
            if (index<0||index>=size){
                throw new IllegalArgumentException("Remove failed. Require index>=0 and index<size.");
            }
            E removeElement=data[index];
            //依次将(i+1)的元素赋值到i
            for (int i = index; i < size-1; i++) {
                data[i]=data[i+1];
            }
            //元素个数-1
            size--;
            //设置为null,程序优化
            data[size]=null;
    
            //当元素个数小于容量的1/4，则减少容量为原来的1/2，且数组容量要大于1
            if (size<data.length/4&&data.length/2!=0){
                resetCapacity(data.length/2);
            }
            return removeElement;
        }
    
        /**
         * 删除第一个元素
         */
        public E removeFirst(){
            return removeByIndex(0);
        }
    
        /**
         * 删除最后一个元素
         */
        public E removeLast(){
            return removeByIndex(size-1);
        }
    
        /**
         * 删除指定元素
         * @param e 指定的元素
         */
        public E removeElement(E e){
            int index=findIndex(e);
            if (index==-1){
                throw new IllegalArgumentException("Remove failed.The element is nonexistent.");
            }else {
                return removeByIndex(index);
            }
        }
    
        /**
         * 删除所有相同的元素e
         * @param e 要删除的元素
         */
        public void removeAllElement(E e){
            int index=findIndex(e);
            if (index==-1){
                System.out.println("Remove failed.The element is nonexistent.");
            }else {
                for (int i = 0; i < size; i++) {
                    if (data[i].equals(e)){
                        removeByIndex(i);
                    }
                }
            }
        }
    }

## main测试： ##

public class Main {
    
        public static void main(String[] args) {
            Array<Integer> array=new Array(10);
            for (int i = 0; i <10 ; i++) {
                array.addLast(i);
            }
            //Array Size:10. Array Capacity:20.
            //[0,1,2,3,4,5,6,7,8,9]
            System.out.println(array);
    
            array.add(1,100);
            //Array Size:11. Array Capacity:20.
            //[0,100,1,2,3,4,5,6,7,8,9]
            System.out.println(array);
    
            array.addFirst(-1);
            //Array Size:12. Array Capacity:20.
            //[-1,0,100,1,2,3,4,5,6,7,8,9]
            System.out.println(array);
    
            //0
            System.out.println(array.get(1));
    
            array.set(11,9999);
            //Array Size:12. Array Capacity:20.
            //[-1,0,100,1,2,3,4,5,6,7,8,9999]
            System.out.println(array);
    
            //Remove success. Removed element:4,Removed index:6
            array.removeElement(4);
            /*
            Array Size:11. Array Capacity:20.
            [-1,0,100,1,2,3,5,6,7,8,9999]
             */
            System.out.println(array);
        }
    }

## 测试结果： ##

> Array Size:10. Array Capacity:10.  
> \[0,1,2,3,4,5,6,7,8,9\]  
> Array Size:11. Array Capacity:20.  
> \[0,100,1,2,3,4,5,6,7,8,9\]  
> Array Size:12. Array Capacity:20.  
> \[-1,0,100,1,2,3,4,5,6,7,8,9\]  
> 0  
> Array Size:12. Array Capacity:20.  
> \[-1,0,100,1,2,3,4,5,6,7,8,9999\]  
> Array Size:11. Array Capacity:20.  
> \[-1,0,100,1,2,3,5,6,7,8,9999\]