数据结构-数组
数组
- 数据结构中最基本的一个结构就是 线性结构 ,而线性结构又分为连续存储结构和离散存储结构。所谓的 连续存储结构 其实就是数组。
- 优点: 插入块如果知道坐标可以快速去地存取
- 缺点: 查找慢,删除慢,大小固定
二次封装数组的增删改查
基类的定义
- 定义一个 工具类 名称-Array
- 接受的参数包括 基本类型和自定义类型 (用泛型来接受,基本类型用包装类)
- 自定义属性两个 :size用来表示数组的大小,data用来表示一个准确的集合
- 概念区分 :size表示数组的大小,capacity表示数组容量的大小
- 构造函数 :有参构造,接受一个int值,用来初始化数组容量;无参构造:给容量一个默认值
- toString()方法 ,输出数组的大小和数组容量的大小,以及数组中的值
- getSize()方法 ,调用方通过方法来获取数组的大小
- getCapacity()方法 ,调用方通过方法来获取数组容量的大小
- isEmpty()方法 ,调用方通过方法来判断数组是否为空(指的是数组中是否有值,没值就为空)
基类的代码
package com.datastructure.array; /** * @program: test * @description: 自定义数组封装 工具 类 * @author: Mr.Yang * @create: 2019-05-01 15:36 **/ public class Array<E> { private Integer size; private E[] data; /** * 有参构造函数 * @param capacity 封装data的容量值 */ public Array(Integer capacity){ data= (E[]) new Object[capacity]; size=0; } /** * 无参构造函数,设置默认容量为10 */ public Array(){ this(10); } /** * 获取数组中的元素个数 * @return */ public Integer getSize(){ return size; } /** * 获取数组的容量 * @return */ public Integer getCapacity(){ return data.length; } /** * 判断数组是否为空 * @return */ public boolean isEmpty(){ return size==0; } @Override public String toString(){ StringBuffer sb = new StringBuffer(); sb.append(String.format("Array: size = %d , 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(); } }
增
添加的方法
- add()方法 ,两个参数,添加元素的索引位置,和元素的值
- addFirst()方法 ,在所有元素的最前面添加
- addLast()方法 ,在所有元素的最后面添加
添加的代码(增)
/** * 在索引为index的位置,插入param * 1.假如在索引为2的位置插入元素 * 2.需要将原来索引为2及其以后的位置向后移动一整位 * 3.移动完成之后,在索引为2的位置插入指定的值 * 4.因为数组中多了一个值,所以size需要+1 * * @param index 元素的索引 * @param param 值 */ public void add(int index, E param) { if (index < 0 || index > size) { throw new IllegalArgumentException("添加失败,索引的值不能小于0,并且索引的值不能大于数组的大小"); } if (size == data.length) { throw new IllegalArgumentException("添加失败,数组的大小已经等于了数组容量的大小"); } for (int i = size - 1; i >= index; i--) { data[i + 1] = data[i]; } data[index] = param; size++; } /** * 在所有元素之前添加值 * * @param param */ public void addFirst(E param) { add(0, param); } /** * 在所有元素之后添加值 * * @param param */ public void addLast(E param) { add(size, param); }
测试代码
package com.datastructure.array; /** * @program: test * @description: * @author: Mr.Yang * @create: 2019-05-01 16:46 **/ public class ArrayTest { public static void main(String[] args) { Array<Integer> integerArray = new Array<Integer>(20); for(int i = 0; i < 10 ; i ++){ integerArray.addLast(i); } System.out.println(integerArray); System.out.println("--------------------索引为3的地方添加元素-----------------------"); integerArray.add(3,666); System.out.println(integerArray); System.out.println("--------------------所有元素的最后面添加值-----------------------"); integerArray.addLast(10000); System.out.println(integerArray); System.out.println("--------------------所有元素的最前面添加值-----------------------"); integerArray.addFirst(-1); System.out.println(integerArray); } }
测试结果
Array: size = 10 , capacity = 20 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] --------------------索引为3的地方添加元素----------------------- Array: size = 11 , capacity = 20 [0, 1, 2, 666, 3, 4, 5, 6, 7, 8, 9] --------------------所有元素的最后面添加值----------------------- Array: size = 12 , capacity = 20 [0, 1, 2, 666, 3, 4, 5, 6, 7, 8, 9, 10000] --------------------所有元素的最前面添加值----------------------- Array: size = 13 , capacity = 20 [-1, 0, 1, 2, 666, 3, 4, 5, 6, 7, 8, 9, 10000]
改
添加的方法
- set ,两个参数,修改的元素的索引位置,和将要修改的值
添加的代码(改)
/** * 修改数组中元素的值 * @param index * @param param */ public void set(int index,E param){ if(index<0 || index>= size){ throw new IllegalArgumentException("获取失败,索引值无效"); } data[index]=param; }
测试代码
package com.datastructure.array; /** * @program: test * @description: * @author: Mr.Yang * @create: 2019-05-01 16:46 **/ public class ArrayTest { public static void main(String[] args) { Array<Integer> integerArray = new Array<Integer>(20); for (int i = 0; i < 10; i++) { integerArray.addLast(i); } System.out.println(integerArray); System.out.println("--------------------索引为3的地方修改值为1010-----------------------"); integerArray.set(3, 1010); System.out.println(integerArray); } }
测试结果
Array: size = 10 , capacity = 20 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] --------------------索引为3的地方修改值为1010----------------------- Array: size = 10 , capacity = 20 [0, 1, 2, 1010, 4, 5, 6, 7, 8, 9]
查
添加的方法
- get() 方法,一个参数,索引值,根据索引返回对应的值
- contains() 方法,一个参数,判断数组中是否包含某个元素
- find() 方法,一个参数,查找数组中是否包含param,如果包含返回索引值,不包含返回-1
- findAll() 方法,一个参数,查找数组中是否包含param,返回包含的索引数组
添加的代码(查)
/** * 获取索引位置的元素 * @param index * @return */ public E get(Integer index){ if(index<0 || index>=size){ throw new IllegalArgumentException("获取失败,索引的值不能小于0,并且索引的值不能大于等于数组的大小"); } return data[index]; } /** * 查看数组中是否包含某个元素 * @param param * @return */ public boolean contains(E param){ for(int i = 0 ; i < size ; i++){ if(data[i] == param){ return true; } } return false; } /** * 查找数组中是否包含param,如果包含返回索引值,不包含返回-1 * @param param * @return */ public Integer find(E param){ for(int i = 0 ; i < size ; i++){ if(data[i] == param){ return i; } } return -1; } /** * 查找数组中是否包含param * 1.创建一个int数组用来接收返回的索引值 * 2.索引容量最大为数组的大小 * 3.用临时变量来存储int数组的大小 * 4.如果相等,给 int数组 为临时变量的元素赋值(相等的索引),临时变量自增 * @param param * @return */ public Integer[] findAll(E param){ int intTemp=0; Integer[] integers = new Integer[size]; for(int i = 0 ; i < size ; i++){ if(data[i] == param){ integers[intTemp]=i; intTemp++; } } return integers; }
测试代码
package com.datastructure.array; import java.util.Arrays; /** * @program: test * @description: * @author: Mr.Yang * @create: 2019-05-01 16:46 **/ public class ArrayTest { public static void main(String[] args) { Array<Integer> integerArray = new Array<Integer>(20); for (int i = 0; i < 10; i++) { integerArray.addLast(i); } integerArray.addLast(3); System.out.println(integerArray); System.out.println("--------------------得到索引为3的值-----------------------"); System.out.println(integerArray.get(3)); System.out.println("--------------------判断是否包含有包含3的值-----------------------"); System.out.println(integerArray.contains(3)); System.out.println("--------------------查找是否包含参数,并返回索引-----------------------"); System.out.println(integerArray.find(3)); System.out.println("--------------------查找是否包含参数,并返回索引数组-----------------------"); System.out.println(Arrays.asList(integerArray.findAll(3))); } }
测试结果
Array: size = 11 , capacity = 20 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 3] --------------------得到索引为3的值----------------------- 3 --------------------判断是否包含有包含3的值----------------------- true --------------------查找是否包含参数,并返回索引----------------------- 3 --------------------查找是否包含参数,并返回索引数组----------------------- [3, 10, null, null, null, null, null, null, null, null, null]
删
添加的方法
- remove() 方法,数组中删除index位置的元素,并且返回对应的值
- removeFirst() 方法,删除第一位元素
- removeLast() 方法,删除最后一位元素
- removeElement() 方法,查看某个值是否在数组中存在,如果存在,删除并返回true,如果不存在 返回false、
- removeLast() 方法, 查找所有元素,获取所有相等的索引,遍历移除
添加的代码(删)
/** * 从数组中删除index位置的元素,并且返回对应的值 * 1.假如删除索引为3的元素 * 2.需要将索引大于3的元素向前移动一位 * 3.因为数组中少了一个值,所以元素-1 * 4.用临时变量来存储删除的值,用来返回 * @param index * @return */ public E remove(int index){ if(index<0 || index>=size){ throw new IllegalArgumentException("删除失败,索引的值不能小于0,并且索引的值不能大于等于数组的大小"); } E temp=data[index]; for(int i = index+1 ; i < size ; i++){ data[i-1]=data[i]; } size--; return temp; } /** * 删除第一位元素 * @return */ public E removeFirst(){ return remove(0); } /** * 删除最后一位元素 */ public E removeLast(){ return remove(size-1); } /** * 查看某个值是否在数组中存在,如果存在,删除并返回true,如果不存在 返回false * @param param */ public boolean removeElement(E param){ Integer index = find(param); if(index != -1){ remove(index); return true; } return false; } /** * 遍历数组,移除元素 * @param param */ public void removeAllElement(E param){ for(E d:data){ removeElement(param); } }
测试代码
package com.datastructure.array; import java.util.Arrays; /** * @program: test * @description: * @author: Mr.Yang * @create: 2019-05-01 16:46 **/ public class ArrayTest { public static void main(String[] args) { Array<Integer> integerArray = new Array<Integer>(20); for (int i = 0; i < 10; i++) { integerArray.addLast(i); } integerArray.addLast(3); integerArray.addLast(4); System.out.println(integerArray); System.out.println("--------------------数组中删除6位置的元素,并且返回对应的值-----------------------"); System.out.println(integerArray.remove(6)); System.out.println(integerArray); System.out.println("--------------------删除第一位元素-----------------------"); System.out.println(integerArray.removeFirst()); System.out.println(integerArray); System.out.println("--------------------删除最后一位元素-----------------------"); System.out.println(integerArray.removeLast()); System.out.println(integerArray); System.out.println("--------------------查看8是否在数组中存在,返回true和fals-----------------------"); System.out.println(integerArray.removeElement(8)); System.out.println(integerArray); System.out.println("--------------------查找所有元素,获取所有相等的索引,遍历移除-----------------------"); integerArray.removeAllElement(3); System.out.println(integerArray); } }
测试结果
Array: size = 12 , capacity = 20 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 3, 4] --------------------数组中删除6位置的元素,并且返回对应的值----------------------- 6 Array: size = 11 , capacity = 20 [0, 1, 2, 3, 4, 5, 7, 8, 9, 3, 4] --------------------删除第一位元素----------------------- 0 Array: size = 10 , capacity = 20 [1, 2, 3, 4, 5, 7, 8, 9, 3, 4] --------------------删除最后一位元素----------------------- 4 Array: size = 9 , capacity = 20 [1, 2, 3, 4, 5, 7, 8, 9, 3] --------------------查看8是否在数组中存在,如果存在,删除并返回true,如果不存在 返回false、----------------------- true Array: size = 8 , capacity = 20 [1, 2, 3, 4, 5, 7, 9, 3] --------------------查找所有元素,获取所有相等的索引,遍历移除----------------------- Array: size = 6 , capacity = 20 [1, 2, 4, 5, 7, 9]
数组动态扩容
添加的方法
- resize()方法,定义为私有,调用方不能通过方法来调用,去修改,否则容易造成BUG
- 扩容倍数,如果用固定值,不好抉择。比如:100容量,扩容10个,没有意义,很快就满了;100容量,扩充1000个,太多了,容易早证浪费。最好选择倍数,都在同一个单位级别,这里代码选择的是2倍
- 添加的时候需要判断扩容,删除的时候需要删除容量,减少资源浪费
- 删除的时候,当元素减少到容量的1/4的时候开始缩,缩减到容量的1/2
- 如果选择1/2的时候开始缩减,然后缩减到1/2会有一定的问题,例如:容量10,现在容量满了,来了一个元素,需要扩容,按照设置的扩容机制,会扩容2倍,也就是20容量,如果删除了一个元素,元素达到了容量的1/2,我们开始进行缩减,缩减1/2,容量又变为10。如果一直在这个临界值,那么元素会一直进行扩容缩减扩容缩减,性能影响太大。
- 如果选择1/4的时候开始缩减,然后缩减到1/2,这样能够较好的避开以上问题,例如:容量10,容量满了,来了一个元素,扩容容量到了20,如果删除一个元素,还不到容量的1/4,所以还不会进行缩减,如果真的到了容量的1/4的时候,我们选择缩减1/2,容量也需要一定的元素,才会进行扩容,防止了容量一直扩容或者缩减
添加的代码
/** * 扩容方法 * 1.需要new一个object,new E[i] java不支持这样写 * 2.object是所有类的基类,用object然后强转一下就可以 * 3.扩展之后,需要将原数组中的值,放入扩展之后的数组中 * @param 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; }
修改的代码
- add() 和 remove()
/** * 在索引为index的位置,插入param * 1.假如在索引为2的位置插入元素 * 2.需要将原来索引为2及其以后的位置向后移动一整位 * 3.移动完成之后,在索引为2的位置插入指定的值 * 4.因为数组中多了一个值,所以size需要+1 * * @param index 元素的索引 * @param param 值 */ public void add(int index, E param) { if (index < 0 || index > size) { throw new IllegalArgumentException("添加失败,索引的值不能小于0,并且索引的值不能大于数组的大小"); } if (size == data.length) { resize(2 * data.length); } for (int i = size - 1; i >= index; i--) { data[i + 1] = data[i]; } data[index] = param; size++; } /** * 从数组中删除index位置的元素,并且返回对应的值 * 1.假如删除索引为3的元素 * 2.需要将索引大于3的元素向前移动一位 * 3.因为数组中少了一个值,所以元素-1 * 4.用临时变量来存储删除的值,用来返回 * @param index * @return */ public E remove(int index){ if(index<0 || index>=size){ throw new IllegalArgumentException("删除失败,索引的值不能小于0,并且索引的值不能大于等于数组的大小"); } E temp=data[index]; for(int i = index+1 ; i < size ; i++){ data[i-1]=data[i]; } size--; if(size == data.length / 4 ){ resize(data.length / 2 ); } return temp; }
测试代码
package com.datastructure.array; import java.util.Arrays; /** * @program: test * @description: * @author: Mr.Yang * @create: 2019-05-01 16:46 **/ public class ArrayTest { public static void main(String[] args) { Array<Integer> integerArray = new Array<Integer>(10); for (int i = 0; i < 10; i++) { integerArray.addLast(i); } System.out.println(integerArray); System.out.printf("--------------------将容量设置为10,添加10个元素,元素的容量 : %d -------------------\r\n",integerArray.getCapacity()); integerArray.addLast(21); System.out.printf("--------------------元素+1,元素的容量 : %d --------------------\r\n",integerArray.getCapacity()); integerArray.removeLast(); System.out.printf("--------------------元素-1,元素的容量 : %d --------------------\r\n",integerArray.getCapacity()); integerArray.removeLast(); System.out.printf("--------------------元素-1,元素的容量 : %d --------------------\r\n",integerArray.getCapacity()); for(int x=0;x<=5;x++){ integerArray.removeLast(); } System.out.printf("--------------------元素-1/4,元素的容量 : %d --------------------\r\n",integerArray.getCapacity()); } }
测试结果
Array: size = 10 , capacity = 10 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] --------------------将容量设置为10,添加10个元素,元素的容量 : 10 ------------------- --------------------元素+1,元素的容量 : 20 -------------------- --------------------元素-1,元素的容量 : 20 -------------------- --------------------元素-1,元素的容量 : 20 -------------------- --------------------元素-1/4,元素的容量 : 10 --------------------
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。