C/C++常用算法手冊（含盤）

第1篇  算法基礎篇
第1章  算法概述
1.1  什么是算法 2
1.2  算法的發(fā)展歷史 3
1.3  算法的分類 4
1.4  算法相關概念的區(qū)別 4
1.5  算法的表示 5
1.5.1  自然語言表示 5
1.5.2  流程圖表示 6
1.5.3  N-S圖表示 7
1.5.4  偽代碼表示 7
1.6  偽代碼與算法程序的對應 8
1.6.1  基本對應規(guī)則 8
1.6.2  分支結構 9
1.6.2  循環(huán)結構 10
1.6.3  數(shù)組及函數(shù) 11
1.7  算法的性能評價 11
1.8  算法實例 12
1.8.1  查找數(shù)字 12
1.8.2  創(chuàng)建項目 13
1.8.3  編譯執(zhí)行 15
1.9  算法的新進展 16
1.10  小結 17
第2章  數(shù)據結構
2.1  數(shù)據結構概述 18
2.1.1  什么是數(shù)據結構 18
2.1.2  數(shù)據結構中的基本 19
2.1.3  數(shù)據結構的內容 19
2.1.4  數(shù)據結構的分類 21
2.1.5  數(shù)據結構的幾種存儲方式 21
2.1.6  數(shù)據類型 22
2.1.7  常用的數(shù)據結構 23
2.1.8  選擇合適的數(shù)據結構解決實際問題 24
2.2  線性表 24
2.2.1  什么是線性表 25
2.2.2  線性表的基本運算 25
2.3  順序表結構 26
2.3.1  準備數(shù)據 26
2.3.2  初始化順序表 27
2.3.3  計算順序表長度 27
2.3.4  插入結點 27
2.3.5  追加結點 28
2.3.6  刪除結點 28
2.3.7  查找結點 29
2.3.8  顯示所有結點 29
2.3.9  順序表操作示例 30
2.4  鏈表結構 33
2.4.1  什么是鏈表結構 34
2.4.2  準備數(shù)據 35
2.4.3  追加結點 35
2.4.4  插入頭結點 36
2.4.5  查找結點 37
2.4.6  插入結點 38
2.4.7  刪除結點 39
2.4.8  計算鏈表長度 39
2.4.9  顯示所有結點 40
2.4.10  鏈表操作示例 40
2.5  棧結構 45
2.5.1  什么是棧結構 45
2.5.2  準備數(shù)據 46
2.5.3  初始化棧結構 46
2.5.4  判斷空棧 47
2.5.5  判斷滿棧 47
2.5.6  清空棧 47
2.5.7  釋放空間 48
2.5.8  入棧 48
2.5.9  出棧 48
2.5.10  讀結點數(shù)據 49
2.5.11  棧結構操作示例 49
2.6  隊列結構 52
2.6.1  什么是隊列結構 52
2.6.2  準備數(shù)據 53
2.6.3  初始化隊列結構 53
2.6.4  判斷空隊列 54
2.6.5  判斷滿隊列 54
2.6.6  清空隊列 54
2.6.7  釋放空間 55
2.6.8  入隊列 55
2.6.9  出隊列 56
2.6.10  讀結點數(shù)據 56
2.6.11  計算隊列長度 57
2.6.12  隊列結構操作示例 57
2.7  樹結構 60
2.7.1  什么是樹結構 60
2.7.2  樹的基本概念 61
2.7.3  二叉樹 62
2.7.4  準備數(shù)據 65
2.7.5  初始化二叉樹 65
2.7.6  添加結點 66
2.7.7  查找結點 68
2.7.8  獲取左子樹 68
2.7.9  獲取右子樹 69
2.7.10  判斷空樹 69
2.7.11  計算二叉樹深度 69
2.7.12  清空二叉樹 70
2.7.13  顯示結點數(shù)據 70
2.7.14  遍歷二叉樹 71
2.7.15  樹結構操作示例 73
2.8  圖結構 75
2.8.1  什么是圖結構 75
2.8.2  圖的基本概念 76
2.8.3  準備數(shù)據 80
2.8.4  創(chuàng)建圖 82
2.8.5  清空圖 83
2.8.6  顯示圖 83
2.8.7  遍歷圖 84
2.8.8  圖結構操作示例 85
2.9  小結 88
第3章  基本算法思想
3.1  常用算法思想概述 89
3.2  窮舉算法思想 89
3.2.1  窮舉算法基本思想 90
3.2.2  窮舉算法示例 90
3.3  遞推算法思想 92
3.3.1  遞推算法基本思想 92
3.3.2  遞推算法示例 92
3.4  遞歸算法思想 94
3.4.1  遞歸算法基本思想 94
3.4.2  遞歸算法示例 95
3.5  分治算法思想 96
3.5.1  分治算法基本思想 96
3.5.2  分治算法示例 96
3.6  概率算法思想 100
3.6.1  概率算法基本思想 100
3.6.2  概率算法示例 101
3.7  小結 103
 
第2篇  算法基本應用篇
 
第4章  排序算法
4.1  排序算法概述 106
4.2  冒泡排序法 107
4.2.1  冒泡排序算法 107
4.2.2  冒泡排序算法示例 108
4.3  選擇排序法 110
4.3.1  選擇排序算法 110
4.3.2  選擇排序算法示例 111
4.4  插入排序法 113
4.4.1  插入排序算法 113
4.4.2  插入排序算法示例 114
4.5  Shell排序法 116
4.5.1  Shell排序算法 116
4.5.2  Shell排序算法示例 117
4.6  快速排序法 119
4.6.1  快速排序算法 119
4.6.2  快速排序算法示例 121
4.7  堆 排 序 法 123
4.7.1  堆排序算法 123
4.7.2  堆排序算法示例 128
4.8  合并排序法 130
4.8.1  合并排序算法 130
4.8.2  合并排序算法示例 133
4.9  排序算法的效率 136
4.10  排序算法的其他應用 137
4.10.1  反序排序 137
4.10.2  字符串數(shù)組的排序 140
4.10.3  字符串的排序 142
4.11  小結 145
第5章  查找算法
5.1  查找算法概述 146
5.2  順序查找 147
5.2.1  順序查找算法 147
5.2.2  順序查找操作示例 147
5.3  折半查找 149
5.3.1  折半查找算法 149
5.3.2  折半查找操作示例 151
5.4  數(shù)據結構中的查找算法 153
5.4.1  順序表結構中的查找算法 153
5.4.2  鏈表結構中的查找算法 157
5.4.3  樹結構中的查找算法 160
5.4.4  圖結構中的查找算法 161
5.5  小結 162
第6章  基本數(shù)學問題
6.1  判斷閏年 163
6.2  多項式計算 165
6.2.1  一維多項式求值 165
6.2.2  二維多項式求值 167
6.2.3  多項式乘法 169
6.2.4  多項式除法 171
6.3  隨機數(shù)生成算法 173
6.4  復數(shù)運算 181
6.4.1  簡單的復數(shù)運算 181
6.4.2  復數(shù)的冪運算 184
6.4.3  復指數(shù)運算 186
6.4.4  復對數(shù)運算 187
6.4.5  復正弦運算 188
6.4.6  復余弦運算 189
6.5  階乘 190
6.6  計算π的近似值 193
6.6.1  割圓術 193
6.6.2  蒙特卡羅算法 196
6.6.3  級數(shù)公式 198
6.7  矩陣運算 200
6.7.1  矩陣加法 200
6.7.2  矩陣減法 202
6.7.3  矩陣乘法 204
6.8  方 程 求 解 206
6.8.1  線性方程求解——高斯消元法 206
6.8.2  非線性方程求解——二分法 211
6.8.3  非線性方程求解——牛頓迭代法 213
6.9  小結 216
第7章  復雜的數(shù)值計算算法
7.1  拉格朗日插值 217
7.1.1  拉格朗日插值算法 217
7.1.2  拉格朗日插值示例 218
7.2  數(shù)值積分 221
7.2.1  數(shù)值積分算法 221
7.2.2  數(shù)值積分示例 222
7.3  開平方 224
7.3.1  開平方算法 224
7.3.2  開平方示例 225
7.4  極值問題的求解算法 226
7.4.1  極值求解算法 226
7.4.2  極值求解示例 229
7.5  特殊函數(shù)的計算算法 232
7.5.1  伽瑪函數(shù) 232
7.5.2  貝塔函數(shù) 236
7.5.3  正弦積分函數(shù) 240
7.5.4  余弦積分函數(shù) 244
7.5.5  指數(shù)積分函數(shù) 247
7.6  小結 252
第8章  經典數(shù)據結構問題
8.1  動態(tài)數(shù)組排序 253
8.1.1  的存儲和排序 253
8.1.2  動態(tài)數(shù)組排序示例 254
8.2  約 瑟 夫 環(huán) 256
8.2.1  簡單約瑟夫環(huán)算法 257
8.2.2  簡單約瑟夫環(huán)求解 258
8.2.3  復雜約瑟夫環(huán)算法 260
8.2.4  復雜約瑟夫環(huán)求解 261
8.3  城市之間的最短總距離 264
8.3.1  最短總距離算法 264
8.3.2  最短總距離求解 267
8.4  最短路徑 271
8.4.1  最短路徑算法 271
8.4.2  最短路徑求解 273
8.5  括號匹配 278
8.5.1  括號匹配算法 279
8.5.2  括號匹配求解 281
8.6  小結 284
第9章  數(shù)論問題
9.1  數(shù)論 285
9.1.1  數(shù)論概述 285
9.1.2  數(shù)論的分類 286
9.1.3  初等數(shù)論 287
9.1.4  基本概念 287
9.2  完全數(shù) 288
9.2.1  完全數(shù)概述 288
9.2.2  計算完全數(shù)算法 289
9.3  親密數(shù) 291
9.3.1  親密數(shù)概述 291
9.3.2  計算親密數(shù)算法 291
9.4  水仙花數(shù) 294
9.4.1  水仙花數(shù)概述 294
9.4.2  計算水仙花數(shù)算法 295
9.5  自守數(shù) 297
9.5.1  自守數(shù)概述 297
9.5.2  計算自守數(shù)算法 298
9.6  最大公約數(shù) 302
9.6.1  計算最大公約數(shù)算法——
輾轉相除法 302
9.6.2  計算最大公約數(shù)算法——Stein算法 303
9.6.3  計算最大公約數(shù)示例 304
9.7  最小公倍數(shù) 305
9.8  素數(shù) 307
9.8.1  素數(shù)概述 307
9.8.2  計算素數(shù)算法 308
9.9  回文素數(shù) 309
9.9.1  回文素數(shù)概述 310
9.9.2  計算回文素數(shù)算法 310
9.10  平方回文數(shù) 313
9.10.1  平方回文數(shù)概述 313
9.10.2  計算平方回文數(shù)算法 313
9.11  分解質因數(shù) 315
9.12  小結 318
第10章  算法經典趣題
10.1  百錢買百雞 319
10.1.1  百錢買百雞算法 319
10.1.2  百錢買百雞求解 320
10.2  五家共井 321
10.2.1  五家共井算法 321
10.2.2  五家共井求解 323
10.3  雞兔同籠 324
10.3.1  雞兔同籠算法 325
10.3.2  雞兔同籠求解 325
10.4  猴子吃桃 326
10.4.1  猴子吃桃算法 326
10.4.2  猴子吃桃求解 327
10.5  舍罕王賞麥 328
10.5.1  舍罕王賞麥問題 328
10.5.2  舍罕王賞麥求解 329
10.6  漢諾塔 330
10.6.1  漢諾塔算法 330
10.6.2  漢諾塔求解 332
10.7  竊賊問題 333
10.7.1  竊賊問題算法 333
10.7.2  竊賊問題求解 335
10.8  馬踏棋盤 338
10.8.1  馬踏棋盤算法 338
10.8.2  馬踏棋盤求解 340
10.9  八皇后問題 342
10.9.1  八皇后問題算法 342
10.9.2  八皇后問題求解 343
10.10  尋找假銀幣 346
10.10.1  尋找假銀幣算法 346
10.10.2  尋找假銀幣求解 348
10.11  青蛙過河 350
10.11.1  青蛙過河算法 351
10.11.2  青蛙過河求解 352
10.12  三色旗 355
10.12.1  三色旗算法 355
10.12.2  三色旗求解 356
10.13  漁夫捕魚 359
10.13.1  漁夫捕魚算法 359
10.13.2  漁夫捕魚求解 360
10.14  愛因斯坦的階梯 360
10.14.1  愛因斯坦的階梯算法 361
10.14.2  愛因斯坦的階梯求解 361
10.15  兔子產仔 362
10.15.1  兔子產仔算法 363
10.15.2  兔子產仔求解 363
10.16  常勝將軍 364
10.16.1  常勝將軍算法 364
10.16.2  常勝將軍求解 365
10.17  新郎和新娘 367
10.17.1  新郎和新娘算法 367
10.17.2  新郎和新娘求解 368
10.18  三色球 370
10.18.1  三色球算法 370
10.18.2  三色球求解 371
10.19  小結 372
第11章  游戲中的算法
11.1  洗撲克牌 373
11.1.1  洗撲克牌算法 373
11.1.2  洗撲克牌示例 374
11.2  取火柴游戲 377
11.2.1  取火柴游戲算法 377
11.2.2  取火柴游戲示例 378
11.3  10點半 380
11.3.1  10點半算法 380
11.3.2  10點半游戲示例 385
11.4  生命游戲 390
11.4.1  生命游戲的原理 391
11.4.2  生命游戲的算法 392
11.4.3  生命游戲示例 393
11.5  小結 399
 
第3篇  算法高級應用篇
 
第12章  密碼學算法
12.1  密碼學概述 402
12.1.1  密碼學的發(fā)展 402
12.1.2  密碼學的基本概念 403
12.1.3  柯克霍夫斯原則 404
12.1.4  經典密碼學算法 404
12.2  換位加密解密 405
12.2.1  換位加密解密算法 405
12.2.2  換位加密解密算法示例 408
12.3  替換加密解密 411
12.3.1  替換加密解密算法 411
12.3.2  替換加密解密算法示例 412
12.4  位加密解密 414
12.4.1  位加密解密算法 414
12.4.2  位加密解密算法示例 416
12.5  一次一密加密解密 417
12.5.1  一次一密加密解密算法 418
12.5.2  一次一密加密解密算法示例 419
12.6  小結 421
第13章  壓縮與解壓縮算法
13.1  壓縮與解壓縮概述 422
13.1.1  壓縮與解壓縮分類 422
13.1.2  典型的壓縮解壓縮算法 423
13.2  壓縮算法 423
13.3  解壓縮算法 426
13.4  壓縮/解壓縮示例 429
13.5  小結 432
 
第4篇  常見面試題
 
第14章  算法常見面試題及解答
14.1  排序類算法面試題 434
14.1.1  排序算法效率 434
14.1.2  雞尾酒排序算法 435
14.1.3  文件排序 437
14.1.4  城市名稱 438
14.2  查找類算法面試題 439
14.2.1  遞歸求極值 439
14.2.2  尋找共同元素 441
14.2.3  查找最大子串 442
14.3  綜合類算法面試題 444
14.3.1  求序列和 444
14.3.2  遞歸球累加和 445
14.3.3  猜蘋果數(shù) 446
14.3.4  擬置字符串 448
14.3.5  遞歸法擬置字符串 449
14.3.6  位運算求負數(shù) 450
14.4  小結 450
第15章  數(shù)據結構常見面試題及解答
15.1  基本數(shù)據結構面試題 451
15.1.1  如何實現(xiàn)數(shù)據緩存區(qū) 451
15.1.2  出棧隊列 451
15.1.3  入棧隊列 452
15.1.4  二叉樹葉節(jié)點個數(shù) 453
15.1.5  有向圖和無向圖 454
15.2  數(shù)據結構應用面試題 454
15.2.1  設計包含min函數(shù)的棧 455
15.2.2  設計計算指定節(jié)點層數(shù)算法 458
15.2.3  鏈表法篩選成績 459
15.2.4  將二叉樹轉變成排序的
雙向鏈表 461
15.2.5  單鏈表逆轉 463
15.3  小結 465