數組
- 數據結構中最基本的一個結構就是線性結構,而線性結構又分為連續存儲結構和離散存儲結構。所謂的連續存儲結構其實就是數組。
- 優點:查詢比較快如果知道座標可以快速去地存取
- 缺點 : 添加,刪除慢,大小固定
二次封裝數組的增刪改查
基類的定義
- 定義一個工具類名稱-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>閱讀更多 愛笑的阿杰 的文章