前言
上篇　算法與數據結構基礎
第1章　基礎算法思想1
1.1　編程的靈魂：數據結構+算法1
1.2　算法的作用：猜價格游戲2
1.2.1　算法的作用2
1.2.2　實例：看商品猜價格2
1.3　枚舉（窮舉）算法思想6
1.3.1　算法思路6
1.3.2　實例：填數游戲6
1.3.3　實例：填運算符8
1.4　遞推算法思想11
1.4.1　算法思路11
1.4.2　順推實例：斐波那契數列11
1.4.3　逆推實例：該存多少錢13
1.5　遞歸算法思想14
1.5.1　算法思路14
1.5.2　實例：求階乘15
1.5.3　實例：數制轉換17
1.6　分治算法思想19
1.6.1　算法思路19
1.6.2　實例：乒乓球比賽日程安排20
1.7　貪婪算法思想23
1.7.1　算法思路24
1.7.2　實例：找零錢24
1.8　試探算法思想26
1.8.1　算法思路26
1.8.2　實例：生成彩票號碼組合27
1.9　模擬算法30
1.9.1　算法思路30
1.9.2　實例：猜數游戲30
1.9.3　實例：擲骰子游戲31
1.10　算法的評價32
1.10.1　算法評價原則32
1.10.2　算法的效率33
1.11　上機實踐34
第2章　簡單數據結構36
2.1　最簡單的結構：線性表36
2.1.1　線性表的概念36
2.1.2　操作順序表37
2.1.3　操作鏈表44
2.1.4　實例：用鏈表制作通訊錄53
2.2　后進先出結構：棧56
2.2.1　棧的概念56
2.2.2　操作棧57
2.2.3　實例：算術表達式求值62
2.3　先進先出結構：隊列68
2.3.1　什么是隊列68
2.3.2　操作隊列69
2.3.3　循環(huán)隊列的操作72
2.3.4　實例：銀行排號程序74
2.4　上機實踐77
第3章 復雜數據結構79
3.1　層次關系結構：樹79
3.1.1　樹的概念79
3.1.2　二叉樹的概念80
3.1.3　二叉樹的存儲82
3.1.4　操作二叉樹84
3.1.5　遍歷二叉樹88
3.1.6　測試二叉樹92
3.1.7　線索二叉樹95
3.1.8　最優(yōu)二叉樹（赫夫曼樹）102
3.2　網狀關系：圖111
3.2.1　圖的定義和基本術語111
3.2.2　圖的存儲115
3.2.3　圖的創(chuàng)建117
3.2.4　圖的遍歷123
3.2.5　最小生成樹128
3.2.6　最短路徑132
3.3　上機實踐136
第4章　常用算法——排序137
4.1　排序概述137
4.1.1　排序算法分類137
4.1.2　數據準備138
4.2　冒泡排序法139
4.2.1　冒泡排序法概述139
4.2.2　改進的冒泡排序法142
4.3　快速排序法143
4.3.1　算法描述143
4.3.2　算法實現144
4.4　簡單選擇排序法146
4.5　堆排序法148
4.5.1　算法描述148
4.5.2　算法實現150
4.6　直接插入排序法152
4.6.1　算法描述152
4.6.2　算法實現153
4.7　希爾（Shell）排序法154
4.7.1　算法描述154
4.7.2　算法實現155
4.8　合并排序法157
4.8.1　算法描述157
4.8.2　算法實現158
4.9　排序算法的選擇161
4.9.1　選擇基準161
4.9.2　各種排序算法的優(yōu)缺點162
4.10　上機實踐163
第5章　常用算法——查找164
5.1　查找的基本概念164
5.2　簡單查找165
5.2.1　順序查找165
5.2.2　折半查找167
5.3　二叉排序樹170
5.3.1　二叉排序樹的定義170
5.3.2　插入節(jié)點170
5.3.3　查找節(jié)點173
5.3.4　刪除節(jié)點174
5.4　索引查找178
5.4.1　索引的概念178
5.4.2　索引查找算法180
5.5　散列表184
5.5.1　散列表概述184
5.5.2　構造散列函數185
5.5.3　處理沖突187
5.5.4　創(chuàng)建和查找散列表188
5.6　上機實踐190
下篇　用算法與數據結構解決實際問題
第6章　數學問題191
6.1　有趣的整數191
6.1.1　完數191
6.1.2　親密數193
6.1.3　水仙花數195
6.1.4　自守數196
6.1.5　最大公約數和最小公倍數197
6.2　素數200
6.2.1　求素數200
6.2.2　回文數203
6.2.3　哥德巴赫猜想206
6.3　階乘209
6.3.1　用遞歸計算階乘210
6.3.2　大數階乘211
6.4　求π的近似值214
6.4.1　概率法214
6.4.2　割圓法216
6.4.3　公式法217
6.4.4　計算任意位數的π218
6.5　方程求解222
6.5.1　高斯消元法解線性方程組222
6.5.2　二分法解非線性方程227
6.5.3　牛頓迭代法解非線性方程228
6.6　矩陣的運算230
6.6.1　矩陣的加法和乘法運算230
6.6.2　多維矩陣轉一維矩陣233
6.6.3　逆矩陣235
6.6.4　稀疏矩陣238
6.7　一元多項式的運算240
6.7.1　多項式加法241
6.7.2　多項式減法245
6.8　上機實踐248
第7章　數據結構問題250
7.1　約瑟夫環(huán)250
7.2　大整數四則運算252
7.2.1　使用數組進行大整數運算252
7.2.2　使用鏈表進行大整數運算264
7.3　進制轉換271
7.3.1　進制轉換的分析272
7.3.2　進制轉換實現代碼272
7.4　括號匹配277
7.5　中序式轉后序式280
7.5.1　后序表達式280
7.5.2　算法實現281
7.5.3　后序表達式求值284
7.6　停車場管理286
7.6.1　問題分析287
7.6.2　算法實現287
7.7　迷宮求解297
7.7.1　迷宮問題297
7.7.2　算法實現297
7.7.3　求迷宮的所有路徑304
7.8　LZW壓縮307
7.8.1　LZW的相關概念308
7.8.2　LZW壓縮過程308
7.8.3　LZW壓縮的實現310
7.8.4　LZW解壓縮過程314
7.8.5　解壓縮函數315
7.8.6　集成壓縮和解壓縮功能318
7.9　上機實踐320
第8章　經典算法問題321
8.1　不定方程問題321
8.1.1　百錢買百雞321
8.1.2　存錢利息最大化323
8.1.3　求階梯數326
8.1.4　五家共井327
8.1.5　雞兔同籠328
8.2　推算問題329
8.2.1　猴子吃桃329
8.2.2　舍罕王的賞賜330
8.3　魔術方陣332
8.3.1　簡捷連續(xù)填數法332
8.3.2　雙向翻轉法335
8.3.3　井字調整法337
8.4　智力趣題340
8.4.1　漢諾塔341
8.4.2　背包問題345
8.4.3　馬踏棋盤352
8.4.4　八皇后問題361
8.4.5　青蛙過河366
8.4.6　三色旗369
8.5　趣味游戲371
8.5.1　取石子游戲372
8.5.2　生命游戲375
8.5.3　洗撲克牌379
8.5.4　黑白棋381
8.5.5　湊24點游戲391
8.5.6　10點半游戲396
8.6　上機實踐401
第9章 信息學奧賽試題精解403
9.1　NOIP普及組試題精解403
9.1.1　求級數之和403
9.1.2　求素數組合406
9.1.3　計算卒的路線409
9.1.4　檢查校驗碼411
9.1.5　排座位413
9.1.6　擊鼓傳花416
9.1.7　繪制模擬立體圖418
9.1.8　公路上的樹422
9.1.9　采藥423
9.1.10　求等價表達式425
9.1.11　不開心的龍龍429
9.1.12　孫悟空摘桃431
9.1.13　FBI樹433
9.1.14　外星人的語言435
9.2　NOIP提高組試題精解440
9.2.1　砝碼稱重440
9.2.2　阿明的零花錢442
9.2.3　購買年貨445
9.2.4　調整隊形448
9.2.5　均分紙牌450
9.2.6　最小矩形面積452
9.2.7　低價買股票460
9.2.8　數字金字塔463
9.2.9　方格取數465
9.2.10　導彈防御系統468
9.3　上機實踐471
第10章 常見面試題及解答473
10.1　數據結構類面試題473
10.1.1　選擇題473
10.1.2　編程題475
10.2　經典算法類面試題482
附錄　Dev-C++開發(fā)環(huán)境的使用489