数据结构与算法/徐雅静

第1章 绪论 1.1 数据结构与算法的重要性 1.2 数据结构的基本概念 1.3 算法和算法分析 1.3.1 算法描述 1.3.2 算法分析 1.3.3 NP问题 1.4 STL与数据结构 1.4.1 STL简介 1.4.2 STL与数据结构的关系 1.5 工程实践和思考 习题1 第2章 线性表 2.1 线性表概述 2.1.1 线性表的定义 2.1.2 线性表的运算 2.1.3 各种常用存储结构 2.2 顺序表的实现 2.2.1 顺序表的存储结构 2.2.2 顺序表的基本运算 2.2.3 顺序表的应用——通信录 2.2.4 STL中的顺序表——vector 2.3 单链表的实现 2.3.1 单链表的存储结构 2.3.2 单链表的基本运算 2.3.3 单链表的应用——通信录 2.4 循环链表的实现 2.5 双链表的实现 2.5.1 双链表的基本结构 2.5.2 双链表的基本运算 2.5.3 STL中的双链表——list 2.6 顺序表与链表的比较 2.6.1 时间性能比较 2.6.2 空间性能比较 2.7 工程实践和思考 问题1：不支持指针的高级语言，如何实现链表？ 问题2：如何实现一元多项式的求和？ 问题3：操作系统的内存如何管理？ 问题4：荷兰国旗问题 习题2 第3章 线性表的扩展 3.1 各种扩展线性表 3.1.1 栈 3.1.2 队列 3.1.3 串 3.1.4 多维数组 3.2 栈的实现 3.2.1 顺序栈 3.2.2 链式栈 3.2.3 STL中的栈——stack 3.3 队列的实现 3.3.1 循环队列 3.3.2 链队列 3.3.3 STL中的队列 3.4 串的实现 3.4.1 串的存储结构 3.4.2 串的模式匹配 3.4.3 KMP算法 3.4.4 STL中的串——string 3.5 多维数组 3.5.1 多维数组的存储 3.5.2 稀疏矩阵 3.6 基于栈的经典算法 3.6.1 递归——斐波那契数列 3.6.2 分治法——汉诺塔游戏 3.6.3 回溯法——迷宫问题 3.6.4 动态规划——背包问题 3.7 工程实践和思考 问题1：优先级队列的调度 问题2：图像识别领域的基本问题——手写数字识别 问题3：贪心算法和动态规划的区别 问题4：穷举法和动态规划的区别 习题3 第4章 树 4.1 基本概念 4.1.1 树 4.1.2 二叉树 4.1.3 森林 4.2 基本操作 4.2.1 树的遍历 4.2.2 二叉树的遍历 4.2.3 森林的遍历 4.2.4 树、森林与二叉树的转换 4.3 存储结构 4.3.1 树的存储结构 4.3.2 二叉树的存储结构 4.4 二叉树的实现 4.4.1 二叉树的声明 4.4.2 二叉树的关键算法 4.4.3 递归算法的规律 4.5 哈夫曼树的应用 4.5.1 哈夫曼树的定义与存储结构 4.5.2 哈夫曼树的构造 4.5.3 哈夫曼编码表的构建 4.5.4 哈夫曼编、解码的实现 4.6 工程实践和思考 问题1：构建算术表达式二叉树 问题2：通信系统中如何使用哈夫曼树压缩信息？ 习题4 第5章 图 5.1 基本概念 5.1.1 图的定义 5.1.2 图的基本术语 5.2 图的存储结构 5.2.1 邻接矩阵 5.2.2 邻接表 5.2.3 十字链表 5.2.4 邻接多重表 5.2.5 边集数组 5.2.6 图的存储结构比较 5.3 图的实现 5.3.1 图的构建 5.3.2 图的遍历 5.3.3 图的析构 5.4 *小生成树 5.4.1 普里姆算法 5.4.2 克鲁斯卡尔算法 5.5 *短路径 5.5.1 Dijkstra算法 5.5.2 Floyd算法 5.6 工程实践与思考 问题1：图着色问题 问题2：地铁换乘线路查找问题 问题3：教学计划安排问题 问题4：关键路径问题 习题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.3.3 B—树 6.3.4 STL中的树表——set和map 6.4 散列查找 6.4.1 散列技术 6.4.2 散列函数设计 6.4.3 冲突处理 6.4.4 常用的散列函数 6.5 工程实践和思考 问题1：自然语言处理的基本问题——中文分词 问题2：数据库索引结构 习题6 第7章 排序 7.1 基本概念 7.1.1 相关概念 7.1.2 排序性能评估 7.1.3 排序方法分析 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 归并排序 7.3.5 STL中常用的排序算法 7.4 非比较的排序算法 7.4.1 计数排序 7.4.2 桶排序 7.4.3 基数排序 7.5 工程实践和思考 问题1：电话号码排序 问题2：大数据下的排序问题 习题7 参考文献 附录 附录1 异常处理 附录2 模板