Last Updated on 2021-11-08 by Clay
陣列（Array）是在學習程式語言中第一個會接觸到的資料結構，它是將全部元素（element）儲存在連續記憶體中，並規定每個元素的資料型態必須相同，如此一來才能在記憶體中以固定的偏移量來存取不同的元素。
簡介
所以 Array 中的結構如下：
- 元素（Element）: 每個儲存在陣列中的項目（item）被稱為元素
- 引數（索引）: 每個陣列中的元素都有著一個屬於自己的索引，大部分的陣列都是以 0 為開頭，但也有一部分索引是從 1 開始
在 C++ 中，我們是這樣來宣告一個陣列的。
int array[5] = {1, 2, 3, 4, 5};
int 代表著這個陣列內元素的資料型態，陣列尺寸為 5，後方則是宣告的陣列元素。
基本操作
- 走訪（Travers）
- 插入（Insertion）
- 刪除（Deletion）
- 搜尋（Search）
- 更新（Update）
以下使用 C++ 來作為範例。
走訪（Travers）
走訪很單純，就是使用索引（index）依序訪問陣列中的每個元素。
#include <iostream>
using namespace std;
int main() {
// Init
int array[5] = {1, 2, 3, 4, 5};
// Travers
for (int i=0; i<5; ++i) {
printf("array[%d] = %d\n", i, array[i]);
}
return 0;
}
Output:
array[0] = 1
array[1] = 2
array[2] = 3
array[3] = 4
array[4] = 5插入（Insertion）
在插入前，必須先將插入位置開始的元素全部向右邊移動，以免被錯誤地覆蓋。除此之外，在宣告陣列時，記得要請求比較大的空間。在 C++ 中配置陣列新的記憶體不是做不到，但程式碼就比較長了。
如果真的有這種需要重新配置記憶體的陣列需求，我想不到任何不推薦 vector 的理由。（請參考：[C++] How to Use "vector" of STL）
#include <iostream>
using namespace std;
int main() {
// Init
int array[10] = {1, 2, 3, 4, 5};
int size = 5;
// Before insertion
printf("Before:\n");
for (int i=0; i<size; ++i) {
printf("array[%d] = %d\n", i, array[i]);
}
// Insert k into index 2
int k = 100;
int insertIndex = 2;
int moveIndex = size-1; // We need to move the index "size-1" element to new index
// Insert
while (moveIndex >= insertIndex) {
array[moveIndex+1] = array[moveIndex];
--moveIndex;
}
array[insertIndex] = k;
++size;
// After insertion
printf("\n\nAfter:\n");
for (int i=0; i<size; ++i) {
printf("array=[%d] = %d\n", i, array[i]);
}
return 0;
}
Output:
Before:
array[0] = 1
array[1] = 2
array[2] = 3
array[3] = 4
array[4] = 5
After:
array=[0] = 1
array=[1] = 2
array=[2] = 100
array=[3] = 3
array=[4] = 4
array=[5] = 5刪除（Deletion）
刪除其實就跟插入的反過來的，我們將右邊的元素覆蓋掉左邊的。
#include <iostream>
using namespace std;
int main() {
// Init
int array[10] = {1, 2, 100, 3, 4, 5};
int size = 6;
// Before insertion
printf("Before:\n");
for (int i=0; i<size; ++i) {
printf("array[%d] = %d\n", i, array[i]);
}
// Deletion index 2
int deleteIndex = 2;
int moveIndex = deleteIndex;
// Insert
while (moveIndex < size) {
array[moveIndex] = array[moveIndex+1];
++moveIndex;
}
--size;
// After insertion
printf("\n\nAfter:\n");
for (int i=0; i<size; ++i) {
printf("array=[%d] = %d\n", i, array[i]);
}
return 0;
}
Output:
Before:
array[0] = 1
array[1] = 2
array[2] = 100
array[3] = 3
array[4] = 4
array[5] = 5
After:
array=[0] = 1
array=[1] = 2
array=[2] = 3
array=[3] = 4
array=[4] = 5搜尋（Search）
搜尋其實就是在走訪的過程中，同時判斷當前的元素是否為自己要搜尋的元素。當然如果是一串排序過的數值陣列，你可以使用更快的演算法來搜尋。
不過在這裡就記錄最單純的 O(n) 搜尋。
#include <iostream>
using namespace std;
int main() {
// Init
int array[10] = {1, 2, 3, 4, 5};
int size = 5;
int searchElement = 4;
// Search
for (int i=0; i<size; ++i) {
if (array[i] == searchElement) {
printf("array[%d]: %d hit!\n", i, array[i]);
}
}
return 0;
}
Output:
array[3]: 4 hit!更新（Update）
更新可說是最單純的語法了。
#include <iostream>
using namespace std;
int main() {
// Init
int array[10] = {1, 2, 3, 4, 5};
int size = 5;
// Before
printf("Before:\n");
for (int i=0; i<size; ++i) {
printf("array[%d] = %d\n", i, array[i]);
}
// Update
array[3] = 100;
// After
printf("\nAfter:\n");
for (int i=0; i<size; ++i) {
printf("array[%d] = %d\n", i, array[i]);
}
return 0;
}
Output:
Before:
array[0] = 1
array[1] = 2
array[2] = 3
array[3] = 4
array[4] = 5
After:
array[0] = 1
array[1] = 2
array[2] = 3
array[3] = 100
array[4] = 5以上就是關於陣列（Array）的基本介紹。