数据结构与算法

　　本书充分展示了面向对象技术在现代数据结构理论中的应用，普遍采用了抽象、封装及继承等技术。本书既介绍了基本的数据结构，包括栈、队列、向量、列表结构；也介绍了若干高级数据结构，包括优先队列结构、映射和词典结构、查找树结构等。并结合具体问题介绍了算法的应用、实现及其分析方法，涉及的算法包括堆结构的生成及调整算法、Huffman编码树算法、平衡查找树的生成、插入和删除算法，并着重介绍了串匹配的KMP和BM算法。本书还通过遍历算法框架将各种图算法统一起来，并基于遍历算法模板加以实现，在同类教材中独树一帜。.本书图文并茂，循序渐进。书中代码都配有详尽而简洁的注释。书中还结合各部分的具体内容穿插了大量问题，以激发读者的求知欲，培养良好的自学习惯和自学能力。本书适合用作计算机专业本科生教材或参考书。本书作者力图突破此类教材多年来形成的定式，在很多方面都做了大胆尝试。..在体例方面，作者结合多年教学实践，对知识点进行了重新整理编排，许多处理方法在同类教材中独树一帜，旨在将读者引向更高层次，使读者形成对数据结构的宏观认识。在内容方面，本书并未对各种数据结构面面俱到，而是按照CC2001标准对必要知识点和技能要求精心加以裁剪，通过系统分类和启发式讲解，在基本数据结构与高级数据结构之间架起一座桥梁。在算法方面，本书不仅强调对复杂度等基本概念的把握，同时结合具体问题介绍算法复杂度的各种分析方法，尤其是分摊分析等高级技巧。而且所有数据结构仍然构成一个完整的体系，帮助读者养成面向实际应用的意识，并掌握构建实际应用的基本能力。...

　　MichaelSpivak微分几何方面世界知名的数学家，Publish-or-Perish出版社的创始人，1964年获得普林斯顿大学博士学位，指导老师为菲尔兹奖和沃尔夫奖得主JohnMilnor。除本书外Spivak还著有五卷本AComprehensiveIntroductiontoDifferentialGeometry和Calculus等名著。

前言
第1章算法及其复杂度.
1.1计算机与算法
1.1.1过指定垂足的直角边
1.1.2三等分线段
1.1.3排序
1.1.4算法的定义
1.2算法性能的分析与评价
1.2.1三个层次
1.2.2时间复杂度及其度量
1.2.3空间复杂度
1.3算法复杂度及其分析
1.3.1O(1)——取非极端元素
1.3.2O(logn)——进制转换
1.3.3O(n)——数组求和
1.3.4O(n2)——起泡排序
1.3.5O(2r)——幂函数
1.4计算模型
1.4.1可解性
1.4.2有效町解
1.4.3下界
1.5递归
1.5.1线性递归
1.5.2递归算法的复杂度分析
1.5.3二分递归
1.5.4多分支递归
第2章栈与队列
2.1栈
2.1.1栈ADT
2.1.2基于数组的简单实现
2.1.3Java虚拟机中的栈
2.1.4栈应用实例
2.2队列
2.2.1队列ADT
2.2.2基于数组的实现
2.2.3队列应用实例
2.3链表
2.3.1单链表
2.3.2基于单链表实现栈
2.3.3基于单链表实现队列
2.4位置
2.4.1位置ADT
2.4.2位置接口
2.5双端队列
2.5.1双端队列ADT
2.5.2双端队列接口
2.5.3双向链表
2.5.4基于双向链表实现的双端队列
第3章向量.列表与序列
3.1向量与数组
3.1.1向量ADT
3.1.2基于数组的简单实现
3.1.3基于可扩充数组的实现
3.1.4java.util,ArrayList类和java.util.Vector类
3.2列表
3.2.1基于节点的操作
3.2.2由秩到位置
3.2.3列表ADT
3.2.4基于双向链表实现的列表
3.3序列
3.3.1序列ADT
3.3.2基于双向链表实现序列
3.3.3基于数组实现序列
3.4迭代器
3.4.1迭代器ADT
3.4.2迭代器接口
3.4.3迭代器的实现
3.4.4Java中的列表及迭代器
第4章树
4.1术语及性质
4.1.1节点的深度.树的深度与高度
4.1.2节点的度与内部节点.外部节点
4.1.3路径
4.1.4祖先.后代.子树和节点的高度
4.1.5共同祖先及最低共同祖先
4.1.6有序树.m叉树
4.1.7二叉树
4.1.8满二叉树与完全二叉树
4.2树ADT及其实现
4.2.1“父亲-长子-弟弟”模型
4.2.2树ADT
4.2.3树的Java接口
4.2.4基于链表实现树
4.3树的基本算法
4.3.1getSize()——统计(子)树的规模
4.3.2getHeight()——计算节点的高度
4.3.3getDepth()——计算节点的深度
4.3.4前序.后序遍历
4.3.5层次遍历
4.3.6树迭代器
4.4二叉树ADT及其实现
4.4.1二叉树ADT
4.4.2二叉树的Java接口
4.4.3二叉树类的实现
4.5二叉树的基本算法
4.5.1getSize().getHeiglit()和getDepth()
4.5.2updateSize()
4.5.3updateHeight()
4.5.4updateDepth()
4.5.5secede()
4.5.6attachL()和attachR()
4.5.7二叉树的遍历
4.5.8直接前驱.直接后继的定位算法
4.6完全二叉树的Java买现
4.6.1完全二叉树的Java接口
4.6.2基于向量的实现
第5章优先队列
5.1优先级.关键码.全序关系与优先队列
5.2条目与比较器
5.2.1条目
5.2.2比较器
5.2.3Comparator接口及其实现
5.3优先队列ADT及其Java接口
5.3.1优先队列的ADT描述
5.3.2优先队列的Java接口
5.3.3基于优先队列的排序器
5.4用向量实现优先队列
5.5用列表实现优先队列
5.5.1基于无序列表的实现及分析
5.5.2基于有序列表的实现及分析
5.6选择排序与插入排序
5.6.1选择排序
5.6.2插入排序
5.6.3效率比较
5.7堆的定义及性质
5.7.1堆结构
5.7.2完全性
5.8用堆实现优先队列
5.8.1基于堆的优先队列及其实现
5.8.2插入与上滤
5.8.3删除与下滤
5.8.4改变任意节点的关键码
5.8.5建堆
5.9堆排序
5.9.1直接堆排序
5.9.2就地堆排序
5.10Huffman编码树
5.10.1二叉编码树
5.10.2最优编码树
5.10.3Huffman编码与Huffman编码树
5.10.4Huffman编码树的构造算法
5.10.5基于优先队列的Huffman编码树构造算法
第6章映射与词典
6.1映射..
6.1.1映射的ADT描述
6.1.2映射的Java接口
6.1.3判等器
6.1.4java.util包中的映射类
6.1.5基于列表实现映射类
6.2散列表
6.2.1桶及桶数组
6.2.2散列函数
6.2.3散列码
6.2.4压缩函数
6.2.5冲突的普遍性
6.2.6解决冲突
6.2.?基于散列表实现映射类
6.2.8装填因子与重散列
6.3无序词典
6.3.1无序词典的ADT描述
6.3.2无序词典的Java接口
6.3.3列表式无序词典及其实现
6.3.4散列表式无序词典及其实现
6.4有序词典
6.4.1全序关系与有序查找表
6.4.2二分查找
6.4.3有序词典的ADT描述
6.4.4有序词典的Java接口
6.4.5基于有序查找表实现有序
词典
第7章查找树
7.1二分查找树
7.1.1定义
7.1.2查找算法
7.1.3完全查找算法
7.1.4插入算法
7.1.5删除算法
7.1.6二分查找树节点类的实现
7.1.?二分查找树类的实现
7.1.8二分查找树的平均性能
7.2AVL树
7.2.1平衡二分查找树
7.2.2等价二分查找树
7.2.3等价变换
7.2.4AVL树
7.2.5插入节点后的重平衡
7.2.6节点删除后的重平衡
7.2.7AVL树的Java实现
7.3伸展树
7.3.1数据局部性
7.3.2逐层伸展
7.3.3双层伸展
7.3.4分摊复杂度
7.3.5伸展树的Java实现
7.3.6插入
7.3.7删除
7.4B-树
7.4.1分级存储
7.4.2B-树的定义
7.4.3关键码的查找
7.4.4性能分析
7.4.5上溢节点的处理
7.4.6关键码的插入
7.4.7下溢节点的处理
7.4.8关键码的删除
第8章排序
8.1归并排序
8.1.1分治策略
8.1.2时间复杂度
8.1.3归并算法
8.1.4Mergesort的Java实现
8.2快速排序
8.2.1分治策略
8.2.2轴点
8.2.3划分算法
8.2.4Quicksort的Java实现
8.2.5时间复杂度
8.3复杂度下界
8.3.1比较树与基于比较的算法
8.3.2下界
第9章串
9.1串及其ADT描述
9.2串模式匹配
9.2.1概念与记号
9.2.2问题
9.2.3算法效率的测试与评价
9.3蛮力算法
9.3.1算法描述
9.3.2算法实现
9.3.3算法分析
9.4KMP算法
9.4.1蛮力算法的改进
9.4.2next[]表的定义及含义
9.4.3KMP算法描述
9.4.4next[]表的特殊情况
9.4.5next[]表的构造
9.4.6next[]表的改进
9.4.7KMP算法的Java实现
9.4.8性能分析
9.5BM算法
9.5.1坏字符策略
9.5.2好后缀策略
9.5.3BM算法
9.5.4BM算法的Java实现
9.5.5性能
第10章图
10.1概述
10.1.1无向图.混合图及有向图
10.1.2度
10.1.3简单图
10.1.4图的复杂度
10.1.5子图.生成子图与限制子图
10.1.6通路.环路及可达分量
10.1.7连通性.等价类与连通分量
10.1.日森林.树以及无向图的生成树
10.1.9有向图的生成树
10.1.10带权网络
10.2抽象数据类型
10.2.1图
10.2.2顶点
10.2.3边
10.3邻接矩阵
10.3.1表示方法
10.3.2时间性能
10.3.3空间性能
10.4邻接表
10.4.1顶点表和边表
10.4.2顶点与邻接边表
10.4.3边
lo.4.4基于邻接表实现图结构
10.5图遍历及其算法模板
10.6深度优先遍历
10.6.1深度优先遍历算法
10.6.2边分类
10.6.3可达分量与DFS树
10.6.4深度优先遍历算法模板
10.6.5可达分量算法
10.6.6单强连通分量算法
10.6.7强连通分量分解算法
10.6.8浓缩图与弱连通性
10.7广度优先遍历
10.7.1广度优先遍历算法
10.7.2边分类
10.7.3可达分量与BFS树
10.7.4广度优先遍历算法模板
10.7.5最短距离算法
10.8最佳优先遍历
10.8.1最佳优先遍历算法
10.8.2最佳优先遍历算法模板
10.8.3最短路径
10.8.4最短路径序列
10.8.5Dijkstra算法
10.8.6最小生成树
10.8.7Prim-Jarnik算法
DSA类关系图...