内容简介

本书系统讲解数据结构和算法，并分析了算法的复杂性。本书选择Jaya语言以面向对象的方式描述数据结构，还特别强调了封装和分解的信息隐藏原理。主要内容包括：面向对象编程的基本原理，判定算法效率的方法，堆栈、队列及其应用，对于多种递归的详细讨论，二叉树、B树、2-4树等的查找和遍历等，分析排序、散列等数据结构的应用，图、NP完整性，数据压缩算法、存储管理技术以及自动机理论和字符串匹配等算法。本书适合作为高等院校计算机专业的教材，也是计算机算法方面的重要参考书。

作品目录

第1章 java语言的面向对象编程 1

1.1 java入门 1

1.1.1 变量的声明 1

1.1.2 运算符 3

1.1.3 选择语句 3

1.1.4 循环语句 4

1.1.5 异常处理 5

1.2 java面向对象编程 6

1.2.1 封装 6

1.2.2 抽象数据类型 12

1.2.3 继承 13

1.2.4 多态性 16

1.3 输入和输出 19

1.3.1 输入、输出字节 21

1.3.2 行输入 21

1.3.3 标志输入：单词和数字 22

1.3.4 基本数据类型的输入和输出 22

1.3.5 对象的输入和输出 23

1.3.6 随机存取文件 24

1.4 java和指针 24

1.5 java.util中的向量 28

1.6 数据结构和面向对象的编程 32

1.7 示例学习：随机存取文件 32

1.8 习题 39

1.9 编程作业 41

参考文献 42

第2章 复杂性分析 44

2.1 计算复杂性和渐近复杂性 44

2.2 大o表示法 44

2.3 大o表示法的性质 46

2.4 w和q表示法 47

2.5 可能出现的问题 48

2.6 复杂性示例 48

2.7 寻找渐近复杂性：示例 49

2.8 最好的、平均的和最坏的情况 51

2.9 平摊复杂性 53

2.10 np完整性 56

2.11 习题 58

参考文献 60

第3章 链表 62

3.1 单向链表 62

3.1.1 插入 66

3.1.2 删除 67

3.1.3 查找 70

3.2 双向链表 72

3.3 循环链表 74

3.4 跳转表 75

3.5 自组织表 80

3.6 稀疏表 83

3.7 java.util的链表 85

3.7.1 linkedlist 85

3.7.2 arraylist 89

3.8 结论 91

3.9 示例学习：图书馆 92

3.10 习题 99

3.11 编程作业 101

参考文献 103

第4章 堆栈和队列 105

4.1 堆栈 105

4.2 队列 111

4.3 优先级队列 117

4.4 示例学习：脱离迷宫 118

4.5 习题 122

4.6 编程作业 124

参考文献 125

第5章 递归 126

5.1 递归定义 126

5.2 方法调用和递归实现 128

5.3 剖析递归调用 129

5.4 尾递归 132

5.5 非尾递归 133

5.6 间接递归 137

5.7 嵌套递归 139

5.8 过分递归 139

5.9 回溯 142

5.10 小结 147

5.11 示例学习：递归下降解 推?147

5.12 习题 153

5.13 编程作业 155

参考文献 157

第6章 二叉树 158

6.1 树、二叉树和二叉查找树 158

6.2 二叉树实现 161

6.3 搜索二叉查找树 163

6.4 树的遍历 164

6.4.1 广度优先遍历 165

6.4.2 深度优先遍历 165

6.4.3 无堆栈深度优先遍历 171

6.5 插入 175

6.6 删除 178

6.6.1 归并删除法 179

6.6.2 复制删除法 181

6.7 树的平衡 183

6.7.1 dsw算法 185

6.7.2 avl树 187

6.8 自调整树 191

6.8.1 自重构树 192

6.8.2 伸展树 192

6.9 堆 196

6.9.1 堆作为优先级队列 197

6.9.2 以堆的形式组织数组 199

6.10 波兰表示法和表达式树 202

6.11 示例学习：计算单词频率 206

6.12 习题 212

6.13 编程作业 214

参考文献 217

第7章 多分树 220

7.1 b树家族 220

7.1.1 b树 221

7.1.2 b*树 229

7.1.3 b+树 230

7.1.4 前缀b+树 232

7.1.5 比特树 233

7.1.6 r树 235

7.1.7 2-4树 236

7.1.8 java.util中的树 248

7.2 检索树 257

7.3 结论 264

7.4 示例学习：拼写检查程序 264

7.5 习题 273

7.6 编程作业 274

参考文献 277

第8章 图 279

8.1 图的表示法 280 ..

8.2 图的遍历 281

8.3 最短路径 284

8.4 圈检测 291

8.5 生成树 293

8.6 连通性 297

8.6.1 无向图的连通性 297

8.6.2 有向图的连通性 300

8.7 拓扑排序 302

8.8 网络 303

8.8.1 最大流 303

8.8.2 最小代价的最大流量 311

8.9 匹配 313

8.9.1 稳定匹配问题 318

8.9.2 分配问题 319

8.9.3 非二部图中的匹配 321

8.10 欧拉图和哈密顿图 322

8.10.1 欧拉图 322

8.10.2 哈密顿图 324

8.11 图的着色 329

8.12 图论中的np完整性问题 331

8.12.1 团问题 331

8.12.2 3色问题 332

8.12.3 顶点覆盖问题 333

8.12.4 哈密顿回路问题 333

8.13 示例学习：典型代表问题 335

8.14 习题 336

8.15 编程作业 345

参考文献 346

第9章 排序 349

9.1 基本排序算法 350

9.1.1 插入排序 350

9.1.2 选择排序 352

9.1.3 冒泡排序 353

9.2 决策树 355

9.3 高效排序算法 357

9.3.1 shell排序 357

9.3.2 堆排序 360

9.3.3 快速排序 363

9.3.4 归并排序 367

9.3.5 基数排序 370

9.4 java.util中的排序 373

9.5 总结 375

9.6 示例学习：多项式加法 376

9.7 习题 383

9.8 编程作业 384

参考文献 384

第10章 散列 387

10.1 散列函数 387

10.1.1 除法 387

10.1.2 折叠法 388

10.1.3 平方取 泻　?388

10.1.4 提取方法 388

10.1.5 基数变换 388

10.2 冲突解决 389

10.2.1 开放定址法 389

10.2.2 链 393

10.2.3 桶定址法 394

10.3 删除 394

10.4 完全散列函数 395

10.4.1 cichelli方法 396

10.4.2 fhcd算法 398

10.5 可扩展文件的散列函数 400

10.5.1 可扩展散列 400

10.5.2 线性散列 402

10.6 java.util中的散列 404

10.6.1 hashmap 404

10.6.2 hashset 407

10.6.3 hashtable 410

10.7 示例学习：桶散列 414

10.8 习题 421

10.9 编程作业 422

参考文献 423

第11章 数据压缩 425

11.1 数据压缩的条件 425

11.2 赫夫曼编码 426

11.3 顺串长度编码 436

11.4 ziv-lempel编码 437

11.5 示例学习：结合顺串长度编码的 赫夫曼方法 439

11.6 习题 448

11.7 编程作业 448

参考文献 449

第12章 存储管理 451

12.1 顺序适配方法 451

12.2 非顺序适配算法 452

12.3 无用单元收集 459

12.3.1 标记和清除算法 459

12.3.2 复制方法 465

12.3.3 增量式无用单元收集 466

12.4 总结 471

12.5 示例学习：内置无用单元收集器 472

12.6 习题 473

12.7 编程作业 479

参考文献 481

第13章 字符串匹配 484

13.1 精确字符串匹配 484

13.1.1 直接匹配算法 484

13.1.2 knuth-morris-pratt算法 486

13.1.3 boyer-moore算法 492

13.1.4 多路查找 500

13.1.5 面向位方法 501

13.1.6 词匹配集 504

13.1.7 正则表达式匹配 510

13.1.8 后缀检索树和树 513

13.1.9 后缀数组 517

13.2 近似字符串匹配 518

13.2.1 字符串相似度 519

13.2.2 k误配的字符串匹配 524

13.3 示例学习：最长公共子字符串 526

13.4 习题 533

13.5 编程作业 535

参考文献 535

附录a 大o的计算 537

a.1 谐波级数 537

a.2 函数lg (n!) 的近似 537

a.3 快速排序平均情况的大o 538

a.4 随机二叉树中的平均路径长度 540

a.5 avl树中的节点数量 541

附录b np完整性 542

索引 554