书名：信息学竞赛宝典 数据结构基础
定价：89.9
ISBN：9787115635020
作者：张新华 梁靖韵 刘树明
版次：第1版
出版时间：2024-06

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



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