C/C++常用算法手冊（第4版）

第1 章　算法概述
1.1 什么是算法 ........................................................................................................1
1.2 算法的發(fā)展歷史和分類 ....................................................................................2
1.3 算法與相關(guān)概念的區(qū)別 ....................................................................................3
1.3.1 算法和公式的關(guān)系 .............................................................................................4
1.3.2 算法與程序的關(guān)系 .............................................................................................4
1.3.3 算法與數(shù)據(jù)結(jié)構(gòu)的關(guān)系 .....................................................................................4
1.4 算法是計算機科學(xué)的靈魂 ................................................................................5
1.5 算法的表示 ........................................................................................................6
1.5.1 自然語言表示 .....................................................................................................6
1.5.2 流程圖表示 .........................................................................................................6
1.5.3 N-S 圖表示 ..........................................................................................................8
1.5.4 偽代碼表示 .........................................................................................................8
1.6 偽代碼與算法程序的對應(yīng) ................................................................................9
1.6.1 基本對應(yīng)規(guī)則 .....................................................................................................9
1.6.2 分支結(jié)構(gòu) ...........................................................................................................10
1.6.3 循環(huán)結(jié)構(gòu) ...........................................................................................................10
1.6.4 數(shù)組及函數(shù) .......................................................................................................11
1.7 算法的性能評價 .............................................................................................. 11
1.8 算法實例 ..........................................................................................................12
1.8.1 查找數(shù)字 ...........................................................................................................12
實例1-1：在擁有20 個整數(shù)數(shù)據(jù)的數(shù)組中查找某個數(shù)據(jù) .......................................13
1.8.2 創(chuàng)建項目 ...........................................................................................................14
1.8.3 編譯執(zhí)行 ...........................................................................................................15
1.9 算法的新進(jìn)展 ..................................................................................................16
1.10 小結(jié)：算法是程序設(shè)計的靈魂和基礎(chǔ) ........................................................17
第2 章　數(shù)據(jù)結(jié)構(gòu)
2.1 數(shù)據(jù)結(jié)構(gòu)概述 ..................................................................................................18
2.1.1 什么是數(shù)據(jù)結(jié)構(gòu) ...............................................................................................18
2.1.2 數(shù)據(jù)結(jié)構(gòu)中的基本概念 ...................................................................................19
2.1.3 數(shù)據(jù)結(jié)構(gòu)的內(nèi)容 ...............................................................................................19
2.1.4 數(shù)據(jù)結(jié)構(gòu)的分類 ...............................................................................................21
2.1.5 數(shù)據(jù)結(jié)構(gòu)的幾種存儲方式 ...............................................................................21
2.1.6 數(shù)據(jù)類型 ...........................................................................................................22
2.1.7 常用的數(shù)據(jù)結(jié)構(gòu) ...............................................................................................23
2.1.8 選擇合適的數(shù)據(jù)結(jié)構(gòu)解決實際問題 ...............................................................24
2.2 線性表 ..............................................................................................................24
2.2.1 什么是線性表 ...................................................................................................24
2.2.2 線性表的基本運算 ...........................................................................................25
2.3 順序表結(jié)構(gòu) ......................................................................................................26
2.3.1 準(zhǔn)備數(shù)據(jù) ...........................................................................................................26
2.3.2 初始化順序表 ...................................................................................................27
2.3.3 計算順序表長度 ...............................................................................................27
2.3.4 插入結(jié)點 ...........................................................................................................27
2.3.5 追加結(jié)點 ...........................................................................................................28
2.3.6 刪除結(jié)點 ...........................................................................................................28
2.3.7 查找結(jié)點 ...........................................................................................................29
2.3.8 顯示所有結(jié)點 ...................................................................................................29
2.3.9 順序表操作示例 ...............................................................................................30
實例2-1：對某班級學(xué)生學(xué)號、姓名和年齡數(shù)據(jù)進(jìn)行順序表操作 .........................30
2.4 鏈表結(jié)構(gòu) ..........................................................................................................33
2.4.1 什么是鏈表結(jié)構(gòu) ...............................................................................................33
2.4.2 準(zhǔn)備數(shù)據(jù) ...........................................................................................................34
2.4.3 追加結(jié)點 ...........................................................................................................34
2.4.4 插入頭結(jié)點 .......................................................................................................35
2.4.5 查找結(jié)點 ...........................................................................................................36
2.4.6 插入結(jié)點 ...........................................................................................................37
2.4.7 刪除結(jié)點 ...........................................................................................................38
2.4.8 計算鏈表長度 ...................................................................................................38
2.4.9 顯示所有結(jié)點 ...................................................................................................39
2.4.10 鏈表操作示例 .................................................................................................39
實例2-2：使用鏈表操作實現(xiàn)用戶管理 .....................................................................39
2.5 棧結(jié)構(gòu) ..............................................................................................................43
2.5.1 什么是棧結(jié)構(gòu) ...................................................................................................43
2.5.2 準(zhǔn)備數(shù)據(jù) ...........................................................................................................44
2.5.3 初始化棧結(jié)構(gòu) ...................................................................................................44
2.5.4 判斷空棧 ...........................................................................................................45
2.5.5 判斷滿棧 ...........................................................................................................45
2.5.6 清空棧 ...............................................................................................................45
2.5.7 釋放空間 ...........................................................................................................46
2.5.8 入棧 ...................................................................................................................46
2.5.9 出棧 ...................................................................................................................46
2.5.10 讀結(jié)點數(shù)據(jù) .....................................................................................................47
2.5.11 棧結(jié)構(gòu)操作示例 .............................................................................................47
實例2-3：使用棧結(jié)構(gòu)實現(xiàn)學(xué)生數(shù)據(jù)操作 .................................................................47
2.6 隊列結(jié)構(gòu) ..........................................................................................................50
2.6.1 什么是隊列結(jié)構(gòu) ...............................................................................................50
2.6.2 準(zhǔn)備數(shù)據(jù) ...........................................................................................................50
2.6.3 初始化隊列結(jié)構(gòu) ...............................................................................................51
2.6.4 判斷空隊列 .......................................................................................................51
2.6.5 判斷滿隊列 .......................................................................................................52
2.6.6 清空隊列 ...........................................................................................................52
2.6.7 釋放空間 ...........................................................................................................52
2.6.8 入隊列 ...............................................................................................................52
2.6.9 出隊列 ...............................................................................................................53
2.6.10 讀結(jié)點數(shù)據(jù) .....................................................................................................53
2.6.11 計算隊列長度 .................................................................................................54
2.6.12 隊列結(jié)構(gòu)操作示例 .........................................................................................54
實例2-4：使用隊列結(jié)構(gòu)實現(xiàn)學(xué)生數(shù)據(jù)操作 .............................................................54
2.7 樹結(jié)構(gòu) ..............................................................................................................57
2.7.1 什么是樹結(jié)構(gòu) ...................................................................................................57
2.7.2 樹的基本概念 ...................................................................................................58
2.7.3 二叉樹 ...............................................................................................................58
2.7.4 準(zhǔn)備數(shù)據(jù) ...........................................................................................................62
2.7.5 初始化二叉樹 ...................................................................................................62
2.7.6 添加結(jié)點 ...........................................................................................................63
2.7.7 查找結(jié)點 ...........................................................................................................64
2.7.8 獲取左子樹 .......................................................................................................65
2.7.9 獲取右子樹 .......................................................................................................65
2.7.10 判斷空樹 .........................................................................................................65
2.7.11 計算二叉樹深度 .............................................................................................66
2.7.12 清空二叉樹 .....................................................................................................66
2.7.13 顯示結(jié)點數(shù)據(jù) .................................................................................................66
2.7.14 遍歷二叉樹 .....................................................................................................67
2.7.15 樹結(jié)構(gòu)操作示例 .............................................................................................69
實例2-5：經(jīng)典二叉樹的遍歷（4 種遍歷方式） ......................................................69
2.8 圖結(jié)構(gòu) ..............................................................................................................71
2.8.1 什么是圖結(jié)構(gòu) ...................................................................................................71
2.8.2 圖的基本概念 ...................................................................................................72
2.8.3 準(zhǔn)備數(shù)據(jù) ...........................................................................................................76
2.8.4 創(chuàng)建圖 ...............................................................................................................78
2.8.5 清空圖 ...............................................................................................................78
2.8.6 顯示圖 ...............................................................................................................79
2.8.7 遍歷圖 ...............................................................................................................79
2.8.8 圖結(jié)構(gòu)操作示例 ...............................................................................................80
實例2-6：使用深度優(yōu)先遍歷算法遍歷圖操作程序 .................................................81
2.9 小結(jié)：數(shù)據(jù)結(jié)構(gòu) 算法= 程序 ......................................................................83
第3 章　基本算法思想
3.1 常用算法思想概述 ..........................................................................................84
3.2 窮舉算法思想 ..................................................................................................84
3.2.1 窮舉算法基本思想 ...........................................................................................85
3.2.2 窮舉算法示例 ...................................................................................................85
實例3-1：雞兔同籠問題 .............................................................................................85
3.3 遞推算法思想 ..................................................................................................87
3.3.1 遞推算法基本思想 ...........................................................................................87
3.3.2 遞推算法示例 ...................................................................................................87
實例3-2：兔子產(chǎn)仔問題 .............................................................................................87
3.4 遞歸算法思想 ..................................................................................................89
3.4.1 遞歸算法基本思想 ...........................................................................................89
3.4.2 遞歸算法示例 ...................................................................................................90
實例3-3：求數(shù)字12 的階乘 .......................................................................................90
3.5 分治算法思想 ..................................................................................................91
3.5.1 分治算法基本思想 ...........................................................................................91
3.5.2 分治算法示例 ...................................................................................................91
實例3-4：從30 枚銀幣中找出僅有的1 枚假銀幣 ...................................................91
3.6 概率算法思想 ..................................................................................................95
3.6.1 概率算法基本思想 ...........................................................................................95
3.6.2 概率算法示例 ...................................................................................................95
實例3-5：利用蒙特卡羅算法計算圓周率π ..............................................................95
3.7 貪心算法思想 ..................................................................................................97
3.7.1 貪心算法基本思想 ...........................................................................................97
3.7.2 貪心算法示例 ...................................................................................................98
實例3-6：利用貪心算法思想兌換硬幣 .....................................................................98
3.8 小結(jié)：思路決定出路 ......................................................................................99
第４章　排序算法
4.1 排序算法概述 ................................................................................................100
4.2 冒泡排序法 ....................................................................................................101
4.2.1 冒泡排序算法 .................................................................................................101
4.2.2 冒泡排序算法示例 .........................................................................................102
實例4-1：對包含10 個數(shù)字的整型數(shù)組進(jìn)行排序 .................................................102
4.3 選擇排序法 ....................................................................................................104
4.3.1 選擇排序算法 .................................................................................................104
4.3.2 選擇排序算法示例 .........................................................................................105
實例4-2：對包含10 個數(shù)字的整型數(shù)組進(jìn)行排序 .................................................105
4.4 插入排序法 ....................................................................................................106
4.4.1 插入排序算法 .................................................................................................107
4.4.2 插入排序算法示例 .........................................................................................108
實例4-3：對包含10 個數(shù)字的整型數(shù)組進(jìn)行排序 .................................................108
4.5 Shell 排序法 ...................................................................................................109
4.5.1 Shell 排序算法 ................................................................................................109
4.5.2 Shell 排序算法示例 ........................................................................................111
實例4-4：對包含10 個數(shù)字的整型數(shù)組進(jìn)行排序 .................................................111
4.6 快速排序法 .................................................................................................... 112
4.6.1 快速排序算法 .................................................................................................112
4.6.2 快速排序算法示例 .........................................................................................114
實例4-5：對包含18 個數(shù)字的整型數(shù)組進(jìn)行排序 .................................................114
4.7 堆排序法 ........................................................................................................ 116
4.7.1 堆排序算法 .....................................................................................................116
4.7.2 堆排序算法示例 .............................................................................................120
實例4-6：對包含10 個數(shù)字的整型數(shù)組進(jìn)行排序 .................................................120
4.8 合并排序法 ....................................................................................................122
4.8.1 合并排序算法 .................................................................................................122
4.8.2 合并排序算法示例 .........................................................................................125
實例4-7：對包含15 個數(shù)字的整型數(shù)組進(jìn)行排序 .................................................125
4.9 排序算法的效率 ............................................................................................128
4.10 排序算法的其他應(yīng)用 ..................................................................................128
4.10.1 反序排序 .......................................................................................................129
4.10.2 反序插入排序算法示例 ...............................................................................129
實例4-8：對包含10 個數(shù)字的整型數(shù)組進(jìn)行排序 .................................................129
4.10.3 字符串的排序 ...............................................................................................131
4.10.4 字符串排序示例 ...........................................................................................132
實例4-9：用快速排序算法對包含16 個字母的字符串進(jìn)行排序 .........................132
4.10.5 字符串?dāng)?shù)組的排序 .......................................................................................133
4.10.6 字符串?dāng)?shù)組排序示例 ...................................................................................134
實例4-10：用快速排序算法對包含5 個單詞的字符串?dāng)?shù)組進(jìn)行排序 .................134
4.11 小結(jié)：排序是基本的算法 ......................................................................136
第5 章　查找算法
5.1 查找算法概述 ................................................................................................137
5.2 順序查找 ........................................................................................................138
5.2.1 順序查找算法 .................................................................................................138
5.2.2 順序查找操作示例 .........................................................................................138
實例5-1：在包含15 個數(shù)字的數(shù)組中查找第7 個數(shù)字 .........................................138
5.3 折半查找 ........................................................................................................140
5.3.1 折半查找算法 .................................................................................................140
5.3.2 折半查找操作示例 .........................................................................................142
實例5-2：在包含15 個數(shù)字的數(shù)組中查找第11 個數(shù)字 .......................................142
5.4 小結(jié)：查找是基本的應(yīng)用 ........................................................................144