数据结构(C++语言版)(第2版)/清华大学计算机系列教材

《清华大学计算机系列教材:数据结构(C++语言版)(第2版)》中穿插验证型、拓展型和反思型习题总计280余道，激发读者的求知欲，培养自学能力和独立思考习惯；260多组300余幅插图结合简练的叙述，230余段代码配合详尽而简洁的注释，使深奥抽象的概念和过程得以具体化且便于理解和记忆；推荐20余册经典的专著与教材，提供30余篇重点的学术论文，便于读者进一步钻研和拓展。

《数据结构(C++语言版第2版清华大学计算机系列教材)》(作者邓俊辉)按照面向对象程序设计的思想，根据作者多年的教学积累，系统地介绍各类数握结构的功能、表示和实现，对比各类数据结构适用的应用环境；结合实际问题展示算法设计的一般性模式与方法、算法实现的主流技巧，以及算法效率的评判依据和分析方法；以高度概括的体例为线索贯穿全书，并通过对比和类比揭示数据结构与算法的内在联系，帮助读者形成整体性认识。    《数据结构(C++语言版第2版清华大学计算机系列教材)》中穿插验证型、拓展型和反思型习题总计280余道，激发读者的求知欲，培养自学能力和独立思考习惯；260多组300余幅插图结合简练的叙述，230余段代码配合详尽而简洁的注释，使深奥抽象的概念和过程得以具体化且便于理解和记忆；推荐20余册经典的专著与教材，提供30余篇重点的学术论文，便于读者进一步钻研和拓展。    结合学生基础，专业方向、教学目标及允许课时总量等因素，本书提供了若干种典型的教学进度及学时分配方案，供授课教师视具体情况参考和选用。

邓俊辉，清华大学计算机系副教授。1993年，1997年分别于清华大学计算机系获工学学士和工学博士学位。主要研究方向为科学计算可视化、计算几何及计算机图形学。长期承担清华大学计算机本科生专业基础课程“数据结构”和研究生基础理论课“计算几何”的教学工作，编著的《数据结构与算法（Java描述）》入选“北京市高等教育精品教材”，参与编著的《数据结构（用面向对象方法与C++语言描述）》入选“重量高等教育精品教材”，曾获清华大学“青年教师教学很好奖”、清华大学“教书育人奖”、清华大学“教学成果奖”二等奖、清华大学“教学成果奖”一等奖、中国高校科学技术奖二等奖、宝钢教育基金“宝钢教育奖”。

第1章绪论
1.1计笪棚与算法
1.1.1古埃及人的绳索
1.1.2欧几里得的尺规
1.1.3起泡排序
1.1.4算法
1.1.5算法效率
1.2复杂度度量
1.2.1时间复杂度
1.2.2渐进复杂度
1.2.3空间复杂度
1.3复杂度分析
1.3.1常数σ（1）
1.3.2对数σ（logn）
1.3.3线性σ（n）
1.3.4多项式σ（polynomial（n））
1.3.5指数σ（2n）
1.3.6复杂度层次
1.3.7输入规模
1.4递归
1.4.1线性递归
1.4.2递归分析
1.4.3递归模式
1.4.4递归消除
1.4.5二分递归
§1.5抽象数据类型
习题
第2章向量
2.1从数组到向量
2.1.1数组
2.1.2向量
2.2接口
2.2.1ADT口
2.2.2操作实例
2.2.3Vector模板类
2.3构造与析构
2.3.1默认构造方法
2.3.2基于复制的构造方法
2.3.3析构方法
2.4动态空间管理
2.4.1静态空间管理
2.4.2可扩充向量
2.4.3扩容
2.4.4分摊分析
2.4.5缩容
2.5常规向量
2.5.1直接引用元素
2.5.2置乱器
2.5.3判等器与比较器
2.5.4无序查找
2.5.5插入
2.5.6删除
2.5.7唯-化
2.5.8遍历
2.6有序向量
2.6.1比较器
2.6.2有序性甄别
2.6.3唯-化
2.6.4查找
2.6.5二分查找（版本A）
2.6.6Fibonacci查找
2.6.7二分查找（版本B）
2.6.8二分查找（版本C）
2.7排序与下界
2.7.1有序性
2.7.2排序及其分类
2.7.3下界
2.7.4比较树
2.7.5估计下界
2.8排序器
2.8.1统一入口
2.8.2起泡排序
2.8.3归并排序
习题
第3章列表
3.1从向量到列表
3.1.1从静态存储到动态存储
3.1.2由秩到位置
3.1.3列表
3.2接口
3.2.1列表节点
3.2.2列表
3.3列表
3.3.1头、尾节点
3.3.2默认构造方法
3.3.3由秩到位置的转换
3.3.4查找
3.3.5插入
3.3.6基于复制的构造
3.3.7删除
3.3.8析构
3.3.9唯-化
3.3.10遍历
§3.4有序列表
3.4.1唯-化
3.4.2查找
3.5排序器
3.5.1统一入口
3.5.2插入排序
3.5.3选择排序
3.5.4归并排序
习题
第4章栈与队列
4.1栈
4.1.1ADT接口
4.1.2操作实例
4.1.3Stack模板类
4.2栈与递归
4.2.1递归的实现
4.2.2避免递归
4.3典型应用
4.3.1逆序输出
4.3.2递归嵌套
4.3.3延迟缓冲
4.3.4逆波兰表达式
4.4试探回溯法
4.4.1试探与回溯
4.4.2八皇后
4.4.3迷宫寻径
4.5队列
4.5.1概述
4.5.2ADT接口
4.5.3操作实例
4.5.4Queue模板类
4.6队列应用
4.6.1循环分配器
4.6.2银行服务模拟
习题
第5章二叉树
5.1二叉树及其表示
5.1.1树
5.1.2二叉树
5.1.3多叉树
5.2编码树
5.2.1二进制编码
5.2.2二叉编码树
5.3二叉树的实现
5.3.1二叉树节点
5.3.2二叉树节点操作接口
5.3.3二叉树
5.4Huffman编码
5.4.1PFC编码及解码
5.4.2最优编码树
5.4.3Huffman编码树
5.4.4Huffman编码算法
5.5遍历
5.5.1递归式遍历
5.5.2迭代版先序遍历
5.5.3迭代版中序遍历
5.5.4迭代版后序遍历
5.5.5层次遍历
习题
第6章图
6.1概述
6.2抽象数据类型
6.2.1操作接口
6.2.2Graph模板类
6.3邻接矩阵
6.3.1原理
6.3.2实现
6.3.3时间性能
6.3.4空间性能
6.4邻接表
6.4.1原理
6.4.2复杂度
6.5图遍历算去概述
6.6广度优先搜索
6.6.1策略
6.6.2实现
6.6.3实例
6.6.4复杂度
6.6.5应用
6.7深度优先搜索
6.7.1策略
6.7.2实现
6.7.3实例
6.7.4复杂度
6.7.5应用
6.8拓扑排序
6.8.1应用
6.8.2有向无环图
6.8.3算法
6.8.4实现
6.8.5实例
6.8.6复杂度
6.9双连通域分解
6.9.1关节点与双连通域
6.9.2蛮力算法
6.9.3算法
6.9.4实现
6.9.5实例
6.9.6复杂度
6.10优先级搜索
6.10.1优先级与优先级数
6.10.2基本框架
6.10.3复杂度
6.11最小支撑树
6.11.1支撑树
6.11.2最小支撑树
6.11.3歧义性
6.11.4蛮力算法
6.11.5Prim算法
6.12最短路径
6.12.1最短路径树
6.12.2歧义性
6.12.3Dijkstra算法
习题
第7章搜索树
7.1查找
7.1.1循关键码访问
7.1.2词条
7.1.3序与比较器
7.2二叉搜素树
7.2.1顺序性
7.2.2中序遍历序列
7.2.3BST模板类
7.2.4查找算法及其实现
7.2.5插入算法及其实现
7.2.6删除算法及其实现
7.3平衡二叉搜索树
7.3.1树高与性能
7.3.2理想平衡与适度平衡
7.3.3等价二叉搜索树
7.3.4等价变换与局部调整
7.4AVL树
7.4.1定义及性质
7.4.2节点插入
7.4.3节点删除
7.4.4统一重平衡算法
习题
第8章高级搜索树
8.1伸展树
8.1.1局部性
8.1.2逐层伸展
8.1.3双层伸展
8.1.4分摊分析
8.1.5伸展树的实现
8.2B-树
8.2.1多路平衡查找
8.2.2ADT接口及其实现
8.2.3关键码查找
8.2.4性能分析
8.2.5关键码插入
8.2.6上溢与分裂
8.2.7关键码删除
8.2.8下溢与合并
8.3红黑树
8.3.1概述
8.3.2红黑树接口定义
8.3.3节点播入算去
8.3.4节点删除算法
8.4kd-树
8.4.1范围查询
8.4.2kd-树
8.4.3基于2d-树的范围查询
习题
第9章词典
9.1词典ADT
9.1.1操作接口
9.1.2操作实例
9.1.3接口定义
9.1.4实现方去
9.2跳转表
9.2.1Skiplist模板类
9.2.2总体逻辑结构
9.2.3四联表
9.2.4查找
9.2.5空间复杂度
9.2.6时间复杂度
9.2.7插入
9.2.8删除
s9.3散列表
9.3.1完美散列
9.3.2装填因子与空间利用率
9.3.3散列函数
9.3.4散列表
9.3.5冲突及其排解
9.3.6闭散列策略
9.3.7查找与删除
9.3.8插入
9.3.9更多闭散列策略
9.3.10散列码转换
9.4散列应用
9.4.1桶排序
9.4.2最大间隙
9.4.3基数排序
习题
第10章优先级队列
10.1优先级队列ADT
10.1.1优先级与优先级队列
10.1.2关键码、比较器与偏序关系
10.1.3操作接口
10.1.4操作实例：选择排序
10.1.5接口定义
10.1.6应用实例：Huffman编码树
10.2堆
10.2.1完全二叉堆
10.2.2元素插入
10.2.3元素删除
10.2.4建堆
10.2.5就地堆排序
10.3左式堆
10.3.1堆合并
10.3.2单侧倾斜
10.3.3PCLLeftHeap模板类
10.3.4空节点路径长度
10.3.5左倾性与左式堆
10.3.6右侧链
10.3.7合并算法
10.3.8实例
10.3.9合并操作merge（）的实现
10.3.10复杂度
10.3.11基于合并的插入和删除
习题
第11肇串
11.1串及串匹配
11.1.1串
11.1.2串匹配
11.1.3测评标准与策略
11.2蛮力算法
11.2.1算法描述
11.2.2算法实现
11.2.3时间复杂度
11.3KMP算法
11.3.1构思
11.3.2next表
11.3.3KMP算法
11.3.4next[0】=-1
11.3.5next[j+1]
11.3.6构造next表
11.3.7性能分析
11.3.8继续改进
11.4BM算法
11.4.1思路与框架
11.4.2坏字符策略
11.4.3好后缀策略
11.4.4GS【】表构造算法
11.4.5算法纵览
11.5Karp-Rabin算法
11.5.1构思
11.5.2算法与实现
习题