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

29次阅读

共计 6469 个字符，预计需要花费 17 分钟才能阅读完成。

数组

什么是数组？

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

须要留神的是数组的索引是从 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)

正文完
数据结构
发表至： 数据结构
2020-08-14
 0
关于数据结构:数据同步一致性保障OPPO自研JinS数据同步框架实践
关于数据结构:折半插入排序
关于数据结构:LeetCode069x的平方根easy
关于数据结构:数据结构与算法系列之跳表GO