信息學競賽寶典 數據結構基礎

张新华

中学高级教师，信息学竞赛教练。取得浙江大学计算机科学与技术学士学位、厦门大学软件工程硕士学位，获得 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