数据结构与抽象：Java语言版

　　本书是为数据结构入门课程（通常课号是CS-2）而编写的教材。作者Frank Carrano和Walter Savitch在编写过程自始至终特别考虑到了Java与对象，为教师和学生提供了一种精心设计并经过教学实验的方式借助Java讲授ADT和对象。本书独特的设计将内容组织为相对较短的章。这种方式使学习更容易，并留出了教学的机动性。本书教给学生如何使用线性表、词典、栈、队列等等来组织数据。利用这些数据组织方式，学生们将学到算法设计的相关技术。书中的“编程提示”给读者额外的编程建议；大量的插图使讲解更形象生动；自测题贯穿各章，书末还给出了答案。本书适合作为数据结构的教学用书。

暂缺《数据结构与抽象：Java语言版》作者简介

第1章  Java类 11.1  对象与类 11.2  在Java类中使用方法 31.2.1  引用与别名 41.2.2  实参与形参 51.3  定义Java类 61.3.1  方法定义 71.3.2  传递实参 91.3.3  Name类的定义 121.3.4  构造函数 131.3.5  toString方法 151.3.6  静态的域与方法 161.4  包 17
第2章  从已有类创建新类 232.1  合成 232.2  继承 272.2.1  在构造函数中调用构造函数 302.2.2  基类的私有域与私有方法 312.2.3  方法的覆盖与重载 322.2.4  保护访问 352.2.5  多重继承 362.3  类型兼容性与基类 362.3.1  Object类 372.3.2  抽象类与抽象方法 392.4  多态性 40
第3章  类的设计 503.1  封装 503.2  方法的说明 523.3  Java接口 553.3.1  编写接口 553.3.2  实现接口 573.3.3  作为数据类型的接口 583.3.4  接口实现中的类型转换 583.3.5  扩展接口 593.3.6  接口中的符号常量 603.3.7  接口与抽象类的比较 613.4  类的选择 633.4.1  类的确定 643.4.2  CRC卡片 643.5  类的复用 66
第4章  线性表 704.1  ADT线性表说明 704.2  使用ADT线性表 784.3  Java类库：List接口 824.4  使用线性表如同使用自动售货机 82
第5章  用数组实现线性表 875.1  使用定长数组实现ADT线性表 875.1.1  类比 875.1.2  Java实现 895.2  使用动态扩展数组实现ADT线性表 965.2.1  扩展数组 975.2.2  线性表新的实现 985.3  使用向量实现ADT线性表 1005.4  用数组实现ADT线性表的优缺点 1045.5  Java类库 1045.5.1  ArrayList类 1045.5.2  Serializable接口 105
第6章  用链表实现线性表 1086.1  链表 1086.1.1  创建一个链表 1096.1.2  创建另一个链表 1116.1.3  仍创建一个链表 1136.2  Node类 1166.3  使用链表实现ADT线性表 1186.3.1  在线性表的末端插入元素 1196.3.2  在线性表的指定位置插入元素 1226.3.3  私有方法getNodeAt 1256.3.4  方法remove 1266.3.5  方法replace 1286.3.6  方法getEntry 1296.3.7  方法contains 1306.3.8  其余方法 1306.3.9  使用具有设置与获取方法的Node类 1316.4  表尾引用 1316.5  用链表实现ADT线性表的优缺点 1366.6  Java类库：LinkedList类 136
第7章  迭代器 1397.1  迭代器是什么 1397.1.1  基本迭代器 1407.1.2  对ADT进行修改的迭代器方法 1437.2  内部迭代器的实现 1457.3  将迭代器本身实现为一个类 1507.3.1  外部迭代器 1537.3.2  内部类迭代器 154
第8章  Java的迭代器接口 1608.1  Iterator接口 1608.2  实现Iterator接口 1638.2.1  基于链表实现 1638.2.2  基于数组实现 1658.3  ListIterator接口 1688.4  基于数组实现ListIterator接口 1748.5  Java类库：重温ArrayList和LinkedList 181
第9章  算法的效率 1849.1  动机 1849.2  度量算法的效率 1869.3  形式化 1929.4  效率的图形表示 1949.5  ADT线性表不同实现的效率 1989.5.1  基于数组实现 1989.5.2  基于链表实现 1999.5.3  比较上述实现 201第10章  递归 20610.1  何谓递归 20610.2  跟踪递归方法 21110.3  有返回值的递归方法 21310.4  递归处理数组 21610.5  递归处理链表 21810.6  递归方法的时间效率 22010.6.1  countDown的时间效率 22010.6.2  计算xn的时间效率 22210.7  困难问题的简单解法 22310.8  简单问题的拙劣解法 22810.9  尾递归 23010.10  协同递归 232
第11章  排序入门 23811.1  选择排序 23911.1.1  迭代选择排序 24011.1.2  递归选择排序 24211.1.3  选择排序的效率 24311.2  插入排序 24311.2.1  迭代插入排序 24411.2.2  递归插入排序 24611.2.3  插入排序的效率 24811.2.4  链表的插入排序 24811.3  希尔排序 25111.3.1  Java代码 25311.3.2  希尔排序的效率 25411.4  算法比较 255
第12章  更快的排序算法 25912.1  归并排序 25912.1.1  数组的归并 25912.1.2  递归归并排序 26012.1.3  归并排序的效率 26212.1.4  迭代归并排序 26412.1.5  Java类库中的归并排序 26412.2  快速排序 26512.2.1  快速排序的效率 26512.2.2  创建划分 26612.2.3  快速排序的Java代码 26812.2.4  Java类库中的快速排序 27212.3  基数排序 27212.3.1  基数排序的伪代码 27412.3.2  基数排序的效率 27412.4  算法比较 275
第13章  有序表 28013.1  ADT有序表的说明 28013.2  链表实现 28413.2.1  add方法 28513.2.2  链表实现的效率 29113.3  使用ADT线性表的实现 292
第14章  继承与线性表 29914.1  使用继承实现有序表 29914.2  基类的设计 30214.3  有序表的一种高效实现 306
第15章  可变对象、不可变对象及可克隆对象 31015.1  可变对象与不可变对象 31015.1.1  同伴类 31315.1.2  使用继承构建同伴类 31515.2  可克隆对象 31715.3  克隆体的有序表 32315.4  克隆数组 32515.5  克隆链表 327
第16章  查找 33416.1  问题描述 33416.2  查找无序数组 33516.2.1  迭代顺序查找无序数组 33516.2.2  递归顺序查找无序数组 33616.2.3  顺序查找数组的效率 33816.3  查找有序数组 33816.3.1  顺序查找有序数组 33816.3.2  折半查找有序数组 33916.3.3  Java类库：方法binarySearch 34316.3.4  折半查找数组的效率 34316.4  查找无序链表 34516.4.1  迭代顺序查找无序链表 34516.4.2  递归顺序查找无序链表 34616.4.3  顺序查找链表的效率 34716.5  查找有序链表 34716.5.1  顺序查找有序链表 34716.5.2  折半查找有序链表 34816.6  查找方法的选择 348
第17章  词典 35217.1  ADT词典的说明 35217.1.1  Java接口 35517.1.2  迭代器 35617.2  使用ADT词典 35717.2.1  电话号码簿 35717.2.2  词频 36117.2.3  词的索引 36317.3  Java类库：Map接口 365
第18章  词典的实现 36818.1  基于数组的实现 36818.1.1  元素 36918.1.2  基于数组的无序词典 37018.1.3  基于数组的有序词典 37118.2  基于向量的实现 37518.3  基于链表的实现 37718.3.1  元素 37718.3.2  基于链表的无序词典 37818.3.3  基于链表的有序词典 379
第19章  用散列实现词典 38519.1  什么是散列 38619.2  散列函数 38819.2.1  计算散列码 38819.2.2  将散列码压缩为散列表的索引 39119.3  处理冲突 39219.3.1  线性探测开放定址 39219.3.2  二次探测开放定址 39619.3.3  双散列开放定址 39719.3.4  开放定址的潜在问题 39819.3.5  链地址 39819.4  效率 40119.4.1  装填因子 40119.4.2  开放定址的开销 40219.4.3  链地址的开销 40319.5  再散列 40419.6  处理冲突的各方案比较 40519.7  使用散列的词典实现 40619.7.1  散列表中的元素 40619.7.2  数据域与构造函数 40719.7.3  方法getValue、remove及add 40819.7.4  迭代器 41519.8  Java类库：类HashMap 416
第20章  栈 42120.1  ADT栈的说明 42120.2  利用栈处理代数表达式 42520.2.1  检查中缀代数表达式中括号是否平衡 42520.2.2  将中缀表达式转化为后缀表达式 43020.2.3  后缀表达式求值 43720.2.4  中缀表达式求值 43920.3  程序栈 44120.4  使用栈代替递归 44320.5  Java类库：类Stack 445
第21章  栈的实现 44921.1  基于链表的实现 44921.2  基于数组的实现 45221.3  基于向量的实现 456
第22章  队列、双端队列及优先队列 46022.1  ADT队列的说明 46022.2  使用队列模拟排队 46422.3  使用队列计算股份销售的资本收益 47022.4  ADT双端队列的说明 47322.5  使用双端队列计算股份销售的资本收益 47522.6  ADT优先队列的说明 47622.7  使用优先队列计算股份销售的资本收益 477
第23章  队列、双端队列及优先队列的实现 48123.1  基于链表实现队列 48123.2  基于数组实现队列 48523.2.1  循环数组 48523.2.2  含有一个不用位置的循环数组 48823.3  基于向量实现队列 49323.4  基于循环链表实现队列 49523.5  基于双向链表实现双端队列 50023.6  实现优先队列可用方法 504
第24章  树 50724.1  树的概念 50724.1.1  层次化的组织 50724.1.2  树的术语 50924.2  树的遍历 51324.2.1  二叉树的遍历 51324.2.2  树的遍历 51524.3  树的Java接口 51624.3.1  所有树的接口 51624.3.2  二叉树接口 51724.4  二叉树举例 51924.4.1  表达式树 51924.4.2  决策树 52124.4.3  二叉查找树 52424.4.4  堆 52624.5  树举例 52824.5.1  语法分析树 52824.5.2  博弈树 530
第25章  树的实现 53425.1  二叉树的节点 53425.1.1  节点的接口 53525.1.2  BinaryNode的实现 53625.2  ADT二叉树的实现 53725.2.1  创建基本二叉树 53725.2.2  方法privateSetTree 53925.2.3  访问者与修改者方法 54225.2.4  计算高度与统计节点 54325.2.5  遍历 54425.3  表达式二叉树的实现 54925.4  树 55025.4.1  树的节点 55025.4.2  用二叉树表示树 551
第26章  二叉查找树的实现 55526.1  预备知识 55526.1.1  二叉查找树接口 55626.1.2  相同的元素 55826.1.3  开始类定义 55926.2  查找与提取 56026.3  遍历 56126.4  插入元素 56126.4.1  迭代实现 56226.4.2  递归实现 56426.5  删除元素 56926.5.1  删除叶子节点中的元素 56926.5.2  删除有一个孩子的节点中的元素 57026.5.3  删除有两个孩子的节点中的元素 57026.5.4  删除根节点中的元素 57326.5.5  迭代实现 57426.5.6  递归实现 57926.6  操作的效率 58226.6.1  平衡的重要性 58326.6.2  插入节点的顺序 58426.7  ADT词典的实现 585
第27章  堆的实现 59127.1  再论ADT堆 59127.2  用数组表示堆 59227.3  插入元素 594