数据结构与算法分析 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 递归简论 6

1.4 Java中的一般对象 9

1.4.1 IntCell类 10

1.4.2 MemoryCell类 12

1.4.3实现一般的findMax方法 13

1.5异常 14

1.6.2 StringTokenizer对象 17

1.6输入和输出 17

1.6.1基本的流操作 17

1.6.3 顺序文件 18

1.7代码的组织 20

1.7.1包 20

1.7.2 MyInteger类 21

1.7.3关于效率的考虑 21

小结 22

练习 22

参考文献 24

第2章 算法分析 25

2.1数学基础 25

2.2模型 27

2.3要分析的问题 27

2.4 运行时间计算 29

2.4.1一个简单的例子 30

2.4.2一般法则 30

2.4.3最大子序列和问题的解 32

2.4.4运行时间中的对数 37

2.4.5检验你的分析 40

2.4.6分析结果的准确性 41

小结 41

练习 42

参考文献 46

第3章 表、栈和队列 47

3.1抽象数据类型（ADT） 47

3.2表ADT 47

3.2.1表的简单数组实现 48

3.2.2链表 48

3.2.3程序设计细节 49

3.2.4 链表 54

3.2.5循环链表 54

3.2.6例子 55

3.2.7链表的游标实现 59

3.3栈ADT 64

3.3.1栈模型 64

3.3.2栈的实现 64

3.3.3 应用 69

3.4队列ADT 75

3.4.1队列模型 75

3.4.2队列的数组实现 75

3.4.3队列的应用 79

小结 80

练习 80

4.1预备知识 85

第4章 树 85

4.1.1树的实现 86

4.1.2树的遍历及应用 87

4.2二叉树 89

4.2.1实现 90

4.2.2一个例子：表达式树 90

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

4.3.1 find 95

4.3.2 findMin和findMax 95

4.3.3 insert 96

4.3.4 remove 97

4.3.5平均情形分析 99

4.4 AVL树 101

4.4.1单旋转 102

4.4.2双旋转 105

4.5伸展树 110

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

4.5.2展开 112

4.6树的遍历 117

4.7 B树 118

小结 122

练习 123

参考文献 128

第5章 散列 131

5.1一般想法 131

5.2散列函数 131

5.3 分离链接法 133

5.4开放定址法 136

5.4.1线性探测法 137

5.4.2平方探测法 138

5.4.3双散列法 143

5.5再散列 144

5.6 可扩散列 145

小结 148

练习 149

参考文献 152

第6章 优先队列（堆） 155

6.1模型 155

6.2一些简单的实现 156

6.3二叉堆 156

6.3.1结构性质 156

6.3.2堆序性质 157

6.3.3基本的堆操作 158

6.3.4其他的堆操作 162

6.4优先队列的应用 164

6.4.1选择问题 165

6.4.2事件模拟 166

6.5 d－堆 167

6.6左式堆 167

6.6.1左式堆性质 167

6.6.2左式堆操作 168

6.7斜堆 173

6.8 二项队列 175

6.8.1二项队列结构 175

6.8.2 项队列操作 176

6.8.3二项队列实现 178

小结 182

练习 183

参考文献 187

7.2.1算法 189

7.2插入排序 189

第7章 排序 189

7.1预备知识 189

7.2.2插入排序的分析 190

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

7.4希尔排序 191

7.5堆排序 194

7.6 归并排序 197

7.7快速排序 202

7.7.1选取枢纽元 202

7.7.2分割策略 204

7.7.3 小数组 206

7.7.4实际的快速排序例程 206

7.7.5快速排序的分析 208

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

7.8排序算法的一般下界 212

7.9桶式排序 214

7.10外部排序 214

7.10.1为什么需要新算法 214

7.10.2外部排序模型 214

7.10.3简单算法 215

7.10.4多路合并 216

7.10.5多相合并 217

7.10.6替换选择 217

小结 218

练习 219

参考文献 223

第8章 不相交集ADT 227

8.1等价关系 227

8.2动态等价性问题 227

8.3基本数据结构 229

8.4灵巧求并算法 232

8.5路径压缩 233

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

8.7一个应用 240

小结 242

练习 242

参考文献 243

第9章 图论算法 245

9.1若干定义 245

9.2拓扑排序 247

9.3最短路径算法 250

9.3.1无权最短路径 251

9.3.2 Dijkstra算法 254

9.3.3具有负边值的图 259

9.3.4无圈图 260

9.3.5所有顶点对最短路径 262

9.4网络流问题 262

9.5最小生成树 266

9.5.1 Prim算法 267

9.5.2 Kruskal算法 269

9.6深度优先搜索的应用 271

9.6.1无向图 271

9.6.2双连通性 272

9.6.3欧拉回路 275

9.6.4有向图 278

9.6.5查找强分支 279

9.7 NP完全性介绍 281

9.7.1难与易 281

9.7.2 NP类 282

9.7.3 NP完全问题 283

小结 284

练习 285

参考文献 291

第10章 算法设计技巧 295

10.1贪婪算法 295

10.1.1一个简单的调度问题 296

10.1.2哈夫曼编码 298

10.1.3近似装箱问题 302

10.2分治算法 309

10.2.1分治算法的运行时间 309

10.2.2最近点问题 311

10.2.3选择问题 314

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

10.3.1用表代替递归 320

10.3动态规划 320

10.3.2矩阵乘法的顺序安排 322

10.3.3最优二叉查找树 325

10.3.4所有点对最短路径 327

10.4随机化算法 329

10.4.1随机数发生器 330

10.4.2跳跃表 333

10.4.3素性测试 335

10.5 溯算法 337

10.5.1 收费公路重建问题 338

10.5.2博弈 341

小结 347

练习 347

参考文献 353

11.1一个无关的智力问题 359

第11章 摊还分析 359

11.2二项队列 360

11.3斜堆 363

11.4斐波那契堆 365

11.4.1切除左式堆中的节点 366

11.4.2二项队列的懒惰合并 368

11.4.3斐波那契堆操作 370

11.4.4 时间界的证明 371

11.5伸展树 373

小结 376

练习 376

参考文献 377

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

12.1自顶向下伸展树 379

12.2红黑树 383

12.2.1自底向上插入 385

12.2.2自顶向下红黑树 386

12.2.3 自顶向下删除 390

12.3确定性跳跃表 391

12.4 AA树 396

12.5 treap树 401

12.6 k-d树 404

12.7配对堆 406

小结 411

练习 411

参考文献 414

附录A 一些库例程 417

附录B Collections类库 429

索引 445