# [APCS] 陣列和字串
###### tags: `APCS`
**陣列**（array）是用來儲存一連串相關資料的一種延伸資料型態，可以看成是一組具有相同名稱與型態的資料集合。
另一方面，**字串**（string）可以看成是由字元組成的特殊陣列，但需要遵守一些規範。
本篇將介紹一維和多維陣列，以及字串的用法。
## 陣列
陣列結構使用一排**連續**的可數記憶體，儲存**單一種型態**的資料。
### 一維陣列
若 $a$ 是一個一維陣列，包含有 $n$ 個元素。我們將 $a$ 的第 $i$ 個元素標示為 $a[i]$（從0開始）。我們可以這樣宣告一個一維的陣列：
```cpp=
資料型態 陣列名稱[陣列長度];
```
例如：
```cpp=
double arr[10];
int tmp[12];
float f[5];
```
也可以直接給予初始值，這時就不必指定長度，例如：
```cpp=
int a[] = {5, 2, 7, 8, 11}
```
如果你指定一個長度不足的初始值給陣列：
```cpp=
int a[3] = {1, 2};
```
程式不會報錯，只會把不足的長度補上0；但如果指定一個長度過大的初始值給陣列：
```cpp=
int a[3] = {1, 2, 3, 4, 5};
```
程式就會報錯，跟你說初始值的長度太大了。
假設陣列起始的記憶體位址（也就是陣列的第一個元素的儲存起始記憶體位址）是 $\alpha$，則因為陣列是儲存在連續的記憶體上，且每個元素佔有記憶體的大小相同（因為型態相同），我們可以計算出陣列的第 $i$ 個元素 $a[i]$ 的位址為 $\alpha + i \cdot d$，其中 $d$ 為陣列中一個元素佔有的記憶體大小。
注意陣列無法直接和陣列比較，只有陣列的元素之間可以相互比較。
### 二維陣列
二維陣列可以用來儲存矩陣，使用陣列名稱與兩個索引值來指定存取陣列元素，宣告方式與一維陣列類似：
```cpp=
資料型態 陣列名稱[陣列長度][陣列寬度];
```
例如：
```cpp=
int a[3][4];
```
這邊宣告了 3 列（row）、4 行（column）的陣列，會配置 $3 \times 4 = 12$ 個整數的記憶體空間給陣列來使用。
以表格來表示這樣的一個陣列會是這樣子：
和一維陣列的時候相同，可以在宣告的同時給予初始值：
```cpp=
int a[2][3] = {{1, 2, 4}, {5, 7, 8}};
```
如果想把所有值都初始化為0，也可以這樣寫：
```cpp=
int a[2][3] = {0};
```
但是，對於多維陣列（二維以上），宣告並賦值的時候你只能省略第一維的維度：
```cpp=
int a[][3] = {{1, 2, 4}, {5, 7, 8}}; // 合法
int a[2][] = {{1, 2, 4}, {5, 7, 8}}; // 不合法
int a[][3] = {0}; // 不合法
```
和一維陣列相似，如果指定的個數少於宣告的陣列元素，會把剩餘的位置設為0。
### 多維陣列
多維陣列（二維以上）中最常見是三維陣列，我們先來討論三維陣列。一個 $u_1\times u_2 \times u_3$ 的三維陣列可以看成是由 $u_1$ 層 $u_2 \times u_3$ 個二維陣列疊起來的立方體：
宣告方式也和二維的狀況相似，例如宣告一個`int`型態的三維陣列：
```cpp=
int a[2][3][4];
```
在設定初始值的時候可以想成是初始化 $2$ 個 $3 \times 4$ 的二維陣列：
```cpp=
int a[2][3][4] = {
{{1, 3, 5, 6}, {2, 3, 4, 5}, {4, 5, 6, 7}},
{{6, 2, 7, 8}, {1, 5, 3, 6}, {2, 2, 1, 1}}
};
```
### Row-major 和 column-major
在記憶體中儲存陣列的方式分為row-major（以列為主）以及column-major（以行為主）兩種。
我們先以最簡單的狀況，也就是二維陣列，來說明這兩種儲存方式的差別。
Row-major是這樣的：
而column-major則是這樣：
可以看出，row-major是一個row一個row依序儲存在記憶體中；而column-major則是一個column一個column依序儲存。
對於row-major，假設 $\alpha$ 為元素 $a[0][0]$ 的記憶體起始位址，則 $a[i][j]$ 的記憶體起始位址為：
$$
\alpha + (n_2 \times i + j) \times d
$$ 其中 $n_2$ 為陣列 $a$ 的寬度（陣列尺寸 $n_1 \times n_2$），而 $d$ 為一個元素佔有的記憶體尺寸。
另一方面，對於column-major的情況，$a[i][j]$ 的記憶體起始位址為：
$$
\alpha + (i + n_1 \times j) \times d
$$
對於多維陣列，可能就沒那麼直觀了。我們考慮一個 $u_1 \times u_2 \times u_3$ 的三維陣列 $a$。
Row-major的情形，我們可以把三維陣列 $a$ 視為 $u_1$ 個 $u_2 \times u_3$ 的二維陣列疊在一起，就跟在輸入的時候一樣。把這些二維陣列依序儲存，就構成了row-major在記憶體中的樣子。因此，元素 $a[i][j][k]$ 在記憶體的起始位址是：
$$
\alpha + (u_2 u_3 \times i + u_3 \times j + k ) \times d
$$
另一方面，column-major的情形則和row-major完全相反，我們是把 $a$ 視為 $u_3$ 個 $u_2 \times u_1$ 的二維陣列。因此，元素 $a[i][j][k]$ 在記憶體的起始位址是：
$$
\alpha + (i + u_1 \times j + u_2 u_1\times k ) \times d
$$
### 例題
* 有一個`8x4`的陣列`a`，`a[0][0]`的位址是108，單位元素需要2單位的記憶體大小，則`a[1][2]`在以列為主（row-major）的方式儲存的位址是多少？
:::spoiler 解答
120
:::
* 以下程式輸出為何？
```cpp=
for (int i = 1; i <= 100; i = i + 1){
b[i] = i;
}
a[0] = 0;
for (int i = 1; i <= 100; i = i + 1){
a[i] = b[i] + a[i - 1];
}
printf("%d\n", a[50] - a[30]);
```
:::spoiler 解答
810
:::
* 若 $a$ 是一個 $m \times n$ 的整數陣列，以下程式用來計算每一列的總和，則下列敘述何者正確？
```cpp=
void main(){
int rowsum = 0;
for (int i = 0; i < m; i = i + 1){
for (int j = 0; j < n; j = j + 1){
rowsum = rowsum + a[i][j];
}
printf("The sum of row %d is %d.", i, rowsum);
}
}
```
(A) 第一列總是正確，其他列不一定正確
(B) 會產生執行期錯誤（run-time error）
\(C\) 有語法錯誤
(D) 會正確執行，並印出每一列的總和
:::spoiler 解答
(A)
:::
* 以下程式輸出結果為何？
```cpp=
int main(){
int s[100], a[100];
for (int i = 0; i < 100; i++){
a[i] = 0, s[i] = 0;
}
s[0] = 1;
for (int i = 0; i < 100; i++){
int index = i / 10;
s[i] = s[i] + s[a[index]];
}
printf("%d", s[15]);
}
```
:::spoiler 解答
2
:::
## 字串
前面我們已經學過了字元這種型態。事實上，在 C 和 C++ 裡面並沒有字串這種**基本型態**，那麼字串是怎麼表示的呢？答案是使用特殊的**字元陣列**。這也是我們把字串跟陣列一起講的原因。
字串跟普通的的由字元構成的陣列有什麼不同呢？最大的不同在於字串的結束處會多安排一個位元組的空間來存放`'\0'`字元（空字元，ASCII碼為0）。
在這邊要特別注意：
* `'a'`代表的是一個字元常數，用**單引號**包括起來
* `"a"`代表的是一個字串常數，用**雙引號**包括起來
我們可以用下面兩種方法宣告並初始化一個字串：
```cpp=
// char 字串名稱[字串長度] = 字串初始值;
char a[4] = "abc";
char a[4] = {'a', 'b', 'c', '\0'}
```
使用第二種方法宣告字串時，務必記得結尾的空字元`'\0'`。
雖然`"abc"`只包含有三個字元，但我們給定的長度卻是4，這是因為在計算長度時必須把最後面的空字元`'\0'`也算進去。
我們也可以選擇不給定字串長度，讓編譯器自己安排記憶體空間：
```cpp=
char msg[] = "Hello world!";
```
有一點要特別注意的，就是在 C 和 C++ 裡面我們**不能利用字串變數的名稱把一個字串直接指派給另一個字串**，必須一個元素一個元素複製過去。例如以下就是不合法的指派：
```cpp=
char str1[] = "apple";
char str2[10];
str2 = str1; // 不合法
```
### 字串陣列
當我們想把多個相關的字串儲存在一起，我們可以利用前面學過的二維陣列，宣告並初始化的方式如下：
```cpp=
// char 字串陣列名稱[字串個數][字串最大長度] = 字串陣列初始值;
char fruits[5][11] = {
"apple",
"banana",
"grape",
"watermelon",
"orange"
};
```
當我們想存取第 $i$ 個字串的時候，直接以`fruits[i]`就可以存取了，例如以下程式碼會印出`watermelon`：
```cpp=
printf(fruits[3]);
```
我們注意到一件事，因為字串陣列屬於靜態記憶體配置，所以宣告的時候必須考慮到裡面字串的最大長度，這樣可能會造成記憶體的浪費。
Sign in with Wallet
Connect another wallet