本书根据教育部计算机类专业教学指导委员会制定的“计算机科学与技术专业规范”中“数据结构与算法”课程大纲和专业培养方案要求编写。教材跟踪和反映国内外技术发展需求和教学改革现状，重点强调数据结构和算法设计两方面的基础知识，体系科学完整，内容简洁实用，实践性强。

本书共10章。第1~8章主要介绍数据结构及经典应用算法，内容包括基本概念、三大基本结构（线性结构、树形结构、图结构）和两大经典应用算法（排序算法、查找算法）。第9~10章主要介绍算法设计方法及应用，内容包括贪心算法、分治算法、动态规划、回溯算法和NP完全性理论。每章均附有知识要点、重点提示、常见问题解答、本章小结及大量的习题，针对难点问题还同时提供微视频讲解（读者可扫描相应二维码观看）。附录给出了课内实验和专题实验指导。

为便于读者使用，本书同时配有电子教案、习题解答、程序代码等资源。详见与本书配套的易课程网站。

本书既可作为高等学校计算机类专业“数据结构与算法”课程教材，也可供从事计算机应用开发和研究的工程技术人员参考。

前辅文
第1章 基础知识
  1.1 数据结构的基本概念
  1.2 抽象数据类型
  1.3 问题、算法和程序
  1.4 算法分析概述
  1.5 时间复杂度
  1.6 渐近分析
   1.6.1 上限表示法
   1.6.2 下限表示法
   1.6.3 Θ表示法
   1.6.4 化简法则
  1.7 空间复杂度
  *1.8 C++语言基础
   1.8.1 面向对象的概念
   1.8.2 数据声明和作用域
   1.8.3 输入／输出
   1.8.4 函数
   1.8.5 参数传递
   1.8.6 函数重载
   1.8.7 动态内存分配
   1.8.8 C++的模板
  本章小结
  习题
第2章 线性表
  2.1 线性表的定义
  2.2 线性表的顺序存储结构
   2.2.1 顺序存储结构
   2.2.2 顺序存储结构的实现
  2.3 线性表的链式存储结构
   2.3.1 单链表
   2.3.2 双向链表
   2.3.3 循环链表
  2.4 线性表应用举例
   2.4.1 一元多项式的表示
   2.4.2 商品链更新
  本章小结
  习题
第3章 受限线性表——栈、队列及串
  3.1 操作受限线性表——栈
  3.2 栈的存储结构
   3.2.1 顺序栈的定义及实现
   3.2.2 链栈的定义及实现
  3.3 栈的应用
   3.3.1 括号匹配检验
   3.3.2 栈与递归
  3.4 操作受限线性表——队列
  3.5 队列的存储结构及实现
   3.5.1 顺序队列的定义及实现
   3.5.2 队列的链式存储结构及实现
  3.6 队列的应用
   3.6.1 杨辉三角形
   3.6.2 火车车厢重排
  *3.7 类型受限线性表——字符串
   3.7.1 串的定义
   3.7.2 串的操作
   3.7.3 串的存储结构
   3.7.4 串类及其实现
   3.7.5 串的模式匹配
  本章小结
  习题
第4章 扩展线性表——数组与广义表
  *4.1 扩展线性表——数组
   4.1.1 数组的定义
   4.1.2 数组的基本操作
   4.1.3 数组的存储结构
   4.1.4 矩阵的压缩存储
  *4.2 扩展线性表——广义表
   4.2.1 广义表的定义及性质
   4.2.2 广义表的存储表示
   4.2.3 广义表的递归操作
  本章小结
  习题
第5章 树和二叉树
  5.1 树的定义与基本术语
   5.1.1 树的定义
   5.1.2 相关的基本术语
  5.2 二叉树的定义、性质和存储结构
   5.2.1 二叉树的定义
   5.2.2 二叉树的主要性质
   5.2.3 二叉树的存储结构
  5.3 二叉树的遍历
   5.3.1 二叉树的先序遍历
   5.3.2 二叉树的中序遍历
   5.3.3 二叉树的后序遍历
  5.4 二叉树应用1：哈夫曼树
   5.4.1 哈夫曼树的构造
   5.4.2 哈夫曼编码
  5.5 二叉树应用2：二叉查找树
   5.5.1 二叉查找树的定义
   5.5.2 二叉查找树的查找
   5.5.3 二叉查找树的插入
   5.5.4 二叉查找树的删除
  5.6 二叉树应用3：平衡二叉查找树
   5.6.1 平衡二叉树的定义
   5.6.2 平衡化旋转
   5.6.3 平衡二叉查找树的插入
   5.6.4 平衡二叉查找树的删除
  5.7 二叉树应用4：堆与优先队列
   5.7.1 堆与优先队列的定义与实现
   5.7.2 堆的插入和堆顶删除
  5.8 树与森林
   5.8.1 树的存储结构
   5.8.2 树、森林与二叉树的转换
   5.8.3 树与森林的遍历
  本章小结
  习题
第6章 图
  6.1 图的定义和术语
  6.2 图的存储结构
   6.2.1 邻接矩阵存储方法
   6.2.2 邻接表存储方法
  6.3 图的遍历
   6.3.1 深度优先搜索
   6.3.2 广度优先搜索
  6.4 图的应用1：拓扑排序
  6.5 图的应用2：关键路径
  6.6 图的应用3：最短路径
   6.6.1 单源点最短路径问题
   6.6.2 任意对顶点之间的最短路径
  6.7 图的应用4：图的最小生成树
   6.7.1 Prim算法
   6.7.2 Kruskal算法
  本章小结
  习题
第7章 排序算法
  7.1 排序的基本概念
  7.2 简单排序
   7.2.1 简单插入排序
   7.2.2 冒泡排序
   7.2.3 简单选择排序
  7.3 高级排序
   7.3.1 希尔排序
   7.3.2 快速排序
   7.3.3 归并排序
   7.3.4 树形选择排序1：锦标赛排序
   7.3.5 树形选择排序2：堆排序
  7.4 关键字比较排序下界问题
  7.5 非关键字比较的排序
   7.5.1 基数排序
   7.5.2 多关键字排序
  7.6 各种排序算法的比较
  本章小结
  习题
第8章 查找算法
  8.1 查找的基本概念
  8.2 静态查找表
   8.2.1 顺序表的查找
   8.2.2 折半查找
  8.3 散列表
   8.3.1 哈希函数的常用构建方法
   8.3.2 解决冲突的办法
   8.3.3 哈希表的实现
   8.3.4 哈希表的分析
  8.4 线性索引
  8.5 树形索引
   8.5.1 2-3树
   8.5.2 B树
   8.5.3 B+树
  本章小结
  习题
第9章 算法设计常用方法
  9.1 贪心算法
   9.1.1 活动安排问题
   9.1.2 贪心算法的设计思想
   9.1.3 贪心算法的应用
  9.2 分治算法
   9.2.1 分治算法的基本思想
   9.2.2 分治算法复杂度分析
   9.2.3 大整数相乘
   9.2.4 矩阵乘法
   9.2.5 快速排序算法的改进
  9.3 动态规划
   9.3.1 动态规划原理
   9.3.2 最优二叉查找树
   9.3.3 最长公共子序列
  9.4 回溯算法
   9.4.1 回溯算法的思想
   9.4.2 N皇后问题
   9.4.3 迷宫问题
  本章小结
  习题
第10章 计算复杂性简介
  10.1 基本概念
   10.1.1 非确定性算法
   10.1.2 P类与NP类问题
  10.2 NP难与NP完全问题
   10.2.1 问题变换与计算复杂度归约
   10.2.2 NP完全性
  10.3 NP完全问题的例子
   10.3.1 CNF-SAT问题
   10.3.3 团问题
   10.3.4 顶点覆盖问题
   10.3.5 其他一些NP完全问题
  本章小结
  习题
附录
  附录A “数据结构与算法”课内实验设计
  附录B “数据结构与算法”专题实验设计
参考文献

“十二五”普通高等教育本科国家级规划教材