C++數(shù)組

「數(shù)組 array」是一種線性數(shù)據(jù)結(jié)構(gòu)，其將相同類型元素存儲在連續(xù)的內(nèi)存空間中。我們將元素在數(shù)組中的位置稱為該元素的「索引 index」。圖 4-1 展示了數(shù)組的主要術(shù)語和概念。

圖 4-1   數(shù)組定義與存儲方式

數(shù)組常用操作

1.   初始化數(shù)組

我們可以根據(jù)需求選用數(shù)組的兩種初始化方式：無初始值、給定初始值。在未指定初始值的情況下，大多數(shù)編程語言會將數(shù)組元素初始化為 0 。

array.cpp

/* 初始化數(shù)組 */
// 存儲在棧上
int arr[5];
int nums[5] { 1, 3, 2, 5, 4 };
// 存儲在堆上（需要手動釋放空間）
int* arr1 = new int[5];
int* nums1 = new int[5] { 1, 3, 2, 5, 4 };

2.   訪問元素

數(shù)組元素被存儲在連續(xù)的內(nèi)存空間中，這意味著計算數(shù)組元素的內(nèi)存地址非常容易。給定數(shù)組內(nèi)存地址（即首元素內(nèi)存地址）和某個元素的索引，我們可以使用圖 4-2 所示的公式計算得到該元素的內(nèi)存地址，從而直接訪問此元素。

圖 4-2   數(shù)組元素的內(nèi)存地址計算

觀察圖 4-2 ，我們發(fā)現(xiàn)數(shù)組首個元素的索引為 0 ，這似乎有些反直覺，因為從 1 開始計數(shù)會更自然。但從地址計算公式的角度看，索引的含義本質(zhì)上是內(nèi)存地址的偏移量。首個元素的地址偏移量是 0 ，因此它的索引為 0 也是合理的。

在數(shù)組中訪問元素是非常高效的，我們可以在 O(1) 時間內(nèi)隨機訪問數(shù)組中的任意一個元素。

array.cpp

/* 隨機訪問元素 */
int randomAccess(int *nums, int size) {
    // 在區(qū)間 [0, size) 中隨機抽取一個數(shù)字
    int randomIndex = rand() % size;
    // 獲取并返回隨機元素
    int randomNum = nums[randomIndex];
    return randomNum;
}

3.   插入元素

數(shù)組元素在內(nèi)存中是“緊挨著的”，它們之間沒有空間再存放任何數(shù)據(jù)。如圖 4-3 所示，如果想要在數(shù)組中間插入一個元素，則需要將該元素之后的所有元素都向后移動一位，之后再把元素賦值給該索引。

圖 4-3   數(shù)組插入元素示例

值得注意的是，由于數(shù)組的長度是固定的，因此插入一個元素必定會導(dǎo)致數(shù)組尾部元素的“丟失”。我們將這個問題的解決方案留在列表章節(jié)中討論。

array.cpp

/* 在數(shù)組的索引 index 處插入元素 num */
void insert(int *nums, int size, int num, int index) {
    // 把索引 index 以及之后的所有元素向后移動一位
    for (int i = size - 1; i > index; i--) {
        nums[i] = nums[i - 1];
    }
    // 將 num 賦給 index 處元素
    nums[index] = num;
}

4.   刪除元素

同理，如圖 4-4 所示，若想要刪除索引 i 處的元素，則需要把索引 i 之后的元素都向前移動一位。

圖 4-4   數(shù)組刪除元素示例

請注意，刪除元素完成后，原先末尾的元素變得“無意義”了，所以我們無須特意去修改它。

array.cpp

/* 刪除索引 index 處元素 */
void remove(int *nums, int size, int index) {
    // 把索引 index 之后的所有元素向前移動一位
    for (int i = index; i < size - 1; i++) {
        nums[i] = nums[i + 1];
    }
}

總的來看，數(shù)組的插入與刪除操作有以下缺點。

• 時間復(fù)雜度高：數(shù)組的插入和刪除的平均時間復(fù)雜度均為 O(n) ，其中 n 為數(shù)組長度。
• 丟失元素：由于數(shù)組的長度不可變，因此在插入元素后，超出數(shù)組長度范圍的元素會丟失。
• 內(nèi)存浪費：我們可以初始化一個比較長的數(shù)組，只用前面一部分，這樣在插入數(shù)據(jù)時，丟失的末尾元素都是“無意義”的，但這樣做也會造成部分內(nèi)存空間的浪費。

5.   遍歷數(shù)組

在大多數(shù)編程語言中，我們既可以通過索引遍歷數(shù)組，也可以直接遍歷獲取數(shù)組中的每個元素。

array.cpp

/* 遍歷數(shù)組 */
void traverse(int *nums, int size) {
    int count = 0;
    // 通過索引遍歷數(shù)組
    for (int i = 0; i < size; i++) {
        count++;
    }
}

6.   查找元素

在數(shù)組中查找指定元素需要遍歷數(shù)組，每輪判斷元素值是否匹配，若匹配則輸出對應(yīng)索引。

因為數(shù)組是線性數(shù)據(jù)結(jié)構(gòu)，所以上述查找操作被稱為“線性查找”。

array.cpp

/* 在數(shù)組中查找指定元素 */
int find(int *nums, int size, int target) {
    for (int i = 0; i < size; i++) {
        if (nums[i] == target)
            return i;
    }
    return -1;
}

7.   擴容數(shù)組

在復(fù)雜的系統(tǒng)環(huán)境中，程序難以保證數(shù)組之后的內(nèi)存空間是可用的，從而無法安全地擴展數(shù)組容量。因此在大多數(shù)編程語言中，數(shù)組的長度是不可變的。

如果我們希望擴容數(shù)組，則需重新建立一個更大的數(shù)組，然后把原數(shù)組元素依次拷貝到新數(shù)組。這是一個 O(n) 的操作，在數(shù)組很大的情況下是非常耗時的。

array.cpp

/* 擴展數(shù)組長度 */
int *extend(int *nums, int size, int enlarge) {
    // 初始化一個擴展長度后的數(shù)組
    int *res = new int[size + enlarge];
    // 將原數(shù)組中的所有元素復(fù)制到新數(shù)組
    for (int i = 0; i < size; i++) {
        res[i] = nums[i];
    }
    // 釋放內(nèi)存
    delete[] nums;
    // 返回擴展后的新數(shù)組
    return res;
}

數(shù)組優(yōu)點與局限性

數(shù)組存儲在連續(xù)的內(nèi)存空間內(nèi)，且元素類型相同。這種做法包含豐富的先驗信息，系統(tǒng)可以利用這些信息來優(yōu)化數(shù)據(jù)結(jié)構(gòu)的操作效率。

• 空間效率高: 數(shù)組為數(shù)據(jù)分配了連續(xù)的內(nèi)存塊，無須額外的結(jié)構(gòu)開銷。
• 支持隨機訪問: 數(shù)組允許在 O(1) 時間內(nèi)訪問任何元素。
• 緩存局部性: 當(dāng)訪問數(shù)組元素時，計算機不僅會加載它，還會緩存其周圍的其他數(shù)據(jù)，從而借助高速緩存來提升后續(xù)操作的執(zhí)行速度。

連續(xù)空間存儲是一把雙刃劍，其存在以下缺點。

• 插入與刪除效率低:當(dāng)數(shù)組中元素較多時，插入與刪除操作需要移動大量的元素。
• 長度不可變: 數(shù)組在初始化后長度就固定了，擴容數(shù)組需要將所有數(shù)據(jù)復(fù)制到新數(shù)組，開銷很大。
• 空間浪費: 如果數(shù)組分配的大小超過了實際所需，那么多余的空間就被浪費了。

數(shù)組典型應(yīng)用

數(shù)組是一種基礎(chǔ)且常見的數(shù)據(jù)結(jié)構(gòu)，既頻繁應(yīng)用在各類算法之中，也可用于實現(xiàn)各種復(fù)雜數(shù)據(jù)結(jié)構(gòu)。

• 隨機訪問：如果我們想要隨機抽取一些樣本，那么可以用數(shù)組存儲，并生成一個隨機序列，根據(jù)索引實現(xiàn)樣本的隨機抽取。
• 排序和搜索：數(shù)組是排序和搜索算法最常用的數(shù)據(jù)結(jié)構(gòu)?？焖倥判?、歸并排序、二分查找等都主要在數(shù)組上進(jìn)行。
• 查找表：當(dāng)我們需要快速查找一個元素或者需要查找一個元素的對應(yīng)關(guān)系時，可以使用數(shù)組作為查找表。假如我們想要實現(xiàn)字符到 ASCII 碼的映射，則可以將字符的 ASCII 碼值作為索引，對應(yīng)的元素存放在數(shù)組中的對應(yīng)位置。
• 機器學(xué)習(xí)：神經(jīng)網(wǎng)絡(luò)中大量使用了向量、矩陣、張量之間的線性代數(shù)運算，這些數(shù)據(jù)都是以數(shù)組的形式構(gòu)建的。數(shù)組是神經(jīng)網(wǎng)絡(luò)編程中最常使用的數(shù)據(jù)結(jié)構(gòu)。
• 數(shù)據(jù)結(jié)構(gòu)實現(xiàn)：數(shù)組可以用于實現(xiàn)棧、隊列、哈希表、堆、圖等數(shù)據(jù)結(jié)構(gòu)。例如，圖的鄰接矩陣表示實際上是一個二維數(shù)組。