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

数据结构是计算机存储、组织数据的方式，往往同高效的检索算法和索引技术有关。学习和掌握数据结构的相关知识，使我们能够更好地运用计算机来解决实际问题。 为了提高读者的学习效率，本书直接从各类竞赛真题入手，以精练而准确的语言、全面细致地介绍了信息学竞赛中经常用到的数据结构类型，包括链表、堆栈、队列、树、图等。本书精挑细选、由浅入深地安排了相关习题。考虑读者接受水平的差异，一般在引入新知识点的题目时，本书会提供该题目的完整参考代码，但随着读者对此知识点的理解逐步加深，后续的同类型题目将逐步向仅提供算法思路、提供伪代码和无任何提示的方式转变。此外，对于一些思维跨度较大的题目，本书会酌情给予读者一定的提示。 本书可以与《信息学竞赛宝典　基础算法》同步学习，也可以作为有一定编程基础的读者学习数据结构算法的独立用书。

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