数组

什么是数组？

数组就是把数据码成一排进行寄存

须要留神的是数组的索引是从0开始

应用Java中的数组

public static void main(String[] args) {
        //定义数组以及长度为10
        int[] arr = new int[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i;
        }
        //定义数组以及数据
        int[] scores = new int[]{100, 99, 98};
        //批改第0个值为10
        scores[0] = 10;
        for (int score : scores) {
            System.out.println(score);
        }
}

封装属于咱们的数组

数组最大的长处：疾速查问。 scores[2]
数组最好利用于”索引有语意”的状况。
然而并非所有有语意的索引都实用于数组
例如：身份证号，如果想用身份证号来当索引的话，咱们要开拓一个很大的空间。

索引没有语意的状况下，如何示意没有元素？

如何增加元素？如何删除元素？

基于Java的数组，二次封装属于咱们本人的数组类。

public class Array {
        private int[] data;
        private int size;

        //无参数的构造函数，默认的数组容量大小为10
        public Array() {
            this(10);
        }

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

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

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

        public boolean isEmpty() {
            return size == 0;
        }
    }

向数组中增加元素

一开始，数组的size是0，如果咱们想增加值为66，数据将会寄存在索引为0的地位，而后size进行自增。

public void addLast(int e){
        if(size >= data.length){
            throw new ArrayIndexOutOfBoundsException("AddLast failed. Array is full");
        }
        data[size] = e;
        size ++;
    }

然而，如果咱们想在指定地位插入数据呢？

如果咱们要把77插入到如图索引为1的地位，咱们首先须要将100往后挪一位，而后将99、88顺次后挪一位，而后腾出地位给77进行插入。插入之后不要遗记将size自增

public void addLast(int e) {
        add(size, e);
}

public void addFirst(int e) {
    add(0, e);
}

public void add(int index, int e) {
    if (size >= data.length) {
        throw new ArrayIndexOutOfBoundsException("add failed. Array is full.");
    }
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("add failed. Require index >= 0 and index <= size.");
    }
    //将大于index的元素都进行索引加一
    for (int i = size - 1; i >= index; i--) {
        data[i + 1] = data[i];
    }
    data[index] = e;
    size++;
}

顺便咱们重写一下toString办法，测试一下咱们的Array类。

    @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 static void main(String[] args) {
        Array array = new Array(20);
        for (int i = 0; i < 10; i++) {
            array.addLast(i);
        }
        array.addLast(15);
        array.addFirst(17);
        array.add(5,18);
        System.out.println(array);
}

Array: size = 13 , capacity = 20[17, 0, 1, 2, 3, 18, 4, 5, 6, 7, 8, 9, 15]

查问元素和批改元素

    //获取index索引地位的元素
    public int get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("get failed. Require index >= 0 and index < size.");
        }
        return data[index];
    }

    //批改index索引地位的元素
    public void set(int index, int e) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("set failed. Require index >= 0 and index < size.");
        }
        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;
    }

如果咱们想删除指定地位的元素，咱们须要将大于指定地位的索引全副顺次往前挪一位。

当数据挪完当前呢，咱们不须要删除索引为4的数据，只须要将索引减一指向4即可。

因为用户是永远看不到size的值是多少，只能查问到size – 1的值。

    //从数组中删除index地位的元素，并返回删除的元素
    public int remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("remove failed. Require index >= 0 and index < size.");
        }
        int ret = data[index];
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size --;
        return ret;
    }
    //从数组中删除最初一个元素，并返回删除的元素
    public int removeLast() {
        return remove(size -1);
    }
    //从数组中删除第一个元素，并返回删除的元素
    public int removeFirst() {
        return remove(0);
    }
    //从数组中删除元素e
    public void removeElement(int e) {
        int index = find(e);
        if (index != -1){
            remove(index);
        }
    }

目前为止，咱们这个Array只能承载int类型，咱们不可能为每个类型创立一个数组类，所以咱们要应用泛型来解决此问题。

应用泛型

这里我就间接放出替换好的Array类

public class Array<E> {
        private E[] data;
        private int size;
        //无参数的构造函数，默认的数组容量大小为10
        public Array() {
            this(10);
        }
        //构造函数，传入数组的容量capacity结构Array
        public Array(int capacity) {
            data = (E[]) new Object[capacity];
            size = 0;
        }
        //获取数组中的元素个数
        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);
        }
        public void addFirst(E e) {
            add(0, e);
        }
        public void add(int index, E e) {
            if (size >= data.length) {
                throw new ArrayIndexOutOfBoundsException("add failed. Array is full.");
            }
            if (index < 0 || index > size) {
                throw new IllegalArgumentException("add failed. Require index >= 0 and index <= size.");
            }
            //将大于index的元素都进行索引加一
            for (int i = size - 1; i >= index; i--) {
                data[i + 1] = data[i];
            }
            data[index] = e;
            size++;
        }
        //获取index索引地位的元素
        public E get(int index) {
            if (index < 0 || index >= size) {
                throw new IllegalArgumentException("get failed. Require index >= 0 and index < size.");
            }
            return data[index];
        }
        //批改index索引地位的元素
        public void set(int index, E e) {
            if (index < 0 || index >= size) {
                throw new IllegalArgumentException("set failed. Require index >= 0 and index < size.");
            }
            data[index] = e;
        }
        //查找数组中是否有元素e
        public boolean contains(E e) {
            for (int i = 0; i < size; i++) {
                if (data[i] == e) {
                    return true;
                }
            }
            return false;
        }
        //查找数组中元素e所在的索引，如果不存在元素e，则返回-1
        public int find(E e) {
            for (int i = 0; i < size; i++) {
                if (data[i] == e) {
                    return i;
                }
            }
            return -1;
        }
        //从数组中删除index地位的元素，并返回删除的元素
        public E remove(int index) {
            if (index < 0 || index >= size) {
                throw new IllegalArgumentException("remove failed. Require index >= 0 and index < size.");
            }
            E ret = data[index];
            for (int i = index + 1; i < size; i++) {
                data[i - 1] = data[i];
            }
            size --;
            //回收以后无用的数据
            data[size] = null;
            return ret;
        }
        //从数组中删除最初一个元素，并返回删除的元素
        public E removeLast() {
            return remove(size -1);
        }
        //从数组中删除第一个元素，并返回删除的元素
        public E removeFirst() {
            return remove(0);
        }
        //从数组中删除元素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 static void main(String[] args) {
        Array<String> arr = new Array<>(10);
        arr.addLast("张三");
        arr.addLast("李四");
        arr.addLast("王五");
        System.out.println(arr);
    }

Array: size = 3 , capacity = 10[张三, 李四, 王五]

这样咱们就能够很轻易的实现了不同对象的数组。

动静数组

当初咱们的数组还是一个无限的固定的容量，如果预估容量过大，会导致节约很多空间，如果预估容量过小，则会呈现不够用，所以咱们须要应用可伸缩的动静数组。

如果以后数组曾经满了，那咱们就开拓一个新的数组，而后将data的数组进行循环拷贝过来，而后将data指向新的数组。

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);
        }
        //将大于index的元素都进行索引加一
        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 (index < 0 || index >= size) {
            throw new IllegalArgumentException("remove failed. Require index >= 0 and index < size.");
        }
        E ret = data[index];
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size --;
        //回收以后无用的数据
        data[size] = null;
        //缩容
        if (size == data.length / 2 && data.length / 2 != 0){
            resize(data.length / 2);
        }
        return ret;
    }

简略工夫复杂度剖析

增加操作
- addLast(e) O(1)
- addFirst(e) O(n)
- add(index,e) O(n/2) = O(n)
删除操作
- removeLast(e) O(1)
- removeFirst(e) O(n)
- remove(index,e) O(n/2) = O(n)
批改操作
- set(index,e) O(1)
查找操作
- get(index) O(1)
- contains(e) O(n)
- find(e) O(n)

关于数据结构:数据结构之数组

数组

应用Java中的数组

封装属于咱们的数组

向数组中增加元素

查问元素和批改元素

蕴含，搜寻和删除

应用泛型

动静数组

简略工夫复杂度剖析

评论

发表回复取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

关于数据结构:数据结构之数组

数组

应用Java中的数组

封装属于咱们的数组

向数组中增加元素

查问元素和批改元素

蕴含，搜寻和删除

应用泛型

动静数组

简略工夫复杂度剖析

评论

发表回复 取消回复

更多文章

DDN HPC 存储硬件架构设计深度分析

探秘IO500：从Lustre并行文件系统出发，开启HPC存储性能新征程

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

发表回复取消回复