【久遠(yuǎn)講算法3】數(shù)組——最簡單的數(shù)據(jù)結(jié)構(gòu)

“閱讀本文大概需要6分鐘”

前言：

你好，我是久遠(yuǎn)，前面兩篇文章：

• 【久遠(yuǎn)講算法①】什么是時間復(fù)雜度

• 【久遠(yuǎn)講算法】什么是空間復(fù)雜度？
  

我們對算法以及時空復(fù)雜度進(jìn)行了詳細(xì)的講解，但是，這其實是遠(yuǎn)遠(yuǎn)不夠的，時空復(fù)雜度只是我們算法學(xué)習(xí)中的冰山一角，下面讓我們通過數(shù)組的學(xué)習(xí)來正式打開算法與數(shù)據(jù)結(jié)構(gòu)的大門吧！

以下是我之后文章的具體走向，感興趣的小伙伴可以跟著路線進(jìn)行自學(xué)哦！

基礎(chǔ)篇暫定走向為：數(shù)組→鏈表→棧和隊列→樹→遞歸

基礎(chǔ)篇更完以后我將會開啟力扣刷題套路篇哦，帶大家一起提高對編程語言以及算法的熟練度。

什么是數(shù)組

關(guān)于數(shù)組，雖然它是數(shù)據(jù)結(jié)構(gòu)世界里最常用以及最簡單的，但是之前仍有同學(xué)向我反饋：數(shù)組難以理解！那我們就來對數(shù)組進(jìn)行詳細(xì)的講解，幫助大家解惑。

首先我們在此聲明，python 本身的庫中其實是沒有數(shù)組這個內(nèi)置類型的，但存在有列表 ( list )這個內(nèi)置類型，列表和數(shù)組在長相以及實際應(yīng)用上是相似的，因此我嘗試拿列表來進(jìn)行數(shù)組相關(guān)知識的講解。（實際上在 python 的 numpy 庫中是存在有數(shù)組這樣一個數(shù)據(jù)結(jié)構(gòu)的，之后我們會專門寫一篇文章來分析數(shù)組和列表的異同。）

在計算機科學(xué)中，數(shù)組數(shù)據(jù)結(jié)構(gòu)，簡稱數(shù)組，英文名為 array ，是由相同類型的元素的集合所組成的數(shù)據(jù)結(jié)構(gòu)，分配一塊連續(xù)的內(nèi)存來存儲。利用元素的索引可以計算出該元素對應(yīng)的存儲地址。

是不是看完這一長串理論，已經(jīng)開始暈了？那我們現(xiàn)在提煉這段話并就來用現(xiàn)實生活的例子來解析這段話，帶大家認(rèn)識到底什么是數(shù)組。

假設(shè)我們是指揮官，我們編程時使用數(shù)組，就相當(dāng)于我們作為指揮官給指定人數(shù)的士兵布置了一個團(tuán)隊任務(wù)。而這個指定人數(shù)的隊伍，就可以視為一個數(shù)組。

• 數(shù)組由相同類型的元素的集合所組成。這就像是現(xiàn)實中的一列士兵，他們的職業(yè)都是軍人，即所謂的類型相同，他們都是同一個連或者同一個團(tuán)的，即同一個集合。

• 數(shù)組分配一塊連續(xù)的內(nèi)存來存儲。即同一列士兵，在做任務(wù)時，一般都會吃住在同一片區(qū)域。

• 利用元素的索引可以計算出該元素對應(yīng)的存儲地址。士兵每天訓(xùn)練時要進(jìn)行有序的排隊，當(dāng)喊到第幾號士兵時，可以通過這位士兵的回答，得知他的各種信息，例如執(zhí)行任務(wù)期間，住在哪片區(qū)域具體哪個位置。我們從平常計數(shù)報數(shù)都是從 1 開始，而計算機默認(rèn)是從 0 開始，這點要記清楚，以防之后進(jìn)行和數(shù)組相關(guān)的操作產(chǎn)生混亂。

因此我們可知，數(shù)組就如同一列整齊的士兵，他們都是正規(guī)的軍人，他們在隊伍里有指定的位置，且通過叫號，可以知曉他們的訊息。正如軍隊里的士兵存在編號一樣，數(shù)組中的每一個元素也有著自己的下標(biāo)，只不過這個下標(biāo)從 0 開始，一直到數(shù)組長度 -1。

數(shù)組一般用來存儲具有 "一對一" 邏輯關(guān)系數(shù)據(jù)的線性存儲結(jié)構(gòu)，即是在內(nèi)存中順序存儲，因此可以很好地實現(xiàn)邏輯上的順序表。

數(shù)組在內(nèi)存中的順序存儲，具體是什么樣子呢？

內(nèi)存是由一個個連續(xù)的內(nèi)存單元組成的，每一個內(nèi)存單元都有自己的地址。在這些內(nèi)存單元中，有些被其他數(shù)據(jù)占用了，有些是空閑的。數(shù)組中的每一個元素，都存儲在小小的內(nèi)存單元中，并且元素之間緊密排列，既不能打亂元素的存儲順序，也不能跳過某個存儲單元進(jìn)行存儲。

這就像是宿舍分配的床位，每個宿舍有幾個指定的床位，床位號一般都是連續(xù)的，每個床位號對應(yīng)一個學(xué)生，這些學(xué)生可能有人每天都在宿舍住，有的可能搬出去住。床位號都是按順序來的，進(jìn)行安排時也不會考慮跳過哪個號進(jìn)行床位分配。

理論性的介紹先告一段落，單單了解數(shù)組的理論知識還遠(yuǎn)遠(yuǎn)不夠，接下來我們將系統(tǒng)性的介紹數(shù)組在編程中的使用。

數(shù)組的使用

任何數(shù)據(jù)結(jié)構(gòu)的操作基本離不開，增刪改查這四種情況。接下來就讓我給大家介紹數(shù)組的增刪改查怎么實現(xiàn)。

數(shù)組元素的查詢

// 初始化
String[] array = new String[]{'red', 'green', 'blue', 'yellow', 'white', 'black'};
// 通過下標(biāo)進(jìn)行索引
System.out.println(array[0]);
System.out.println(array[1]);
System.out.println(array[2]);

list_array=['red', 'green', 'blue', 'yellow', 'white', 'black']
print( list_array[0] )#red
print( list_array[1] )#green
print( list_array[2] )#blue

對 python 代碼進(jìn)行講解：

我們新建了一個長度為 6 的數(shù)組，并查詢數(shù)組 list_array 下標(biāo)為 0，1，2的元素，并將他們打印出來。

對于數(shù)組來說，讀取元素是最簡單的操作。由于數(shù)組在內(nèi)存中順序存儲，所以只要給出一個數(shù)組下標(biāo)，就可以讀取到對應(yīng)的數(shù)組元素。

例如我們當(dāng)前新建的 list_array 數(shù)組，我們要讀取數(shù)組下標(biāo)為 3 的元素，就寫作 array_list[3]；讀取的元素即為 ?yellow ，讀取數(shù)組下標(biāo)為 5 的元素，就寫作 array_list[5]，讀取的數(shù)組為 black ，需要注意的是，輸入的下標(biāo)必須在數(shù)組的長度范圍之內(nèi)，否則會出現(xiàn)數(shù)組越界。

• tips:

  在 python 中，使用 list 進(jìn)行數(shù)組的新建，然后索引時，它其實是不會報錯的，這也是數(shù)組和列表的一大區(qū)別，其實本質(zhì)還是因為列表類似于動態(tài)數(shù)組，我們在別的編程語言中使用的數(shù)組，明確而言是有指定的長度的， 超越指定的長度時，它會進(jìn)行越界報錯，而動態(tài)數(shù)組的長度是沒有準(zhǔn)確規(guī)定，只要不超出內(nèi)存，即可在數(shù)組末尾一直添加元素，這點是不是和python中的列表很像呢？

數(shù)組元素的更改

String[] array = new String[]{'red', 'green', 'blue', 'yellow', 'white', 'black'};
array[0] = 'orange';

list_array=['red', 'green', 'blue', 'yellow', 'white', 'black']
list_array[0] = 'orange' 

對 python 代碼進(jìn)行講解：

依舊是我們的 list_array ?,現(xiàn)在我想把第一位的紅色變成橘色，那么我們直接使用下標(biāo)索引，找到 'red' ,然后將其賦值為 'orange' 即可。

要把數(shù)組中某一個元素的值改為一個新值，也是非常簡單的操作。我們直接利用下標(biāo)索引到它，然后將其賦值為新的值就可以了。

時間復(fù)雜度分析

• tips:

  關(guān)于時間復(fù)雜度的講解，參考我之前的文章。

數(shù)組元素的插入

數(shù)組元素的插入分為以下幾種：

• 尾部插入
• 中間插入
• 超范圍插入

• 尾部插入

在 java 和 c 語言中，尾部插入是最簡單的方法,我們只需要對數(shù)組進(jìn)行一次循環(huán)找到要插入的位置，然后進(jìn)行賦值即可。

• 中間插入

而進(jìn)行中間的插入時，我們就要考慮這些：

• 確認(rèn)數(shù)組本身是否還有空余的位置。如果沒有空余的位置，那么我們就要進(jìn)行超范圍插入了。如果有空余的位置，我們進(jìn)行下面的操作。
• 挪位置。先為了給這個元素讓出一個位置，這個元素指定的位置之后的元素都要向后移動一個位置，不然的話，是沒有位置留給插入的那個元素的。
• 將元素放進(jìn)騰出的那個位置。原來的元素進(jìn)行挪位操作后，該元素進(jìn)行賦值歸位，這樣元素就插入成功了。
• 數(shù)組長度+1，正因為成功插入了一個元素，所以數(shù)組的長度進(jìn)行了變化。
• 超范圍插入

什么是超范圍插入？比如我定義了一個數(shù)組，長度為 6 ，而從 0 到 5 這6個位置，都有元素，數(shù)組已經(jīng)滿了，但是我們依舊想要向其中插入插入元素，這個時候我們就需要擴(kuò)大數(shù)組的長度了，可是數(shù)組的長度在創(chuàng)建時就已經(jīng)確定了，不是說變就可以輕易的改變的，所以我們通常的操作便是，創(chuàng)建一個新數(shù)組，長度是舊數(shù)組的 2 倍，再把舊數(shù)組中的元素統(tǒng)統(tǒng)復(fù)制過去，這樣就實現(xiàn)了數(shù)組的擴(kuò)容。

以下是 java 代碼實現(xiàn)的，新建一個數(shù)組，對其進(jìn)行插入操作。雖然和我上面說的步驟幾乎是一樣的，但是代碼量可以說是很多了。

private int[] array;
private int size;

public MyArray(int capacity){
    this.array = new int[capacity];
    size = 0;
}

/**
 * 數(shù)組插入元素
 * * index 插入的位置
 * element 插入的元素
 */
public void insert(int index, int element)  {
    //判斷訪問下標(biāo)是否超出范圍
    if(index<0 || index>size){
        System.out.println("超出數(shù)組實際元素范圍！");
    }
    //如果實際元素達(dá)到數(shù)組容量上限，則對數(shù)組進(jìn)行擴(kuò)容
    if(size >= array.length){
        resize();
    }
    //從右向左循環(huán)，將元素逐個向右挪1位
    for(int i=size-1; i>=index; i--){
        array[i+1] = array[i];
    }
    //騰出的位置放入新元素
    array[index] = element;
    size++;
}
/**
* 數(shù)組擴(kuò)容
*/
public void resize(){
    int[] arrayNew = new int[array.length*2];
    //從舊數(shù)組復(fù)制到新數(shù)組
    System.arraycopy(array, 0, arrayNew, 0, array.length);
    array = arrayNew;
}

/**
* 輸出數(shù)組
*/
public void output(){
    for(int i=0; i        System.out.println(array[i]);
    }
}

public static void main(String[] args) {
    MyArray myArray = new MyArray(10);
    myArray.insert(0,7);
    myArray.insert(1,5);
    myArray.insert(2,9);
    myArray.insert(3,8);
    myArray.insert(1,4);
    myArray.output();
}

而在 python 中，我們在現(xiàn)實的使用過程中，無需擔(dān)心自己是否也要像使用 java 那樣，只為處理一個插入操作，就寫了如此多的代碼，我們只要調(diào)用列表自帶的方法就可以了。

• 列表中的 append 方法

列表中的 append 方法，對應(yīng)數(shù)組中的尾部插入，它的底層實現(xiàn)形式類似于上文提到的java中的實現(xiàn)形式。

list_array = ['red', 'green', 'blue']
list_array.append('black')
print ("更新后的列表 : ", list_array) 
#更新后的列表為['red', 'green', 'blue','black']

對 python 代碼進(jìn)行講解：

我們新生成的列表對其直接使用append方法，在其中輸入我們要添加的元素即可，然后我們的元素就被添加到了列表的末尾了。

• 列表中的 insert 方法

列表中的 insert 方法，對應(yīng)數(shù)組中的中間插入，只需要一步調(diào)用方法，即可完成 java 中那么多的判斷以及元素的插入，可見 python 的強大。又因為列表本身可以視為動態(tài)數(shù)組，其實對于長度的要求并沒有數(shù)組那么苛刻，它是可以隨意插入元素的，無需擔(dān)心長度，容量問題。

list_array = ['red', 'green', 'blue']
list_array.insert(0, 'black')
print ('列表插入元素后為 : ', list_array)
#更新后的列表為 ['black', 'red', 'green', 'blue']

對 python 代碼進(jìn)行講解：

對新生成的列表使用 insert 方法，insert 方法有兩個參數(shù)，第一個參數(shù)為，我們要將元素插入到列表的哪個位置，第二個參數(shù)為元素內(nèi)容。該段代碼即為使用 insert 方法將 'black' 插入到列表的頭部。

• 列表中的 extend 方法

列表中的 extend 方法，用于在列表末尾一次性追加另一個序列中的多個值（用新列表擴(kuò)展原來的列表）?？梢砸暈槭菙?shù)組擴(kuò)容的一種特殊情況。

list_array = ['red', 'green', 'blue']
list2=list(range(5)) # 創(chuàng)建 0-4 的列表
list1.extend(list2)  # 擴(kuò)展列表
print ("擴(kuò)展后的列表：", list1)
#擴(kuò)展后的列表：['red', 'green', 'blue', 0, 1, 2, 3, 4]

數(shù)組元素的刪除

數(shù)組的刪除操作和插入操作的過程相反，如果是在數(shù)組的最后刪除元素，那么直接去除元素即可，但是如果是在頭部或者數(shù)組的中間刪除元素，那么其后的元素都需要向前挪動 1 位。

刪除簡單的地方在于，我們無需關(guān)心下標(biāo)是否會越界，容量是肯定不會超過申請的大小的。

public int delete(int index)  {
    //判斷訪問下標(biāo)是否超出范圍
    if(index<0 || index>=size){
        System.out.println("超出數(shù)組實際元素范圍！");
    }
    int deleted= array[index];
    //從左向右循環(huán)，將元素逐個向左挪1位
    for(int i=index; i1; i++){
        array[i] = array[i+1];
    }
    size--;
    return deleted;
}

python 列表中有兩種方法和數(shù)組的刪除操作匹配，即 pop 和 remove 方法。

• 列表中的pop方法

pop() 函數(shù)用于移除列表中的一個元素（默認(rèn)最后一個元素），并且返回該元素的值。

list1 = ['red', 'green', 'blue']
list1.pop()
print ("列表現(xiàn)在為 : ", list1)
#列表現(xiàn)在為 :  ['red', 'green']
list1.pop(1)
print ("列表現(xiàn)在為 : ", list1)
#列表現(xiàn)在為 :  ['red']

對 python 代碼進(jìn)行講解：

新建一個 list1 列表，我們對其使用 pop() ，那么 list1 列表中最后一個元素被移除，這個元素即為 'blue' ，然后繼續(xù)對 list1 使用 pop 操作，此時 list1 中最后一個元素為 'green'，將其移除， list1 中最后只有 'red' 一個元素了。

• 列表中的 remove 方法

remove() 函數(shù)用于移除列表中某個值的第一個匹配項。即當(dāng)列表中有一樣的元素的時候，使用 remove 刪除這個元素， remove 將會刪除下標(biāo)較小的。

list1 = ['red', 'green', 'blue']
list1.remove('red')
print ("列表現(xiàn)在為 : ", list1)
# 列表現(xiàn)在為 :  ['green','blue']
list1.remove('green')
print ("列表現(xiàn)在為 : ", list1)
# 列表現(xiàn)在為 :  ['blue']

# 有重復(fù)元素的情況
list2 = ['red','red','green','blue','blue']
list2.remove('red')
print("列表現(xiàn)在為：",list2)
# 列表現(xiàn)在為：['red', 'green', 'blue', 'blue']
list2.remove('green')
print("列表現(xiàn)在為：",list2)
# 列表現(xiàn)在為：['red', 'blue', 'blue']

對 python 代碼進(jìn)行講解：

新建一個 list2 列表，我們對其使用 remove('red') ，那么 list2 列表中第一個 'red' 將會被移除，然后繼續(xù)對 list2 使用 remove 操作，這次我們移除列表中第一個 'blue' ，打印列表可以發(fā)現(xiàn)，我們原列表中的 0 號位的 'red' 和 3 號位的 'blue' 都被刪掉了，而剩下的 'red' 和 'blue' 沒有被移除。

時間復(fù)雜度分析

數(shù)組的插入，我們首先要考慮數(shù)組的長度和容量，如果容量空余，我們在插入前還要為元素騰出位置，因此我們在此的時間復(fù)雜度 為 ?, 如果元素的容量已滿，我們要擴(kuò)容數(shù)組，那么這個操作的時間復(fù)雜度仍為?，綜合考慮，數(shù)組的插入操作時間復(fù)雜度為? .

數(shù)組的刪除，無需考慮數(shù)組的長度和容量問題，只需要在刪除元素之后，改變其它元素的位置即可，因此數(shù)組的刪除操作消耗的時間在此的時間復(fù)雜度為 ? .

數(shù)組的優(yōu)勢和劣勢

數(shù)組的優(yōu)勢體現(xiàn)在查詢和修改元素上，我們只需要知道元素的數(shù)組下標(biāo)即可對其進(jìn)行查詢和修改，非常的方便。而這種特性也被二分查找法充分的利用了。

數(shù)組的劣勢體現(xiàn)在它的插入操作和刪除操作上，當(dāng)插入一個元素或者刪除一個元素時，其他的元素都需要改變，這極大地影響了程序的運行效率。

總之?dāng)?shù)組適用于，查找，修改較多，插入，刪除較少的場景下。我們下周要講的鏈表則和它的情況相反。

流沙團(tuán)隊聯(lián)合AI悅創(chuàng)|久遠(yuǎn)·推出輔導(dǎo)班啦，包括「Python 語言輔導(dǎo)班、C++ 輔導(dǎo)班、java 輔導(dǎo)班、算法/數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)班、少兒編程、pygame 游戲開發(fā)」，全部都是一對一教學(xué)：一對一輔導(dǎo) + 一對一答疑 + 布置作業(yè) + 項目實踐等。QQ、微信在線，隨時響應(yīng)！