数据结构（二）数组

数组就是把数据码成一排进行存放：数组的最大优点：快速查询。scores[2]我们基于Java的静态数组，封装一个属于自己的动态数组类Array，加深对于数组这种数据结构的理解。我们基于Java静态数组data来封装我们的动态数组Array类，capacity表示数组容量，可以通过data.length获得。size表示数组元素个数，初始为0（也可以看成是下一个新增元素的索引位置）。据此，设计Array类结构。初始数组类结构public class Array<E> { private E[] data; private int size; // 构造函数，传入数组的容量captacity构造Array public Array(int capacity) { data = (E[])new Object[capacity]; size = 0; } // 无参数的构造函数，默认数组的容量capacity=10 public Array() { this(10); } // 获取数组中的元素个数 public int getSize() { return size; } // 获取数组的容量 public int getCapacity() { return data.length; } // 返回数组是否为空 public boolean isEmpty() { return size == 0; } }向数组末尾添加元素添加元素前：添加元素后：分析得出，如果要向数组添加元素e，只要在size所在索引位置设置元素e，然后size向后移动（size++）即可。据此，增加添加元素相关的代码：// 在所有元素后添加一个新元素public void addLast(E e) { if(size == data.length) { // 数组容量已填满，则不能再添加 throw new IllegalArgumentException(“AddLast failed. Array is full.”); } data[size] = e; size++;}向指定位置添加元素添加前：添加后：分析得出，只要把要插入元素的索引位置的当前元素以及其后的所有元素，都往后挪动一位，然后在指定索引位置设置新元素即可，最后size++。为避免元素覆盖，具体挪的时候，需要从后往前推进完成元素挪动的整个过程。修改代码：// 在第index个位置插入一个新元素epublic void add(int index, E e) { if(size == data.length) { throw new IllegalArgumentException(“Add failed. Array is full.”); } 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++;}调整addLast，复用add方法，同时增加一个addFirst：// 在所有元素后添加一个新元素public void addLast(E e) { add(size, e);}// 在所有元素前添加一个新元素public void addFirst(E e) { add(0, e);}获取元素和修改元素// 获取index索引位置的元素public E get(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException(“Get failed. Index is illegal.”); } return data[index];}// 修改index索引位置的元素public void set(int index, E e) { if (index < 0 || index >= size) { throw new IllegalArgumentException(“Set failed. Index is illegal.”); } data[index] = e;}包含、搜索// 查找数组中是否有元素epublic boolean contains(E e) { for (int i = 0; i < size; i++) { if (data[i].equals(e)) { return true; } } return false;}// 查找数组中元素e所在的索引，如果不存在元素e，则返回-1public int find(E e) { for (int i = 0; i < size; i++) { if (data[i].equals(e)) { return i; } } return -1;}从数组中删除元素删除前：删除后：分析得出，只要将要删除位置之后的元素都往前挪动一位即可。然后size减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–; return ret;}// 从数组中删除第一个元素，返回删除的元素public E removeFirst() { return remove(0);}// 从数组中删除最后一个元素，返回删除的元素public E removeLast() { return remove(size - 1);}// 从数组中删除元素e（只删除一个）public boolean removeElement(E e) { int index = find(e); if (index != -1) { remove(index); return true; } return false;}动态数组容量开太大，浪费空间，容量开小了，空间不够用。所以需要实现动态数组。具体做法如下：就是在方法中开辟一个更大容量的数组，循环遍历原来的数组元素，设置到新的数组上。然后将原数组的data指向新数组。修改代码：// 数组容量扩容/缩容public void resize(int newCapacity) { E[] newData = (E[])new Object[newCapacity]; for (int i = 0; i < size; i++) { newData[i] = data[i]; } data = newData;}修改添加元素的代码，添加时自动扩容：// 在第index个位置插入一个新元素epublic void add(int index, E e) { if (index < 0 || index > size) { throw new IllegalArgumentException(“AddLast failed. Require index >= 0 and index <= size”); } if (size == data.length) { resize(2 * data.length); // 扩容为原来的2倍 } for (int i = size - 1; i >= index; i–) { data[i + 1] = data[i]; } data[index] = e; size++;}修改删除元素的代码，必要时自动缩容：// 从数组中删除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; // loitering objects != memory leak if (size == data.length / 4 && data.length / 2 != 0) { // 缩减数组使用lazy方式（避免复杂度震荡），在1/4的时候缩容 resize(data.length / 2); // 缩容为原来的一半 } return ret;}测试数组@Overridepublic 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<Integer> arr = new Array<>(); for (int i = 0; i < 10; i++) { arr.addLast(i); } System.out.println(arr); arr.add(1, 100); System.out.println(arr); arr.addFirst(-1); System.out.println(arr); arr.remove(2); System.out.println(arr); arr.removeElement(4); System.out.println(arr); arr.removeFirst(); System.out.println(arr);}console输出：Array: size = 10, capacity = 10[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]Array: size = 11, capacity = 20[0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]Array: size = 12, capacity = 20[-1, 0, 100, 1, 2, 3, 4, 5, 6, 7, 8, 9]Array: size = 11, capacity = 20[-1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9]Array: size = 10, capacity = 20[-1, 0, 1, 2, 3, 5, 6, 7, 8, 9]Array: size = 9, capacity = 20[0, 1, 2, 3, 5, 6, 7, 8, 9]完整代码public class Array<E> { private E[] data; private int size; // 构造函数，传入数组的容量captacity构造Array public Array(int capacity) { data = (E[])new Object[capacity]; size = 0; } // 无参数的构造函数，默认数组的容量capacity=10 public Array() { this(10); } // 获取数组中的元素个数 public int getSize() { return size; } // 获取数组的容量 public int getCapacity() { return data.length; } // 返回数组是否为空 public boolean isEmpty() { return size == 0; } // 在第index个位置插入一个新元素e 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); // 扩容为原来的2倍 } for (int i = size - 1; i >= index; i–) { data[i + 1] = data[i]; } data[index] = e; size++; } // 在所有元素后添加一个新元素 public void addLast(E e) { add(size, e); } // 在所有元素前添加一个新元素 public void addFirst(E e) { add(0, e); } // 获取index索引位置的元素 public E get(int index) { if (index < 0 || index >= size) { throw new IllegalArgumentException(“Get failed. Index is illegal.”); } return data[index]; } // 修改index索引位置的元素 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)) { 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; // loitering objects != memory leak if (size == data.length / 4 && data.length / 2 != 0) { // 缩减数组使用lazy方式（避免复杂度震荡），在1/4的时候才缩容 resize(data.length / 2); // 缩容为原来的一半 } return ret; } // 从数组中删除第一个元素，返回删除的元素 public E removeFirst() { return remove(0); } // 从数组中删除最后一个元素，返回删除的元素 public E removeLast() { return remove(size - 1); } // 从数组中删除元素e（只删除一个） public boolean removeElement(E e) { int index = find(e); if (index != -1) { remove(index); return true; } return false; } public void resize(int newCapacity) { E[] newData = (E[])new Object[newCapacity]; for (int i = 0; i < size; i++) { newData[i] = data[i]; } data = newData; } @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<Integer> arr = new Array<>(); for (int i = 0; i < 10; i++) { arr.addLast(i); } System.out.println(arr); arr.add(1, 100); System.out.println(arr); arr.addFirst(-1); System.out.println(arr); arr.remove(2); System.out.println(arr); arr.removeElement(4); System.out.println(arr); arr.removeFirst(); System.out.println(arr); }}