数据结构-数组

数据结构-数组

数组

• 数据结构中最基本的一个结构就是线性结构，而线性结构又分为连续存储结构和离散存储结构。所谓的连续存储结构其实就是数组。
• 优点：查询比较快如果知道坐标可以快速去地存取
• 缺点 : 添加,删除慢,大小固定

二次封装数组的增删改查

基类的定义

• 定义一个工具类名称-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 {

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>

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);/<integer>/<integer>

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);/<integer>/<integer>

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);/<integer>/<integer>

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);/<integer>/<integer>

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>

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);/<integer>/<integer>

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 --------------------

/<size>

/<size>