# 第二週課程內容 (2018/09/07)
# 何謂資料結構（data structure）
資料結構即我們==如何保存、放入或拿出資料==的方法。
在資料結構中，我們在意的是存取資料的==操作==。
每種資料結構，會各自有對應的可行操作，
在選擇合適的資料儲存方式時，最優先考慮的便是我們打算對資料進行什麼樣的操作，
以此選擇能夠為這些操作特化的資料結構。
目前我們學過的資料結構，應該只有『陣列』一種。
# 最基本的資料結構：陣列（array）
陣列用以儲存==複數的相同形別資料==，
能做的操作是透過指定 index 取得特定的資料。
可以看成是一個大櫃子，每一格可以存放一個東西，
並且每一格被賦予一個編號，編號為從 0 開始的連續非負整數。
編號稱作索引（index），而每個被存放的東西稱為元素（element）。
例如，透過陣列儲存 5 個整數：3, 7, 5, 6, 4
儲存起來會像這樣子：
| 索引 | 0 | 1 | 2 | 3 | 4 |
| --- | - | - | - | - | - |
| 內容 | 3 | 7 | 5 | 6 | 4 |
## 陣列的宣告
以下為宣告一長度 1024 元素型別 int 的陣列，名為 ary：
```cpp=
int ary[1024]; // 型別 變數名[元素個數];
```
依此類推，宣告 100 個 string 的方式如下：
```cpp=
string ss[100]; // 編號 0 ~ 99
```
注意：由於編號從 0 開始，若我們宣告大小為 k 的陣列，
從 0 開始數 k 個元素的話，最大索引將只會到 k-1。
陣列不能改變大小，所以必須考慮最差情形來宣告。
例如題目最多給 1000 個數字，則宣告時就要考慮至少開 1005 的大小。
:::info
為避免出錯，當需要長度 k 的陣列時，通常會宣告 k+5 ~ k+10 的長度。
:::
## 陣列的宣告位置
:::info
安全起見，陣列最好一律宣告為全域變數。
:::
主因是解題過程，時常需要開相當大的陣列，
可能是數百、甚至上千萬個 int。
能夠宣告在區域變數中的大小，
遠較全域來得小，而且每台電腦未必一致。
同時他會佔用系統 stack 的空間，
會更容易發生遞迴過深等 stack overflow 相關的問題。
這些屬於潛在的、不一定發生且難以預見和判斷的問題，
為了規避不必要的風險，最安穩的方法就是將陣列一律宣告於全域。
此外，==宣告在全域的陣列，每個元素皆會被初始化為 0。==
宣告為==區域變數則沒有這個性質==。
更多細節可以參考 Lys0829 所寫的 [這篇文章](https://hackmd.io/tTAs-GXpQIqGLfIrEkfLRA) 或者 google 相關的關鍵字。
## 陣列的初始化
可以用 {} 在宣告時對陣列進行初始化，例如：
```cpp=
int dx[4] = {0, 1, 0, -1};
```
注意：{} 僅用於初始化，並不能用於對已宣告好的陣列做賦值（assign）的動作，
例如以下是錯誤行為：
```cpp=
int dx[4];
dx = {0, 1, 0, -1}; // compile error!!
```
初始化時未指定的部份，會自動填入 0，例如以下：
```cpp=
int dx[4] = {0};
for (int i=0; i<4; i++)
{
cout << dx[i] << '\n';
}
```
一個常見的誤會是將上述寫法誤解成把每一格都填成 0，這是==錯==的；
雖然真的每格都變成 0，但真正的意思是：==把第一格填成 0，剩下沒填到的補 0==。
差別在：如果你認為以下 code 可以把陣列每一格初始化成 -1 的話。
事實上==並不會==。
```cpp=
int dx[4] = {-1};
for (int i=0; i<4; i++)
{
cout << dx[i] << '\n';
}
```
如果你有正確的認識，你會知道：變成 -1 的只有第一格。
若你對陣列有初始化，你可以略過長度，
則此陣列長度自然會變成你初始化時給的元素個數：
```cpp=
int ary[] = {3, 7, 5, 6, 4};
cout << (sizeof ary) / (sizeof ary[0]) << '\n';
```
sizeof 可以計算變數所佔用的空間大小，單位是位元組（byte）。
陣列佔用空間為：元素個數 x 元素大小
藉由除掉一個元素的大小，可以得出元素個數。
## 取得陣列特定索引的元素
這件事可以透過中括號 [] 做到：
```cpp=
int ary[] = {3, 7, 5, 6, 4};
for (int i=0; i<5; i++)
{
cout << ary[i] << '\n';
}
```
陣列中的每個元素都相當於是一個變數，
一個 int 陣列，每個元素都相當於是一個 int 變數。
平常能對 int 變數做的事，都可以對 int 陣列中的某個元素來做。
例如賦值：
```cpp=
int ary[5];
for (int i=0; i<5; i++)
{
ary[i] = i + 1;
}
```
# 記憶體（memory）與位址（address）
任何變數都有以下三項：
- 名字（name）
- 儲存的值（value）
- 實際在記憶體中所在的位址（address）
名字是讓我們指名變數用的識別代號，
實際上變數是 C++ 向作業系統所要來的一塊記憶體空間，
位址則是此記憶體空間開始的位址，實際上可能佔用多個地址。
而儲存的值，則是這塊記憶體空間中保存的內容。
## 陣列在記憶體中的長相
陣列會是記憶體中一塊==連續的空間==，依序儲存從索引 0 開始的每個元素。
例如一個 int 陣列可能長得如下：
`int ary[5] = {3, 7, 5, 6, 4};`
| 位址 | 100 | 104 | 108 | 112 | 116 |
| -------- | -------- | -------- | -------- | -------- | -------- |
| 索引 | 0 | 1 | 2 | 3 | 4 |
| 值 | 3 | 7 | 5 | 6 | 4 |
可知實際元素位址是由 `起始位址 + 元素索引 * 元素大小` 計算得出。
# 陣列應用
陣列除了可用來保存複數個相同型別的東西外，
也能直接當作表格，來保存、查詢指定整數所代表的值。
例如，以 `tbl[n] = k;` 來儲存二年 n 班修課人數有 k 人。
例如，以 `tbl[n] = k;` 來儲存第 n 個字母，在一篇文章中出現了 k 次。
# 多維陣列（multi-dimension array）
一個 n 維陣列，將會是一個==所有元素皆為 n-1 維陣列==的一維陣列。
宣告時，有 n 維的陣列，就會有 n 組大括號，代表每一維的長度。
例如二維陣列，依上述將會是一個『所有元素皆為 1 維陣列』的一維陣列。
`int tbl[5][3];` 在記憶中的長相如下：
| 索引 | 0 | 1 | 2 | 3 | 4 |
| -------- | -------- | -------- | -------- | -------- | -------- |
| 值 | 陣列0 | 陣列1 | 陣列2 | 陣列3 | 陣列4 |
每一個元素是一個 int 的一維陣列，所以長得如下（值我隨便填的）：
| 索引 | 0 | 1 | 2 |
| -------- | -------- | -------- | -------- |
| 值 | 4 | 1 | 6 |
實際上 `tbl[i][j]` 代表存取第 i 個元素（它是一個長度 3 的陣列）中的第 j 個元素。
展開會長得像這樣：
| tbl索引（i）↓ | tbl[i]索引（j）→ | 0 | 1 | 2 |
| -------- | -------- | -------- | -------- | -------- |
| 0 | tbl[0] | 4 | 1 | 6 |
| 1 | tbl[1] | 4 | 1 | 6 |
| 2 | tbl[2] | 4 | 1 | 6 |
| 3 | tbl[3] | 4 | 1 | 6 |
| 4 | tbl[4] | 4 | 1 | 6 |
二維陣列當作一維陣列來看待的話，就很容易理解 `tbl[i]` 是什麼意思。
它是這個陣列中，索引 i 的元素，型別是一維陣列。
`tbl[i][j]` 由此來理解，就是 `tbl[i]` 這個陣列中，索引 j 的元素：
`(tbl[i])[j]`
更高維的陣列依此遞迴規則類推即可。
## 二維陣列的初始化
在此只提較常用的二維，三維或更高維的初始化可依此類推。
上面提過一維陣列的初始化，與此同理：
```cpp=
int tbl[5][3] = { // 5 個元素，以 , 隔開
{4, 1, 6}, // 每個元素 tbl[i] 亦是一個陣列，同樣用 {} 初始化
{4, 2, 6}, // tbl[1]
{5, 1, 2}, // tbl[2]
{2, 5, 6}, // tbl[3]
{1, 2, 8} // tbl[4]
};
```
## 座標系 (x, y) vs 表格的橫列 (row) 直排 (column)
由於英文的書寫習慣上，是先左到右，再上到下。
陣列在記憶體中的長相，也更接近如此。
在第 r 橫列的第 c 直排上，通常會表達作 `tbl[r][c]`。
然而，座標系卻習慣先寫 x 再寫 y，
座標系上的 x 相當於直排（x=1 是上下延伸的直線），
y 相當於橫列（y=1 是左右延伸的直線），
和上述的先橫列再直排是相反的，在使用上要十分注意不要搞混。
建議大部份情形，如果迴圈這樣寫：
```cpp=
for (int i=0; i<n; i++)
{
for (int j=0; j<m; j++)
{
cin >> ary[i][j];
}
}
```
可知 i 在第一維、j 在第二維，剛好按照英文書寫的順序。
這個順序基於 C++ 的一些優化，會是最快速的。
若將第一維、第二維的順序反過來，變成先上到下，再左到右，效能會差很多。
# 指標（pointer） - 儲存『位址』的變數
指標是一種特殊的變數，不過本質還是變數，因此同樣具有以下三個要素：
- 名字
- 值
- 位址
只是它的『值』的實際意義會是一個『位址』。
當一個指標 p 儲存的『值』相等於另一個變數 a 的『位址』，
或者說指標 p 儲存著另一個變數 a 的『位址』時，
我們說==指標 p 指向變數 a==。
## 指標的宣告
指標的宣告方式為：指向對象的型別 *變數名字;
例如指向 int 的指標：
```cpp=
int *p;
```
此時 p 的型別為 int\*
但我們通常不以 `int* p;` 來宣告，原因如下：
```cpp=
int* p, q;
```
在這個宣告下，p 的型別為 int\*，q 的型別為 int。
也就是說實際上意思較接近是：
```cpp=
int *p, q;
```
這個很好驗證，只要宣告一個肯定跟指標不同大小的型別便知：
```cpp=
char *p, q;
cout << sizeof(p) << " <> " << sizeof(q) << '\n';
```
附帶一提，指標所佔用的空間大小依系統而定，
在 32 位元系統下佔 32 位元（4 位元組），
在 64 位元系統下佔 64 位元（8 位元組）。
這也是為什麼需要 64 位元系統的原因：
32 位元（4 位元組）只能表達 4294967296 種不同的東西，
這意味著位址的可能性只有 4 * 10^9 種，約是 4GB 大小。
要讓記憶體擴充至 4GB 以上，就需要更多空間來存位址。
## 取址 && 指向
如果用過 scanf() 想必對於 & 這個『取址運算子』十分熟悉。
在變數名前加上 & 可取得該變數的位址：
```cpp=
int a;
cout << &a << '\n';
```
由於指標儲存的『值』就是『位址』的意思，
因此將變數取址得出的『位址』存到指標的『值』中，就相當於是讓指標指向該變數：
```cpp=
int a, *p;
p = &a;
```
## 取值
在指標前加上 * 可存取指標所儲存位址的內容，
例如讓指標 p 指向變數 a 的位址，
則 \*p 相當於存取變數 a 所在位址，
此時 \*p 等價於 a。
```cpp=
int a = 5;
int *p = &a;
*p = 16;
cout << &a << ": " << a << '\n';
cout << p << ": " << *p << '\n';
```
# 指標與陣列
陣列本身其實也是一種指標，
只是一來它的值（指向的位址）不能夠被更動，並且會指向自己；
二來它會要來一大塊的空間來存放他的元素們。
```cpp=
int a[5];
cout << a << " : " << &a << '\n';
```
如此一來，陣列便不需要額外要一塊空間，來儲存『元素們所在的位址』，
同時自己可以當作指標（值是位址）來用。
## 指向陣列的指標
由於陣列本身的值就是陣列自身的位址，因此以下兩種寫法都一樣：
```cpp=
int ary[5];
int *p;
p = ary;
p = &ary;
```
## 指標的加法
指標的加法代表意義是：前進多少個單位。
因此，指向 int 的指標 p，
`p+1` 代表的是指標 p 指向的位址，再前進一個 int 的位址。
```cpp=
int ary[5], *p;
p = ary;
cout << (p+1) << " : " << &ary[1] << '\n';
```
由於前進的是一個 int 的位址，實際位址是前進了 4，
因為位址的單位是 byte，而 int 佔用 4 byte。
同理，若是 char 指標，則實際會前進 1 byte；
long long 指標則會前進 8 byte。
## [] 的真意
從上可知，`&ary[i]` 其實等價於 `ary+i`；
而 `ary[i]` 等價於 `*(ary+i)`。
它只是一種為了方便的縮寫而已。
這也表示 [] 其實是指標用的，而不只是陣列的專利：
```cpp=
int ary[5] = {3, 7, 5, 6, 4}, *p;
p = ary;
cout << p[1] << '\n';
p[2] = 16;
cout << *(p+2) << '\n';
```
更甚者，a[b] 運算其實是 *(a+b) 的關係，我們甚至可以這麼寫：
```cpp=
int ary[5] = {3, 7, 5, 6, 4}, *p;
p = ary;
cout << 1[p] << '\n';
*(p+2+1) = 16;
cout << (2+1)[ary] << '\n';
```
## 指標的減法
指標減去一個整數，等同於加上該整數的變號。
例如 p-5 等價於 p+(-5)，意義上是往後移 -5 格，相當於往前移 5 格的意思。
兩個指標相減則代表它們之間的距離差了幾格，
例如兩個 `int*` 相減，就代表這兩個位址差了多少個 int。
如果 `p+5 == ary` 則 `ary-p == 5`，這樣的感覺。
## 指向虛無（void）型別的指標
`void*` 型別可以指向任何型別的東西。
但因為它自身不代表任何型別，所以不能做取值 \* 的運算。
函數某些時候會需要它來吃不特定型別的參數，
比如說排序用的 qsort() 就需要它來吃不特定型別的陣列，
以便對應任何型別的陣列。
## 不指向任何位址的指標
我們以指向 `NULL` （其值相當於 0），
來代表一個指標其實並沒有被指向任何一個地方。
NULL（0）這個位址是特別的，是系統保留用的，平常無法使用。
# 指標的應用 - 鏈結串列（linked list）
鏈結串列和陣列同樣是儲存多個相同類型的元素使用。
由於陣列在刪去特定元素、或加入特定元素時，會需要大量的資料改動；
例如將陣列 {3, 7, 5, 6, 4} 刪去元素索引 2：
| 索引 | 0 | 1 | 2 | 3 | 4 |
| -------- | -------- | -------- | -------- | -------- | -------- |
| 值 | 3 | 7 | ~~5~~ | 6 | 4 |
變成：
| 索引 | 0 | 1 | 2 | 3 | 4 |
| -------- | -------- | -------- | -------- | -------- | -------- |
| 值 | 3 | 7 | 6 | 4 |
在索引 2 之後每個元素都要往前搬移，同理將元素 8 插入至索引 2，
則需要將索引 2 之後每個元素往後搬移：
| 索引 | 0 | 1 | 2 | 3 | 4 | 5 |
| -------- | -------- | -------- | -------- | -------- | -------- | -------- |
| 值 | 3 | 7 | 5 | 6 | 4 |
變成：
| 索引 | 0 | 1 | 2 | 3 | 4 | 5 |
| -------- | -------- | -------- | -------- | -------- | -------- | -------- |
| 值 | 3 | 7 | 8 | 5 | 6 | 4 |
若陣列有 n 個元素，則插入和刪除最多需要搬動 n 個元素，
需要的計算量十分可觀。
## 鏈結串列的原理
鏈結串列不需要連續的記憶體，每個元素可打散到記憶體中不同位址，
每個元素會記得他的下一個元素的位址，因此只要記住第一個元素，
就可以一路找到下一個元素，直到最後一個為止。
最後一個元素通常會被指向 NULL，表示後面已經沒有東西了。
儘管在找第 i 個元素時相當慢，需要一路問 i 次，
但在刪除和插入卻相當快。
例如上圖，要刪去 5 的時候，
只需將 5 的上一個（也就是 7），指向 5 的下一個（也就是 6），
5 就消失在這一串鏈結串列中了。
下圖藍色代表更動的部份：
從 3 出發只會找到 3, 7, 6, 4 而不會走到 5 去，刪除成功。
插入同理，只需將要插入的 8 指向它的上一個（7）的下一位（5），
再把它的上一個（7）指向自己（8），如下圖藍色部份：
如此從 3 出發尋訪時，會依序找到 3, 7, 8, 5, 6, 4，插入成功。
從此可發現，插入與刪除都無須做大量的資料搬移。
## 實作面
我們會需要在一個元素中儲存我們要的值，以及一個指向下一個元素的指標。
用 struct 可以將任意相異的變數，包成一個新的型別：
```cpp=
struct node
{
int value;
node *next;
};
```
上述的 code 可以打造出一個新的名為 node 的型別，
其包含兩個變數：value（int）以及 next（node\*）
則從此可以宣告 node 型別的變數，使用 . 來存取 node 型別裡宣告的變數：
```cpp=
node ele, eve;
ele.value = 16;
ele.next = &eve;
eve.value = 32;
eve.next = NULL;
for (node *ptr=&ele; ptr!=NULL; ptr=(*ptr).next)
{
cout << (*ptr).value << '\n';
}
```
如此便成功串成了長度為 2 的鏈結串列：{16, 32}
由於每次要寫 `(*ptr).value` 實在太麻煩，C++ 同樣提供了等價的縮寫：
`ptr->value`
因此，上述 code 可寫成如下：
```cpp=
node ele, eve;
ele.value = 16;
ele.next = &eve;
eve.value = 32;
eve.next = NULL;
for (node *ptr=&ele; ptr!=NULL; ptr=ptr->next)
{
cout << ptr->value << '\n';
}
```
## 創造足夠多的 node 來串成鏈結串列
通常的做法是：需要插入新元素時，new 一個新的 node 型別實體出來，
但比賽使用 new 效能不佳，也通常沒有必要。
這裡我們提競賽用的做法，new 的做法作為額外參考，有興趣者自行參考。
競賽中通常我們會知道最差情況，要串幾個元素，因此可做預先宣告：
```cpp=
node pool[10000005];
```
用一個指標指向 pool 中下一個可用的元素，每一組測資重置：
```cpp=
node *pptr = pool;
```
每次要一個新東西時：
```cpp=
node *next = pptr++;
```
`pptr++` 會得出 pptr 原本的值，但在這之後 pptr 的值會被 += 1，
next 則會指向新的可用的 node。
# 額外內容：即時創造新的實體
使用 new 可在執行階段動態向系統要一塊新的記憶體空間，
而非在編譯時期決定要多少記憶體：
```cpp=
node *next = new node;
```
不過要來的記憶體，在你 delete 它之前是不會不見的。
new 需要時間，delete 需要時間，而且比起你直接要一整塊大塊的，
分成一塊塊每次 new 是更花費時間的。
每組測資重新 new 起，也很容易不小心用到超出記憶體限制。
只考慮競賽的話是十分不推薦的方法。
# 額外內容：函數的傳值、傳址、傳參考
一般函數呼叫時，會將傳遞的參數直接複製一份傳進去（call by value），
這時函數內不管如何改動，對原本的變數而言只是塗改被複製出來的一份罷了。
在 C 中，需要在函數中變更變數的值時，則需要將位址傳進去（call by address），
這時函數內可透過 address 更改到目標變數的值。
在 C++ 則追加了能對參數宣告為參考（call by reference），
例如將參數宣告為 int &a 則 a 會參照至傳遞進來的變數，
也就是讓 a 實際的位址相等於傳遞的變數。
```cpp=
void f(int p, int *q, int &r)
{
p = 6;
*q = 8;
r = 9;
cout << "p: " << p << ", " << &p << '\n';
cout << "q: " << *q << ", " << q << '\n';
cout << "r: " << r << ", " << &r << '\n';
}
int main()
{
int a = 2, b = 3, c = 5;
cout << "a: " << &a << ", b: " << &b << ", c: " << &c << '\n';
f(a, &b, c);
cout << "a: " << a << ", b: " << b << ", c: " << c << '\n';
return 0;
}
```
從以上測試可發現：p 和 a 毫無瓜葛，b 的位址被複製進 q，
而 c 和 r 雖不同名，取址卻會得到完全相同的位址。
簡單地說，call by value 就是東西讓你抄一份拿去用；
call by address 告訴你我把東西放在哪裡，但不直接給你那個東西；
call by reference 就是直接把原本的東西拿給你。
# 額外內容：指標的指標
既然指標也是變數，也有位址來存一個值，
那麼就可以用指標指向它。
一個指向 `(int*)` 型別的指標，照前面的規則應是要再加上一個 \* 成為：
`int **pp;`
則其取值後的型別為 `int*`，仍是指標。
依此邏輯將指標 `int*` 看成一個大型別，
一層一層剝開就可以較不混亂地去理解指標的指標。
一般而言競賽不至於用到指標的指標，並不是那麼地重要。
# 額外內容：可變長度二（多）維陣列
直接宣告二維陣列時，由於是看成每個元素皆為一維陣列，
陣列中每個元素會相同，因此長度其實會完全一致。
若希望有個陣列的陣列，
每條陣列不一樣長，那就會變得麻煩一些：
考慮每條陣列需要一個位址，因此會是一個指標 int\*；
我們需要很多條陣列，所以需要很多個 int\*。
很多個指標就是指標的陣列：
```cpp=
int *pary[64];
for (int i=0; i<64; i++)
{
pary[i] = new int[i+1];
}
```
這樣第 i 條陣列就有 i+1 的長度，實現了並不是很整齊的二維陣列。
同理，如果連有幾條陣列都動態宣告的話，
由於每個元素 pary[i] 都將是 int\* 型態，
而型態 T 的陣列，可以 T\* 來動態配置，
例如將 T 置換成 int：
```cpp=
int *ary = new int[128];
```
那如果每個元素都是 int\* 型態的話，就將 T 換成 int\*，
很自然地得到 int** 型態：
```cpp=
int n = 64;
int **pary = new int*[n];
for (int i=0; i<n; i++)
{
pary[i] = new int[n+i];
}
```
:::info
困擾時，將型別用 T 代換掉，用 T 去思考該怎麼做，
最後再換回目標型別，邏輯就會很清楚
:::
或者我們可以善用 typedef 將型別賦予別名：
```cpp=
typedef int* T; // 賦予 int* 新的別名：T
int n = 64;
T* pary = new T[n];
for (int i=0; i<n; i++)
{
pary[i] = new int[n+i];
}
```
這樣整體邏輯也會十分清楚，
把 T 換成更好懂的名稱（ARY 之類的）會再更清楚。
多維陣列依此類推。
# 額外內容：二（多）維陣列的指標
整齊的二維陣列，其實是可以透過每個元素的長度，
當作一條一維陣列看待的；
但是在上面整理出來的 int\*\* 卻不包含這些資訊。
對 int\*\* 而言，每個元素就是 int\* 這麼大而已。
假設有個二維陣列 `int tbl[8][7];` 那麼每個元素大小應為 `sizeof(int) * 7`
而不是 `sizeof(int*)`
而每個元素大小為 `sizeof(int) * 7` 的指標，可以被這麼宣告：
```cpp=
int tbl[8][7];
int (*ptbl)[7];
ptbl = tbl;
```
多維陣列依此類推。
# 額外內容：函數的指標
函數實際上在 C++ 中，也是擁有位址的，
因此也可以用指標來指向，只要需求參數相同。
這實質上主要是在 C 刻大型程式比較會用上，
例如將「攻擊」這個動作用「函數指標」型態的變數來存，
這樣要把主角的攻擊從「揮劍」改為「詠唱火球術」時，
只需將「攻擊」指標從指向「揮劍」改為指向「詠唱火球術」即可完成，
而呼叫時同樣只需要 `main_chara.attack();` 不需要改變呼叫的函數。
其它可以用在像是，對於「NPC」的移動AI，用函數指標來儲存，
這樣對不同 NPC 只要指向不同函數，就可以用同樣變數來應對不同移動方式。
寫法如下：
```cpp=
int wood_sword(int str)
{
return str;
}
int excalibur(int str)
{
return str * str;
}
int main()
{
int (*attack)(int str); // 宣告一回傳值為 int 參數列 (int) 的函數指標 attack
attack = wood_sword;
cout << attack(5) << '\n';
attack = excalibur;
cout << attack(5) << '\n';
return 0;
}
```
只要回傳值型別相同、參數列也相同（順序相同、型別相同、個數相同，參數名不重要且可省略），
都可以指。
函數指標一樣用 () 把參數傳進去就能呼叫。
# 作業
這次作業以熟悉陣列與其運用為主，但開始摻雜其它題型。
畢竟真正考 APCS 時，題型是要讀完題目後自行判斷的。
指標由於很難找到單純的題目，畢竟它能做的事有太多替代案，
指標相關以鏈結串列的練習為主。
:::info
注意：題目未按難易或上課提及之順序排列。卡住時建議先看後面題目。
:::
[SkyOJ 連結](http://sky.tfcis.org/rank.php?mod=commonboard&id=61)
- UVa 245
- UVa 350
- UVa 484
- UVa 10010
- UVa 10500
- UVa 11192
- UVa 11946
- UVa 11988
- UVa 12195
- UVa 12650
## 建議
面對複雜的題目時，特別是==資料結構==時，
需要先判斷我們==想要儲存的資料長什麼樣子==，
以及==存取時有什麼特性==，
再根據這些特性來尋找或思考合適的方法。
在實作變得複雜時，事先想好==整體流程==，
再將流程==拆成一個個的步驟==，分開完成。
這樣每次只需考慮一個步驟，會比考慮如何實作一個完成的大問題來得容易。
想好流程再動手，動手時再針對目前步驟去想細節。
『總之先寫再說』的話流程容易亂、步驟間分工不明確；
動手之前先規劃細節，很可能因經驗不足想得不完整，以致難以實行，
甚至卡在思考無法進展。細節可以一邊嘗試、實驗，一邊修飾。
:::danger
寫百行程式碼的難度，絕不只是五十行的兩倍。
:::
如果拆了還是太難，就把步驟當成大問題再往下分析流程、拆成小步驟。
## 給資訊社競賽組的作業
:::warning
非資訊社競賽組的同學們可以無視這部份。
當然也歡迎挑戰，雖然可能會十分吃力，
並且可能會需要你們完全沒學過的技能與知識。
:::
這次會集中在遞迴、排序、或者基本資料結構上。
雖然有主題，但還是需要自行判斷一下題型，以及小心是否有例外。
:::info
注意：有些題目在 Lucky 貓仍未有翻譯，
若有閱讀上的困難可以拿去社團求助。
:::
[SkyOJ 連結](http://sky.tfcis.org/rank.php?mod=commonboard&id=62)
- UVa 10324
- UVa 110
- UVa 196
- UVa 198
- UVa 536
- UVa 640
- UVa 727
- UVa 10017
- UVa 10858
- UVa 11351
- UVa 10063
- UVa 271
###### tags: `APCS2018上`
Sign in with Wallet
Connect another wallet