信息學競賽寶典 數據結構基礎
張新華 梁靖韻 劉樹明
買這商品的人也買了...
-
$2,150$2,043 -
$960$864 -
$700$665 -
$301並行演算法設計與性能優化
-
$454深入淺出 HTTPS : 從原理到實戰
-
$774$735 -
$602用“芯”探核基於龍芯的 Linux 內核探索解析
-
$1,600$1,520 -
$594$564 -
$708$673 -
$505CPU 設計實戰
-
$1,820$1,729 -
$594$564 -
$419$398 -
$648$616 -
$662算法訓練營:海量圖解 + 競賽刷題 (入門篇)
-
$468$445 -
$774$735 -
$534$507 -
$254程序員的數學4:圖論入門
-
$434程序設計競賽專題挑戰教程
-
$407程序員的制勝技
-
$806Linux 源碼趣讀
-
$454CPU 眼裡的 C/C++
-
$419$398
相關主題
商品描述
數據結構是電腦存儲、組織數據的方式,往往同高效的檢索算法和索引技術有關。學習和掌握數據結構的相關知識,使我們能夠更好地運用電腦來解決實際問題。
為了提高讀者的學習效率,本書直接從各類競賽真題入手,以精練而準確的語言、全面細致地介紹了信息學競賽中經常用到的數據結構類型,包括鏈表、堆棧、隊列、樹、圖等。本書精挑細選、由淺入深地安排了相關習題。考慮讀者接受水平的差異,一般在引入新知識點的題目時,本書會提供該題目的完整參考代碼,但隨著讀者對此知識點的理解逐步加深,後續的同類型題目將逐步向僅提供算法思路、提供偽代碼和無任何提示的方式轉變。此外,對於一些思維跨度較大的題目,本書會酌情給予讀者一定的提示。
本書可以與《信息學競賽寶典 基礎算法》同步學習,也可以作為有一定編程基礎的讀者學習數據結構算法的獨立用書。
作者簡介
张新华
中学高级教师,信息学竞赛教练。取得浙江大学计算机科学与技术学士学位、厦门大学软件工程硕士学位,获得 2009年普通高中信息技术现场优质课比赛全国一等奖。培养的学生多次获得全国青少年信息学奥赛国家一等奖及亚洲与太平洋地区信息学奥赛奖牌。著有“信息学竞赛宝典”系列书。开发了三维图形化 C++ 编程工具 Dev-C++ 智能
开发平台和 Python 可视化界面设计软件 Visual Python。
梁靖韵
中学高级教师,高级程序员,取得华南师范大学硕士学位,入选广州市“百千万人才培养工程”第二批名教师培养对象。长期从事信息学竞赛、计算机作品比赛与科技创新竞赛辅导工作。
刘树明
深圳市第二实验学校信息技术教师,二十一世纪教育网创始人。精通 C++、C#、Python、PHP 语言编程,有大量大型软件系统的研发经验,独立或者与他人一起研发的排课系统、阅卷系统等教育教学软件在国内享有良好口碑。
目錄大綱
第 1章 鏈表
1.1 何謂鏈表 / 1
1.2 簡單靜態鏈表 / 2
1.3 動態鏈表 / 3
1.3.1 鏈表的建立 / 3
1.3.2 鏈表的顯示 / 4
1.3.3 查找節點元素x的位置 / 4
1.3.4 返回鏈表的長度 / 4
1.3.5 獲得節點元素值 / 5
1.3.6 節點的插入 / 5
1.3.7 節點的刪除 / 6
1.3.8 釋放鏈表 / 7
1.4 數組與鏈表的比較 / 7
1.5 課後練習 / 8
第 2章 堆棧
2.1 堆棧的定義 / 9
2.2 數組模擬堆棧 / 9
2.3 單調棧 / 12
2.4 後序表達式 / 16
2.5 課後練習 / 19
第3章 隊列
3.1 隊列的定義 / 21
3.2 數組模擬隊列 / 21
3.3 數組循環隊列 / 23
3.4 單調隊列 / 29
3.5 課後練習 / 31
第4章 樹
4.1 樹的介紹 / 32
4.1.1 樹的概念及表示 / 32
4.1.2 樹的相關術語 / 33
4.2 二叉樹 / 34
4.2.1 二叉樹的概念 / 34
4.2.2 二叉樹的性質 / 35
4.3 二叉樹的表示 / 42
4.3.1 二叉樹數組表示法 / 42
4.3.2 二叉樹結構體數組表示法 / 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 最優二叉樹及應用 / 71
4.5.1 最優二叉樹 / 71
4.5.2 哈夫曼編碼 / 72
4.6 一般樹轉換成二叉樹 / 74
4.7 堆排序的實現 / 76
4.8 優先隊列的實現 / 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 鄰接數組表示法 / 111
5.1.3 加權邊的圖 / 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算法的堆優化 / 132
5.4.3 Floyd算法 / 133
5.4.4 最小環問題 / 135
5.4.5 Bellman-Ford算法 / 137
5.4.6 SPFA及優化 / 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 哈密爾頓環 / 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 基環樹 / 200
5.10.3 度限制生成樹 / 206
5.10.4 最小樹形圖 / 208
第6章 哈希
6.1 哈希 / 215
6.2 字符串哈希 / 223
6.3 哈希樹 / 228
第7章 樹狀數組
7.1 樹狀數組介紹 / 230
7.2 樹狀數組的簡單應用 / 232
7.3 樹狀數組的區間更新 / 236
7.4 樹狀數組維護區間最值 / 239
7.5 樹狀數組求逆序對 / 244
7.6 樹狀數組的應用 / 246
7.7 二維樹狀數組 / 249
7.8 課後練習 / 253
第8章 並查集
8.1 基礎並查集 / 254
8.2 帶權並查集 / 259
8.3 種類並查集 / 261
8.4 課後練習 / 266
第9章 線段樹
9.1 線段樹的基本操作 / 267
9.2 懶惰標記的使用 / 282
9.3 線段樹區間乘與加 / 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