數據結構之數組詳解

2020 年 6 月 2 日
筆記
數據結構

數組(Array)是由相同類型的元素(element)集合組成的固定長度(Size)的一種數據結構。在內存中是連續存儲的，因此可以通過索引(Index)計算出某個元素的地址。

下面介紹都是已java為示例。對於沒有詳細了解過的相信有所收穫。

基礎知識

聲明

type arrayName[] 或者 type[] arrayName。

如：

int arrInt[] 或者 int[] arrInt

聲明過程，只是告訴編譯器: arrInt變量保存了一個int類型的數組。這個過程並沒有分配內存。

new分配內存

分配內存需要通過new完成，同時指明類型和數組大小。

如：

int[] arrInt = new int[4];

數組中元素通過new分配後自動完成初始化，一般有幾種：數字類型初始化為0(如：int/byte/short/long初始化為0，float/double初始化為0.0)，布爾型初始化為false(boolean初始化為false),String或者其他對象類型初始化為null。

數組賦值也有兩種

int[] arrInt = {1,3,5,7};
或
int[] arrInt = new int[4];
arrInt[0] = 1;
arrInt[1] = 3;
arrInt[2] = 5;
arrInt[3] = 7;

示意圖如下：

多維數組

多維數組類似，即數組中的元素也是數組。如

int[][] arrInt = {{1,3,5},{2,4,6},{0,10,20}};

示意圖如下：

數組特點

索引(即下標) 一般從0開始，如java, C/C++。
長度固定，在申請時長度固定。內存連續，在內存中則是申請一塊連續的固定大小的空間。
數組有一維數組和多維數組，數組元素可以是基本數據類型(Primitive)，也可以是對象引用(Reference)。
隨機訪問，能夠根據位置(下標)直接訪問到元素。

註：

基本數據類型和對象引用數據類型

Primitive類型在java中有八種(具體內容後續整理)，Primitive類型在內存位置直接存入實際的值，引用對象的內存分配是在堆上(Heap)。

Primitive類型： boolean、char、byte、short、int、long、float、double

數組下標從0開始

數組變量引用指向了數組實際分配的連續內存的開始地址即第一個元素的地址(firstAdrr)，數組下標(index)即偏移量。假使每個元素大小為size.

那麼數組元素位置計算：firstAdrr+index*size。

所以大部分語言數組下標是0開始。如果從1開始，計算位置時偏移量要減1操作，多了一步運算。

數組關聯的Class對象

每個數組有一個關聯的Class對象，與其他相同類型數組共享。

如：JNI中傳遞的參數經常看到：I表示int類型，[ 表示一個數組，[I 即int數組。

System.out.println("int array:" + new int[3].getClass());
System.out.println("int array:" + new int[3].getClass().getSuperclass());
System.out.println("String array:" + new String[3].getClass());
System.out.println("boolean array:" + new boolean[3].getClass());

結果為：

int array:class [I
int array super:class java.lang.Object
String array:class [Ljava.lang.String;
boolean array:class [Z

數組的拷貝

一維數組拷貝

一維數組的clone()是深度拷貝，拷貝了數組內的原始數據到新數組，而不是引用的複製。

如：

int arrInt[] = {1,2,3};
 
int arrClone[] = arrInt.clone();
arrClone[1] = 5;
  
System.out.println(arrInt == arrClone);
  
for (int i = 0; i < arrClone.length; i++) {
    System.out.println(arrInt[i]+" "+arrClone[i]);
}

結果為：

false
1 1
2 5
3 3

示意圖如下：

多維數組拷貝

但多維數組則不是這樣。如：

int arrInt[][] = {{1,2,3},{4,5,6}};
        
int[][] arrClone = arrInt.clone();
arrClone[0][1] = 50;
arrInt[0][1] = 100;
  
System.out.println(arrInt == arrClone);
System.out.println(arrInt[0] == arrClone[0]);
  
for (int i = 0; i < arrInt.length; i++) {
    for (int j = 0; j < arrInt[i].length; j++) {
        System.out.println(arrInt[i][j]+" "+arrClone[i][j]);
    }
    
}

結果為：

false
true
1 1
100 100
3 3
4 4
5 5
6 6

示意圖如下：

數組操作

插入

如圖，向數組中插入一個元素，插入位置及之後的所有元素都需要向後挪動一位來完成插入操作。

如果數組已經滿了(或者保證數組長度與元素個數一致),則只能創建一個新的數組(長度增加的)來完成插入操作。

時間複雜度上，最好的是數組未滿插入到最後只需直接插入，操作一次(O(1))。最壞是插入到第一位，需要操作N次。

平均時間複雜度，(1 + 2 + … + n) / n ~= O(n)

這是一個簡單的插入示例。在現有數組的position位置插入value值，首先創建了一個新數組(長度+1)，依次填入數據。

private int[] insertArr(int[] srcArr, int position, int value) {
    if (position < 0 || position >= srcArr.length) return null;
    int[] desArr = new int[srcArr.length+1];
    System.arraycopy(srcArr, 0, desArr, 0, position);
    desArr[position] = value;
    System.arraycopy(srcArr, position, desArr, position+1, srcArr.length-position);
    return desArr;
}

刪除

類似插入的反向操作，刪除某個元素，該位置及之後的所有元素向前挪一位。

如果要保證數組長度與數組元素個數一致，則也需要重新創建一個(長度減小的)數組來完成。

示意圖：

查找

查找某一元素位置，只能一位位的遍歷查找了。

訪問

對於某位置的元素，直接讀取或修改就可以了。數組是隨機訪問的。

時間複雜度總結

最後整理個表格，上述操作的時間複雜度大致如下，很容易理解就不詳細解釋了。

操作	平均時間複雜度	最壞條件時間複雜度
插入	O(n)	O(n)
刪除	O(n)	O(n)
查找	O(n)	O(n)
訪問	O(1)	O(1)

Tags: 數據結構