C++ 導論 — Introduction Interactive

CONTENTS · 內容目錄

P00為什麼學資料結構？ P01原子型別與變數 P02指標 P03集合型別 P04輸入與輸出 P05控制結構 P06例外處理 P07函式與傳參 P08類別：Fraction P09繼承：邏輯閘 EX練習題 REF總覽與詞彙

PROLOGUE · 開場

演算法、抽象化，還有這門課要帶你去哪 cppds §1.1–1.6

面對一個問題，資訊科學家的目標是寫出演算法：一份一步一步的指令清單，能解決這個問題的任何一個實例。講義給了正式定義，四個條件缺一不可：

① 定義良好

指令是有序的集合，每一步都明確。

② 步驟不含糊

說「把兩個整數相加」，就得先講清楚什麼是整數、什麼是加。

③ 產生結果

回傳資料，或造成某種效果（例如印出東西）。

④ 有限時間內停止

跑不完的程序不算演算法。存在演算法可解的問題，我們說它是「可計算的」（computable）。

資訊科學同時也是研究抽象化的學問。開車不需要懂引擎，你只用方向盤、油門、煞車這組「介面」。寫程式也一樣：#include <cmath> 之後喊一聲 sqrt(16) 就拿到 4，不必知道底層是牛頓法還是查表。這叫程序抽象化。

把同一招用在資料上，就是抽象資料型別（ADT）：只描述資料有哪些操作、行為是什麼，完全不管怎麼實作。使用者摸到的是外殼，實作藏在殼裡面一層，這層包裝叫封裝。而 ADT 的具體實作，就是我們整學期要磨的東西：資料結構。

為什麼值得花一學期？同一個 ADT 通常有好幾種實作，介面一樣、效能天差地遠。第 2 章開始你會看到：同一個問題，一種寫法跑一秒，另一種要跑到天荒地老。學會「評估解法」跟學會「寫出解法」一樣重要。

為什麼用 C++？ C++ 讓你貼著記憶體學：指標、new/delete、值語意，這些被高階語言藏起來的細節全部攤開。課程用 cppds 這本書，程式碼跟著書的風格走（NULL、手刻結構）。

PART 01 · 原子型別

原子型別與變數：每個變數都是一格固定大小的記憶體 cppds §1.8

C++ 要求每個變數先宣告型別才能用。數值型別主要是 int 與 double（後者精度是 float 的兩倍）；算術運算子 + - * / % 都在，次方則要用 <cmath> 的 pow()。先看一段講義的示範：

cout << 2 + 3 * 4;        // 14，先乘除後加減
cout << (2 + 3) * 4;      // 20，括號改變順序
cout << pow(2, 10);       // 1024
cout << 7 / 3;            // 2！整數除法直接截斷
cout << 7.0 / 3;          // 2.33333，有一邊是 double 就是浮點除法
cout << 7 % 3;            // 1，取餘數
cout << pow(2, 100);      // 1.26765e+30：double 近似值，不是精確整數

int 是固定大小的

C++ 的 int 通常 32 位元，上限 2,147,483,647。所以 pow(2, 100) 只能給你 double 近似值。超過上限不會報錯，直接繞回負數，這種溢位是經典 bug 來源。

整數除法

7 / 3 是 2，不是 2.33。兩個 int 相除結果就是 int，往零截斷。想要小數，至少讓一邊是 double。

布林、比較與邏輯運算子

bool 只有 true 和 false 兩個值，搭配 &&（且）、||（或）、!（非）。比較運算的結果也是 bool。整理成一張表：

運算	寫法	說明
大小比較	< > <= >=	結果是 bool
相等／不等	== 　!=	注意 `=` 是賦值，`==` 才是比較
邏輯且／或／非	&& 　\|\| 　!	短路求值：左邊定案就不看右邊

連鎖比較是陷阱 10 < 5 < 3 在 C++ 會編譯、會跑，而且結果是 true：先算 10 < 5 得 0，再算 0 < 3 得 true。想表達區間，乖乖寫 (5 >= 1) && (5 <= 10)。另外 cout 預設把 bool 印成 1/0，想看 true/false 要先插入 boolalpha。

變數是一個「有名字的盒子」

宣告 int the_sum = 0; 時，編譯器保留一塊剛好放得下 int 的記憶體，把 0 直接放進去。之後的賦值都是換掉盒子裡的值。三件事值得慢慢咀嚼：

盒子的型別終身不變。把 true 塞給 int 變數是合法的，但值會被轉成 1，變數還是 int。
識別字（identifier）以字母或底線開頭、大小寫視為不同，保留字（int、class、while）不能拿來當名字。
這叫靜態型別：編譯器在程式跑起來之前就知道每個變數的型別，型別錯誤在編譯期就抓到，跑起來之後不會再有「名字突然變成別種東西」的意外。

QUIZ · 型別與除法

int n = 7; double d = n / 2; 之後 d 的值是？

(A) 3.0

(B) 3.5

QUIZ · 布林運算

cout << (10 < 5 < 3); 印出什麼？

(A) 1

(B) 0

PART 02 · 指標

指標：存位址的變數 cppds §1.8（Pointers）

C++ 把兩種世界都交到你手上：一般變數直接放值，指標是一種放「別的變數的位址」的變數。兩個運算子要熟到變反射動作：& 取位址、* 解參考（沿位址取值）。

程式對照 CODE

int varN = 100;      // 一般變數：住著值
int *ptrN = &varN;    // 指標：住著位址
cout << ptrN;          // 印出位址（如 0x7ffe...）
cout << *ptrN;         // 解參考：沿位址取值，得到 100
*ptrN = 50;            // 透過指標改 varN 本人
ptrN = NULL;           // 指向「無」；解參考 NULL 會當機

為什麼現在就要學指標？

第 4 章的鏈結串列、第 8 章的樹、第 9 章的圖，全部用「節點＋指標」蓋出來。NULL 扮演「這裡沒有東西」的哨兵：解參考 NULL 的下場是 segfault，程式當場倒地。

QUIZ · 讀指標

接上面第 ③ 步之後執行 cout << varN;，印出什麼？

(A) 50

(B) 100

QUIZ · 危險的指標

int *p; cout << *p; 這兩行的問題是？

(A) 解參考未初始化的指標，行為未定義

(B) 語法錯誤

PART 03 · 集合型別

集合型別：vector、string、array、set、map cppds §1.9

有序集合（sequence）有 array、vector、string；無序集合有 set 和 map 家族。這一節的幾張表整學期都會回頭查，值得現在花時間讀熟。

vector：會自己長大的序列

vector 是同型別元素的有序集合，可以動態長大。兩個要點：元素必須同型別；切片這類「取一段」的需求用迭代器範圍表達 vector<double>(v.begin()+1, v.begin()+3) 做出來（取索引 1 到 2，不含 3）。

方法	用法	說明
[ ] / .at(i)	v[i]、v.at(i)	索引從 0 起算；`at()` 有界限檢查、越界丟例外，`[]` 沒有
push_back	v.push_back(x)	加到尾端
pop_back	v.pop_back()	移除最後一項，不回傳值！要值先讀 `v.back()`
insert / erase	v.insert(v.begin()+i, x)	在第 i 格插入／刪除（要搬移後面所有元素）
size / front / back	v.size()	長度、第一項、最後一項
sort / reverse / count / find	sort(v.begin(), v.end())	來自 `<algorithm>`，吃迭代器範圍

string：可變的字元序列

雙引號是 string、單引號是 char，兩者不能混用。串接用 +，長度是 length()。重點： C++ 的字串是可變的，my_name[0] = 'X' 完全合法。

方法	用法	說明
substr	s.substr(pos, len)	從 pos 取 len 個字元的子字串
find	s.find("v")	第一次出現的索引
append / +=	s.append(" Ranum")	接在尾端
insert / erase	s.insert(pos, t)	插入／刪除一段
c_str	s.c_str()	轉成 C 風格字元陣列（printf 會用到）

沒有內建 split()：之後解析輸入時會用 <sstream> 的 stringstream 達到同樣效果。

array：固定大小、零防護

C 語言傳下來的原生陣列 int my_arr[] = {2, 1, 4}; 大小定了就不能改，它完全沒有界限檢查： my_arr[3] 會編譯、會執行、然後靜靜讀出一格垃圾記憶體。附錄 A 的自學頁會深挖它的底層。

set：不重複、自動排序

set<int> s = {3, 6, 4, 6, 3}; 建出來只剩 3、4、6：重複的直接丟掉。成員檢查用 s.count(x)（回 1 或 0），加入 insert、移除 erase。聯集、交集、差集、子集判斷由 <algorithm> 的 set_union、set_intersection、set_difference、includes 提供，搭配 inserter 把結果倒進新容器。

map／unordered_map：key 對應 value

key 對應 value 的查找表。map 內部照 key 排序，unordered_map 用雜湊表（第 2、6 章會分析它們的效能）。走訪時拿到的是 pair，key 是 .first、value 是 .second。

操作	用法	說明
[ ]	m["Iowa"]	取值；key 不存在時會自動插入一個預設值，這是地雷
at	m.at(k)	取值，key 不存在改丟例外
count	m.count(k)	1 表示存在、0 不存在，安全的成員檢查
find	m.find(k) == m.end()	找不到回 end()；這是 C++ 版的「查不到給預設值」慣用法
erase / size / clear	m.erase(k)	刪除、數量、清空

QUIZ · map 的 [] 陷阱

map<string,int> m; cout << m["kent"]; cout << m.size(); 印出什麼？

(A) 0 和 1

(B) 0 和 0

QUIZ · 字串可變性

string s = "David"; s[0] = 'X'; 在 C++ 的結果是？

(A) 合法，s 變成 "Xavid"

(B) 執行期錯誤

PART 04 · 講義補充

輸入與輸出：cin、cout 與格式化講義補充（cppds §1.7 範疇）

cout 寫到標準輸出、cin 從標準輸入讀，都住在 <iostream>。 cin >> radius 有個好用的特性：目標變數的型別決定文字怎麼轉換。讀進 double 就直接轉成數字，不用自己再轉一次型。代價是輸入不合法時 cin 不丟錯誤，而是進入 fail 狀態，之後的讀取全部沉默失敗，除錯時要特別留意。

cout 也跟 print() 不同：沒有自動空格、沒有自動換行，分隔符自己用 << 串、行尾自己加 endl。要控制欄寬和小數位數，用 <iomanip> 的串流操縱子（stream manipulator）：

操縱子	效果	持續性
endl	換行並沖刷緩衝	—
setw(n)	下一個值放進寬度 n 的欄位	只影響下一個值
fixed + setprecision(n)	定點表示、小數點後 n 位	持續有效
left / right	欄位內靠左／靠右	持續有效
setfill(c)	欄位空白改用字元 c 填	持續有效
boolalpha	bool 印成 true/false	持續有效

cout << "The " << setw(10) << item << " costs " ... << price

setw 對齊 setfill setprecision

printf 也還活著

printf("The %10s costs %5.2f\n",
item.c_str(), double(price));

C 傳下來的格式字串，後來很多語言的 % 格式化都是從它抄的。注意 string 要先 c_str()。

QUIZ · setw 的持續性

cout << setw(10) << "a" << "b"; 的輸出是？

(A) 9 個空白、a、緊接著 b

(B) a、b 各佔 10 格

PART 05 · 講義補充

控制結構：迴圈與選擇講義補充（cppds §1.7 範疇）

演算法需要兩種控制結構：迭代與選擇。C++ 的身體是大括號圍出來的，縮排只是給人看的，編譯器完全不管。初學最容易踩的坑：縮排看起來對、大括號漏了，程式的意思就變了。

三種迴圈

寫法	用途
while (counter <= 5) { ... }	條件為真就重複
for (int item : my_list)	range-based for：走訪容器成員
for (int i = 0; i < 10; i++)	計數迴圈，起點、終點、步幅全自訂

計數 for 的三段式讓起點、終點、步幅全部自訂：

for (int i = 5; i < 10; i++)   // i = 5,6,…,9
for (int i = 5; i < 10; i += 2) // i = 5,7,9
for (int i = 10; i > 1; i--)   // i = 10,9,…,2

選擇：if、else if、else

巢狀 if 疊四層看得眼花，慣用寫法是把 else 跟下一個 if 接成 else if。最後的 else 是保底，漏了它，所有條件都不成立時就什麼都不做：

if (score >= 90)      cout << "A";
else if (score >= 80) cout << "B";
else if (score >= 70) cout << "C";
else if (score >= 60) cout << "D";
else                    cout << "F";

list comprehension 的等價寫法

「取 1 到 10 的奇數、各自平方、收進 vector」這類篩選＋轉換需求，C++ 用迴圈與條件組合：

vector<int> sqList;
for (int x = 1; x <= 10; x++) {
    if (x % 2 != 0) sqList.push_back(x * x);
}

之後學到 <algorithm> 的 transform 和 copy_if，會有更接近宣告式的寫法。

QUIZ · 講義練習改編：average 函式

寫 average(a_list)：平均 ≥ 60 印 pass、否則 fail，平均取到小數一位。對 {99,100,74,63,100,100} 應印出？

(A) pass (Average: 89.3)

(B) pass (Average: 89.0)

PART 06 · 講義補充

例外處理：錯誤發生時給程式一條活路講義補充

錯誤分兩種。語法錯誤是句子寫壞了，編譯器直接拒收，程式根本生不出來，這其實是 C++ 對你最溫柔的時刻。邏輯錯誤是程式會跑但答案不對；其中最糟的一類會直接把程式弄死，像除以零、用越界的索引，這種執行期錯誤叫例外。

vector<int> v = {1, 2, 3};
try {
    cout << v.at(10);            // at() 越界會 throw out_of_range
} catch (const out_of_range& e) {
    cout << "Bad index for the vector";
    cout << v.back();            // 改用最後一個元素頂著
}

自己丟例外

if (aNumber < 0)
    throw runtime_error(
      "You can't use a negative number");
else
    cout << sqrt(aNumber);

與其把負數餵給 sqrt 拿到 nan，不如自己檢查、自己 throw，錯誤訊息由你定義。

[] 與 at() 的分工

v[10] 越界是未定義行為，安靜地读垃圾； v.at(10) 越界丟例外，吵但誠實。開發期用 at() 抓 bug，效能關鍵處確定安全後再用 []。

QUIZ · 例外基本功

下列哪個「不會」被 try/catch 接住？

(A) v[10] 的越界存取

(B) v.at(10) 的越界存取

PART 07 · 函式

定義函式與三種傳參方式 cppds §1.10

C++ 函式的定義需要四樣東西：回傳型別、名字、帶型別的參數列、本體，用 return 交回結果。int square(int n) { return n * n; } 就是完整的一課：連回傳值的型別都要先說好。

參數怎麼傳進去，決定函式能不能動到呼叫端的變數。C++ 預設傳值（整份複製），加 & 變傳參考（操作原變數），傳指標則介於中間：複製的是位址。

三種傳法 CODE

int square(int n) { return n * n; }
 
void byValue(int x)  { x = 99; }   // 拿到影本
void byRef(int &x) { x = 99; }   // 拿到本人
void byPtr(int *x) { *x = 99; }  // 拿到位址
int a = 1;
byValue(a);   // a 還是 1
byRef(a);     // a 變 99
byPtr(&a);    // a 變 99

兩個實務慣例

① 大容器用 const vector<int>& v：借看不借改，也省下整包複製。
② C 風格陣列當參數會退化成指標，函式裡改 a[i] 就是改原陣列，而且長度資訊會遺失。vector 沒有這些怪癖。

QUIZ · swap 的正確簽名

要讓 swap2(x, y) 真的交換呼叫端的兩個變數，參數該怎麼宣告？

(A) int &a, int &b

(B) int a, int b

PART 08 · 類別

自訂型別：把 Fraction 一步一步蓋起來 cppds §1.11

浮點數存 1/3 只能存個近似值。想要「精確的分數」，就得自己造型別。講義用五步把 Fraction 從空殼蓋成能加、能比、能印的完整類別，每一步都有理由。

第 1 步：建構子與 private 成員

class Fraction {
    public:
        Fraction(int top, int bottom) { num = top; den = bottom; }
    private:
        int num, den;
};

建構子跟類別同名、沒有回傳型別。物件自己用隱含指標 this 存取，成員直接叫名字就好（要明講也可以寫 this->num）。重點在 private:：C++ 的 private 是編譯器強制執行的，外面寫 a.num 直接編譯錯誤：這不是命名慣例的君子協定，是法律。順帶一提，class 不寫存取修飾詞時，預設全部 private。

第 2 步：建構子多載（多型的第一課）

Fraction(int top, int bottom) { num = top; den = bottom; }  // 3/5
Fraction(int top) { num = top; den = 1; }                   // 整數 5 → 5/1
Fraction() { num = 1; den = 1; }                            // 沒給就是 1/1
// 或者一行解決：Fraction(int top = 0, int bottom = 1)

三個建構子同名不同參數列，編譯器在編譯期依引數的數量與型別挑一個。用預設參數也能做到同一件事，使用者根本分不出來你選了哪種寫法，這正是封裝的意思。

第 3 步：operator<<，讓 cout 認得你

cout << my_fraction 一開始直接編譯失敗。 C++ 不會偷偷退回某種預設表示法幫你混過去，它拒絕猜。解法是多載串流插入運算子，並宣告成 friend，讓它能讀 private 的 num 和 den：

friend ostream& operator<<(ostream& stream, const Fraction& f) {
    stream << f.num << "/" << f.den;
    return stream;   // 回傳 stream 才能繼續串接
}

第 4 步：operator+，加法要順便約分

通分相加：a/b + c/d = (ad + cb)/bd。直接這樣存會愈加愈肥（1/4 + 1/2 = 6/8），所以建構子或加法要用最大公因數約分，6/8 進門就變 3/4。這維護了一條不變量： Fraction 永遠是最簡分數，其他方法都可以放心依賴這件事。

Fraction operator+(Fraction other) {
    int newNum = num * other.den + other.num * den;
    int newDen = den * other.den;
    return Fraction(newNum / gcd(newNum, newDen), newDen / gcd(newNum, newDen));
}

第 5 步：operator==，定義「相等」是什麼意思

沒定義 operator== 之前，f1 == f2 也不能編譯。用交叉相乘 num * other.den == other.num * den，1/2 和 2/4 就會相等，這叫深相等：比的是值，不是「是不是同一個物件」。另外記住 C++ 的值語意：f3 = f1 是把整個物件複製一份，不是多一個名字指向同一個物件。

+ =?

QUIZ · 值語意

Fraction f1(1,2); Fraction f3 = f1; 之後改動 f3，f1 會變嗎？

(A) 不會，f3 是完整的複製品

(B) 會，f3 和 f1 指向同一物件

QUIZ · 講義練習：負分母

講義要求 Fraction(9, -10) 也要能跟其他分數正確比大小。建構子該做什麼？

(A) 分母為負時，分子分母同乘 −1

(B) 丟出例外拒絕負分母

PART 09 · 繼承

繼承與多型：用邏輯閘蓋一座電路 cppds §1.12

vector 是一種循序集合，我們說 vector「是一個」（IS-A）sequence：這就是繼承要表達的關係。子類拿到父類的全部家當，再加上自己的特色。講義用數位電路模擬把這套想法跑一遍，類別階層長這樣：LogicGate →（BinaryGate、UnaryGate）→ （AndGate、OrGate、NotGate）。

A B

AND g1

C D

AND g2

→

OR g3

→

NOT g4

對應程式：AndGate g1, g2; OrGate g3; NotGate g4;
Connector c1(&g1,&g3), c2(&g2,&g3), c3(&g3,&g4); 然後 g4.getOutput()。

這段設計裡的四個關鍵字 virtual ... = 0：純虛擬函式。LogicGate 自己不知道怎麼算邏輯，所以宣告了卻不實作，這讓它成為抽象類別，沒有人能直接 new 一個 LogicGate。
protected：介於 public 與 private 之間，子類碰得到、外人碰不到。label、pin 都放這層。
: LogicGate(n)：初始化列，呼叫父類建構子把 n 交上去。
HAS-A：Connector 不繼承 LogicGate，它「擁有」兩個閘（fromGate、toGate）。 IS-A 用繼承、HAS-A 用成員，分清楚這兩種關係是物件導向設計的第一堂課。

基底與 BinaryGate CODE

class LogicGate {
  public:
    LogicGate(string n) { label = n; }
    int getOutput() { output = performGateLogic(); return output; }
    virtual int performGateLogic() = 0;  // 純虛擬函式
  protected:                        // 子類看得到、外界看不到
    string label;  int output;
};
 
class BinaryGate : public LogicGate {
  public:
    BinaryGate(string n) : LogicGate(n) {  // 初始化列呼叫父類建構子
        pinA = NULL;  pinB = NULL;
    }
    void setNextPin(Connector* source) {
        if (pinA == NULL) pinA = source;
        else if (pinB == NULL) pinB = source;
        else cout << "Cannot Connect: NO EMPTY PINS";
    }
  protected:
    Connector *pinA, *pinB;   // NULL = 這隻腳還空著
};

具體的閘 CODE

class AndGate : public BinaryGate {
  public:
    AndGate(string n) : BinaryGate(n) {}
    int performGateLogic() {
        return (getPinA() == 1 && getPinB() == 1) ? 1 : 0;
    }
};   // OrGate、NotGate 同款，只換這一個函式

Connector CODE

class Connector {        // 不在閘的階層裡：HAS-A
  public:
    Connector(LogicGate* fgate, LogicGate* tgate) {
        fromGate = fgate;  toGate = tgate;
        tgate->setNextPin(this);  // 把自己插上目的閘的腳位
    }
  private:
    LogicGate *fromGate, *toGate;
};

QUIZ · 多型的機關

getOutput() 定義在 LogicGate，卻能執行到 AndGate 的邏輯。靠的是？

(A) virtual：執行期依實際型別挑選 performGateLogic

(B) 編譯器看變數名稱猜的

QUIZ · 抽象類別

LogicGate g("G0"); 這行會怎樣？

(A) 編譯錯誤：抽象類別不能實例化

(B) 可以，但 getOutput 會回傳 0

想逐步看物件、指標與 virtual 派發的過程，可以把 gates 的程式碼貼進 C++ Tutor 跑一遍。

EXERCISES · 練習

綜合練習 cppds §1 綜合

EXERCISE 1 · 溢位

int big = 2147483647; big = big + 1; 之後 big 是？

(A) -2147483648

(B) 2147483648

EXERCISE 2 · pop_back 的回傳值

想取出 vector 最後一個元素並移除它，正確的寫法是？

(A) int x = v.back(); v.pop_back();

(B) int x = v.pop_back();

EXERCISE 3 · 深相等

Fraction x(1,2); Fraction z(2,4); 定義了交叉相乘的 operator== 之後，x == z 是？

(A) true：比的是值，不是物件身分

(B) false：成員不同就不等

EXERCISE 4 · 型別選擇

要記錄「每位學生的成績清單」，讓你能用學號查到該生所有成績，最直接的容器組合是？

(A) map<string, vector<int>>

(B) vector<map<string,int>>

REFERENCE · 總覽

本章地圖與詞彙 cppds §1 總覽

主題	cppds	本頁	之後在哪裡用到
演算法、抽象化、ADT	§1.1–1.6	P00	每一章的開場白
原子型別、變數、運算子	§1.8	P01	附錄 A 的位址計算
指標	§1.8	P02	串列（ch4）、樹（ch8）、圖（ch9）
集合型別五張表	§1.9	P03	vector/map 全書主力
I/O 與格式化	講義補充	P04	之後所有輸出排版
控制結構	講義補充	P05	所有演算法的骨架
例外處理	講義補充	P06	at()、自訂錯誤
函式與傳參	§1.10	P07	所有演算法的簽名
類別、多載、值語意	§1.11	P08	自訂 Stack、Queue、BST
繼承、virtual、HAS-A	§1.12	P09	物件導向設計

關鍵詞彙（講義 Key terms 精選）

抽象與封裝

ADT：只講操作與行為的資料模型。
資料結構：ADT 的具體實作。
封裝：把狀態藏起來，只留公開介面。
介面：元件之間交換資訊的邊界。

語言機制

編譯器：把整份原始碼翻成機器碼，型別錯誤在這關被抓。
指標／& 取址／* 解參考。
namespace：標準函式庫都住在 std 裡。
標頭檔：#include 拉進來的宣告。

錯誤三兄弟

語法錯誤：編譯期被擋。
邏輯錯誤：會跑但答案錯。
例外：執行期被打斷，可 try/catch 接住。

物件導向

建構子：與類別同名、無回傳型別。
多載：同名不同參數列。
覆寫：子類換掉父類的實作。
多型：同一介面、各自表述（virtual）。
深／淺複製：複製內容 vs 複製參考。

C++ 導論：型別、指標與物件