零基礎(chǔ)學(xué)算法（第4版）

前言
上篇　算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)
第1章　基礎(chǔ)算法思想1
1.1　編程的靈魂：數(shù)據(jù)結(jié)構(gòu)+算法1
1.2　算法的作用：猜價(jià)格游戲2
1.2.1　算法的作用2
1.2.2　實(shí)例：看商品猜價(jià)格2
1.3　枚舉（窮舉）算法思想6
1.3.1　算法思路6
1.3.2　實(shí)例：填數(shù)游戲6
1.3.3　實(shí)例：填運(yùn)算符8
1.4　遞推算法思想11
1.4.1　算法思路11
1.4.2　順推實(shí)例：斐波那契數(shù)列11
1.4.3　逆推實(shí)例：該存多少錢(qián)13
1.5　遞歸算法思想14
1.5.1　算法思路14
1.5.2　實(shí)例：求階乘15
1.5.3　實(shí)例：數(shù)制轉(zhuǎn)換17
1.6　分治算法思想19
1.6.1　算法思路19
1.6.2　實(shí)例：乒乓球比賽日程安排20
1.7　貪婪算法思想23
1.7.1　算法思路24
1.7.2　實(shí)例：找零錢(qián)24
1.8　試探算法思想26
1.8.1　算法思路26
1.8.2　實(shí)例：生成彩票號(hào)碼組合27
1.9　模擬算法30
1.9.1　算法思路30
1.9.2　實(shí)例：猜數(shù)游戲30
1.9.3　實(shí)例：擲骰子游戲31
1.10　算法的評(píng)價(jià)32
1.10.1　算法評(píng)價(jià)原則32
1.10.2　算法的效率33
1.11　上機(jī)實(shí)踐34
第2章　簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)36
2.1　最簡(jiǎn)單的結(jié)構(gòu)：線性表36
2.1.1　線性表的概念36
2.1.2　操作順序表37
2.1.3　操作鏈表44
2.1.4　實(shí)例：用鏈表制作通訊錄53
2.2　后進(jìn)先出結(jié)構(gòu)：棧56
2.2.1　棧的概念56
2.2.2　操作棧57
2.2.3　實(shí)例：算術(shù)表達(dá)式求值62
2.3　先進(jìn)先出結(jié)構(gòu)：隊(duì)列68
2.3.1　什么是隊(duì)列68
2.3.2　操作隊(duì)列69
2.3.3　循環(huán)隊(duì)列的操作72
2.3.4　實(shí)例：銀行排號(hào)程序74
2.4　上機(jī)實(shí)踐77
第3章 復(fù)雜數(shù)據(jù)結(jié)構(gòu)79
3.1　層次關(guān)系結(jié)構(gòu)：樹(shù)79
3.1.1　樹(shù)的概念79
3.1.2　二叉樹(shù)的概念80
3.1.3　二叉樹(shù)的存儲(chǔ)82
3.1.4　操作二叉樹(shù)84
3.1.5　遍歷二叉樹(shù)88
3.1.6　測(cè)試二叉樹(shù)92
3.1.7　線索二叉樹(shù)95
3.1.8　最優(yōu)二叉樹(shù)（赫夫曼樹(shù)）102
3.2　網(wǎng)狀關(guān)系：圖111
3.2.1　圖的定義和基本術(shù)語(yǔ)111
3.2.2　圖的存儲(chǔ)115
3.2.3　圖的創(chuàng)建117
3.2.4　圖的遍歷123
3.2.5　最小生成樹(shù)128
3.2.6　最短路徑132
3.3　上機(jī)實(shí)踐136
第4章　常用算法——排序137
4.1　排序概述137
4.1.1　排序算法分類(lèi)137
4.1.2　數(shù)據(jù)準(zhǔn)備138
4.2　冒泡排序法139
4.2.1　冒泡排序法概述139
4.2.2　改進(jìn)的冒泡排序法142
4.3　快速排序法143
4.3.1　算法描述143
4.3.2　算法實(shí)現(xiàn)144
4.4　簡(jiǎn)單選擇排序法146
4.5　堆排序法148
4.5.1　算法描述148
4.5.2　算法實(shí)現(xiàn)150
4.6　直接插入排序法152
4.6.1　算法描述152
4.6.2　算法實(shí)現(xiàn)153
4.7　希爾（Shell）排序法154
4.7.1　算法描述154
4.7.2　算法實(shí)現(xiàn)155
4.8　合并排序法157
4.8.1　算法描述157
4.8.2　算法實(shí)現(xiàn)158
4.9　排序算法的選擇161
4.9.1　選擇基準(zhǔn)161
4.9.2　各種排序算法的優(yōu)缺點(diǎn)162
4.10　上機(jī)實(shí)踐163
第5章　常用算法——查找164
5.1　查找的基本概念164
5.2　簡(jiǎn)單查找165
5.2.1　順序查找165
5.2.2　折半查找167
5.3　二叉排序樹(shù)170
5.3.1　二叉排序樹(shù)的定義170
5.3.2　插入節(jié)點(diǎn)170
5.3.3　查找節(jié)點(diǎn)173
5.3.4　刪除節(jié)點(diǎn)174
5.4　索引查找178
5.4.1　索引的概念178
5.4.2　索引查找算法180
5.5　散列表184
5.5.1　散列表概述184
5.5.2　構(gòu)造散列函數(shù)185
5.5.3　處理沖突187
5.5.4　創(chuàng)建和查找散列表188
5.6　上機(jī)實(shí)踐190
下篇　用算法與數(shù)據(jù)結(jié)構(gòu)解決實(shí)際問(wèn)題
第6章　數(shù)學(xué)問(wèn)題191
6.1　有趣的整數(shù)191
6.1.1　完數(shù)191
6.1.2　親密數(shù)193
6.1.3　水仙花數(shù)195
6.1.4　自守?cái)?shù)196
6.1.5　最大公約數(shù)和最小公倍數(shù)197
6.2　素?cái)?shù)200
6.2.1　求素?cái)?shù)200
6.2.2　回文數(shù)203
6.2.3　哥德巴赫猜想206
6.3　階乘209
6.3.1　用遞歸計(jì)算階乘210
6.3.2　大數(shù)階乘211
6.4　求π的近似值214
6.4.1　概率法214
6.4.2　割圓法216
6.4.3　公式法217
6.4.4　計(jì)算任意位數(shù)的π218
6.5　方程求解222
6.5.1　高斯消元法解線性方程組222
6.5.2　二分法解非線性方程227
6.5.3　牛頓迭代法解非線性方程228
6.6　矩陣的運(yùn)算230
6.6.1　矩陣的加法和乘法運(yùn)算230
6.6.2　多維矩陣轉(zhuǎn)一維矩陣233
6.6.3　逆矩陣235
6.6.4　稀疏矩陣238
6.7　一元多項(xiàng)式的運(yùn)算240
6.7.1　多項(xiàng)式加法241
6.7.2　多項(xiàng)式減法245
6.8　上機(jī)實(shí)踐248
第7章　數(shù)據(jù)結(jié)構(gòu)問(wèn)題250
7.1　約瑟夫環(huán)250
7.2　大整數(shù)四則運(yùn)算252
7.2.1　使用數(shù)組進(jìn)行大整數(shù)運(yùn)算252
7.2.2　使用鏈表進(jìn)行大整數(shù)運(yùn)算264
7.3　進(jìn)制轉(zhuǎn)換271
7.3.1　進(jìn)制轉(zhuǎn)換的分析272
7.3.2　進(jìn)制轉(zhuǎn)換實(shí)現(xiàn)代碼272
7.4　括號(hào)匹配277
7.5　中序式轉(zhuǎn)后序式280
7.5.1　后序表達(dá)式280
7.5.2　算法實(shí)現(xiàn)281
7.5.3　后序表達(dá)式求值284
7.6　停車(chē)場(chǎng)管理286
7.6.1　問(wèn)題分析287
7.6.2　算法實(shí)現(xiàn)287
7.7　迷宮求解297
7.7.1　迷宮問(wèn)題297
7.7.2　算法實(shí)現(xiàn)297
7.7.3　求迷宮的所有路徑304
7.8　LZW壓縮307
7.8.1　LZW的相關(guān)概念308
7.8.2　LZW壓縮過(guò)程308
7.8.3　LZW壓縮的實(shí)現(xiàn)310
7.8.4　LZW解壓縮過(guò)程314
7.8.5　解壓縮函數(shù)315
7.8.6　集成壓縮和解壓縮功能318
7.9　上機(jī)實(shí)踐320
第8章　經(jīng)典算法問(wèn)題321
8.1　不定方程問(wèn)題321
8.1.1　百錢(qián)買(mǎi)百雞321
8.1.2　存錢(qián)利息