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

第 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