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

内容提要

前言

第1章 链表

1.1 何谓链表

1.2 简单静态链表

1.3 动态链表

1.3.1 链表的建立

1.3.2 链表的显示

1.3.3 查找节点元素x的位置

1.3.4 返回链表的长度

1.3.5 获得节点元素值

1.3.6 节点的插入

1.3.7 节点的删除

1.3.8 释放链表

1.4 数组与链表的比较

1.5 课后练习

第2章 堆栈

2.1 堆栈的定义

2.2 数组仿真堆栈

2.3 单调栈

2.4 后序表达式

2.5 课后练习

第3章 队列

3.1 队列的定义

3.2 数组仿真队列

3.3 数组循环队列

3.4 单调队列

3.5 课后练习

第4章 树

4.1 树的介绍

4.1.1 树的概念及表示

4.1.2 树的相关术语

4.2 二叉树

4.2.1 二叉树的概念

4.2.2 二叉树的性质

4.3 二叉树的表示

4.3.1 二叉树数组表示法

4.3.2 二叉树结构体数组表示法

4.3.3 二叉树链表表示法

4.4 二叉树的遍历

4.4.1 二叉树的前序遍历

4.4.2 二叉树的中序遍历

4.4.3 二叉树的后序遍历

4.4.4 二叉树的图形化显示

4.4.5 已知前序、中序遍历序列求后序遍历序列

4.4.6 已知后序、中序遍历序列求前序遍历序列

4.4.7 已知前序、后序遍历序列求中序遍历序列

4.4.8 表达式处理

4.5 最优二叉树及应用

4.5.1 最优二叉树

4.5.2 哈夫曼编码

4.6 一般树转换成二叉树

4.7 堆排序的实现

4.8 优先队列的实现

4.9 树的一些应用

4.9.1 树的最小支配集

4.9.2 树的最小点覆盖

4.9.3 树的最大独立集

4.9.4 树的直径

4.9.5 树的重心

4.10 二叉查找树

第5章 图

5.1 图的介绍

5.1.1 图的基本概念

5.1.2 邻接数组表示法

5.1.3 加权边的图

5.2 前向星

5.2.1 前向星表示法

5.2.2 前向星的DFS

5.2.3 前向星的BFS

5.3 生成树问题

5.3.1 Kruskal算法

5.3.2 Prim算法

5.4 最短路问题

5.4.1 Dijkstra算法

5.4.2 Dijkstra算法的堆优化

5.4.3 Floyd算法

5.4.4 最小环问题

5.4.5 Bellman-Ford算法

5.4.6 SPFA及优化

5.5 拓扑排序

5.5.1 拓扑排序介绍

5.5.2 关键路径

5.6 DAG最长路

5.7 边和顶点的可行遍性

5.7.1 欧拉图

5.7.2 哈密尔顿环

5.8 无向图的一些应用

5.8.1 最大团问题

5.8.2 无向图的割点和桥

5.8.3 无向图的双连通分量

5.9 Kosaraju算法

5.10 树的一些应用

5.10.1 次小生成树算法

5.10.2 基环树

5.10.3 度限制生成树

5.10.4 最小树形图

第6章 哈希

6.1 哈希

6.2 字符串哈希

6.3 哈希树

第7章 树状数组

7.1 树状数组介绍

7.2 树状数组的简单应用

7.3 树状数组的区间更新

7.4 树状数组维护区间最值

7.5 树状数组求逆序对

7.6 树状数组的应用

7.7 二维树状数组

7.8 课后练习

第8章 并查集

8.1 基础并查集

8.2 带权并查集

8.3 种类并查集

8.4 课后练习

第9章 线段树

9.1 线段树的基本操作

9.2 懒惰标记的使用

9.3 线段树区间乘与加

9.4 课后练习

第10章 二分图

10.1 二分图的概念及判定

10.2 二分图最大匹配问题

10.3 最小点覆盖问题

10.4 最小边覆盖问题

10.5 最小路径覆盖问题

10.6 最佳匹配问题

10.7 课后练习