零基礎學算法(第二版)（簡體書）

《零基礎學算法(第2版)(附DVD光盤1張)》分為上、下兩篇，共10章，上篇用5章的篇幅介紹了算法和數據結構的基礎知識，包括基礎算法思想、簡單數據結構、復雜數據結構、排序和查找算法等內容；下篇用5章的篇幅介紹了用數據結構解決實際問題的相關程序，包括解決數學問題、數據結構問題、算法經典問題等內容以及信息學奧賽部分試題的程序，最後一章介紹了與算法和數據結構相關的常見面試題。
《零基礎學算法(第2版)(附DVD光盤1張)》案例實用性強、結構清晰、實例代碼講解詳盡。可作為大中專院校學生學習數據結構，做課程設計的參考書，也可以作為有一定程序設計基礎的程序員的參考書，還可作為參加信息學奧賽選手的參考書。

《零基礎學算法(第2版)(附DVD光盤1張)》編輯推薦：
由淺入深：《零基礎學算法(第2版)(附DVD光盤1張)》從日常生活中常見的實例入手，引領讀者進入算法和數據結構的抽象世界；
簡單易學：《零基礎學算法(第2版)(附DVD光盤1張)》在編寫過程中，盡量使用讀者容易理解的、簡單的語言來描述算法和數據結構，對于復雜一些的內容，也是以圖、表等形式介紹其原理，使讀者能很快理解相關知識；
詳細的代碼：為了便于讀者理解相應的知識點，《零基礎學算法(第2版)(附DVD光盤1張)》對每一個知識點都提供了完整、詳細的代碼，讀者可通過閱讀代碼，并上機調試來逐步體會、理解相應的知識點。精選習題加強訓練，面試題讓您輕松應對職場！

前言
上篇 算法與數據結構基礎
第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　枚舉（窮舉）算法思想 9
1.4.1 算法思路 9
1.4.2 實例：填數游戲 10
1.4.3 實例：填運算符 12
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 實例：乒乓球比賽日程安排 19
1.7 貪婪算法思想 23
1.7.1 算法思路 23
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 實例：用鏈表制作通信錄 54
2.2 先進先出結構：隊列 57
2.2.1 什么是隊列 58
2.2.2 操作隊列 58
2.2.3 循環隊列的操作 62
2.2.4 實例：銀行排號程序 64
2.3 後進先出結構：棧 67
2.3.1 什么是棧 67
2.3.2 操作棧 67
2.3.3 實例：算術表達式求值 72
2.4 上機實踐 79
第3章 復雜數據結構 81
3.1 層次關系結構：樹 81
3.1.1 樹的概念 81
3.1.2 二叉樹的概念 82
3.1.3 二叉樹的存儲 84
3.1.4 操作二叉樹 86
3.1.5 遍歷二叉樹 90
3.1.6 測試二叉樹 94
3.1.7 線索二叉樹 98
3.1.8 最優二叉樹（哈夫曼樹） 105
3.2 網狀關系：圖 115
3.2.1 圖的定義和基本術語 115
3.2.2 圖的存儲 119
3.2.3 創建圖 121
3.2.4 圖的遍歷 127
3.2.5 最小生成樹 132
3.2.6 最短路徑 137
3.3 上機實踐 141
第4章 常用算法—排序 142
4.1 排序概述 142
4.1.1 排序算法分類 142
4.1.2 數據準備 143
4.2 冒泡排序法 144
4.2.1 冒泡排序法概述 144
4.2.2 改進的冒泡排序法 147
4.3 快速排序法 148
4.3.1 算法描述 148
4.3.2 算法實現 149
4.4 簡單選擇排序法 151
4.5 堆排序法 153
4.5.1 算法描述 153
4.5.2 算法實現 156
4.6 直接插入排序法 158
4.6.1 算法描述 158
4.6.2 算法實現 159
4.7 希爾（Shell）排序法 160
4.7.1 算法描述 160
4.7.2 算法實現 161
4.8 合并排序法 162
4.8.1 算法描述 162
4.8.2 算法實現 164
4.9 排序算法的選擇 167
4.9.1 選擇基準 167
4.9.2 各種排序算法的優缺點 168
4.10 上機實踐 168
第5章 常用算法—查找 170
5.1 查找的基本概念 170
5.2 簡單查找 171
5.2.1 順序查找 171
5.2.2 折半查找 173
5.3 二叉排序樹 176
5.3.1 二叉排序樹的定義 176
5.3.2 插入節點 177
5.3.3 查找節點 180
5.3.4 刪除節點 181
5.4 索引查找 185
5.4.1 索引的概念 185
5.4.2 索引查找算法 187
5.5 散列表 191
5.5.1 散列表概述 191
5.5.2 構造散列函數 192
5.5.3 處理沖突 194
5.5.4 創建和查找散列表 195
5.6 上機實踐 197
下篇 用數據結構解決實際問題
第6章 數學問題 199
6.1 有趣的整數 199
6.1.1 完數 199
6.1.2 親密數 201
6.1.3 水仙花數 203
6.1.4 自守數 204
6.1.5 最大公約數和最小公倍數 206
6.2 素數 208
6.2.1 求素數 209
6.2.2 回文數 212
6.2.3 哥德巴赫猜想 215
6.3 階乘 219
6.3.1 用遞歸計算階乘 219
6.3.2 大數階乘 220
6.4 求p的近似值 224
6.4.1 概率法 224
6.4.2 割圓法 225
6.4.3 公式法 227
6.4.4 計算任意位數的p 228
6.5 方程求解 231
6.5.1 高斯消元法解線性方程組 232
6.5.2 二分法解非線性方程 237
6.5.3 牛頓迭代法解非線性方程 238
6.6 矩陣的運算 240
6.6.1 矩陣加法和乘法運算 240
6.6.2 多維矩陣轉一維矩陣 243
6.6.3 逆矩陣 245
6.6.4 稀疏矩陣 249
6.7 一元多項式的運算 251
6.7.1 多項式加法 251
6.7.2 多項式減法 256
6.8 上機實踐 260
第7章 數據結構問題 261
7.1 約瑟夫環 261
7.2 大整數四則運算 263
7.2.1 使用數組進行大整數運算 263
7.2.2 使用鏈表進行大整數運算 276
7.3 進制轉換 284
7.3.1 進制轉換的分析 284
7.3.2 進制轉換實現代碼 285
7.4 括號匹配 290
7.5 中序式轉後序式 292
7.5.1 後序表達式 293
7.5.2 算法實現 294
7.5.3 後序表達式求值 297
7.6 停車場管理 299
7.6.1 問題分析 300
7.6.2 算法實現 300
7.7 迷宮求解 310
7.7.1 迷宮問題 310
7.7.2 算法實現 311
7.7.3 求迷宮所有路徑 318
7.8 LZW壓縮的實現 322
7.8.1 LZW的相關概念 322
7.8.2 LZW壓縮過程 323
7.8.3 LZW壓縮的實現 324
7.8.4 LZW解壓縮過程 329
7.8.5 解壓縮函數 330
7.8.6 集成壓縮和解壓縮功能 333
7.9 上機實踐 335
第8章 算法經典問題 337
8.1 不定方程問題 337
8.1.1 百錢買百雞 337
8.1.2 存錢利息最大化 339
8.1.3 求階梯數 342
8.1.4 五家共井 343
8.1.5 雞兔同籠 344
8.2 推算問題 345
8.2.1 猴子吃桃 346
8.2.2 舍罕王的賞賜 347
8.3 魔術方陣 348
8.3.1 簡捷連續填數法 348
8.3.2 雙向翻轉法 351
8.3.3 井字調整法 354
8.4 智力趣題 357
8.4.1 漢諾塔 357
8.4.2 背包問題 361
8.4.3 馬踏棋盤 369
8.4.4 八皇後問題 379
8.4.5 青蛙過河 384
8.4.6 三色旗 387
8.5 趣味游戲 390
8.5.1 取石子游戲 390
8.5.2 生命游戲 394
8.5.3 洗撲克牌 398
8.5.4 黑白棋 400
8.5.5 湊24點游戲 410
8.5.6 10點半游戲 416
8.6 上機實踐 421
第9章 信息學奧賽試題精解 423
9.1 NOIP普及組試題精解 423
9.1.1 求級數之和 423
9.1.2 求素數組合 426
9.1.3 計算卒的路線 429
9.1.4 檢查校驗碼 432
9.1.5 排座位 434
9.1.6 擊鼓傳花 437
9.1.7 繪制模擬立體圖 439
9.1.8 公路上的樹 443
9.1.9 采藥 444
9.1.10 求等價表達式 446
9.1.11 不開心的龍龍 451
9.1.12 孫悟空摘桃 452
9.1.13 FBI樹 455
9.1.14 外星人的語言 457
9.2 NOIP提高組試題精解 462
9.2.1 砝碼稱重 462
9.2.2 阿明的零花錢 464
9.2.3 購買年貨 467
9.2.4 調整隊形 470
9.2.5 均分紙牌 473
9.2.6 最小矩形面積 475
9.2.7 低價買股票 483
9.2.8 數字金字塔 486
9.2.9 方格取數 488
9.2.10 導彈防御系統 492
9.3 上機實踐 494
第10章 常見面試題及解答 497
10.1 數據結構類面試題 497
10.1.1 選擇題 497
10.1.2 編程題 499
10.2 經典算法類面試題 506
附錄 Dev-C++開發環境的使用 514

第1章 基礎算法思想
算法設計的任務就是：對一個具體的問題（如存錢問題），設計一種良好的算法（計算方法），獲取最佳的結果。常用的算法有：窮舉搜索法、遞歸法、回溯法、貪心法、分治法等。本章將使用生活中的常見實例，逐個介紹這些算法的基本思想。
在大部分教科書中，對“算法”（Algorithm）這個名詞都是很專業的解釋，例如，算法是對特定問題求解步驟的一種描述，算法是解決問題方法的精確描述等。其實，說得通俗一點，算法就是一種方案。例如，在現有的利率情況下，怎樣存錢最劃算？這時，可根據各種利率情況，以及今後一段時間對現金的使用情況，分別計算出各種情況下利息的收益，最後可得出最合算的一種存錢方案。這就是一種算法。1.1編程的靈魂：數據結構+算法說到編程，可能大家首先想到的就是程序設計語言。隨著計算機軟件技術的不斷發展，計算機程序設計語言層出不窮，常見的如Basic、VB、C、C++、C#、Java、Pascal、Delphi、PB等。
其實，編程語言只是一個很初級的工具。熟練地掌握這些編程語言中的一門，就好像學會了寫字。在現實生活中，會寫字的人不見得會寫出好文章，同樣道理，學會了一門（或多門）編程語言的使用并不一定就能編寫出好程序。那么，怎樣才能編寫出好的程序呢？這牽涉很多方面的問題，單從程序設計角度來看，可將程序理解為以下公式：
程序=數據結構+算法+程序設計語言
即首先需要根據程序要處理的數據（包括輸入和輸出的數據）設計數據結構，再設計相應的算法來實現程序要達到的功能，最後才是使用某一門程序設計語言來進行編碼。其中，設計數據結構和算法都是獨立于程序設計語言的，程序設計語言只完成最後的編碼工作。由此可以看出，程序設計中數據結構和算法是最重要的，是編程的靈魂。
提示：這里是按程序設計的概念來說的。一個項目是由若干個小程序組成的，從軟件工程的角度來看，上面的公式還需要加上更多的內容，如項目管理、質量控制、代碼規范等。
數據結構是算法實現的基礎，算法總是依賴于某種數據結構來實現的。往往是在研究一種算法的時候，構建了適合于這種算法的數據結構。一種數據結構如果脫離了算法，也就沒有存在的價值了。