算法学习之动态数组类
算法学习之动态数组类
一、整型动态数组类
数组操作逻辑代码实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 |
public class Array { private int[] data; private int size; //构造函数，传入数组的容量capacity构造Array public Array(int capacity){ data = new int[capacity]; size = 0; } //无参构造函数，默认数组的容量capacity=10 public Array() { this(10); } // 获取数组的容量 public int getCapacity(){ return data.length; } // 获取数组中的元素个数 public int getSize(){ return size; } // 返回数组是否为空 public boolean isEmpty(){ return size == 0; } // 向所有元素后添加一个新元素 public void addLast(int e){ // if(size == data.length) // throw new IllegalArgumentException("AddLast failed. Array is full."); // // data[size] = e; // size ++; add(size, e); //代码的复用 } // 在所有元素前添加一个新元素 public void addFirst(int e){ add(0, e); } // 在index索引的位置插入一个新元素e public void add(int index, int 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 ++; } //获取index索引位置的元素 public int get(int index){ if (index<0 || index>=size) throw new IllegalArgumentException("Get failed. Index is illegal."); return data[index]; } // 修改index索引位置的元素为e public void set(int index, int e){ if(index < 0 || index >= size) throw new IllegalArgumentException("Set failed. Index is illegal."); 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; } // 从数组中删除index位置的元素, 返回删除的元素 public int remove(int index){ if(index < 0 || index >= size) throw new IllegalArgumentException("Remove failed. Index is illegal."); int ret = data[index]; for(int i = index + 1 ; i < size ; i ++) data[i - 1] = data[i]; size --; return ret; } // 从数组中删除第一个元素, 返回删除的元素 public int removeFirst(){ return remove(0); } // 从数组中删除最后一个元素, 返回删除的元素 public int removeLast(){ return remove(size - 1); } // 从数组中删除元素e public void removeElement(int 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(); } } |
数组操作测试
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 |
public class Main { public static void main(String[] args) { // int[] arr = new int[20]; // for (int i = 0; i < arr.length; i++) { //arr.length可变 // arr[i] = i; // } // // int[] scores = new int[]{100, 99, 98}; // for (int score : scores) // foreach循环的实现 // System.out.println(score); Array arr = new Array(20); 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); } } |
二、使用泛型
让我们的数据结构可以放置“任何”数据类型
不可以是基本数据类型，只能是类对象
boolean，byte , char，short，int，long，float，double
每个基本数据类型都有对应的包装类
Boolean，Byte，Char，Short , Int , Long，Float，Double
需要改动的地方：
1、声明数组的方式，不再只是int
|
1 2 3 4 5 6 7 |
public class Array<E>{ private E[] data; ... //创建类数组 data = (E[])new Object[capacity]; } |
2、传入参数类型改变
|
1 2 3 4 |
public void addLast(E e){ //不再是int e add(size, e); } |
3、值比较与引用比较
|
1 2 3 4 5 6 7 8 9 10 |
判断相等的时候不能用==，改为equals()方法 // 查找数组中是否有元素e public boolean contains(E e){ for(int i = 0 ; i < size ; i ++){ if(data[i].equals(e)) //data[i] == e return true; } return false; } |
4、声明存放数据类型
|
1 2 3 4 |
Array<Integer> arr = new Array<>(20); int类型的包装类 //下面是原来的 Array arr = new Array(20); |
修改后的泛型数组代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 |
public class Array<E> { private E[] data; private int size; // 构造函数，传入数组的容量capacity构造Array public Array(int capacity){ data = (E[])new Object[capacity]; size = 0; } // 无参数的构造函数，默认数组的容量capacity=10 public Array(){ this(10); } // 获取数组的容量 public int getCapacity(){ return data.length; } // 获取数组中的元素个数 public int getSize(){ return size; } // 返回数组是否为空 public boolean isEmpty(){ return size == 0; } // 在index索引的位置插入一个新元素e public 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 ++; } // 向所有元素后添加一个新元素 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索引位置的元素为e 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 return ret; } // 从数组中删除第一个元素, 返回删除的元素 public E removeFirst(){ return remove(0); } // 从数组中删除最后一个元素, 返回删除的元素 public E removeLast(){ return remove(size - 1); } // 从数组中删除元素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(); } } |
泛型数组操作代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
public class Student { private String name; private int score; public Student(String studentName, int studentScore){ name = studentName; score = studentScore; } @Override public String toString(){ return String.format("Student(name: %s, score: %d)", name, score); } public static void main(String[] args) { Array<Student> arr = new Array<>(); arr.addLast(new Student("Alice", 100)); arr.addLast(new Student("Bob", 66)); arr.addLast(new Student("Charlie", 88)); System.out.println(arr); } } |
三、动态数组
当数组的长度大于数组实际的个数的时候，多余的空间就会浪费，可以自动调用方法使数组长度变小。
一般采取2倍的操作，扩容2倍或者缩小2倍。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
// 在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); 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 / 2) resize(data.length / 2); return ret; } // 将数组空间的容量变成newCapacity大小 private void resize(int newCapacity){ E[] newData = (E[])new Object[newCapacity]; for(int i = 0 ; i < size ; i ++) newData[i] = data[i]; data = newData; } |
四、复杂度震荡
当长度刚好是数组长度时，增加一个和删除一个末尾的元素都需要扩容，时间复杂度都是O(n)，在这个极端情况下产生的复杂度变化称为复杂度震荡。解决的方式就是懒处理，当元素在原来的1/4时缩小一半。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// 从数组中删除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) resize(data.length / 2); return ret; } |