定 價(jià)：32 元
叢書名：大數(shù)據(jù)技術(shù)系列叢書
- 作者：雷小宇
- 出版時(shí)間：2023/6/1
- ISBN：9787560668741
- 出 版 社：西安電子科技大學(xué)出版社
- 中圖法分類：TP301.6
- 頁碼：180
- 紙張：
- 版次：1
- 開本：16開
本書是一本深入淺出，通俗易懂，原理性、趣味性和實(shí)用性相結(jié)合的算法設(shè)計(jì)教材。本書在介紹常見數(shù)據(jù)結(jié)構(gòu)基本知識(shí)的基礎(chǔ)上，著重從“易讀、易學(xué)、易用”和培養(yǎng)“問題解決能力”兩方面對(duì)常見算法進(jìn)行了有效組織與闡述。
本書是銜接本科生“算法與數(shù)據(jù)結(jié)構(gòu)”與研究生“算法分析與設(shè)計(jì)”兩門課程的、面向高年級(jí)本科生的算法設(shè)計(jì)教材。本書內(nèi)容設(shè)計(jì)合理，既包括常見的算法介紹，又包括流算法、圖算法等流行算法的介紹；講解清晰、透徹，能夠幫助初學(xué)者建立信心，快速入手。本書采用“問題導(dǎo)引”的方式依次介紹數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識(shí)，分治、枚舉、貪心、遞歸等基礎(chǔ)算法，排序、查找、字符串匹配、圖論、動(dòng)態(tài)規(guī)劃等常見算法，計(jì)算幾何基礎(chǔ)以及流算法、圖算法等高級(jí)算法。
本書適合作為高等院校各專業(yè)本科生的算法設(shè)計(jì)教材，也可以作為廣大計(jì)算機(jī)愛好者及各類自學(xué)人員的參考資料。
近年來，隨著ACM國際大學(xué)生程序設(shè)計(jì)競(jìng)賽(ACM ICPC)在國內(nèi)深入推廣和中國大學(xué)生程序設(shè)計(jì)競(jìng)賽(CCPC)以及藍(lán)橋杯程序設(shè)計(jì)競(jìng)賽的興起，參加程序設(shè)計(jì)競(jìng)賽的學(xué)生越來越多。程序設(shè)計(jì)競(jìng)賽主要考察大學(xué)生分析問題和運(yùn)用計(jì)算機(jī)解決實(shí)際問題的綜合能力，而算法設(shè)計(jì)是程序設(shè)計(jì)中的重要環(huán)節(jié)，算法實(shí)現(xiàn)能力對(duì)于參加程序設(shè)計(jì)競(jìng)賽的同學(xué)來說尤為重要。尤其是ACM ICPC對(duì)大學(xué)生的算法設(shè)計(jì)能力要求更高，更強(qiáng)調(diào)算法在有限存儲(chǔ)空間下運(yùn)行的高效性。該競(jìng)賽涉及的知識(shí)也相當(dāng)廣泛，包括程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學(xué)、算法分析與設(shè)計(jì)、數(shù)論、圖論、操作系統(tǒng)、概率論、計(jì)算幾何等。
中國人民解放軍陸軍工程大學(xué)從2012年正式參加程序設(shè)計(jì)競(jìng)賽并開展了正式集中訓(xùn)練，2013年夏天在南京理工大學(xué)余立功老師的幫助下搭建了學(xué)校的OnlineJudge實(shí)踐平臺(tái)，從此程序設(shè)計(jì)課程和競(jìng)賽的實(shí)踐教學(xué)都依托此平臺(tái)開展，吸引了大批熱衷于程序設(shè)計(jì)和算法競(jìng)賽的同學(xué)。學(xué)校程序設(shè)計(jì)競(jìng)賽團(tuán)隊(duì)的整體水平逐年提高，多次在ACM ICPC區(qū)域賽中摘得獎(jiǎng)牌。本書以歷年培訓(xùn)內(nèi)容和OnlineJudge實(shí)踐平臺(tái)資源為基礎(chǔ)，精選數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)，分治、遞歸、枚舉、貪心等基礎(chǔ)算法，排序、查找、字符串匹配和高精度運(yùn)算、圖論、動(dòng)態(tài)規(guī)劃等常見算法，計(jì)算幾何基礎(chǔ)以及流算法、圖算法、信息匹配等高級(jí)算法等內(nèi)容，精心剖析各知識(shí)點(diǎn)，通過大量實(shí)例講解常見問題的解決方案和算法設(shè)計(jì)方法。在編寫過程中，力求將復(fù)雜的知識(shí)通過淺顯易懂的語言來表述，從而提高讀者的閱讀興趣。
本書通過對(duì)實(shí)例的分析和對(duì)數(shù)據(jù)結(jié)構(gòu)、算法的討論，著重培養(yǎng)學(xué)生解決問題的思維方式、解決問題的能力以及面對(duì)問題時(shí)的應(yīng)變能力。
本書由雷小宇主編，第1章由鄭雨編寫，第2章和第4章由蔣園園編寫，第3章、第8章和第5.2節(jié)由雷小宇編寫，第5.1節(jié)和第6章由張賽男編寫，第7章和第9章由胡琨編寫。雷小宇對(duì)整個(gè)書稿進(jìn)行了校對(duì)。書中的所有案例和代碼由胡哲、孫毅、徐有為、王楠、李明倩和楊義鑫等同學(xué)調(diào)試通過，在此對(duì)他們的辛勤付出表示衷心的感謝。在本書編寫過程中還得到了許多國內(nèi)前輩、同行及CSDN論壇許多版主的指導(dǎo)，因篇幅有限不一一列出，一并表示誠摯的謝意！
在此，衷心感謝所有為此書出版做出貢獻(xiàn)的人！
因編者水平有限，書中疏漏之處在所難免，歡迎讀者提出意見和建議，以便我們及時(shí)更正。
編 者
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 算法性能評(píng)價(jià) 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：孿生素?cái)?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)計(jì) 73
4.2 二分查找 75
4.2.1 二分查找的基本概念 75
4.2.2 二分查找的應(yīng)用舉例1：查找元素x 75
4.2.3 二分查找的應(yīng)用舉例2：統(tǒng)計(jì)數(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 簡(jiǎn)單計(jì)算方法—“列豎式” 96
5.2.2 大數(shù)求和的程序?qū)崿F(xiàn) 97
5.2.3 階乘的精確計(jì)算 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章 動(dòng)態(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 滾動(dòng)數(shù)組 135
7.4 動(dòng)態(tài)規(guī)劃應(yīng)用舉例1：倉庫的警犬 136
7.5 動(dòng)態(tài)規(guī)劃應(yīng)用舉例2：火力打擊 137
7.6 本章小結(jié) 138
第8章 計(jì)算幾何基礎(chǔ)* 140
8.1 幾何基礎(chǔ)概念 140
8.1.1 點(diǎn)、直線、線段和向量 140
8.1.2 向量的運(yùn)算 141
8.1.3 常見幾何問題計(jì)算 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章 高級(jí)算法 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 自動(dòng)機(jī) 169
9.4 本章小結(jié) 170
參考文獻(xiàn) 172
書單推薦
