信息學競賽寶典 數(shù)據(jù)結(jié)構(gòu)基礎
定 價：89.9 元
- 作者：張新華 梁靖韻 劉樹明
- 出版時間：2024/6/1
- ISBN：9787115635020
- 出 版 社：人民郵電出版社
- 中圖法分類：TP3
- 頁碼：314
- 紙張：
- 版次：01
- 開本：16開
數(shù)據(jù)結(jié)構(gòu)是計算機存儲、組織數(shù)據(jù)的方式，往往同高效的檢索算法和索引技術(shù)有關。學習和掌握數(shù)據(jù)結(jié)構(gòu)的相關知識，使我們能夠更好地運用計算機來解決實際問題。
為了提高讀者的學習效率，本書直接從各類競賽真題入手，以精練而準確的語言、全面細致地介紹了信息學競賽中經(jīng)常用到的數(shù)據(jù)結(jié)構(gòu)類型，包括鏈表、堆棧、隊列、樹、圖等。本書精挑細選、由淺入深地安排了相關習題。考慮讀者接受水平的差異，一般在引入新知識點的題目時，本書會提供該題目的完整參考代碼，但隨著讀者對此知識點的理解逐步加深，后續(xù)的同類型題目將逐步向僅提供算法思路、提供偽代碼和無任何提示的方式轉(zhuǎn)變。此外，對于一些思維跨度較大的題目，本書會酌情給予讀者一定的提示。
本書可以與《信息學競賽寶典 基礎算法》同步學習，也可以作為有一定編程基礎的讀者學習數(shù)據(jù)結(jié)構(gòu)算法的獨立用書。
● 包含 NOIP 中常用的數(shù)據(jù)結(jié)構(gòu)類型
● 直接從各類競賽真題入手
● 配有 PPT+ 源碼
● 提供對應在線題庫
配套資源豐富，全面地介紹了比較常見的數(shù)據(jù)結(jié)構(gòu)類型，為讀者了解和參與信息學競賽提供了全面的引導，是信息學愛好者深入學習的很好選擇。
張新華
中學高級教師，信息學競賽教練。取得浙江大學計算機科學與技術(shù)學士學位、廈門大學軟件工程碩士學位，獲得 2009年普通高中信息技術(shù)現(xiàn)場優(yōu)質(zhì)課比賽全國一等獎。培養(yǎng)的學生多次獲得全國青少年信息學奧賽國家一等獎及亞洲與太平洋地區(qū)信息學奧賽獎牌。著有“信息學競賽寶典”系列書。開發(fā)了三維圖形化 C++ 編程工具 Dev-C++ 智能
開發(fā)平臺和 Python 可視化界面設計軟件 Visual Python。
梁靖韻
中學高級教師，高級程序員，取得華南師范大學碩士學位，入選廣州市“百千萬人才培養(yǎng)工程”第二批名教師培養(yǎng)對象。長期從事信息學競賽、計算機作品比賽與科技創(chuàng)新競賽輔導工作。
劉樹明
深圳市第二實驗學校信息技術(shù)教師，二十一世紀教育網(wǎng)創(chuàng)始人。精通 C++、C#、Python、PHP 語言編程，有大量大型軟件系統(tǒng)的研發(fā)經(jīng)驗，獨立或者與他人一起研發(fā)的排課系統(tǒng)、閱卷系統(tǒng)等教育教學軟件在國內(nèi)享有良好口碑。
第 1章 鏈表
1.1 何謂鏈表 / 1
1.2 簡單靜態(tài)鏈表 / 2
1.3 動態(tài)鏈表 / 3
1.3.1 鏈表的建立 / 3
1.3.2 鏈表的顯示 / 4
1.3.3 查找節(jié)點元素x的位置 / 4
1.3.4 返回鏈表的長度 / 4
1.3.5 獲得節(jié)點元素值 / 5
1.3.6 節(jié)點的插入 / 5
1.3.7 節(jié)點的刪除 / 6
1.3.8 釋放鏈表 / 7
1.4 數(shù)組與鏈表的比較 / 7
1.5 課后練習 / 8
第 2章 堆棧
2.1 堆棧的定義 / 9
2.2 數(shù)組仿真堆棧 / 9
2.3 單調(diào)�！�/ 12
2.4 后序表達式 / 16
2.5 課后練習 / 19
第3章 隊列
3.1 隊列的定義 / 21
3.2 數(shù)組仿真隊列 / 21
3.3 數(shù)組循環(huán)隊列 / 23
3.4 單調(diào)隊列 / 29
3.5 課后練習 / 31
第4章 樹
4.1 樹的介紹 / 32
4.1.1 樹的概念及表示 / 32
4.1.2 樹的相關術(shù)語 / 33
4.2 二叉樹 / 34
4.2.1 二叉樹的概念 / 34
4.2.2 二叉樹的性質(zhì) / 35
4.3 二叉樹的表示 / 42
4.3.1 二叉樹數(shù)組表示法 / 42
4.3.2 二叉樹結(jié)構(gòu)體數(shù)組表示法 / 45
4.3.3 二叉樹鏈表表示法 / 48
4.4 二叉樹的遍歷 / 50
4.4.1 二叉樹的前序遍歷 / 50
4.4.2 二叉樹的中序遍歷 / 53
4.4.3 二叉樹的后序遍歷 / 54
4.4.4 二叉樹的圖形化顯示 / 55
4.4.5 已知前序、中序遍歷序列求后序遍歷序列 / 61
4.4.6 已知后序、中序遍歷序列求前序遍歷序列 / 62
4.4.7 已知前序、后序遍歷序列求中序遍歷序列 / 63
4.4.8 表達式處理 / 66
4.5 最優(yōu)二叉樹及應用 / 71
4.5.1 最優(yōu)二叉樹 / 71
4.5.2 哈夫曼編碼 / 72
4.6 一般樹轉(zhuǎn)換成二叉樹 / 74
4.7 堆排序的實現(xiàn) / 76
4.8 優(yōu)先隊列的實現(xiàn) / 80
4.9 樹的一些應用 / 86
4.9.1 樹的最小支配集 / 86
4.9.2 樹的最小點覆蓋 / 91
4.9.3 樹的最大獨立集 / 93
4.9.4 樹的直徑 / 95
4.9.5 樹的重心 / 100
4.10 二叉查找樹 / 102
第5章 圖
5.1 圖的介紹 / 109
5.1.1 圖的基本概念 / 109
5.1.2 鄰接數(shù)組表示法 / 111
5.1.3 加權(quán)邊的圖 / 113
5.2 前向星 / 113
5.2.1 前向星表示法 / 113
5.2.2 前向星的DFS / 117
5.2.3 前向星的BFS / 120
5.3 生成樹問題 / 122
5.3.1 Kruskal算法 / 123
5.3.2 Prim算法 / 126
5.4 最短路問題 / 128
5.4.1 Dijkstra算法 / 128
5.4.2 Dijkstra算法的堆優(yōu)化 / 132
5.4.3 Floyd算法 / 133
5.4.4 最小環(huán)問題 / 135
5.4.5 Bellman-Ford算法 / 137
5.4.6 SPFA及優(yōu)化 / 140
5.5 拓撲排序 / 147
5.5.1 拓撲排序介紹 / 147
5.5.2 關鍵路徑 / 152
5.6 DAG最長路 / 157
5.7 邊和頂點的可行遍性 / 159
5.7.1 歐拉圖 / 159
5.7.2 哈密爾頓環(huán) / 164
5.8 無向圖的一些應用 / 171
5.8.1 最大團問題 / 171
5.8.2 無向圖的割點和橋 / 175
5.8.3 無向圖的雙連通分量 / 185
5.9 Kosaraju算法 / 191
5.10 樹的一些應用 / 194
5.10.1 次小生成樹算法 / 194
5.10.2 基環(huán)樹 / 200
5.10.3 度限制生成樹 / 206
5.10.4 最小樹形圖 / 208
第6章 哈希
6.1 哈�！�/ 215
6.2 字符串哈�！�/ 223
6.3 哈希樹 / 228
第7章 樹狀數(shù)組
7.1 樹狀數(shù)組介紹 / 230
7.2 樹狀數(shù)組的簡單應用 / 232
7.3 樹狀數(shù)組的區(qū)間更新 / 236
7.4 樹狀數(shù)組維護區(qū)間最值 / 239
7.5 樹狀數(shù)組求逆序?qū)Α? 244
7.6 樹狀數(shù)組的應用 / 246
7.7 二維樹狀數(shù)組 / 249
7.8 課后練習 / 253
第8章 并查集
8.1 基礎并查集 / 254
8.2 帶權(quán)并查集 / 259
8.3 種類并查集 / 261
8.4 課后練習 / 266
第9章 線段樹
9.1 線段樹的基本操作 / 267
9.2 懶惰標記的使用 / 282
9.3 線段樹區(qū)間乘與加 / 284
9.4 課后練習 / 287
第 10章 二分圖
10.1 二分圖的概念及判定 / 288
10.2 二分圖最大匹配問題 / 291
10.3 最小點覆蓋問題 / 297
10.4 最小邊覆蓋問題 / 299
10.5 最小路徑覆蓋問題 / 303
10.6 最佳匹配問題 / 309
10.7 課后練習 / 314
書單推薦
