本書從日常生活中常見的實例入手,引領(lǐng)讀者進入算法和數(shù)據(jù)結(jié)構(gòu)的抽象世界。由于數(shù)據(jù)結(jié)構(gòu)、算法的知識比較抽象,使許多讀者望而卻步。本書在編寫過程中,盡量使用讀者容易理解的、簡單的語言來描述算法和數(shù)據(jù)結(jié)構(gòu),對于一些復(fù)雜的內(nèi)容,采用圖文并茂的方式介紹其原理,使讀者能很快理解相關(guān)知識。第1~5章介紹了常用算法和數(shù)據(jù)結(jié)構(gòu)的相應(yīng)代碼,第6~8章介紹了使用數(shù)據(jù)結(jié)構(gòu)和算法解決一些經(jīng)典問題的程序,第9章介紹了信息學奧賽部分試題的解題代碼,第10章給出了與算法和數(shù)據(jù)結(jié)構(gòu)相關(guān)的常見面試題。書中的所有程序都是在Dev-C++開發(fā)環(huán)境中編寫而成的,本書附錄簡單介紹了該開發(fā)環(huán)境的使用。
前言
上篇 算法與數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)
第1章 基礎(chǔ)算法思想1
1.1 編程的靈魂:數(shù)據(jù)結(jié)構(gòu)+算法1
1.2 算法的作用:猜價格游戲2
1.2.1 算法的作用2
1.2.2 實例:看商品猜價格2
1.3 枚舉(窮舉)算法思想6
1.3.1 算法思路6
1.3.2 實例:填數(shù)游戲6
1.3.3 實例:填運算符8
1.4 遞推算法思想11
1.4.1 算法思路11
1.4.2 順推實例:斐波那契數(shù)列11
1.4.3 逆推實例:該存多少錢13
1.5 遞歸算法思想14
1.5.1 算法思路14
1.5.2 實例:求階乘15
1.5.3 實例:數(shù)制轉(zhuǎn)換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 實例:猜數(shù)游戲30
1.9.3 實例:擲骰子游戲31
1.10 算法的評價32
1.10.1 算法評價原則32
1.10.2 算法的效率33
1.11 上機實踐34
第2章 簡單數(shù)據(jù)結(jié)構(gòu)36
2.1 最簡單的結(jié)構(gòu):線性表36
2.1.1 線性表的概念36
2.1.2 操作順序表37
2.1.3 操作鏈表44
2.1.4 實例:用鏈表制作通訊錄53
2.2 后進先出結(jié)構(gòu):棧56
2.2.1 棧的概念56
2.2.2 操作棧57
2.2.3 實例:算術(shù)表達式求值62
2.3 先進先出結(jié)構(gòu):隊列68
2.3.1 什么是隊列68
2.3.2 操作隊列69
2.3.3 循環(huán)隊列的操作72
2.3.4 實例:銀行排號程序74
2.4 上機實踐77
第3章 復(fù)雜數(shù)據(jù)結(jié)構(gòu)79
3.1 層次關(guān)系結(jié)構(gòu):樹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 網(wǎng)狀關(guān)系:圖111
3.2.1 圖的定義和基本術(shù)語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 數(shù)據(jù)準備138
4.2 冒泡排序法139
4.2.1 冒泡排序法概述139
4.2.2 改進的冒泡排序法142
4.3 快速排序法143
4.3.1 算法描述143
4.3.2 算法實現(xiàn)144
4.4 簡單選擇排序法146
4.5 堆排序法148
4.5.1 算法描述148
4.5.2 算法實現(xiàn)150
4.6 直接插入排序法152
4.6.1 算法描述152
4.6.2 算法實現(xiàn)153
4.7 希爾(Shell)排序法154
4.7.1 算法描述154
4.7.2 算法實現(xiàn)155
4.8 合并排序法157
4.8.1 算法描述157
4.8.2 算法實現(xiàn)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 構(gòu)造散列函數(shù)185
5.5.3 處理沖突187
5.5.4 創(chuàng)建和查找散列表188
5.6 上機實踐190
下篇 用算法與數(shù)據(jù)結(jié)構(gòu)解決實際問題
第6章 數(shù)學問題191
6.1 有趣的整數(shù)191
6.1.1 完數(shù)191
6.1.2 親密數(shù)193
6.1.3 水仙花數(shù)195
6.1.4 自守數(shù)196
6.1.5 最大公約數(shù)和最小公倍數(shù)197
6.2 素數(shù)200
6.2.1 求素數(shù)200
6.2.2 回文數(shù)203
6.2.3 哥德巴赫猜想206
6.3 階乘209
6.3.1 用遞歸計算階乘210
6.3.2 大數(shù)階乘211
6.4 求π的近似值214
6.4.1 概率法214
6.4.2 割圓法216
6.4.3 公式法217
6.4.4 計算任意位數(shù)的π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 多維矩陣轉(zhuǎn)一維矩陣233
6.6.3 逆矩陣235
6.6.4 稀疏矩陣238
6.7 一元多項式的運算240
6.7.1 多項式加法241
6.7.2 多項式減法245
6.8 上機實踐248
第7章 數(shù)據(jù)結(jié)構(gòu)問題250
7.1 約瑟夫環(huán)250
7.2 大整數(shù)四則運算252
7.2.1 使用數(shù)組進行大整數(shù)運算252
7.2.2 使用鏈表進行大整數(shù)運算264
7.3 進制轉(zhuǎn)換271
7.3.1 進制轉(zhuǎn)換的分析272
7.3.2 進制轉(zhuǎn)換實現(xiàn)代碼272
7.4 括號匹配277
7.5 中序式轉(zhuǎn)后序式280
7.5.1 后序表達式280
7.5.2 算法實現(xiàn)281
7.5.3 后序表達式求值284
7.6 停車場管理286
7.6.1 問題分析287
7.6.2 算法實現(xiàn)287
7.7 迷宮求解297
7.7.1 迷宮問題297
7.7.2 算法實現(xiàn)297
7.7.3 求迷宮的所有路徑304
7.8 LZW壓縮307
7.8.1 LZW的相關(guān)概念308
7.8.2 LZW壓縮過程308
7.8.3 LZW壓縮的實現(xiàn)310
7.8.4 LZW解壓縮過程314
7.8.5 解壓縮函數(shù)315
7.8.6 集成壓縮和解壓縮功能318
7.9 上機實踐320
第8章 經(jīng)典算法問題321
8.1 不定方程問題321
8.1.1 百錢買百雞321
8.1.2 存錢利息最大化323
8.1.3 求階梯數(shù)326
8.1.4 五家共井327
8.1.5 雞兔同籠328
8.2 推算問題329
8.2.1 猴子吃桃329
8.2.2 舍罕王的賞賜330
8.3 魔術(shù)方陣332
8.3.1 簡捷連續(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 背包問題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 求級數(shù)之和403
9.1.2 求素數(shù)組合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 調(diào)整隊形448
9.2.5 均分紙牌450
9.2.6 最小矩形面積452
9.2.7 低價買股票460
9.2.8 數(shù)字金字塔463
9.2.9 方格取數(shù)465
9.2.10 導(dǎo)彈防御系統(tǒng)468
9.3 上機實踐471
第10章 常見面試題及解答473
10.1 數(shù)據(jù)結(jié)構(gòu)類面試題473
10.1.1 選擇題473
10.1.2 編程題475
10.2 經(jīng)典算法類面試題482
附錄 Dev-C++開發(fā)環(huán)境的使用489