数据结构-数组
数组
- 数据结构中最基本的一个结构就是 线性结构 ，而线性结构又分为连续存储结构和离散存储结构。所谓的 连续存储结构 其实就是数组。
- 优点： 插入块如果知道坐标可以快速去地存取
- 缺点： 查找慢,删除慢,大小固定
二次封装数组的增删改查
基类的定义
- 定义一个 工具类 名称-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 --------------------
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Iterative Methods for Sparse Linear Systems, Second Edition
Yousef Saad / Society for Industrial and Applied Mathematics / 2003-04-30 / USD 102.00
Tremendous progress has been made in the scientific and engineering disciplines regarding the use of iterative methods for linear systems. The size and complexity of linear and nonlinear systems arisi......一起来看看 《Iterative Methods for Sparse Linear Systems, Second Edition》 这本书的介绍吧!
