目前，信息技術(shù)已被廣泛應(yīng)用于互聯(lián)網(wǎng)、金融、航空、軍事、醫(yī)療等各個(gè)領(lǐng)域，在未來(lái)的應(yīng)用將更加廣泛和深入�，F(xiàn)在，很多中小學(xué)都已開(kāi)設(shè)計(jì)算機(jī)語(yǔ)言課程，并且越來(lái)越多的中小學(xué)生對(duì)編程、算法感興趣，甚至在NOIP、NOI等算法競(jìng)賽中大顯身手。大學(xué)生通常參加ACM-ICPC、CCPC等算法競(jìng)賽，其獲獎(jiǎng)?wù)吒潜桓鞔竺笏嗖A。
學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法，不僅可以使我們具備較強(qiáng)的思維能力及解決問(wèn)題的能力，還可以使我們快速學(xué)習(xí)各種新技術(shù)，擁有超強(qiáng)的學(xué)習(xí)能力。
寫作背景
很多讀者都覺(jué)得數(shù)據(jù)結(jié)構(gòu)與算法太難，市面上晦澀難懂的各種教材更是“嚇退”了一大批讀者。實(shí)際上，數(shù)據(jù)結(jié)構(gòu)與算法并沒(méi)有我們想象中那么難，反而相當(dāng)有趣。每當(dāng)有學(xué)生說(shuō)看不懂某個(gè)算法的時(shí)候，筆者就會(huì)讓其畫圖。筆者認(rèn)為，畫圖是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法最好的方法，它可以把抽象難懂的數(shù)據(jù)結(jié)構(gòu)、算法展現(xiàn)得生動(dòng)形象、簡(jiǎn)單易懂。在出版《趣學(xué)數(shù)據(jù)結(jié)構(gòu)》《趣學(xué)算法》兩本書之后，很多讀者建議筆者寫一本算法競(jìng)賽的書，延續(xù)前兩本書的圖解風(fēng)格，再加上競(jìng)賽刷題的內(nèi)容。經(jīng)過(guò)近兩年的籌備，《算法訓(xùn)練營(yíng)：海量圖解+競(jìng)賽刷題（入門篇）》和《算法訓(xùn)練營(yíng)：海量圖解+競(jìng)賽刷題（進(jìn)階篇）》兩本書終于和大家見(jiàn)面了！這兩本書以海量圖解的形式，結(jié)合大量競(jìng)賽實(shí)例進(jìn)行講解。全書圖文并茂，可幫助讀者全面、系統(tǒng)地搭建數(shù)據(jù)結(jié)構(gòu)與算法知識(shí)體系，以模塊化方式逐一拆解算法問(wèn)題。以通俗易懂的方式講解算法，讓更多的讀者愛(ài)上算法，這也是筆者寫作這兩本書的初衷。
本書詳細(xì)講解常用的數(shù)據(jù)結(jié)構(gòu)和算法，還增加了語(yǔ)言基礎(chǔ)和STL函數(shù)的內(nèi)容。如果讀者已經(jīng)熟悉C++，則可跳過(guò)這些基礎(chǔ)章節(jié)。本書不是知識(shí)點(diǎn)的堆砌，也不是粘貼代碼的簡(jiǎn)單題解，而是將知識(shí)點(diǎn)講解和對(duì)應(yīng)的競(jìng)賽刷題融會(huì)貫通，可使讀者在輕松閱讀的同時(shí)進(jìn)行實(shí)戰(zhàn)，在實(shí)戰(zhàn)中體會(huì)算法的妙處，感受算法之美。
本書特色
本書具有以下特色。
（1）完美圖解，通俗易懂。本書對(duì)每個(gè)算法的基本操作都有圖解演示。通過(guò)圖解，許多問(wèn)題都變得簡(jiǎn)單，可迎刃而解。
（2）實(shí)例豐富，簡(jiǎn)單有趣。本書結(jié)合大量競(jìng)賽實(shí)例，講解如何利用數(shù)據(jù)結(jié)構(gòu)與算法解決實(shí)際問(wèn)題，使復(fù)雜難懂的問(wèn)題變得簡(jiǎn)單有趣，幫助讀者輕松掌握算法知識(shí)，體會(huì)其中的妙處。
（3）深入淺出，透析本質(zhì)。本書透過(guò)問(wèn)題看本質(zhì)，重點(diǎn)講解如何分析和解決問(wèn)題。本書采用了簡(jiǎn)潔易懂的代碼，對(duì)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)和算法的描述全面細(xì)致，而且有算法復(fù)雜性分析及優(yōu)化過(guò)程。
（4）實(shí)戰(zhàn)演練，循序漸進(jìn)。本書在對(duì)每個(gè)數(shù)據(jù)結(jié)構(gòu)與算法講解清楚后，都進(jìn)行了實(shí)戰(zhàn)演練，使讀者在實(shí)戰(zhàn)中體會(huì)數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)和操作，從而提高了獨(dú)立思考、動(dòng)手實(shí)踐的能力。書中有豐富的練習(xí)題和競(jìng)賽題，可幫助讀者及時(shí)檢驗(yàn)對(duì)知識(shí)的掌握情況，為從小問(wèn)題出發(fā)、逐步解決大型復(fù)雜性工程問(wèn)題奠定基礎(chǔ)。
（5）網(wǎng)絡(luò)資源，技術(shù)支持。本書為讀者提供書中所有范例程序的源代碼、競(jìng)賽題及答案解析，讀者可以對(duì)這些源代碼自由修改編譯，以符合自己的需要。本書提供博客、微信群、QQ群技術(shù)支持，可隨時(shí)為讀者答疑解惑。
建議和反饋
寫書是極其瑣碎、繁重的工作，盡管筆者已經(jīng)竭力使本書和網(wǎng)絡(luò)支持接近完美，但仍然可能存在很多漏洞和瑕疵。歡迎讀者提供關(guān)于本書的反饋意見(jiàn)，因?yàn)閷?duì)本書的評(píng)論和建議有利于我們改進(jìn)和提高，以幫助更多的讀者。如果對(duì)本書有什么評(píng)論和建議，或者有問(wèn)題需要幫助，可以加入QQ群1029262418，也可以致信rainchxy@126.com與筆者交流，筆者將不勝感激。
讀者資源請(qǐng)參照本書封底提示。
致謝
感謝筆者的家人和朋友在本書寫作過(guò)程中提供的大力支持。感謝電子工業(yè)出版社工作嚴(yán)謹(jǐn)、高效的張國(guó)霞編輯，她的認(rèn)真負(fù)責(zé)促成本書的早日出版。感謝提供寶貴意見(jiàn)的同事們，感謝提供技術(shù)支持的同學(xué)們。感恩遇到這么多良師益友！
第1章 語(yǔ)言基礎(chǔ)... 1
1.1 開(kāi)啟算法之旅：hello world! 1
1.2 常見(jiàn)數(shù)據(jù)類型及其表達(dá)范圍... 2
1.3 玩轉(zhuǎn)輸入輸出... 2
1.4 人生就是不斷地選擇：if…else. 9
1.5 每天都有很多次重復(fù)：for/while. 13
1.6 如何輕松寫一個(gè)函數(shù)... 20
1.7 從前有座山，山里有座廟：遞歸之法... 25
1.8 信息攜帶者：定義一個(gè)結(jié)構(gòu)體... 29
1.9 巧用數(shù)組——好玩貪吃蛇... 31
1.10 玩轉(zhuǎn)字符串——不一樣的風(fēng)格... 37
第2章 算法入門... 42
2.1 算法之美... 42
2.1.1 如何評(píng)價(jià)一個(gè)算法的優(yōu)劣... 42
2.1.2 算法復(fù)雜度的計(jì)算方法... 45
2.2 貪心算法... 48
2.2.1 貪心本質(zhì)... 48
2.2.2 最優(yōu)裝載問(wèn)題... 49
2.3 分治算法... 51
2.3.1 分治算法秘籍... 51
2.3.2 合并排序... 51
2.3.3 快速排序... 57
2.4 STL應(yīng)用... 65
2.4.1 vector 65
訓(xùn)練 間諜... 67
2.4.2 棧... 68
訓(xùn)練 Web導(dǎo)航... 69
2.4.3 queue. 75
訓(xùn)練 騎士移動(dòng)... 75
2.4.4 list 77
訓(xùn)練 士兵隊(duì)列訓(xùn)練... 78
2.4.5 deque. 79
訓(xùn)練 度度熊學(xué)隊(duì)列... 80
2.4.6 priority_queue. 82
訓(xùn)練 黑盒子... 83
2.4.7 bitset 85
訓(xùn)練 集合運(yùn)算... 88
2.4.8 set/multiset 90
訓(xùn)練1 集合合并... 91
訓(xùn)練2 并行處理... 92
2.4.9 map/multimap. 94
訓(xùn)練1 硬木種類... 96
訓(xùn)練2 雙重隊(duì)列... 97
訓(xùn)練3 水果... 99
2.4.10 STL的常用函數(shù)... 100
訓(xùn)練1 差的中位數(shù)... 106
訓(xùn)練2 中位數(shù)... 108
訓(xùn)練3 訂單管理... 109
訓(xùn)練4 字謎... 110
第3章 線性表的應(yīng)用... 112
3.1 順序表... 112
3.2 單鏈表... 116
3.3 雙向鏈表... 119
3.4 循環(huán)鏈表... 122
3.5 靜態(tài)鏈表... 123
訓(xùn)練1 區(qū)塊世界... 126
訓(xùn)練2 悲劇文本... 132
訓(xùn)練3 移動(dòng)盒子... 133
第4章 棧和隊(duì)列的應(yīng)用... 140
4.1 順序棧... 140
4.2 鏈棧... 143
4.3 順序隊(duì)列... 146
4.4 鏈隊(duì)列... 155
訓(xùn)練1 括號(hào)匹配... 158
訓(xùn)練2 鐵軌... 160
訓(xùn)練3 矩陣連乘... 164
訓(xùn)練4 打印隊(duì)列... 168
訓(xùn)練5 并發(fā)模擬器... 171
第5章 樹的應(yīng)用... 187
5.1 樹... 187
5.1.1 樹的存儲(chǔ)... 190
5.1.2 樹、森林與二叉樹的轉(zhuǎn)換... 193
5.2 二叉樹... 194
5.2.1 二叉樹的性質(zhì)... 195
5.2.2 二叉樹的存儲(chǔ)結(jié)構(gòu)... 200
5.2.3 二叉樹的創(chuàng)建... 202
5.3 二叉樹遍歷... 210
5.3.1 先序遍歷... 210
5.3.2 中序遍歷... 214
5.3.3 后序遍歷... 217
5.3.4 層次遍歷... 221
5.3.5 遍歷序列還原樹... 224
訓(xùn)練1 新二叉樹... 228
訓(xùn)練2 還原樹... 229
訓(xùn)練3 樹... 230
5.4 哈夫曼樹... 232
原理 哈夫曼編碼... 232
訓(xùn)練1 圍欄修復(fù)... 245
訓(xùn)練2 信息熵... 246
訓(xùn)練3 轉(zhuǎn)換哈夫曼編碼... 248
訓(xùn)練4 可變基哈夫曼編碼... 251
第6章 圖論基礎(chǔ)... 256
6.1 圖的存儲(chǔ)... 257
6.1.1 鄰接矩陣... 257
6.1.2 邊集數(shù)組... 263
6.1.3 鄰接表... 263
6.1.4 鏈?zhǔn)角跋蛐?.. 271
訓(xùn)練1 最大的節(jié)點(diǎn)... 274
訓(xùn)練2 有向圖D和E. 276
訓(xùn)練3 奶牛排序... 278
6.2 圖的遍歷... 279
6.2.1 廣度優(yōu)先遍歷... 279
6.2.2 深度優(yōu)先遍歷... 283
訓(xùn)練1 油田... 287
訓(xùn)練2 理想路徑... 290
訓(xùn)練3 騎士的旅程... 293
訓(xùn)練4 抓住那頭牛... 295
6.3 圖的連通性... 298
6.3.1 連通性的相關(guān)知識(shí)... 298
6.3.2 Tarjan算法... 302
訓(xùn)練1 電話網(wǎng)絡(luò)... 306
訓(xùn)練2 道路建設(shè)... 308
訓(xùn)練3 圖的底部... 311
訓(xùn)練4 校園網(wǎng)絡(luò)... 313
第7章 圖的應(yīng)用... 316
7.1 最短路徑... 316
7.1.1 Dijkstra算法... 316
7.1.2 Floyd算法... 322
7.1.3 Bellman-Ford算法... 326
7.1.4 SPFA算法... 328
訓(xùn)練1 重型運(yùn)輸... 329
訓(xùn)練2 貨幣兌換... 331
訓(xùn)練3 蟲洞... 332
訓(xùn)練4 最短路徑... 335
7.2 最小生成樹... 336
7.2.1 Prim算法... 337
7.2.2 Kruskal算法... 346
訓(xùn)練1 叢林之路... 351
訓(xùn)練2 聯(lián)網(wǎng)... 352
訓(xùn)練3 空間站... 354
訓(xùn)練4 道路建設(shè)... 356
7.3 拓?fù)渑判?.. 358
原理 拓?fù)渑判?.. 358
訓(xùn)練1 家族樹... 362
訓(xùn)練2 全排序... 364
訓(xùn)練3 標(biāo)簽球... 366
訓(xùn)練4 秩序... 369
7.4 關(guān)鍵路徑... 371
原理 關(guān)鍵路徑... 371
訓(xùn)練1 關(guān)鍵路徑... 380
訓(xùn)練2 指令安排... 382
訓(xùn)練3 家務(wù)瑣事... 384
訓(xùn)練4 免費(fèi)DIY之旅... 385
訓(xùn)練5 游戲玩家... 388
第8章 查找算法... 391
8.1 哈希表... 391
8.1.1 散列函數(shù)... 392
8.1.2 處理沖突的方法... 394
8.1.3 散列查找及性能分析... 404
訓(xùn)練1 雪花... 406
訓(xùn)練2 公式... 407
訓(xùn)練3 正方形... 409
8.2 字符串模式匹配... 411
8.2.1 BF算法... 412
8.2.2 KMP算法... 415
訓(xùn)練1 統(tǒng)計(jì)單詞數(shù)... 421
訓(xùn)練2 KMP字符串匹配... 423
8.3 二叉查找樹... 424
原理 二叉查找樹詳解... 424
訓(xùn)練1 落葉... 436
訓(xùn)練2 完全二叉搜索樹... 439
訓(xùn)練3 硬木種類... 441
訓(xùn)練4 二叉搜索樹... 442
8.4 平衡二叉樹... 444
原理 AVL樹詳解... 445
訓(xùn)練1 平衡二叉樹... 458
訓(xùn)練2 雙重隊(duì)列... 461
訓(xùn)練3 黑盒子... 464
訓(xùn)練4 硬木種類... 465
第9章 搜索技術(shù)... 466
9.1 二分搜索... 466
原理 二分搜索技術(shù)... 466
訓(xùn)練1 跳房子游戲... 471
訓(xùn)練2 烘干衣服... 475
訓(xùn)練3 花環(huán)... 477
訓(xùn)練4 電纜切割... 479
9.2 深度優(yōu)先搜索... 480
9.2.1 回溯法... 480
9.2.2 子集樹... 483
9.2.3 m叉樹... 491
9.2.4 排列樹... 499
訓(xùn)練1 魅力手鐲... 515
訓(xùn)練2 圖的m著色問(wèn)題... 516
訓(xùn)練3 N皇后問(wèn)題... 517
9.2.5 DFS+剪枝優(yōu)化... 517
訓(xùn)練1 數(shù)獨(dú)游戲... 518
訓(xùn)練2 生日蛋糕... 521
訓(xùn)練3 木棒... 522
9.3 廣度優(yōu)先搜索... 524
9.3.1 分支限界法... 525
9.3.2 隊(duì)列式廣度優(yōu)先搜索.... 525
9.3.3 優(yōu)先隊(duì)列式廣度優(yōu)先搜索... 535
訓(xùn)練1 迷宮問(wèn)題... 541
訓(xùn)練2 加滿油箱... 542
9.3.4 嵌套廣度優(yōu)先搜索... 545
訓(xùn)練 推箱子... 545
9.3.5 雙向廣度優(yōu)先搜索... 549
訓(xùn)練 魔鬼Ⅱ... 549
9.4 啟發(fā)式搜索... 551
9.4.1 A*算法... 552
9.4.2 IDA*算法... 552
訓(xùn)練1 八數(shù)碼... 552
訓(xùn)練2 八數(shù)碼II 562
訓(xùn)練3 第K短路... 565
訓(xùn)練4 冪運(yùn)算... 567
書單推薦
