信息学竞赛宝典 数据结构基础

作者简介

张新华 中学高级教师，信息学竞赛教练。取得浙江大学计算机科学与技术学士学位、厦门大学软件工程硕士学位，获得 2009年普通高中信息技术现场优质课比赛全国一等奖。培养的学生多次获得全国青少年信息学奥赛国家一等奖及亚洲与太平洋地区信息学奥赛奖牌。著有“信息学竞赛宝典”系列书。开发了三维图形化 C++ 编程工具 Dev-C++ 智能 开发平台和 Python 可视化界面设计软件 Visual Python。 梁靖韵 中学高级教师，高级程序员，取得华南师范大学硕士学位，入选广州市“百千万人才培养工程”第二批名教师培养对象。长期从事信息学竞赛、计算机作品比赛与科技创新竞赛辅导工作。 刘树明 深圳市第二实验学校信息技术教师，二十一世纪教育网创始人。精通 C++、C#、Python、PHP 语言编程，有大量大型软件系统的研发经验，独立或者与他人一起研发的排课系统、阅卷系统等教育教学软件在国内享有良好口碑。

内容简介

● 包含 NOIP 中常用的数据结构类型 ● 直接从各类竞赛真题入手 ● 配有 PPT+ 源码 ● 提供对应在线题库 配套资源丰富，全面地介绍了比较常见的数据结构类型，为读者了解和参与信息学竞赛提供了全面的引导，是信息学爱好者深入学习的很好选择。

● 包含 NOIP 中常用的数据结构类型 ● 直接从各类竞赛真题入手 ● 配有 PPT 源码 ● 提供对应在线题库 配套资源丰富，全面地介绍了比较常见的数据结构类型，为读者了解和参与信息学竞赛提供了全面的引导，是信息学爱好者深入学习的很好选择。

书籍目录

第 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