数据结构与算法分析 Java 语言描述PDF|Epub|txt|kindle电子书版本网盘下载

数据结构与算法分析 Java 语言描述PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第1章 引论1

1.1本书讨论的内容1

1.2数学知识复习2

1.2.1指数2

1.2.2对数2

1.2.3级数3

1.2.4模运算4

1.2.5证明的方法4

1.3递归简论5

1.4实现泛型特性构件pre-Java 58

1.4.1使用Object表示泛型9

1.4.2基本类型的包装9

1.4.3使用接口类型表示泛型10

1.4.4数组类型的兼容性10

1.5利用Java 5泛性实现泛型特性成分12

1.5.1简单的泛型类和接口12

1.5.2自动装箱／拆箱12

1.5.3带有限制的通配符13

1.5.4泛型static方法14

1.5.5类型限界15

1.5.6类型擦除16

1.5.7对于泛型的限制16

1.6函数对象17

小结19

练习19

参考文献20

第2章 算法分析22

2.1数学基础22

2.2模型24

2.3要分析的问题24

2.4运行时间计算26

2.4.1一个简单的例子26

2.4.2一般法则27

2.4.3最大子序列和问题的求解28

2.4.4运行时间中的对数33

2.4.5检验你的分析36

2.4.6分析结果的准确性37

小结38

练习38

参考文献42

第3章表、栈和队列44

3.1抽象数据类型44

3.2表ADT44

3.2.1表的简单数组实现45

3.2.2简单链表45

3.3 Java Collections API中的表46

3.3.1 Collection接口46

3.3.2Iterator接口47

3.3.3 List接口、ArrayList类和LinkedList类48

3.3.4例：remove方法对LinkedList类的使用50

3.3.5关于ListIterator接口51

3.4 ArrayList类的实现52

3.4.1基本类52

3.4.2迭代器、Java嵌套类和内部类55

3.5 LinkedList类的实现58

3.6栈ADT64

3.6.1栈模型64

3.6.2栈的实现64

3.6.3应用65

3.7队列ADT70

3.7.1队列模型70

3.7.2队列的数组实现71

3.7.3队列的应用72

小结73

练习73

第4章树77

4.1预备知识77

4.1.1树的实现78

4.1.2树的遍历及应用78

4.2二叉树82

4.2.1实现82

4.2.2例子：表达式树82

4.3查找树ADT——二叉查找树84

4.3.1 contains方法86

4.3.2 findMin方法和findMax方法87

4.3.3 insert方法88

4.3.4 remove方法89

4.3.5平均情况分析90

4.4 AVL树92

4.4.1单旋转94

4.4.2双旋转96

4.5伸展树100

4.5.1一个简单的想法（不能直接使用）101

4.5.2展开102

4.6树的遍历106

4.7 B树108

4.8标准库中的集合与映射111

4.8.1关于Set接口112

4.8.2关于Map接口112

4.8.3 TreeSet类和TreeMap类的实现112

4.8.4使用多个映射的例113

小结118

练习118

参考文献123

第5章 散列126

5.1一般想法126

5.2散列函数126

5.3分离链接法128

5.4不用链表的散列表132

5.4.1线性探测法132

5.4.2平方探测法133

5.4.3双散列138

5.5再散列139

5.6标准库中的散列表141

5.7可扩散列142

小结144

练习145

参考文献148

第6章 优先队列（堆）150

6.1模型150

6.2一些简单的实现151

6.3二叉堆151

6.3.1结构性质151

6.3.2堆序性质153

6.3.3基本的堆操作153

6.3.4其他的堆操作155

6.4优先队列的应用159

6.4.1选择问题159

6.4.2事件模拟160

6.5 d-堆161

6.6左式堆162

6.6.1左式堆性质162

6.6.2左式堆操作163

6.7斜堆168

6.8二项队列169

6.8.1二项队列结构170

6.8.2二项队列操作170

6.8.3二项队列的实现172

6.9标准库中的优先队列177

小结177

练习177

参考文献181

第7章 排序183

7.1预备知识183

7.2插入排序183

7.2.1算法183

7.2.2插入排序的分析184

7.3一些简单排序算法的下界184

7.4希尔排序185

7.5堆排序188

7.6归并排序191

7.7快速排序195

7.7.1选取枢纽元197

7.7.2分割策略197

7.7.3小数组199

7.7.4实际的快速排序例程199

7.7.5快速排序的分析200

7.7.6选择问题的线性期望时间算法203

7.8排序算法的一般下界205

7.9桶式排序207

7.10外部排序207

7.10.1为什么需要一些新的算法207

7.10.2外部排序模型207

7.10.3简单算法208

7.10.4多路合并209

7.10.5多相合并210

7.10.6替换选择210

小结211

练习题212

参考文献216

第8章 不相交集类219

8.1等价关系219

8.2动态等价性问题219

8.3基本数据结构221

8.4灵巧求并算法223

8.5路径压缩225

8.6路径压缩和按秩求并的最坏情形227

8.7一个应用231

小结233

练习题233

参考文献234

第9章 图论算法237

9.1若干定义237

9.2拓扑排序239

9.3最短路径算法241

9.3.1无权最短路径242

9.3.2 Dijkstra算法246

9.3.3具有负边值的图250

9.3.4无圈图251

9.3.5所有点对最短路径253

9.3.6最短路径的例子253

9.4网络流问题255

9.5最小生成树258

9.5.1 Prim算法259

9.5.2 Kruskal算法260

9.6深度优先搜索的应用262

9.6.1无向图262

9.6.2双连通性263

9.6.3欧拉回路266

9.6.4有向图268

9.6.5查找强分支269

9.7 NP-完全性介绍270

9.7.1难与易270

9.7.2 NP类271

9.7.3 NP完全问题272

小结273

练习273

参考文献279

第10章 算法设计技巧282

10.1贪婪算法282

10.1.1一个简单的调度问题282

10.1.2哈夫曼编码284

10.1.3近似装箱问题287

10.2分治算法293

10.2.1分治算法的运行时间293

10.2.2最近点问题295

10.2.3选择问题297

10.2.4一些算术问题的理论改进300

10.3动态规划303

10.3.1用一个表代替递归303

10.3.2矩阵乘法的顺序安排305

10.3.3最优二叉查找树306

10.3.4所有点对最短路径309

10.4随机化算法311

10.4.1随机数发生器312

10.4.2跳跃表315

10.4.3素性测试316

10.5回溯算法319

10.5.1收费公路重建问题319

10.5.2博弈322

小结328

练习328

参考文献335

第11章 摊还分析339

11.1一个无关的智力问题339

11.2二项队列340

11.3斜堆343

11.4斐波那契堆345

11.4.1切除左式堆中的节点345

11.4.2二项队列的懒惰合并347

11.4.3斐波那契堆操作348

11.4.4时间界的证明349

11.5伸展树351

小结353

练习354

参考文献355

第12章 高级数据结构及其实现356

12.1自顶向下伸展树356

12.2红黑树362

12.2.1自底向上的插入362

12.2.2自顶向下红黑树363

12.2.3自顶向下的删除367

12.3确定性跳跃表368

12.4 AA树373

12.5 treap树378

12.6 k-d树381

12.7配对堆383

小结389

练习389

参考文献391

索引394