C/C++程序設計實用案例教程（簡體書）

本書精選了大量綜合編程案例，基本上涵蓋了當前基礎算法領域的熱點問題。本書共有8章，分別為字符串，排序和查找，棧、鏈表與隊列，樹與圖，遞歸與分治器，集合與映射，Win32 GUI編程基礎，綜合編程課程設計實例。

前 言
隨著信息技術的迅猛發展，程序設計在各個領域都起到舉足輕重的作用。目前大部分高校的計算機、軟件及相關專業都開設了各種程序設計語言數據結構課程。然而掌握一門程序設計語言或者瞭解數據結構知識並不等同於“會編程”。在實際教學中存在大量的只會考試但不會寫代碼解決問題的學生，這是令人焦慮的現象。
雖然已出版的關於算法設計的書籍比較多，但大都是介紹算法的理論基礎。對於實際生活中的各種問題，需要將算法靈活地應用。本書精選了大量綜合編程案例，基本上涵蓋了當前基礎算法領域的熱點問題。
本書的特色如下。
一、本書提供大量的綜合編程實例，涉及各種基礎算法的應用領域。
二、所有的綜合編程實例都按照設計思路、相關概念、原理、具體實現進行介紹，讀者能夠很容易地掌握實例的算法設計思路。
三、本書介紹了圖形用戶界面(GUI)編程基礎，將4個綜合編程實例的算法進行可視化，從而讓讀者理解並掌握算法可視化方法，進一步幫助對算法的理解與調試。
要運行本書中的絕大部分實例，讀者只需要安裝任何C/C++開發工具，如CodeBlocks、Visual Studio 2015 社區版、Dev C++等。如果要運行4個算法的可視化實例，讀者需要安裝CodeBlocks或Visual Studio 2015社區版。以上工具均可以免費下載。如果讀者的計算機運行的還是VC ++6.0，我們強烈建議您放棄它。因為它的編譯器版本太低，不支持C/C++新標準，並且對模板的支持不夠。
本書共有8章，內容如下。
第1章字符串。主要介紹字符串拷貝、連接、與數的轉換、查找、刪除，以及字典比較等各種字符串操作。其後，給出若干字符串處理常見問題的解決方法。本章最後給出綜合編程實例：公民數據模擬。
第2章排序和查找。主要介紹桶排序、qsort快速排序、STL中std::sort排序、std::greater用法、二分查找算法、std::find用法，並給出兩個綜合實例：員工KPI排名與MOOC期終成績。
第3章棧、鏈表與隊列。主要介紹STL中std::stack、std::list、std::queue與std::deque的用法。對以上數據結構分別給出了若干綜合編程實例，如關於棧的火車調度問題、鏈表的約瑟夫環問題、隊列的卡片遊戲等。
第4章樹與圖。樹的內容主要包括完全二叉樹定義、二叉樹遍歷、手寫二叉樹的遍歷、二叉樹高度計算，以及二叉樹刪除，其後給出4個關於樹的綜合編程實例。圖內容主要包括圖基本操作、圖表示方法，最後給出3個關於圖的綜合編程實例。
第5章遞歸與分治。主要介紹7個典型的遞歸與分治問題：漢諾塔、子串組合、數組組合、格子排列、八皇后、循環賽日程安排與棋盤覆蓋。
第6章集合與映射。主要介紹STL集合容器std::set、映射容器std::map、多鍵映射容器std::multimap，以及哈希映射的用法。同時給出集合相似度與哈希衝突解決的綜合實例，
第7章Win32 GUI編程基礎。主要介紹使用Win32 API開發圖形界面程序的基礎。在實際工程中，算法的過程或者結果通常都需要可視化，一方面可以用來調試程序，另一方面可以用來展示算法效果。因此本章使用CodeBlocks或者Visual Studio2010及以上版本開發圖形界面程序。內容涉及Win32消息基礎和圖形設備接口GDI。同時給出綜合編程實例：簡單多邊形的創建、繪製、平移與旋轉。
第8章介紹4個綜合編程課程設計實例。分別是撲克洗牌、二叉樹重建可視化、L-System分形樹建模，以及迷宮實現。這些實例要求讀者能將算法實現和圖形界面編程進行結合，從而把最終的算法和交互過程展現出來。
本書由丁展、梁穎紅和李廣水主編。在編寫過程中，我們力求精益求精，但難免存在一些不足之處，如果讀者使用本書時遇到問題，可以發送E-mail到dingzh@jit.edu.cn，我們會及時給您回復。

編 者
2018年5月

目 錄


第1章　字符串處理 1
1.1 字符串基本操作 1
1.1.1　字符串拷貝 1
1.1.2 字符串連接 3
1.1.3 反轉字符串 6
1.1.4 大小寫轉換 8
1.1.5 字符串與數的轉換 10
1.1.6 字符串查找 14
1.1.7 刪除字符 16
1.1.8 字符串字典比較 17
1.2　字符串處理常見問題 20
1.2.1 居民身份證號的表示 20
1.2.2 std::string與const char*轉換 21
1.2.3 字符串與buffer緩衝 21
1.2.4 設置浮點數精度 22
1.2.5 得到一行輸入的字符串 23
1.2.6 統計一行文本中單詞個數 24
1.2.7 std::stream的高速緩衝方法 25
1.3 綜合編程實例：公民數據模擬 27
第2章　排序和查找 34
2.1 桶排序（bucket sort） 34
2.2 qsort排序 34
2.2.1 整型數組的qsort 35
2.2.2 浮點型數組的qsort 36
2.2.3 字符型數組的qsort 37
2.2.4 字符串數組的qsort 38
2.2.5 結構類型數組的qsort 40
2.3 std::sort排序 43
2.3.1 std::sort基本用法 44
2.3.2 std::greater基本用法 46
2.3.3 自定義類型排序 46
2.4 二分查找算法 48
2.5 std::find查找 51
2.6 綜合編程實例 52
第3章　棧、鏈表與隊列 64
3.1 棧 64
3.1.1 std::stack 64
3.1.2 綜合編程實例 65
3.2 鏈表 74
3.2.1 std::list 75
3.2.2 綜合編程實例 77
3.3 隊列 80
3.3.1 std::queue 80
3.3.2 std::deque 81
3.3.3 綜合編程實例：卡片遊戲 82
第4章　樹與圖 84
4.1　二叉樹 84
4.1.1 完全二叉樹 84
4.1.2 二叉樹遍歷 85
4.1.3 手寫二叉樹的遍歷 86
4.1.4 二叉樹高度計算 87
4.1.5 二叉樹刪除 88
4.1.6 綜合編程實例 88
4.2 圖 102
4.2.1 圖的基本操作 102
4.2.2 圖的表示方法 102
4.2.3 綜合編程實例 103
第5章　遞歸與分治 112
5.1 漢諾塔 112
5.2 子串組合 113
5.3 數組組合 115
5.4 格子排列 118
5.5 八皇后 122
5.6 循環賽日程安排 124
5.7 棋盤覆蓋 128
第6章　集合與映射 132
6.1　集合 132
6.1.1 std::set 132
6.1.2 集合求交 set_intersection 133
6.1.3 集合求並 set_union 135
6.1.4 集合求差 set_difference 136
6.1.5 綜合編程實例：集合相似度 137
6.2 映射 139
6.2.1 std::map 139
6.2.2 std::multimap 140
6.3 哈希映射 142
6.3.1 常用的哈希函數 142
6.3.2 哈希衝突的處理方法 142
6.3.3 綜合編程實例 143
第7章　Win32 GUI編程基礎 148
7.1 Win32 GUI 148
7.1.1 CodeBlocks第一個Win32教程 148
7.1.2 Visual Studio 2015第一個Win32 GUI程序 150
7.1.3 代碼分析 151
7.2 Win32 消息基礎 155
7.2.1 窗口關閉消息WM_CLOSE 155
7.2.2 窗口大小調整消息 WM_SIZE 156
7.2.3 窗口創建消息 WM_CREATE 157
7.2.4 菜單或其他按鈕消息 WM_COMMAND 158
7.2.5 鼠標消息 159
7.2.6 繪製消息WM_PAINT 160
7.2.7 鍵盤消息WM_KEYDOWN 和 WM_KEYUP 161
7.3 綜合編程實例：簡單多邊形的創建、繪製、平移與旋轉 162
7.4 Win32 圖形設備接口GDI 176
7.4.1 線段和曲線繪製 177
7.4.2 筆、畫刷、填充繪製 180
7.4.3 字體和文本 184
7.4.4 光柵操作 186
7.4.5 雙緩衝機制 188
第8章　綜合編程實例 190
8.1　撲克洗牌 190
8.2 二叉樹重建可視化 194
8.3 L-System分形樹建模 204
8.4 迷宮問題 218
參考文獻 226