從零開始的演算法競賽入門教學
0%

0-7 陣列

發表於 更新於

陣列

詳細的陣列教學文

當我們要儲存 5 個變數時，要怎麼做呢？

1
int a, b, c, d, e;

我們可能會這樣寫。但，如果今天要儲存 5000 個變數時，要怎麼做呢？

宣告

使用陣列，可以以陣列名稱+位置，儲存大量資料，基本語法如下：

1
2
3
4
int arr[15];
char c[15];
double d[20];
string strs[15];

arr 是這個 int 陣列的名稱，而15則是它的大小。

陣列也可以在宣告時指定值，例如：

1
2
int arr[4] = {1, 4, 2, 3};
cout<<arr[0]<<" "<<arr[3]<<'\n';

輸出：

1
1 3

可以不用指派每一個元素的值，只指派前幾個，不足者會自動補 0。像這樣：

1
2
int arr[4] = {1, 4};
cout<<arr[0]<<" "<<arr[3]<<'\n';

輸出：

1
1 0

但若全部未指定值，則陣列中每個元素的值可能是任何值！

陣列宣告過後，不可改變大小或重新宣告。

取值、修改

如果我們想輸出陣列中位於 3 號的元素的值，這樣寫：

1
cout<<arr[3]<<'\n';

其中，arr是你自己取的陣列名稱，[]是中括號。

要特別注意的一點是，在程式語言的世界裡，編號從 0 開始，因此編號 3 其實是這個陣列的第 4 個值。若宣告大小為 5 的陣列，其可用空間為 0 號到 4 號，若使用 5 號元素會產生不可預期的錯誤！

陣列中的元素就像一般元素一樣，可以加減乘除，可以任意指派值，直接把它當成平常的變數就好：

1
2
3
arr[1] += 15;
arr[3] = arr[2] - 1;
arr[5] = 65;

產生 RE 錯誤

若存取了超過陣列空間的元素，例如：

1
2
3
int arr[5];
arr[-1] += 5; // 不可是負的
arr[5] --; // 陣列大小是 5 的話，可用的編號是 0 ~ 4

有機率產生 Runtime Error 錯誤。

錯誤發生時，其表現與 / 0 時相同，在windows上會當機一小段時間，之後出現非 0 的 return code。

這樣的錯誤不會導致Compile Error，因此很危險。更危險的地方是，這樣的錯誤不一定每一次都會發生，甚至有機率在本地測試時是正確的！

因此，務必特別注意此類錯誤，不要再依賴編譯器了！

競賽中的慣例

陣列放在全域

全域，在這裡先理解為：main函式以外。

全域與它的相反–區域是個重要的概念，之後會有詳細介紹。

如果要宣告陣列，在競賽中我們通常不會這樣寫：

1
2
3
int main(){
    int arr[5];
}

我們會這樣寫：

1
2
3
4
int arr[5];
int main(){

}

為什麼呢？有以下兩個原因

  1. 全域變數會自動初始化為每種型態的預設值，在 int 是 0，在 string 是 “” (空字串)，可避免很多不必要的錯誤。

    • 複習一下，如果宣告在區域又未指定初始值，它的值是不一定的喔！

  2. 在硬體中的儲存位置，導致區域陣列通常只能開到數百萬的大小，但全域陣列可開到數千萬。

    • 區域陣列開太大超出限制的話，會在運行到那一行時產生RE。
    • 全域陣列開太大超出限制的話，在編譯時，編譯器就會將其擋住，無法通過編譯。

因此，在競賽上，我們通常將陣列宣告於全域。

開多大？

在全域變數宣告的缺點，便是無法依據輸入大小調整陣列大小，不能寫像這樣的code：

1
2
3
4
5
int N;
int main(){
    cin>>N;
    int arr[N+5];
}

因為陣列宣告後，是不可改變大小的，因此通常以題目的最大值作為陣列大小。

你說題目沒有給你最大個數限制？那就亂開吧，發生RE的話，就再開大一點。

順帶一提，沒有範圍的題目，99%是爛題。

多維陣列

陣列是可以有多個維度的，例如：

1
2
3
int arr[15][15][15][15];
cin>>arr[1][2][3][4];
cout<<arr[5][3][1][0]<<'\n';

若一個陣列有 n 列 m 行，則其可儲存 n*m 個資料，編號從 [0][0] 、 [0][1] …. [0][m-1] [1][0] … 到 [n-1][m-1]。多維以此類推。

多維陣列用法與相同。要注意，乘起來不可以超過大小限制(約 $10^8$)，不然會 RE / CE。

練習

陣列練習題通常會配合迴圈的使用，以進行讀取或輸出，因此練習題統一置於下一章節。