数据结构与算法分析：Java语言描述

第1章  引论
 1. 1  本书讨论的内容
 1. 2  数学知识复习
 1. 2. 1  指数
 1. 2. 2  对数
 1. 2. 3  级数
 1. 2. 4  模运算
 1. 2. 5  证明方法
 1. 3  递归简论
 1. 4  Java中的一般对象
 1. 4. 1  IntCell类
 1. 4. 2  MemoryCell类
 1. 4. 3  实现一般的findMax方法
 1. 5  异常
 1. 6  输入和输出
 1. 6. 1  基本的流操作
 1. 6. 2  StringTokenizer对象
 1. 6. 3  顺序文件
 1. 7  代码的组织
 1. 7. 1  包
 1. 7. 2  MyInteger类
 1. 7. 3  关于效率的考虑
 小结
 练习
 参考文献
 第2章  算法分析
 2. 1  数学基础
 2. 2  模型
 2. 3  要分析的问题
 2. 4  运行时间计算
 2. 4. 1  一个简单的例子
 2. 4. 2  一般法则
 2. 4. 3  最大子序列和问题的解
 2. 4. 4  运行时间中的对数
 2. 4. 5  检验你的分析
 2. 4. 6  分析结果的准确性
 小结
 练习
 参考文献
 笫3章  表. 栈和队列
 3. 1  抽象数据类型(ADT)
 3. 2  表ADT
 3. 2. 1  表的简单数组实现
 3. 2. 2  链表
 3. 2. 3  程序设计细节
 3. 2. 4  双链表
 3. 2. 5  循环链表
 3. 2. 6  例子
 3. 2. 7  链表的游标实现
 3. 3  栈ADT
 3. 3. 1  栈模型
 3. 3. 2  栈的实现
 3. 3. 3  应用
 3. 4  队列ADT
 3. 4. 1  队列模型
 3. 4. 2  队列的数组实现
 3. 4. 3  队列的应用
 小结
 练习
 第4章  树
 4. 1  预备知识
 4. 1. 1  树的实现
 4. 1. 2  树的遍历及应用
 4. 2  二叉树
 4. 2. 1  实现
 4. 2. 2  一个例子：表达式树
 4. 3  查找树ADT-二叉查找树
 4. 3. 1  find
 4. 3. 2  findMin和findMax
 4. 3. 3  insert
 4. 3. 4  remove
 4. 3. 5  平均情形分析
 4. 4  AVL树
 4. 4. 1  单旋转
 4. 4. 2  双旋转
 4. 5  伸展树
 4. 5. 1  一个简单的想法(不能直接使用)
 4. 5. 2  展开
 4. 6  树的遍历
 4. 7  B树
 小结
 练习
 参考文献
 第5章  散列
 5. 1  一般想法
 5. 2  散列函数
 5. 3  分离链接法
 5. 4  开放定址法
 5. 4. 1  线性探测法
 5. 4. 2  平方探测法
 5. 4. 3  双散列法
 5. 5  再散列
 5. 6  可扩散列
 小结
 练习
 参考文献
 第6章  优先队列(堆)
 6. 1  模型
 6. 2  一些简单的实现
 6. 3  二叉堆
 6. 3. 1  结构性质
 6. 3. 2  堆序性质
 6. 3. 3  基本的堆操作
 6. 3. 4  其他的堆操作
 6. 4  优先队列的应用
 6. 4. 1  选择问题
 6. 4. 2  事件模拟
 6. 5  d-堆
 6. 6  左式堆
 6. 6. 1  左式堆性质
 6. 6. 2  左式堆操作
 6. 7  斜堆
 6. 8  二项队列
 6. 8. 1  二项队列结构
 6. 8. 2  二项队列操作
 6. 8. 3  二项队列实现
 小结
 练习
 参考文献
 第7章  排序
 7. 1  预备知识
 7. 2  插入排序
 7. 2. 1  算法
 7. 2. 2  插入排序的分析
 7. 3  一些简单排序算法的下界
 7. 4  希尔排序
 7. 5  堆排序
 7. 6  归并排序
 7. 7  快速排序
 7. 7. 1  选取枢纽元
 7. 7. 2  分割策略
 7. 7. 3  小数组
 7. 7. 4  实际的快速排序例程
 7. 7. 5  快速排序的分析
 7. 7. 6  选择问题的线性期望时间算法
 7. 8  排序算法的一般下界
 7. 9  桶式排序
 7. 10  外部排序
 7. 10. 1  为什么需要新算法
 7. 10. 2  外部排序模型
 7. 10. 3  简单算法
 7. 10. 4  多路合并
 7. 10. 5  多相合并
 7. 10. 6  替换选择
 小结
 练习
 参考文献
 第8章  不相交集ADT
 8. 1  等价关系
 8. 2  动态等价性问题
 8. 3  基本数据结构
 8. 4  灵巧求并算法
 8. 5  路径压缩
 8. 6  按秩求并和路径压缩的最坏情形
 8. 7  一个应用
 小结
 练习
 参考文献
 第9章  图论算法
 9. 1  若干定义
 9. 2  拓扑排序
 9. 3  最短路径算法
 9. 3. 1  无权最短路径
 9. 3. 2  Dijkstra算法
 9. 3. 3  具有负边值的图
 9. 3. 4  无圈图
 9. 3. 5  所有顶点对最短路径
 9. 4  网络流问题
 9. 5  最小生成树
 9. 5. 1  Prim算法
 9. 5. 2  Kruskal算法
 9. 6  深度优先搜索的应用
 9. 6. 1  无向图
 9. 6. 2  双连通性
 9. 6. 3  欧拉回路
 9. 6. 4  有向图
 9. 6. 5  查找强分支
 9. 7  NP完全性介绍
 9. 7. 1  难与易
 9. 7. 2  NP类
 9. 7. 3  NP完全问题
 小结
 练习
 参考文献
 第10章  算法设计技巧
 10. 1  贪婪算法
 10. 1. 1  一个简单的调度问题
 10. 1. 2  哈夫曼编码
 10. 1. 3  近似装箱问题
 10. 2  分治算法
 10. 2. 1  分治算法的运行时间
 10. 2. 2  最近点问题
 10. 2. 3  选择问题
 10. 2. 4  一些算术问题的理论改进
 10. 3  动态规划
 10. 3. 1  用表代替递归
 10. 3. 2  矩阵乘法的顺序安排
 10. 3. 3  最优二叉查找树
 10. 3. 4  所有点对最短路径
 10. 4  随机化算法
 10. 4. 1  随机数发生器
 10. 4. 2  跳跃表
 10. 4. 3  素性测试
 10. 5  回溯算法
 10. 5. 1  收费公路重建问题
 10. 5. 2  博弈
 小结
 练习
 参考文献
 第11章  摊还分析
 11. 1  一个无关的智力问题
 11. 2  二项队列
 11. 3  斜堆
 11. 4  斐波那契堆
 11. 4. 1  切除左式堆中的节点
 11. 4. 2  二项队列的懒惰合并
 11. 4. 3  斐波那契堆操作
 11. 4. 4  时间界的证明
 11. 5  伸展树
 小结
 练习
 参考文献
 第12章  高级数据结构及其实现
 12. 1  自顶向下伸展树
 12. 2  红黑树
 12. 2. 1  自底向上插入
 12. 2. 2  自顶向下红黑树
 12. 2. 3  自顶向下删除
 12. 3  确定性跳跃表
 12. 4  AA树
 12. 5  treap树
 12. 6  k-d树
 12. 7  配对堆
 小结
 练习
 参考文献
 附录A  一些库例程
 附录B  Co11ectioas类库
 索引