超圖解C語言：用資料結構×演算法突破APCS

作者：趙英傑
出版社：旗標科技股份有限公司
出版日期：2022.11.25
頁數：688頁（PDF索引檔下載）
定價：NT$780

“C”是一種程式語言的名字，在計算機科學和電機工程領域，C程式設計是必要的基本技能，因為每天都有數十億個微電腦設備，從血壓計、微波爐、交通號誌、個人電腦、無人機到人造衛星，它們大都仰賴採用C或C++語言編寫成的程式和作業系統運作。

有人稱C語言為「程式語言之母」，C不僅廣泛用於各種領域且執行效率高，它的語法也啟發了許多後進的程式語言，甚至某些程式語言本身或部分機能就是用C或C++語言創造出來的，例如：Python, Java, JavaScript, PHP, …等等。

APCS是教育部智慧創新跨域人才培育計畫的一項專案，代表Advanced Placement Computer Science（大學程式設計先修檢測），主要目的是評量學生的程式設計學習狀況。APCS官網指出，APCS成績是數十所大學特殊選才等多元入學管道重要參考依據，其命題內容涵蓋：程式語法和邏輯，以及各種儲存、分析和處理資料的「資料結構」與「演算法」。

工欲善其事，必先利其器－－用料理來比喻，熟悉程式語法，相當於掌握料理的基本功，比方說，知道選用合適的刀具來處理食材。

演算法則是優化處理步驟、讓你事半功倍，乾淨俐落地完成工作或者精進廚藝、提升食材風味的技能。

演算法的問題類似這樣：「用簡單的步驟計算1+2+3+…+N」、「從一堆未整理的數據中找出某一筆資料」或者「探索並紀錄走出迷宮的路徑」。本書以APCS命題方向為藍本，採圖解說明搭配程式演練，涵蓋程式設計入門、資料結構和演算法三大主題，也包含考試不會考，但身為C程式設計師都必須了解的基礎知識，例如，程式編譯指令和檔案處理程式，是全方位的C程式入門教材。有了扎實的C程式語言基礎，加上資料結構與演算法功底，再學習其他程式語言或者閱讀進階書籍就不是難事。

牛頓曾說：「如果我能看得更遠， 那是因為站在巨人的肩膀上。」

前提是，你要找到巨人並設法爬上他的肩膀。在網路上，我們和各方專業達人（巨人）僅僅相隔一片螢幕，各種專業知識信手拈來。然而，許多達人講解的程式設計專業知識，都要有基礎才能吸收理解。本書的目的，就是扮演學習程式設計和演算法的「階梯」，幫助沒有程式設計經驗、對大學電腦科學課程有興趣的讀者打好穩固的根基，進而攀上巨人的肩膀。

跟寫作和數理科目一樣，學習程式設計絕對不能只用看的，必須動手做才能真正學會。以前的程式開發工具需要付費，還要安裝設定才能使用。現在，程式開發工具也上雲端了，只要打開瀏覽器就能直接編寫、測試程式而且免費，只要你有心，隨時隨地都能練習寫程式。

資料結構和演算法也是程式設計人員求職面試的重點，國外的LeetCode.com網羅眾多求職面試的程式設計考古題，是許多有志成為軟體工程師必定造訪、勤加練習（也稱為「刷題」）的網站。網路上有許多達人分享LeetCode和APCS解題技巧，有些人採用C++語言解說。C++比C語言複雜，程式的寫作手法和觀念也不一樣，但是在解決許多「演算法」問題方面，C和C++的程式寫法其實差異不大，所以本書附錄C比較了C和C++的幾個不同點，作為學習C++的入門磚，幫助讀者理解基本的C++程式。

在撰寫本書的過程中，非常感謝旗標科技的黃昕暐先生提供許多專業的看法，例如，他建議在第2章加入「運算子的副作用」單元，並且在他的codemee個人網站撰寫了相關的技術文件，第14章的「把陣列想像成環形」、第16章最後的「雜湊表」和其他幾個範例程式，也經他改寫得更精簡，還有其他糾正內容的錯誤、添加文字讓文章更通順、晚上和假日加班改稿…由衷感謝昕暐先生對本書的貢獻。

目錄

第1章 認識 C 語言、資料結構和演算法

1-1∣認識 C 程式語言
1-2∣C 語言的基本結構和執行流程
1-3∣電腦語言翻譯機：編譯器和直譯器
1-4∣資料結構和演算法
APCS 觀念題練習

第2章 數學運算子、變數與資料型態

2-1∣運算子、變數和常數
2-2∣運算式
APCS 觀念題練習
2-3∣整數和浮點數資料型態
APCS 觀念題練習
2-4∣printf()：合併字串和資料
2-5∣整理程式演算思緒的好幫手：虛擬碼和流程圖
APCS 觀念題練習

第3章 字串、字元編碼與自訂函式

3-1∣確認資料型態大小以及注意事項
3-2∣字元與字串資料型態
APCS 觀念題練習
3-3∣建立自訂函式
3-4∣變數的儲存等級、有效範圍和生命週期
APCS 觀念題練習

第4章 流程控制：選擇 (selection) 與迴圈 (iteration) 敘述

4-1∣讀取鍵盤輸入資料的 scanf() 函式
4-2∣改變程式流程的 if 條件式
4-3∣條件運算子
APCS 觀念題練習
4-4∣switch…case 控制結構
4-5∣努力不懈的迴圈
4-6∣使用輾轉相除法求最大公因數
4-7∣continue 和 break 指令
APCS 觀念題練習
APCS 實作題 購物車（堆積木）

第5章 排列與隨機

5-1∣內容不可改變的「常數」
5-2∣產生隨機數字
5-3∣排列圖案
5-4∣常用的數學函式
5-5∣判斷某數字是否為「阿姆斯壯數」
APCS 觀念題練習
APCS 實作題 辨別三角形

第6章 陣列與字串

6-1∣基本資料結構：陣列
6-2∣處理字串資料
6-3∣文字位移加密（shift cipher）
6-4∣刪除字串裡的空白字元
6-5∣運用 string.h 函式庫處理字串
6-6∣使用 strtok() 函式切割、擷取子字串
6-7∣檢測迴文句子以及變數的有效範圍
6-8∣計算大數據
APCS 觀念題練習
APCS 實作題 修補圍籬 (壽司拼盤)
APCS 實作題 猜拳遊戲（甲蟲爭霸戰）

第7章 遞迴和堆疊

7-1∣遞迴：函式呼叫自己
7-2∣認識「堆疊」記憶體區域和資料結構
7-3∣利用 pythontutor.com 觀察程式運作狀況
7-4∣河內塔問題
APCS 觀念題練習

第8章 指標與多維陣列

8-1∣取址運算子與指標運算子
8-2∣指標與加減運算
8-3∣二維陣列：表格式資料
8-4∣用二維陣列儲存多筆字串資料
8-5∣帕斯卡三角形和二項式係數
APCS 觀念題練習
APCS 實作題 矩陣總和

第9章 前置處理器、標頭檔與程式模組

9-1∣外部 C 程式檔
9-2∣前置處理指令與標頭檔
9-3∣再談 extern（外部）與 static（靜態）儲存等級
9-4∣#define：定義巨集
9-5∣條件編譯
APCS 觀念題練習
APCS 實作題 矩陣轉置

第10章 自訂資料型態

10-1∣列舉型態 enum
10-2∣結構體（struct）
10-3∣結構體陣列
10-4∣在函式中使用結構體
10-5∣讓記憶體空間華麗轉身的 union 自訂型態
10-6∣位元欄位（bit-field）與位元資料操作
10-7∣位元運算子（bitwise operator）與位移運算
10-8∣互斥或（XOR）加密和解密
APCS 觀念題練習
APCS 實作題 邏輯運算子

第11章 演算法、資料排序和搜尋

11-1∣測量執行程式的花費時間
11-2∣評估演算法效率和大 O 符號
11-3∣資料排序
11-4∣氣泡排序原理與實作
11-5∣快速排序原理與實作
11-6∣求取中位數
11-7∣二分搜尋法
APCS 觀念題練習
APCS 實作題 購買力計算
APCS 實作題 成績指標
APCS 實作題 線段覆蓋長度
APCS 實作題 基地台覆蓋問題

第12章 動態配置記憶體與鏈接串列資料結構

12-1∣動態配置記憶體
12-2∣函式中的雙重指標參數
12-3∣鏈結串列資料結構
12-4∣使用區域變數指向串列的開頭
12-5∣在串列的結尾新增節點
12-6∣搜尋鏈接串列的內容
12-7∣刪除節點
APCS 觀念題練習
APCS 實作題 定時 K 彈（約瑟夫問題）

第13章 樹狀結構

13-1∣樹狀結構
APCS 實作題 樹狀圖分析
13-2∣二元樹與平衡二元樹
13-3∣使用鏈接串列建立二元樹
13-4∣走訪與搜尋二元樹的節點資料
13-5∣新增二元樹的節點
13-6∣刪除節點
APCS 觀念題練習
APCS 實作題 自動分裝（旅行團團員分配）

第14章 圖形、佇列、最長距離與最短路徑

14-1∣圖形結構
14-2∣深度優先（DFS）與廣度優先（BFS）走訪
14-3∣佇列（queue）與廣度優先（BFS）走訪
14-4∣用陣列實作佇列
14-5∣廣度優先走訪（BFS）程式實作
APCS 實作題 最長路徑（血緣關係）
14-6∣計算最短路徑：Dijkstra（戴克斯特拉）演算法
APCS 實作題 機器人移動路徑

第15章 動態規劃

15-1∣計算費式數列
15-2∣背包問題
15-3∣找零所需的最少硬幣數量
15-4∣最長共同子序列
APCS 實作題 置物櫃（板凳）出租
APCS 實作題 勇者修練

第16章 回溯法與雜湊表

16-1∣走出迷宮
16-2∣N 皇后問題
APCS 實作題 美麗彩帶（完美序列）
16-3∣可壓縮儲存空間的「雜湊表（Hash Table）」
16-4∣具備碰撞處理機制的雜湊函式
APCS 實作題 完美序列（雜湊版）

附錄A 程式開發工具、GCC 以及 Makefile 編譯命令檔

A-1∣安裝 Code::Blocks 程式開發工具
A-2∣手動編譯 C 程式
A-3∣其他 gcc 命令選項以及 gdb 除錯工具
A-4∣封裝函式庫以及靜態連結函式庫
A-5∣採用 makefile 檔編譯程式
A-6∣在 Mac 電腦上安裝與設置 C 程式開發工具

附錄B 讀寫檔案

B-1∣文字檔和二進位檔
B-2∣操作檔案的函式
B-3∣讀取文字檔
B-4∣寫入文字檔
B-5∣採用 “w+” 讀寫與 “r+” 寫讀模式開啟檔案
B-6∣在文字檔案中新增文字
B-7∣以二進位形式讀寫檔案
B-8∣處理多國語系字串： wchar_t 型態以及語言環境設定

附錄C C++

C-1∣處理標準輸出∕輸入資料流以及命名空間
C-2∣物件導向程式設計（OOP）與 string 字串物件
C-3∣函式簽名、多載以及預設參數值
C-4∣標準樣板程式庫（STL）