定 價：32 元
叢書名：大數(shù)據(jù)技術(shù)系列叢書
- 作者：雷小宇
- 出版時間：2023/6/1
- ISBN：9787560668741
- 出 版 社：西安電子科技大學(xué)出版社
- 中圖法分類：TP301.6
- 頁碼：180
- 紙張：
- 版次：1
- 開本：16開
本書是一本深入淺出，通俗易懂，原理性、趣味性和實(shí)用性相結(jié)合的算法設(shè)計教材。本書在介紹常見數(shù)據(jù)結(jié)構(gòu)基本知識的基礎(chǔ)上，著重從“易讀、易學(xué)、易用”和培養(yǎng)“問題解決能力”兩方面對常見算法進(jìn)行了有效組織與闡述。
本書是銜接本科生“算法與數(shù)據(jù)結(jié)構(gòu)”與研究生“算法分析與設(shè)計”兩門課程的、面向高年級本科生的算法設(shè)計教材。本書內(nèi)容設(shè)計合理，既包括常見的算法介紹，又包括流算法、圖算法等流行算法的介紹；講解清晰、透徹，能夠幫助初學(xué)者建立信心，快速入手。本書采用“問題導(dǎo)引”的方式依次介紹數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識，分治、枚舉、貪心、遞歸等基礎(chǔ)算法，排序、查找、字符串匹配、圖論、動態(tài)規(guī)劃等常見算法，計算幾何基礎(chǔ)以及流算法、圖算法等高級算法。
本書適合作為高等院校各專業(yè)本科生的算法設(shè)計教材，也可以作為廣大計算機(jī)愛好者及各類自學(xué)人員的參考資料。
近年來，隨著ACM國際大學(xué)生程序設(shè)計競賽(ACM ICPC)在國內(nèi)深入推廣和中國大學(xué)生程序設(shè)計競賽(CCPC)以及藍(lán)橋杯程序設(shè)計競賽的興起，參加程序設(shè)計競賽的學(xué)生越來越多。程序設(shè)計競賽主要考察大學(xué)生分析問題和運(yùn)用計算機(jī)解決實(shí)際問題的綜合能力，而算法設(shè)計是程序設(shè)計中的重要環(huán)節(jié)，算法實(shí)現(xiàn)能力對于參加程序設(shè)計競賽的同學(xué)來說尤為重要。尤其是ACM ICPC對大學(xué)生的算法設(shè)計能力要求更高，更強(qiáng)調(diào)算法在有限存儲空間下運(yùn)行的高效性。該競賽涉及的知識也相當(dāng)廣泛，包括程序設(shè)計、數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學(xué)、算法分析與設(shè)計、數(shù)論、圖論、操作系統(tǒng)、概率論、計算幾何等。
中國人民解放軍陸軍工程大學(xué)從2012年正式參加程序設(shè)計競賽并開展了正式集中訓(xùn)練，2013年夏天在南京理工大學(xué)余立功老師的幫助下搭建了學(xué)校的OnlineJudge實(shí)踐平臺，從此程序設(shè)計課程和競賽的實(shí)踐教學(xué)都依托此平臺開展，吸引了大批熱衷于程序設(shè)計和算法競賽的同學(xué)。學(xué)校程序設(shè)計競賽團(tuán)隊(duì)的整體水平逐年提高，多次在ACM ICPC區(qū)域賽中摘得獎牌。本書以歷年培訓(xùn)內(nèi)容和OnlineJudge實(shí)踐平臺資源為基礎(chǔ)，精選數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)，分治、遞歸、枚舉、貪心等基礎(chǔ)算法，排序、查找、字符串匹配和高精度運(yùn)算、圖論、動態(tài)規(guī)劃等常見算法，計算幾何基礎(chǔ)以及流算法、圖算法、信息匹配等高級算法等內(nèi)容，精心剖析各知識點(diǎn)，通過大量實(shí)例講解常見問題的解決方案和算法設(shè)計方法。在編寫過程中，力求將復(fù)雜的知識通過淺顯易懂的語言來表述，從而提高讀者的閱讀興趣。
本書通過對實(shí)例的分析和對數(shù)據(jù)結(jié)構(gòu)、算法的討論，著重培養(yǎng)學(xué)生解決問題的思維方式、解決問題的能力以及面對問題時的應(yīng)變能力。
本書由雷小宇主編，第1章由鄭雨編寫，第2章和第4章由蔣園園編寫，第3章、第8章和第5.2節(jié)由雷小宇編寫，第5.1節(jié)和第6章由張賽男編寫，第7章和第9章由胡琨編寫。雷小宇對整個書稿進(jìn)行了校對。書中的所有案例和代碼由胡哲、孫毅、徐有為、王楠、李明倩和楊義鑫等同學(xué)調(diào)試通過，在此對他們的辛勤付出表示衷心的感謝。在本書編寫過程中還得到了許多國內(nèi)前輩、同行及CSDN論壇許多版主的指導(dǎo)，因篇幅有限不一一列出，一并表示誠摯的謝意！
在此，衷心感謝所有為此書出版做出貢獻(xiàn)的人！
因編者水平有限，書中疏漏之處在所難免，歡迎讀者提出意見和建議，以便我們及時更正。
編 者
2023年2月
第1章 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 1
1.1 常見的數(shù)據(jù)結(jié)構(gòu) 1
1.1.1 數(shù)組 1
1.1.2 鏈表 3
1.1.3 堆棧和隊(duì)列 6
1.1.4 樹和圖 9
1.1.5 散列表 15
1.2 算法 16
1.2.1 算法及性質(zhì) 16
1.2.2 算法性能評價 18
1.3 本章小結(jié) 20
第2章 基礎(chǔ)算法 21
2.1 分治法 21
2.1.1 分治法的基本概念 21
2.1.2 分治法應(yīng)用舉例1：循環(huán)賽日程表 22
2.1.3 分治法應(yīng)用舉例2：大整數(shù)乘法 24
2.2 遞歸法 28
2.2.1 遞歸法的基本概念 28
2.2.2 遞歸應(yīng)用舉例1：斐波那契數(shù)列 30
2.2.3 遞歸優(yōu)化—斐波那契數(shù)列的優(yōu)化求解 32
2.2.4 遞歸應(yīng)用舉例2：飲料換購 35
2.2.5 遞歸應(yīng)用舉例3：輸出全排列 36
2.3 枚舉法 38
2.3.1 枚舉法的基本概念 38
2.3.2 枚舉法應(yīng)用舉例1：百雞百錢 38
2.3.3 枚舉法應(yīng)用舉例2：雞兔同籠問題 39
2.3.4 枚舉法應(yīng)用舉例3：水仙花數(shù) 41
2.3.5 枚舉法應(yīng)用舉例4：孿生素數(shù) 42
2.3.6 枚舉法應(yīng)用舉例5：最大公約數(shù) 43
2.4 貪心法 45
2.4.1 貪心法的基本概念 45
2.4.2 貪心法應(yīng)用舉例1：找零錢 46
2.4.3 貪心法應(yīng)用舉例2：刪除k位數(shù)字 47
2.5 本章小結(jié) 48
第3章 排序算法 50
3.1 排序的相關(guān)概念 50
3.2 冒泡排序 50
3.2.1 冒泡排序算法描述 51
3.2.2 冒泡排序程序?qū)崿F(xiàn)舉例 52
3.2.3 冒泡排序算法分析 55
3.3 選擇排序 55
3.3.1 選擇排序算法描述 56
3.3.2 選擇排序算法實(shí)現(xiàn)舉例 57
3.3.3 選擇排序算法分析 59
3.4 插入排序 60
3.4.1 插入排序算法描述 60
3.4.2 插入排序算法實(shí)現(xiàn)舉例 61
3.4.3 插入排序算法分析 62
3.5 歸并排序 62
3.5.1 歸并排序算法描述 63
3.5.2 歸并排序算法實(shí)現(xiàn)舉例 63
3.5.3 歸并排序算法分析 66
3.6 快速排序 66
3.6.1 快速排序算法描述 66
3.6.2 快速排序算法實(shí)現(xiàn)舉例 68
3.6.3 快速排序算法分析 70
3.7 排序算法的性能比較 70
3.8 本章小結(jié) 70
第4章 查找 72
4.1 順序查找 72
4.1.1 順序查找的基本概念 72
4.1.2 順序查找的應(yīng)用舉例1：找最大值 72
4.1.3 順序查找的應(yīng)用舉例2：字母統(tǒng)計 73
4.2 二分查找 75
4.2.1 二分查找的基本概念 75
4.2.2 二分查找的應(yīng)用舉例1：查找元素x 75
4.2.3 二分查找的應(yīng)用舉例2：統(tǒng)計數(shù)字在有序數(shù)組中出現(xiàn)的次數(shù) 77
4.3 圖的搜索 79
4.3.1 DFS的基本概念 79
4.3.2 BFS的基本概念 81
4.3.3 DFS與BFS的應(yīng)用舉例1：最小高度樹 82
4.3.4 DFS與BFS的應(yīng)用舉例2：水壺問題 86
4.4 本章小結(jié) 89
第5章 字符串匹配和高精度運(yùn)算 91
5.1 字符串匹配 91
5.1.1 樸素模式匹配 91
5.1.2 KMP模式匹配 93
5.2 高精度運(yùn)算 96
5.2.1 簡單計算方法—“列豎式” 96
5.2.2 大數(shù)求和的程序?qū)崿F(xiàn) 97
5.2.3 階乘的精確計算 100
5.3 本章小結(jié) 102
第6章 圖論算法 104
6.1 最小生成樹 104
6.2 最短路徑 110
6.2.1 Dijkstra算法 111
6.2.2 使用優(yōu)先隊(duì)列的Dijkstra算法 116
6.2.3 Bellman-Ford算法 117
6.2.4 Floyd算法 120
6.3 最大匹配—匈牙利算法 124
6.4 本章小結(jié) 127
第7章 動態(tài)規(guī)劃算法 128
7.1 基本思想和概念 128
7.2 算法原理和步驟 129
7.3 0-1背包問題 132
7.3.1 0-1背包問題的多階段決策 132
7.3.2 規(guī)劃方向 133
7.3.3 滾動數(shù)組 135
7.4 動態(tài)規(guī)劃應(yīng)用舉例1：倉庫的警犬 136
7.5 動態(tài)規(guī)劃應(yīng)用舉例2：火力打擊 137
7.6 本章小結(jié) 138
第8章 計算幾何基礎(chǔ)* 140
8.1 幾何基礎(chǔ)概念 140
8.1.1 點(diǎn)、直線、線段和向量 140
8.1.2 向量的運(yùn)算 141
8.1.3 常見幾何問題計算 143
8.2 包含關(guān)系 147
8.2.1 判斷圖形是否在矩形中 147
8.2.2 判斷圖形是否在多邊形內(nèi)部 147
8.3 凸包 148
8.3.1 凸包的定義 148
8.3.2 求解凸包的算法 148
8.4 本章小結(jié) 154
第9章 高級算法 155
9.1 流算法 155
9.1.1 數(shù)據(jù)流的基本概念 155
9.1.2 數(shù)據(jù)流的基本問題—確定頻繁元素 156
9.1.3 Lossy Counting和Sticky Sampling算法 158
9.2 圖算法 159
9.2.1 中心性算法 160
9.2.2 社群發(fā)現(xiàn)算法 164
9.3 信息匹配 166
9.3.1 窮舉法 168
9.3.2 自動機(jī) 169
9.4 本章小結(jié) 170
參考文獻(xiàn) 172
書單推薦
