本書(shū)從日常生活中常見(jiàn)的實(shí)例入手，引領(lǐng)讀者進(jìn)入算法和數(shù)據(jù)結(jié)構(gòu)的抽象世界。由于數(shù)據(jù)結(jié)構(gòu)、算法的知識(shí)比較抽象，使許多讀者望而卻步。本書(shū)在編寫(xiě)過(guò)程中，盡量使用讀者容易理解的、簡(jiǎn)單的語(yǔ)言來(lái)描述算法和數(shù)據(jù)結(jié)構(gòu)，對(duì)于一些復(fù)雜的內(nèi)容，采用圖文并茂的方式介紹其原理，使讀者能很快理解相關(guān)知識(shí)。第1~5章介紹了常用算法和數(shù)據(jù)結(jié)構(gòu)的相應(yīng)代碼，第6~8章介紹了使用數(shù)據(jù)結(jié)構(gòu)和算法解決一些經(jīng)典問(wèn)題的程序，第9章介紹了信息學(xué)奧賽部分試題的解題代碼，第10章給出了與算法和數(shù)據(jù)結(jié)構(gòu)相關(guān)的常見(jiàn)面試題。書(shū)中的所有程序都是在Dev-C++開(kāi)發(fā)環(huán)境中編寫(xiě)而成的，本書(shū)附錄簡(jiǎn)單介紹了該開(kāi)發(fā)環(huán)境的使用。
前言
上篇 算法與數(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)利息最大化323
8.1.3 求階梯數(shù)326
8.1.4 五家共井327
8.1.5 雞兔同籠328
8.2 推算問(wèn)題329
8.2.1 猴子吃桃329
8.2.2 舍罕王的賞賜330
8.3 魔術(shù)方陣332
8.3.1 簡(jiǎn)捷連續(xù)填數(shù)法332
8.3.2 雙向翻轉(zhuǎn)法335
8.3.3 井字調(diào)整法337
8.4 智力趣題340
8.4.1 漢諾塔341
8.4.2 背包問(wèn)題345
8.4.3 馬踏棋盤(pán)352
8.4.4 八皇后問(wèn)題361
8.4.5 青蛙過(guò)河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點(diǎn)游戲391
8.5.6 10點(diǎn)半游戲396
8.6 上機(jī)實(shí)踐401
第9章 信息學(xué)奧賽試題精解403
9.1 NOIP普及組試題精解403
9.1.1 求級(jí)數(shù)之和403
9.1.2 求素?cái)?shù)組合406
9.1.3 計(jì)算卒的路線409
9.1.4 檢查校驗(yàn)碼411
9.1.5 排座位413
9.1.6 擊鼓傳花416
9.1.7 繪制模擬立體圖418
9.1.8 公路上的樹(shù)422
9.1.9 采藥423
9.1.10 求等價(jià)表達(dá)式425
9.1.11 不開(kāi)心的龍龍429
9.1.12 孫悟空摘桃431
9.1.13 FBI樹(shù)433
9.1.14 外星人的語(yǔ)言435
9.2 NOIP提高組試題精解440
9.2.1 砝碼稱(chēng)重440
9.2.2 阿明的零花錢(qián)442
9.2.3 購(gòu)買(mǎi)年貨445
9.2.4 調(diào)整隊(duì)形448
9.2.5 均分紙牌450
9.2.6 最小矩形面積452
9.2.7 低價(jià)買(mǎi)股票460
9.2.8 數(shù)字金字塔463
9.2.9 方格取數(shù)465
9.2.10 導(dǎo)彈防御系統(tǒng)468
9.3 上機(jī)實(shí)踐471
第10章 常見(jiàn)面試題及解答473
10.1 數(shù)據(jù)結(jié)構(gòu)類(lèi)面試題473
10.1.1 選擇題473
10.1.2 編程題475
10.2 經(jīng)典算法類(lèi)面試題482
附錄 Dev-C++開(kāi)發(fā)環(huán)境的使用489
書(shū)單推薦
