Advance C/C++

Table of Contents

1. Sort

排序(Sorting)是將一組資料依照特定的順序重新排列的過程，是程式設計中最基礎也最重要的演算法之一。

1.1. Bubble Sort (氣泡排序)

氣泡排序的概念很簡單：反覆比較相鄰的兩個元素，如果順序不對就交換，就像水中的氣泡一樣，較大的元素會逐漸「浮」到陣列的尾端。

 1: #include <iostream>
 2: using namespace std;
 3: 
 4: int main() {
 5:     int arr[] = {64, 34, 25, 12, 22, 11, 90};
 6:     int n = 7;
 7: 
 8:     // Bubble Sort
 9:     for (int i = 0; i < n - 1; i++) {       // 共需 n-1 輪
10:         for (int j = 0; j < n - 1 - i; j++) { // 每輪少比一次
11:             if (arr[j] > arr[j + 1]) {
12:                 // 交換
13:                 int temp = arr[j];
14:                 arr[j] = arr[j + 1];
15:                 arr[j + 1] = temp;
16:             }
17:         }
18:     }
19: 
20:     cout << "排序結果: ";
21:     for (int i = 0; i < n; i++)
22:         cout << arr[i] << " ";
23:     cout << endl;
24:     return 0;
25: }
  • 時間複雜度：O(n²)
  • 空間複雜度：O(1)

1.2. Selection Sort (選擇排序)

選擇排序的想法是：每一輪從未排序的部分中找出最小值，放到已排序部分的尾端。

 1: #include <iostream>
 2: using namespace std;
 3: 
 4: int main() {
 5:     int arr[] = {64, 25, 12, 22, 11};
 6:     int n = 5;
 7: 
 8:     for (int i = 0; i < n - 1; i++) {
 9:         int minIdx = i;  // 假設目前位置為最小值
10:         for (int j = i + 1; j < n; j++) {
11:             if (arr[j] < arr[minIdx])
12:                 minIdx = j;  // 記錄更小值的位置
13:         }
14:         // 將最小值交換到正確位置
15:         int temp = arr[i];
16:         arr[i] = arr[minIdx];
17:         arr[minIdx] = temp;
18:     }
19: 
20:     cout << "排序結果: ";
21:     for (int i = 0; i < n; i++)
22:         cout << arr[i] << " ";
23:     cout << endl;
24:     return 0;
25: }
  • 時間複雜度：O(n²)
  • 空間複雜度：O(1)

1.3. Insertion Sort (插入排序)

插入排序的概念類似於打撲克牌時整理手牌的方式：從第二張牌開始，將每張牌插入到前面已排序部分的正確位置。

 1: #include <iostream>
 2: using namespace std;
 3: 
 4: int main() {
 5:     int arr[] = {12, 11, 13, 5, 6};
 6:     int n = 5;
 7: 
 8:     for (int i = 1; i < n; i++) {
 9:         int key = arr[i];  // 要插入的元素
10:         int j = i - 1;
11:         // 將比 key 大的元素往後移
12:         while (j >= 0 && arr[j] > key) {
13:             arr[j + 1] = arr[j];
14:             j--;
15:         }
16:         arr[j + 1] = key;  // 插入正確位置
17:     }
18: 
19:     cout << "排序結果: ";
20:     for (int i = 0; i < n; i++)
21:         cout << arr[i] << " ";
22:     cout << endl;
23:     return 0;
24: }
  • 時間複雜度：O(n²)，但對於近乎排序好的資料效率很高
  • 空間複雜度：O(1)

1.4. 三種排序法比較

排序法 最佳 平均 最差 穩定性
Bubble O(n) O(n²) O(n²) 穩定
Selection O(n²) O(n²) O(n²) 不穩定
Insertion O(n) O(n²) O(n²) 穩定

2. String

3. 2D Array

3.1. Array of string

  1. CPP
  2. C
     1: #include <stdio.h>
 2: #include <string.h>
 3: #include <stdlib.h>
 4: int main(int argc, const char * argv[]) {
 5:     // insert code here...
 6:     char  poker[53][5];
 7:     char m[4] = {'A','B','C','D'};
 8:     char tmp[5];
 9:     int i, j, k;
10:     for (i = 0; i < 4; i++) {
11:         for (j = 0; j < 13; j++) {
12:             k = 13 * i + j;
13:             sprintf(tmp, "%d%c", j+1, m[i]);
14:             //printf("%d: %s\n", k, tmp);
15:             strcpy(poker[k], tmp);
16:         }
17:     }
18:     for (i = 0; i < 52; i++) {
19:         printf("%s\n", poker[i]);
20:     }
21: 
22:     return 0;
23: }
24:

4. Variable

4.1. Global v.s. Local

在 C/C++ 中，變數依照宣告的位置不同，可分為全域變數(Global Variable)和區域變數(Local Variable)，兩者的生命週期與可見範圍(scope)截然不同。

  1. Global Variable (全域變數)

    宣告在所有函式之外的變數，程式中任何函式都可以存取。

  2. Local Variable (區域變數)

    宣告在函式或區塊（大括號 {} ）內的變數，只在該區塊內有效。

     1: #include <iostream>
 2: using namespace std;
 3: 
 4: int globalVar = 100;  // 全域變數，所有函式都能存取
 5: 
 6: void showValues() {
 7:     int localVar = 50;  // 區域變數，只在此函式內有效
 8:     cout << "在 showValues() 中：" << endl;
 9:     cout << "  globalVar = " << globalVar << endl;
10:     cout << "  localVar = " << localVar << endl;
11: }
12: 
13: int main() {
14:     int localVar = 200;  // 此 localVar 與 showValues() 中的不同
15: 
16:     cout << "在 main() 中：" << endl;
17:     cout << "  globalVar = " << globalVar << endl;
18:     cout << "  localVar = " << localVar << endl;
19: 
20:     showValues();
21: 
22:     globalVar = 999;  // 修改全域變數
23:     cout << "修改後 globalVar = " << globalVar << endl;
24: 
25:     return 0;
26: }
  3. 注意事項
    • 全域變數若未初始化，預設值為 0；區域變數若未初始化，其值為不確定(garbage value)
    • 當全域變數和區域變數同名時，在函式內會優先使用區域變數（區域變數會遮蔽全域變數）
    • 過度使用全域變數會讓程式難以維護與除錯，應盡量使用區域變數

5. Function

5.2. Recursion

遞迴(Recursion)是指函式在執行過程中呼叫自己本身的技巧。每一個遞迴函式都需要具備兩個要素：

  1. *終止條件(Base Case)*：讓遞迴停止的條件，否則會無窮呼叫導致程式崩潰
  2. *遞迴呼叫(Recursive Case)*：函式呼叫自己，但問題規模必須逐漸縮小
  1. 階乘 (Factorial)

    n! = n × (n-1) × (n-2) × … × 1，例如 5! = 5 × 4 × 3 × 2 × 1 = 120。

     1: #include <iostream>
 2: using namespace std;
 3: 
 4: int factorial(int n) {
 5:     if (n <= 1)       // Base Case：0! = 1, 1! = 1
 6:         return 1;
 7:     return n * factorial(n - 1);  // Recursive Case
 8: }
 9: 
10: int main() {
11:     for (int i = 0; i <= 10; i++)
12:         cout << i << "! = " << factorial(i) << endl;
13:     return 0;
14: }
  2. 費氏數列 (Fibonacci)

    費氏數列的定義為：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)。

     1: #include <iostream>
 2: using namespace std;
 3: 
 4: int fibonacci(int n) {
 5:     if (n == 0) return 0;  // Base Case
 6:     if (n == 1) return 1;  // Base Case
 7:     return fibonacci(n - 1) + fibonacci(n - 2);  // Recursive Case
 8: }
 9: 
10: int main() {
11:     cout << "費氏數列前 15 項：" << endl;
12:     for (int i = 0; i < 15; i++)
13:         cout << "F(" << i << ") = " << fibonacci(i) << endl;
14:     return 0;
15: }
  3. 河乃乃塔 (Tower of Hanoi)

    經典的遞迴問題：將 n 個盤子從 A 柱移動到 C 柱，過程中可借助 B 柱，且大盤不可放在小盤上方。

     1: #include <iostream>
 2: using namespace std;
 3: 
 4: void hanoi(int n, char from, char to, char aux) {
 5:     if (n == 1) {
 6:         cout << "將盤子 1 從 " << from << " 移到 " << to << endl;
 7:         return;
 8:     }
 9:     hanoi(n - 1, from, aux, to);   // 先將上方 n-1 個盤子移到輔助柱
10:     cout << "將盤子 " << n << " 從 " << from << " 移到 " << to << endl;
11:     hanoi(n - 1, aux, to, from);   // 再將 n-1 個盤子從輔助柱移到目標柱
12: }
13: 
14: int main() {
15:     int n = 3;
16:     cout << n << " 個盤子的河乃乃塔步驟：" << endl;
17:     hanoi(n, 'A', 'C', 'B');
18:     return 0;
19: }
  4. 遞迴 vs. 迴圈
    • 遞迴程式碼通常較簡潔易讀，但每次呼叫會佔用 stack 記憶體，層數過深會導致 stack overflow
    • 迴圈效率通常較高，不會有 stack overflow 的問題
    • 許多遞迴問題都可以改寫為迴圈版本

6. 指標Pointer

7. 資料結構

7.1. Array

7.2. Stack

Stack（堆疊）是一種後進先出（LIFO, Last In First Out）的資料結構，就像疊盤子一樣，最後放上去的盤子會最先被拿走。

Stack 的基本操作：

  • *push*：將元素放入堆疊頂端
  • *pop*：移除堆疊頂端的元素
  • *top*：查看堆疊頂端的元素（不移除）
  • *empty*：檢查堆疊是否為空
  1. 用陣列實作 Stack
     1: #include <iostream>
 2: using namespace std;
 3: 
 4: const int MAX_SIZE = 100;
 5: int stack[MAX_SIZE];
 6: int topIdx = -1;  // -1 表示空堆疊
 7: 
 8: void push(int val) {
 9:     if (topIdx >= MAX_SIZE - 1) {
10:         cout << "Stack Overflow!" << endl;
11:         return;
12:     }
13:     stack[++topIdx] = val;
14: }
15: 
16: void pop() {
17:     if (topIdx < 0) {
18:         cout << "Stack Underflow!" << endl;
19:         return;
20:     }
21:     topIdx--;
22: }
23: 
24: int top() {
25:     return stack[topIdx];
26: }
27: 
28: bool empty() {
29:     return topIdx < 0;
30: }
31: 
32: int main() {
33:     push(10);
34:     push(20);
35:     push(30);
36:     cout << "頂端元素: " << top() << endl;  // 30
37: 
38:     pop();
39:     cout << "pop 後頂端元素: " << top() << endl;  // 20
40: 
41:     pop();
42:     pop();
43:     cout << "Stack 是否為空: " << (empty() ? "是" : "否") << endl;
44:     return 0;
45: }
  2. 使用 C++ STL 的 stack
     1: #include <iostream>
 2: #include <stack>
 3: using namespace std;
 4: 
 5: int main() {
 6:     stack<int> s;
 7:     s.push(10);
 8:     s.push(20);
 9:     s.push(30);
10: 
11:     cout << "頂端: " << s.top() << endl;
12:     s.pop();
13:     cout << "pop 後頂端: " << s.top() << endl;
14:     cout << "大小: " << s.size() << endl;
15:     return 0;
16: }
  3. Stack 的應用
    • 括號配對檢查
    • 運算式求值（中序轉後序）
    • 函式呼叫的 call stack
    • 瀏覽器的上一頁功能（Back）

7.3. Queue

Queue（佇列）是一種先進先出（FIFO, First In First Out）的資料結構，就像排隊買東西一樣，先排的人先服務。

Queue 的基本操作：

  • *enqueue（push）*：將元素加入佇列尾端
  • *dequeue（pop）*：移除佇列前端的元素
  • *front*：查看佇列前端的元素
  • *empty*：檢查佇列是否為空
  1. 用陣列實作 Queue
     1: #include <iostream>
 2: using namespace std;
 3: 
 4: const int MAX_SIZE = 100;
 5: int queue[MAX_SIZE];
 6: int frontIdx = 0, rearIdx = 0;
 7: 
 8: void enqueue(int val) {
 9:     if (rearIdx >= MAX_SIZE) {
10:         cout << "Queue 已滿!" << endl;
11:         return;
12:     }
13:     queue[rearIdx++] = val;
14: }
15: 
16: void dequeue() {
17:     if (frontIdx >= rearIdx) {
18:         cout << "Queue 為空!" << endl;
19:         return;
20:     }
21:     frontIdx++;
22: }
23: 
24: int front() {
25:     return queue[frontIdx];
26: }
27: 
28: bool empty() {
29:     return frontIdx >= rearIdx;
30: }
31: 
32: int main() {
33:     enqueue(10);
34:     enqueue(20);
35:     enqueue(30);
36:     cout << "前端元素: " << front() << endl;  // 10
37: 
38:     dequeue();
39:     cout << "dequeue 後前端元素: " << front() << endl;  // 20
40: 
41:     cout << "Queue 是否為空: " << (empty() ? "是" : "否") << endl;
42:     return 0;
43: }
  2. 使用 C++ STL 的 queue
     1: #include <iostream>
 2: #include <queue>
 3: using namespace std;
 4: 
 5: int main() {
 6:     queue<int> q;
 7:     q.push(10);
 8:     q.push(20);
 9:     q.push(30);
10: 
11:     cout << "前端: " << q.front() << endl;
12:     cout << "尾端: " << q.back() << endl;
13:     q.pop();
14:     cout << "pop 後前端: " << q.front() << endl;
15:     cout << "大小: " << q.size() << endl;
16:     return 0;
17: }
  3. Queue 的應用
    • 作業系統的工作排程（CPU scheduling）
    • 印表機列印佇列
    • 廣度優先搜尋（BFS）
    • 訊息傳遞系統

8. 演算法

8.2. 隨機演算法

9. LeeCode

10. Dynamic programming

11. Page Infos

Author: Yung-Chin Yen

Created: 2026-02-22 Sun 14:34