---
# System prepended metadata

title: '[APCS] 陣列和字串'
tags: [APCS]

---

# [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}
```
![](https://hackmd.io/_uploads/S18xvQD0o.png)

如果你指定一個長度不足的初始值給陣列：
```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$ 個整數的記憶體空間給陣列來使用。

以表格來表示這樣的一個陣列會是這樣子：
![](https://hackmd.io/_uploads/ByiR-wuAj.png)

和一維陣列的時候相同，可以在宣告的同時給予初始值：
```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$ 個二維陣列疊起來的立方體：
![](https://hackmd.io/_uploads/HJdIMK_Co.png)
宣告方式也和二維的狀況相似，例如宣告一個`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是這樣的：
![](https://hackmd.io/_uploads/SJGRUKdRj.png)

而column-major則是這樣：
![](https://hackmd.io/_uploads/BJqALYuRj.png)

可以看出，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]);
```
我們注意到一件事，因為字串陣列屬於靜態記憶體配置，所以宣告的時候必須考慮到裡面字串的最大長度，這樣可能會造成記憶體的浪費。