数据结构与抽象

本书是数据结构的经典教材，内容涵盖线性结构、层次结构、图等数据结构，排序、查找等重要方法，以及算法的评估和迭代/递归实现方式等，并采用Java语言基于数组和链表实现了各种ADT。本书的组织方式独特，语言简洁，示例丰富，程序规范，习题多样。 本书新特色 新增加了一章讨论递归，介绍语法、语言及回溯。 增加了新的设计决策、注、安全说明及编程技巧。 在大部分章节中，增加了侧重游戏、电子商务及财务的练习和程序设计项目。 调整了某些主题的次序，相关的主题集中介绍，内容连贯。 修改了插图，使之更容易阅读和理解。 将“自测题”改名为“学习问题”，并将答案移至网站中，鼓励小组一起讨论答案。 书中包含了关于Java类的附录，而不是将其放在网站中。

出版者的话 译者序 前言 导论　组织数据 1 序言　设计类 3 封装 3 规范说明方法 5 注释 5 前置条件和后置条件 5 断言 6 Java接口 7 写一个接口 8 实现一个接口 9 接口作为数据类型 11 派生一个接口 12 接口内的命名常量 13 选择类 14 标识类 15 CRC卡 15 统一建模语言 16 重用类 18 练习 19 项目 19 第1章　包 22 什么是包 22 包的行为 23 规范说明一个包 23 一个接口 28 使用ADT包 30 像使用自动贩卖机一样使用ADT 33 ADT集合 34 Java类库：接口Set 35 本章小结 35 练习 36 项目 37 Java插曲1　泛型 40 泛型数据类型 40 接口中的泛型 40 泛型类 41 第2章　使用数组实现包 44 使用定长数组实现ADT包 44 模拟 44 一组核心方法 45 实现核心方法 46 让实现安全 52 测试核心方法 54 实现更多的方法 57 删除项的方法 59 使用变长数组实现ADT包 67 变长数组 67 包的新实现 69 使用数组实现ADT包的优缺点 71 本章小结 72 程序设计技巧 72 练习 73 项目 74 Java插曲2　异常 75 基础 75 处理异常 77 延缓处理：throws子句 77 现在处理：try-catch块 78 多个catch块 79 抛出异常 80 第3章　使用链式数据实现包 83 链式数据 83 添加到开头形成一个链表 84 ADT包的链式实现 85 私有类Node 85 类LinkedBag的框架 87 定义一些核心方法 88 测试核心方法 91 方法getFrequencyOf 92 方法contains 93 从链表中删除一项 94 方法remove和clear 95 有设置和获取方法的类Node 98 使用链表实现ADT包的优缺点 101 本章小结 101 程序设计技巧 101 练习 102 项目 102 第4章　算法的效率 104 动机 104 算法效率的衡量 105 统计基本操作 107 最优、最差和平均情况 109 大O表示 109 程序结构的复杂度 112 图示化效率 113 实现ADT包的效率 115 基于数组的实现 115 链式实现 117 两种实现的比较 118 本章小结 118 练习 118 项目 121 第5章　栈 123 ADT栈的规范说明 123 使用栈来处理代数表达式 127 问题求解：检查中缀代数表达式中平衡的分隔符 128 问题求解：将中缀表达式转换为后缀表达式 132 问题求解：计算后缀表达式的值 136 问题求解：计算中缀表达式的值 137 程序栈 139 Java类库：类Stack 140 本章小结 141 程序设计技巧 141 练习 141 项目 143 第6章　栈的实现 146 链式实现 146 基于数组的实现 149 基于向量的实现 152 Java类库：类Vector 153 使用Vector实现ADT栈 154 本章小结 155 练习 156 项目 156 Java插曲3　再论异常 158 程序员定义的异常类 158 继承和异常 162 finally块 163 第7章　队列、双端队列和优先队列 166 ADT队列 166 问题求解：模拟排队 169 问题求解：计算股票售出的资本收益 174 Java类库：接口Queue 177 ADT双端队列 177 问题求解：计算股票售出的资本收益 180 Java类库：接口Deque 181 Java类库：类ArrayDeque 182 ADT优先队列 183 问题求解：跟踪指派 184 Java类库：类PriorityQueue 185 本章小结 186 程序设计技巧 187 练习 187 项目 188 第8章　队列、双端队列和优先队列的实现 192 队列的链式实现 192 基于数组实现队列 196 循环数组 196 带一个未用元素的循环数组 198 队列的循环链式实现 203 两部分组成的循环链表 204 Java类库：类AbstractQueue 209 队列的双向链式实现 209 优先队列的可能实现方案 213 本章小结 213 程序设计技巧 214 练习 214 项目 215 第9章　递归 217 什么是递归 217 跟踪递归方法 221 返回一个值的递归方法 224 递归处理数组 226 递归处理链表 228 递归方法的时间效率 230 countDown的时间效率 230 计算xn的时间效率 231 尾递归 232 使用栈来替代递归 233 本章小结 234 程序设计技巧 234 练习 235 项目 237 第10章　线性表 240 ADT线性表的规范说明 240 使用ADT线性表 246 问题求解：使用大整数 250 Java类库：接口List 252 Java类库：类ArrayList 252 本章小结 253 练习 253 项目 254 第11章　使用数组实现线性表 257 使用数组实现ADT线性表 257 模拟 257 Java实现 259 使用数组实现ADT线性表的效率 266 本章小结 268 练习 268 项目 269 第12章　使用链式数据实现线性表 271 结点链表上的操作 271 在不同的位置添加结点 271 从不同的位置删除结点 275 私有方法getNodeAt 276 实现之初 277 数据域和构造方法 278 添加到线性表表尾 279 在线性表的给定位置添加 280 方法isEmpty和toArray 281 测试核心方法 283 继续实现 284 完善实现 286 尾引用 287 使用链表实现ADT线性表的效率 290 Java类库：类LinkedList 292 本章小结 292 练习 293 项目 294 Java插曲4　迭代器 296 什么是迭代器 296 接口Iterator 297 接口Iterable 298 使用接口Iterator 299 Iterable和for-each循环 302 接口ListIterator 303 再论接口List 306 使用接口ListIterator 306 第13章　ADT线性表的迭代器 309 实现迭代器的方法 309 独立类迭代器 309 内部类迭代器 312 链式实现 313 基于数组的实现 316 为什么迭代器方法在它自己的类中 319 基于数组实现接口ListIterator 320 内部类 322 本章小结 327 程序设计技巧 327 练习 327 项目 329 第14章　使用递归求解问题 331 困难问题的简单求解方案 331 简单问题的低劣求解方案 336 语言和语法 338 Java标识符语言 338 前缀表达式语言 339 前缀表达式的计算 342 间接递归 343 回溯 343 穿越迷宫 344 n皇后问题 345 本章小结 347 练习 348 项目 349 Java插曲5　再论泛型 352 接口Comparable 352 泛型方法 354 限定的类型参数 354 通配符 357 限定的通配符 357 第15章　排序简介 360 对数组进行排序的Java方法的组织 360 选择排序 361 迭代的选择排序 362 递归的选择排序 364 选择排序的效率 364 插入排序 365 迭代的插入排序 366 递归的插入排序 367 插入排序的效率 369 结点链表上的插入排序 369 希尔排序 372 算法 373 希尔排序的效率 374 算法比较 374 本章小结 375 程序设计技巧 375 练习 375 项目 377 第16章　更快的排序方法 379 归并排序 379 归并数组 379 递归的归并排序 380 归并排序的效率 382 迭代的归并排序 384 Java类库中的归并排序 384 快速排序 385 快速排序的效率 385 创建划分 386 实现快速排序 388 Java类库中的快速排序 390 基数排序 390 基数排序的伪代码 392 基数排序的效率 392 算法比较 393 本章小结 393 练习 394 项目 395 Java插曲6　可变及不可变对象 397 可变对象 397 不可变对象 398 创建只读类 399 伴生类 400 第17章　有序表 403 ADT有序表的规范说明 403 使用ADT有序表 406 链式实现 407 方法add 408 链式实现的效率 414 使用ADT线性表的实现 414 效率问题 417 本章小结 418 练习 419 项目 419 Java插曲7　继承和多态 421 继承的其他方面 421 何时使用继承 421 保护访问 422 抽象类和方法 422 接口与抽象类 424 多态 425 第18章　继承和线性表 430 使用继承实现有序表 430 设计一个基类 432 创建抽象基类 436 有序表的高效实现 439 方法add 439 本章小结 440 程序设计技巧 440 练习 440 项目 441 第19章　查找 443 问题 443 在无序数组中查找 443 无序数组中的迭代顺序查找 444 无序数组中的递归顺序查找 445 顺序查找数组的效率 446 在有序数组中查找 446 有序数组中的顺序查找 447 有序数组中的二分查找 447 Java类库：binarySearch方法 451 数组中二分查找的效率 451 在无序链表中查找 453 无序链表中的迭代顺序查找 453 无序链表中的递归顺序查找 453 链表中顺序查找的效率 454 在有序链表中查找 454 有序链表中的顺序查找 454 有序链表中的二分查找 455 查找方法的选择 455 本章小结 456 程序设计技巧 456 练习 456 项目 458 Java插曲8　三论泛型 460 多个泛型 460 第20章　字典 462 ADT字典的规范说明 462 Java接口 465 迭代器 466 使用ADT字典 468 问题求解：电话号码簿 468 问题求解：单词的频率 472 问题求解：单词的索引 475 Java类库：接口Map 478 本章小结 478 程序设计技巧 478 练习 479 项目 479 第21章　字典的实现 482 基于数组的实现 482 基于无序数组的字典 482 基于有序数组的字典 487 链式实现 491 无序链式字典 491 有序链式字典 492 本章小结 494 程序设计技巧 494 练习 494 项目 495 第22章　散列简介 496 什么是散列 496 散列函数 498 计算散列码 498 将散列码压缩为散列表的下标 501 解决冲突 502 开放地址的线性探查 502 开放地址的二次探查 507 开放地址的双散列 508 开放地址的潜在问题 510 拉链法 510 本章小结 513 练习 513 项目 514 第23章　使用散列实现字典 516 散列的效率 516 装填因子 516 开放地址法的代价 517 拉链法的代价 518 再散列 519 冲突解决机制的比较 520 使用散列实现字典 521 散列表中的项 521 数据域和构造方法 522 方法getValue、remove和add 523 迭代器 525 Java类库：类HashMap 526 Java类库：类HashSet 527 本章小结 527 练习 528 项目 528 第24章　树 531 树的概念 531 层次结构 531 树的术语 532 树的遍历 537 二叉树的遍历 537 一般树的遍历 538 用于树的Java接口 539 用于所有树的接口 539 用于二叉树的接口 540 二叉树示例 541 表达式树 541 决策树 543 二叉查找树 545 堆 547 一般树示例 548 解析树 549 游戏树 550 本章小结 550 练习 551 项目 553 第25章　树的实现 555 二叉树中的结点 555 二叉结点类 556 ADT二叉树的实现 557 创建基本二叉树 557 方法initializeTree 559 访问方法和赋值方法 561 计算高度和结点个数 562 遍历 563 表达式树的实现 567 一般树 568 用于一般树的结点 568 使用二叉树表示一般树 569 本章小结 570 程序设计技巧 570 练习 570 项目 572 Java插曲9　克隆 574 可克隆的对象 574 克隆一个数组 579 克隆一个链表 581 有序表的克隆 585 克隆一个二叉结点 587 第26章　二叉查找树的实现 589 入门知识 589 用于二叉查找树的接口 590 重复项 591 开始定义类 592 查找和获取 593 遍历 595 添加一项 595 递归实现 596 迭代实现 598 删除一项 600 删除叶结点中的项 600 删除仅有一个孩子的结点中的项 600 删除有两个孩子的结点中的项 601 删除根中的项 604 递归实现 604 迭代实现 607 操作效率 610 平衡的重要性 611 结点按什么次序添加 611 ADT字典的实现 612 本章小结 614 练习 615 项目 617 第27章　堆的实现 620 再论：ADT堆 620 使用数组表示堆 620 添加项 623 删除根 626 创建堆 628 堆排序 630 本章小结 633 练习 633 项目 634 第28章　平衡查找树 636 AVL树 636 单旋转 636 双旋转 639 实现细节 642 2-3树 646 在2-3树中进行查找 646 向2-3树中添加项 647 添加过程中结点的分裂 649 2-4树 650 向2-4树中添加项 650 AVL树、2-3树和2-4树的比较 652 红黑树 653 红黑树的特性 654 向红黑树中添加项 654 Java类库：类TreeMap 659 B树 659 本章小结 660 练习 660 项目 661 第29章　图 663 一些示例及术语 663 公路地图 663 航空公司的航线 665 迷宫 666 先修课程 666 树 667 遍历 667 广度优先遍历 668 深度优先遍历 669 拓扑序 670 路径 672 寻找路径 673 无权图中的最短路径 673 带权图中的最短路径 675 用于ADT图的Java接口 678 本章小结 681 练习 682 项目 684 第30章　图的实现 686 两个实现概述 686 邻接矩阵 686 邻接表 687 顶点和边 688 规范说明类Vertex 688 内部类Edge 690 类Vertex的实现 691 ADT图的实现 694 基本操作 694 图算法 697 本章小结 699 练习 699 项目 701 附录A　文档和程序设计风格 702 附录B　Java类 706 附录C　从其他类创建类 727 补充材料1　Java基础（在线） 补充材料2　文件输入输出（在线） 补充材料3　词汇表（在线） 补充材料4　学习问题答案（在线）

弗兰克·M. 卡拉诺（Frank M. Carrano） 是美国罗得岛大学计算机科学系荣誉退休教授，1969年获得美国锡拉丘兹大学计算机科学专业博士学位。他的研究兴趣包括数据结构、计算机科学教育、社会问题的计算处理和数值计算。Carrano教授撰写了多本著名的计算机科学高年级本科生教科书。 蒂莫西·M. 亨利（Timothy M. Henry） 是美国新英格兰理工学院计算机科学系副教授，1986年获得美国欧道明大学计算机科学专业硕士学位，2001年获得美国罗得岛大学应用数学专业博士学位

暂无其它内容！

暂时还没有人为这本书评论！