本书以数据结构基础和算法设计方法为知识单元，系统地介绍了数据结构与算法的基本知识及套用，简明扼要地阐释了计算机算法的设计与分析方法。本书的主要内容包括线性表、树、图等基础数据结构，同时也包括一些实用性较强的算法及高级数据结构，如并查集、伸展树等。以经典问题算法为例，书中分类介绍了算法设计方法以及查找与排序算法等。编者结合ACM国际大学生程式设计竞赛的需求，对各章节知识的灵活套用进行了详细的分析，用丰富的实例帮助读者由浅入深、快速地掌握算法设计的技巧，提升算法设计能力。本书的算法全部採用C语言描述，且在DevC++中测试通过，习题安排上注重能力培养和实战训练的需求。

第1章绪论

1.1数据结构简介

1.1.1数据结构课程的内容

1.1.2数据结构的基本概念和术语

1.2抽象数据类型

1.3算法的执行效率及其度量

1.3.1算法

1.3.2算法设计的要求

1.3.3算法效率的度量

1.3.4算法的存储空间需求

1.4算法分析

1.4.1算法设计与分析的重要性

1.4.2一个简单的算法分析设计实例

习题

ACM/ICPC实战练习

第2章线性结构

2.1线性表

2.1.1线性表的定义

2.1.2线性表的抽象数据类型

2.1.3线性表的存储结构

2.2线性表的顺序存储及运算实现

2.2.1顺序表

2.2.2顺序表上基本运算的实现

2.2.3顺序表套用举例

2.3线性表的链式存储和运算实现

2.3.1单鍊表

2.3.2单鍊表上基本运算的实现

2.3.3循环鍊表

2.3.4双向鍊表

2.3.5静态鍊表

2.3.6单鍊表套用举例

2.3.7线性表实现方法比较

2.4栈

2.4.1顺序栈

2.4.2链式栈

2.4.3栈的套用举例

2.4.4栈与递归

2.5伫列

2.5.1顺序伫列

2.5.2链式伫列

2.5.3基于伫列的算法设计实例

2.6数组

2.6.1数组的定义

2.6.2数组的顺序表示和实现

2.6.3特殊矩阵的压缩存储

习题

ACM/ICPC实战练习

第3章字元串

3.1串类型定义

3.2串的表示和实现

3.2.1串的定长顺序存储结构及其基本运算实现

3.2.2串的堆存储结构及其基本运算实现

3.2.3串的链式存储结构及其基本运算实现

3.3串的模式匹配算法

3.3.1朴素匹配算法

3.3.2KMP算法

3.3.3基于KMP算法的套用举例

习题

ACM/ICPC实战练习

第4章树和二叉树

4.1树

4.1.1树的定义和基本术语

4.1.2树的抽象数据类型

4.1.3树的存储结构

4.1.4树的遍历

4.1.5树的套用

4.2二叉树

4.2.1二叉树的定义

4.2.2二叉树的性质

4.2.3二叉树的存储结构

4.2.4表达式树

4.2.5二叉树的基本操作及实现

4.3遍历二叉树和线索二叉树

4.3.1遍历二叉树

4.3.2二叉树遍历的非递归实现

4.3.3线索二叉树

4.4树、森林和二叉树的转换

4.4.1树转换为二叉树

4.4.2森林转换为二叉树

4.4.3二叉树转换为树和森林

4.5Huffman编码树

4.5.1最优二叉树(Huffman树)

4.5.2Huffman编码

4.6二叉搜寻树

4.6.1二叉搜寻树的基本操作

4.6.2平衡二叉树(AVL树)

4.7伸展树

4.7.1伸展树的基本操作

4.7.2伸展树的参考例程

4.8堆与优先伫列

4.8.1堆的逻辑定义

4.8.2堆的性质

4.8.3堆的基本操作

4.8.4堆的实现例程

4.9B树和B+树

4.9.1B树及其查找

4.9.2B树的插入和删除

4.9.3B+树

4.10树型结构搜寻算法套用案例

4.10.1基于二叉树遍历的套用

4.10.2ACM/ICPC竞赛题例分析

习题

ACM/ICPC实战练习

第5章图论算法

5.1图

5.1.1图的定义和术语

5.1.2图的抽象数据类型

5.1.3图的存储结构

5.2图的遍历算法

5.2.1深度优先搜寻

5.2.2广度优先搜寻

5.2.3深度与广度优先搜寻套用

5.3图的连通性

5.3.1无向图的连通性

5.3.2有向图的连通性

5.3.3生成树和生成森林

5.3.4关节点和重连通分量

5.3.5有向图的强连通分量

5.4有向无环图及其套用

5.4.1有向无环图的概念

5.4.2AOV网与拓扑排序

5.4.3AOE网与关键路径

5.5最短路径算法

5.5.1无权最短路径

5.5.2Dijkstra算法

5.5.3具有负边值的图

5.5.4所有点对的最短路径

5.6最小支撑树

5.6.1Prim算法

5.6.2Kruskal算法

5.6.3最小生成树算法套用

5.7网路流问题

5.7.1网路流的最大流问题

5.7.2网路流套用

习题

ACM/ICPC实战练习

第6章内部排序

6.1概述

6.2基于顺序比较的简单排序算法

6.2.1插入排序(InsertionSort)

6.2.2冒泡排序(BubbleSort)

6.2.3直接选择排序(DirectlySelectionSort)

6.2.4简单排序算法的时间代价对比

6.3缩小增量排序方法——Shell排序(ShellSort)

6.4基于分治策略的排序

6.4.1快速排序(QuickSort)

6.4.2归併排序(MergeSort)

6.5树形排序方法

6.5.1堆排序(HeapSort)

6.5.2树形选择排序(TreeSelectSort)

6.6分配排序和基数排序

6.6.1桶式排序(BucketSort)

6.6.2基数排序(RadixSort)

6.7内部排序问题讨论与分析

6.7.1常用排序算法性能简要分析

6.7.2排序问题的下限

6.8排序套用举例

习题

ACM/ICPC实战练习

第7章档案管理和外排序

7.1外存储器

7.1.1磁碟

7.1.2磁碟访问时间估算

7.2外存档案的组织

7.2.1档案组织

7.2.2档案上的操作

7.2.3C语言中的档案流操作

7.3缓冲区和缓冲池

7.4外排序(ExternalSort)

7.4.1二路外排序

7.4.2多路平衡归併的实现

7.5置换选择排序

7.6最佳归併树

习题

第8章检索与散列表

8.1检索的基本概念

8.2基于线性表的检索

8.2.1顺序检索

8.2.2有序表的二分检索

8.2.3有序表的插值查找和斐波那契查找

8.2.4分块检索

8.3集合的检索

8.3.1集合的数学特性

8.3.2计算机中的集合

8.4键树

8.4.1基本概念

8.4.2键树的存储表示

8.4.3键树相关算法实现

8.5散列方法及其检索

8.5.1散列函式

8.5.2开散列方法（分离连结法）

8.5.3开放定址法

8.5.4散列方法的效率分析

8.6散列表及检索的套用

习题

ACM/ICPC实战练习

第9章算法设计方法

9.1算法设计方法概论

9.1.1常用的算法设计方法

9.1.2算法设计中的最最佳化问题

9.2分治法

9.2.1分治策略的思想

9.2.2高精度计算

9.2.3矩阵相乘的Strassen算法

9.2.4选择问题的分治算法

9.2.5分治法求最近点对问题

9.2.6分治法的套用

9.3贪心法

9.3.1贪心算法的思想

9.3.2活动安排问题

9.3.3背包问题

9.3.4多机调度问题的近似算法

9.3.5任务调度问题

9.3.6贪心算法的套用

9.4回溯与分支限界

9.4.1回溯与分支限界简介

9.4.2八皇后问题

9.4.301背包问题的回溯算法

9.4.4分支限界算法

9.4.5回溯与分支限界套用

9.5动态规划法

9.5.1Fibonacci数的计算

9.5.2矩阵连乘的顺序问题

9.5.3适合动态规划算法的两个条件

9.5.4最长不降子序列问题

9.5.5最长公共子序列问题

9.5.6石子合併问题

9.5.7凸多边形最优三角剖分

习题

ACM/ICPC实战练习

参考文献