“数据结构与算法”是计算机科学与技术专业的一门非常重要的专业基础课,是《中国计算机科学与技术学科教程2002》指定的核心课程之一。本书由长期担任本课程教学任务的教授主持编写,内容覆盖了该教程规定的关于本门课程的全部知识点,并融入了编者的教学经验和对课程内涵的深入思考。全书共分l0章,内容涉及数据结构的基本概念、线性表、栈和队列、串和数组、广义表、树、图、查找、排序及算法设计方法。
本书可作为高等院校计算机专业及相关专业的教材和参考书,也可供IT工程技术人员参考。

第1章 绪论
1.1 引言
1.1.1 解决问题的步骤
1.1.2 一个例子
1.2 数据结构
1.2.1 有关概念和术语
1.2.2 抽象数据类型
1.2.3 描述工具——类C语言
1.3 算法和算法分析
1.3.1 算法的定义及算法设计的要求
1.3.2 算法性能分析与度量
1.3.3 复杂度函数的增长率
1.3.4 复杂度分析的例子
本章小结
习题1
第2章 线性表
2.1 线性表的类型定义
2.1.1 线性表的概念
2.1.2 线性表的抽象数据类型
2.1.3 线性表的例子
2.2 线性表的顺序表示和实现
2.2.1 线性表的顺序表示
2.2.2 顺序表操作的实现
2.3 线性表的链式表示和实现
2.3.1 单链表的表示
2.3.2 线性链表操作的实现
2.4 线性表实现方法的比较
2.5 循环链表
2.6 双向链表
2.7 静态链表
﹡2.8 算法设计实例——一元多项式的表示及相加
本章小结
习题2
第3章 栈和队列
3.1 栈
3.1.1 栈的类型定义
3.1.2 栈的表示和实现
3.1.3 顺序栈和链栈的比较
3.2 队列
3.2.1 队列的类型定义
3.2.2 循环队列
3.2.3 链队——队列的链式表示和实现
*3.3 递归
3.3.1 递归的定义
3.3.2 递归的实现
3.3.3 递归和迭代
3.3.4 递归的消除
*3.4 算法设计实例
3.4.1 数制转换
3.4.2 表达式求值算法
本章小结
习题3
第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 KMP算法
*4.4 串的应用举例
本章小结
习题4
第5章 数组和广义表
5.1 数组的概念及其基本操作
5.1.1 数组的抽象数据类型
5.1.2 二维数组
5.2 数组的顺序存储
5.3 矩阵的压缩存储
5.3.1 特殊矩阵
5.3.2 稀疏矩阵
*5.4 广义表
5.4.1 广义表的定义
5.4.2 广义表的存储结构
本章小结
习题5
第6章 树与二叉树
6.1 树的概念和操作
6.1.1 树的定义
6.1.2 树的基本术语
6.1.3 树的基本操作
6.2 二叉树
6.2.1 二叉树的概念及操作
6.2.2 二叉树的性质
6.2.3 二叉树的存储结构
6.3 二叉树的遍历
6.3.1 二叉树的遍历
6.3.2 遍历算法的应用
6.4 线索二叉树
6.4.1 线索二叉树的基本概念
6.4.2 线索二叉树的基本操作
6.5 树和森林
6.5.1 树的存储结构
6.5.2 森林、树、二叉树的相互转换
6.5.3 树和森林的遍历
6.6 哈夫曼树及其应用
6.6.1 *优二叉树(哈夫曼树)
6.6.2 哈夫曼编码
*6.7 算法设计实例
本章小结
习题6
第7章 图
7.1 图的定义和术语
7.1.1 图的基本概念
7.1.2 图的基本操作
7.2 图的存储结构
7.2.1 数组表示法
7.2.2 邻接表
7.3 图的遍历
7.3.1 深度优先搜索
7.3.2 广度优先搜索
7.4 图的连通性问题
7.4.1 图的连通分量和生成树
7.4.2 *小生成树
7.5 有向无环图及其应用
7.5.1 拓扑排序
*7.5.2 关键路径
7.6 *短路径
7.6.1 从某个源点到其他各顶点的*短路径
7.6.2 每一对顶点之间的*短路径
*7.7 网络流问题
*7.8 算法实例
本章小结
习题7
第8章 查找
8.1 概述
8.2 线性表上的查找
8.2.1 顺序表上的查找
8.2.2 有序表上的二分查找
8.3 索引表上的查找
8.4 树表上的查找
8.4.1 二叉排序树
8.4.2 平衡二叉树
*8.4.3 B_树
*8.4.4 键树
8.5 哈希表
8.5.1 哈希表查找的基本概念
8.5.2 构造哈希函数的方法
8.5.3 哈希冲突的解决方法
8.5.4 哈希表的查找及分析
*8.6 算法设计实例
本章小结
习题8
第9章 排序
9.1 概述
9.1.1 排序的定义
9.1.2 排序的分类
9.1.3 排序的基本操作
9.1.4 排序算法的性能评价
9.1.5 排序算法涉及的数据类型
9.2 插入排序
9.2.1 直接插入排序
9.2.2 折半插入排序
9.2.3 希尔排序
9.2.4 其他插入排序
9.3 交换排序
9.3.1 冒泡排序
9.3.2 快速排序
9.4 选择排序
9.4.1 简单选择排序
9.4.2 堆排序
9.5 归并排序
9.5.1 归并排序
9.5.2 二路归并排序
9.6 分配排序
9.6.1 多关键字排序
9.6.2 基数排序
9.7 计数排序
9.7.1 计数排序
9.7.2 计数排序算法实现
9.8 内部排序比较与选择
9.8.1 内部排序算法性能比较
9.8.2 内部排序算法的选择
*9.9 外部排序简介
9.9.1 磁盘文件管理
9.9.2 多路归并排序
9.9.3 二路归并排序算法
9.9.4 磁盘文件排序的例子
9.9.5 提高外部排序算法效率的途径
本章小结
习题9
第10章 算法设计初步
10.1 迭代法与穷举法
10.1.1 迭代法
10.1.2 穷举法
10.2 递归技术与分治法
10.2.1 递归技术
10.2.2 分治法
10.3 回溯法
10.3.1 回溯法的基本思想
10.3.2 0-1背包问题
10.3.3 旅行商问题
10.3.4 求解迷宫问题
10.4 倒推法
10.4.1 倒推法的基本思想
10.4.2 倒推法应用实例
10.5 贪心法
10.5.1 贪心法的基本思想
10.5.2 使用贪心法的前提
10.5.3 贪心法应用实例
10.6 分枝限界法
10.6.1 分枝限界法的基本思想
10.6.2 分枝限界法的应用实例
10.7 动态规划法
10.7.1 动态规划法的基本思想
10.7.2 动态规划法的基本要素
10.7.3 动态规划法的变形——备忘录方法
10.8 随机算法
10.8.1 随机数的产生
10.8.2 用随机算法计算p的值
10.8.3 蒙特卡罗积分
本章小结
习题10
参考文献