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

作　者：	Mark Allen Weiss 冯舜玺冯舜玺
出版社：	机械工业出版社
丛编项：	计算机科学丛书
版权说明：	本书为公共版权或经版权方授权，请支持正版图书
标　签：	数据结构

ISBN	出版时间	包装	开本	页数	字数
未知	暂无	暂无	未知	0	暂无

作者简介

　　Mark Allen Weiss 佛罗里国际大学计算机学院教授，普林斯顿于数据结构与算法方面的著名教材还有：《数据结构与算法分析——C语言描述》，该书中文版已由机械工业出版社引进出版，以及《Data Structures and Problem Solving ：Using Java》、《 Data Structures and Prblem Solving：Using C++》等。他目前是Advanced Placement Computer Science Development Committee主席。

内容简介

本书是国外数据结构与算法分析方面的标准教材，使用最卓越的Java编程语言作为实现工具讨论了数据结构（组织大量数据的方法）和算法分析（对算法运行时间的估计）。书中着重阐述了抽象数据类型的概念，并对算法的效率、性能和运行时间做了全面的分析，为读者开发高效率的程序奠定了基础。本书可作为高级数据结构课程或者高等院校本科生、研究生算法分析课程的教材。本书作者在数据结构和算法分析方面卓有建树，他写的关于数据结构和算法分析的著作尤其畅销，并受到广泛好评。本书使用最卓越的Java编程语言作为实现工具对数据结构和算法进行了深入和独到的讨论。书中着重阐述了抽象数据类型的概念，并对算法的效率、性能和运行时间做了全面的分析。本书的主要特点：·包含用Java语言编写的丰富的样例程序，这些代码可从因特网上得到·专用一章来讨论算法设计技巧，包括贪婪算法、分治算法、动态规划算法、随机化算法以及回溯算法·阐述当前流行的论题和新的数据结构，如斐波那契堆、斜堆、二项队列、跳跃表和伸展树·专用一章讨论摊还分析，并进而考察书中描述的一些高级数据结构的性能·安排了一章讨论高级数据结构及其实现，其中包括红黑树、自上而下伸展树、k-d树、配对堆等·提出一些尚未解决和尚末完全解决的问题·书末附有两个关于Java语言的附录，附录A介绍基本的Java类，附录B则讨论Collections类库，介绍了许多与本书的数据结构和算法密切相关的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类库

索引