数据结构与抽象 Java版 第3版PDF电子书下载

第1章 袋子 1

袋子 1

袋子的行为 2

袋子的规格说明 3

接口 7

ADT袋子的使用 9

像使用自动售货机一样使用ADT 12

Java类库：接口Set 14

第2章 使用数组实现袋子 19

使用固定大小的数组实现ADT袋子 19

一个类比 19

一组核心方法 20

核心方法的实现 21

核心方法的测试 27

更多方法的实现 30

删除物品的方法 31

使用可变大小的数组实现ADT袋子 38

调整数组的大小 38

袋子的一种新的实现 41

使用数组实现ADT袋子的优缺点 43

第3章 使用链表实现袋子 48

链表 48

通过添加节点到表头来创建链表 49

ADT袋子的链表实现 50

私有的类Node 51

类LinkedBag的概要 52

一些核心方法的定义 53

核心方法的测试 56

方法getFrequencyOf 57

方法contains 58

从链表中删除物品 58

方法remove和clear 59

具有方法set和get的类Node 62

使用链表实现ADT袋子的优缺点 64

第4章 算法的效率 69

动机 69

算法效率的度量 70

基本操作次数的统计 72

最好、最坏和平均情况 74

大O表示法 74

程序结构的复杂度 77

效率的图形化表示 78

ADT袋子不同实现的效率 80

基于数组的实现 80

基于链表的实现 82

两种实现方法的比较 83

第5章 栈 89

ADT栈的规格说明 89

利用栈处理代数表达式 92

应用问题：中缀代数表达式中括号平衡的检查 93

应用问题：中缀表达式向后缀表达式的转换 97

应用问题：后缀表达式的求值 101

应用问题：中缀表达式的求值 102

程序栈 104

Java类库：类Stack 105

第6章 栈的实现 111

基于链表的实现 111

基于数组的实现 114

基于向量的实现 117

Java类库：Vector类 117

使用向量实现ADT栈 118

第7章 递归 123

什么是递归 123

跟踪一个递归方法 127

有返回值的递归方法 130

递归地处理一个数组 132

递归地处理一个链表 134

递归方法的时间效率 135

countDown的时间效率 135

计算xn的时间效率 137

一个复杂问题的简单解决方案 138

一个简单问题的拙劣解决方案 142

尾递归 144

间接递归 146

使用栈代替递归 146

第8章 排序引论 156

组织Java对数组排序的方法 157

选择排序 158

迭代选择排序 159

递归选择排序 160

选择排序的效率 161

插入排序 161

迭代插入排序 162

递归插入排序 163

插入排序的效率 165

链表的插入排序 165

希尔排序 167

Java代码 169

希尔排序的效率 170

算法比较 170

第9章 快速排序方法 176

归并排序 176

数组的归并 176

递归的归并排序 177

归并排序的效率 179

迭代的归并排序 181

Java类库中的归并排序 181

快速排序 182

快速排序的效率 182

创建划分 183

快速排序的Java代码 185

Java类库中的快速排序 187

基数排序 188

基数排序的伪代码 189

基数排序的效率 189

算法比较 190

第10章 队列、双端队列和优先队列 195

ADT队列 195

解决问题：模拟排队 198

解决问题：计算出售股票时的资本增益（一） 203

Java类库：接口Queue 206

ADT双端队列 207

解决问题：计算出售股票时的资本增益（二） 209

Java类库：接口Deque 209

Java类库：ArrayDeque类 211

ADT优先队列 211

解决问题：跟踪你的作业 212

Java类库：类PriorityQueue 214

第11章 队列、双端队列和优先队列的实现 219

基于链表队列的实现 219

基于数组队列的实现 222

循环数组 223

有一个未使用存储单元的循环数组 224

基于向量队列的实现 229

基于循环链表队列的实现 231

由两部分构成的循环链表 231

Java类库：类AbstractQueue 236

基于双向链表双端队列的实现 236

实现优先队列的可用方法 240

第12章 线性表 245

ADT线性表的规格说明 245

使用ADT线性表 250

Java类库：List接口 253

Jave类库：ArraryList类 253

第13章 用数组实现线性表 257

用数组实现ADT线性表 257

一个类比 257

Java实现 259

用数组实现ADT线性表的效率 264

用Vector实现ADT线性表 266

第14章 用链表实现线性表 272

操作链表节点 272

在多种位置加入节点 272

在多种位置删除节点 276

私有方法getNodeAt 276

开始实现 277

数据域和构造函数 278

在列表结尾加入 279

在列表给定位置加入 280

方法isEmpty和toArray 281

测试核心方法 283

继续实现 284

一个更好的实现 286

尾引用 286

用链表实现ADT列表的效率 289

Java类库：类 LinkedList 291

第15章 迭代器 296

迭代器是什么 296

Iterator接口 297

使用Iterator接口 298

独立类迭代器 302

内部类迭代器 305

基于链表实现 305

基于数组实现 309

为什么迭代器方法在它们自己的类中 311

ListIterator接口 313

使用ListIterator接口 315

ListIterator接口基于数组的实现 318

内部类 319

Java类库：Iterable接口 323

lterable和for-each循环 324

修改版接口List 324

第16章 有序表 330

ADT有序表的规格说明 330

使用ADT有序表 332

链表实现 333

方法add 334

链表实现的效率 340

使用ADT线性表的实现 340

效率问题 343

第17章 继承及线性表 348

使用继承实现有序表 348

设计一个基类 350

创建一个抽象基类 354

有序表的一种高效实现 355

方法add 356

第18章 查找 359

问题引入 359

查找无序数组 360

无序数组的迭代式顺序查找 360

无序数组的递归式顺序查找 361

顺序查找数组的效率 362

查找有序数组 362

有序数组的顺序查找 363

有序数组的二分查找 363

Java类库：方法binarySearch 367

二分查找数组的效率 367

查找无序链表 368

无序链表的迭代式顺序查找 369

无序链表的递归式顺序查找 369

顺序查找链表的效率 370

查找有序链表 370

有序链表的顺序查找 370

二分查找有序链表 371

查找方法的选择 371

第19章 词典 377

ADT词典规格说明 377

Java接口 380

迭代器 381

使用ADT词典 382

问题解决：电话号码本 382

问题解决：词频 386

问题解决：词的索引 389

Java类库：Map接口 392

第20章 词典的实现 396

基于数组的实现 396

一个无序数组词典 397

一个有序数组词典 401

基于向量的实例 404

链式实例 408

一个无序链式词典 409

一个有序链式词典 409

第21章 散列概述 415

散列是什么 415

散列函数 417

计算散列码 418

将散列码压缩成散列表的索引 420

处理冲突 421

用线性探测实现开放定址 421

用二次探测实现开放定址 424

用双重散列实现开放定址 425

开放定址的潜在问题 426

链地址 427

第22章 用散列实现词典 433

散列的效率 433

容载分析 434

开放定址消耗分析 434

链地址消耗分析 435

再散列 436

不同冲突解决方案的对比 437

用散列实现词典的实例 438

散列表中的条目 438

数据域和构造函数 439

getValue，remove和add方法 440

迭代器 445

Java类库：HashMap类 446

Java类库：HashSet类 446

第23章 树 450

树的概念 450

层次化的数据组织 450

树的术语 452

树的遍历 455

遍历二叉树 456

一般树的遍历 457

树的Java接口 458

树的通用接口 458

二叉树的接口 459

二叉树的例子 460

表达式树 460

决策树 461

二叉查找树 464

堆 466

一般树的例子 468

语法分析树 468

游戏树 469

第24章 树的实现 476

二叉树的节点 476

节点的接口 477

二叉树节点的实现 478

ADT二叉树的实现 479

创建基本二叉树 479

privateSetTree方法 480

访问器与更改器方法 482

计算高度和节点数 483

遍历 484

表达式树的实现 488

一般树 489

一般树的节点 489

用二叉树表示一般树 490

第25章 二叉查找树的实现 495

开始 495

二叉查找树接口 496

重复的条目 498

开始类定义 498

查找和检索 500

遍历 501

添加条目 501

递归实现 502

迭代实现 505

删除条目 506

删除一个叶子节点的条目 506

删除节点有一个孩子的条目 507

删除节点有两个孩子的条目 507

删除为根的条目 510

递归实现 510

迭代实现 513

操作的效率 516

平衡的重要性 517

节点添加的顺序 517

ADT词典实现 518

第26章 堆的实现 528

再论ADT堆 528

用数组表／示堆 528

插入条目 530

删除根 533

创建堆 535

堆排序 537

第27章 平衡查找树 545

AVL树 545

单旋转 546

双旋转 548

实现细节 551

2-3树 554

查找2-3树 555

添加条目至2-3树 556

添加时分裂节点 557

2-4树 558

添加条目至2-3树 558

比较AVL，2-3和2-4树 560

红黑树 561

红黑树的性质 562

添加条目到红黑树 562

Java类库：TreeMap类 567

B树 567

第28章 图 573

一些示例和术语 573

公路线路图 573

航空线路图 575

迷宫 576

树 577

遍历 577

广度优先遍历 578

深度优先遍历 579

拓扑排序 580

路径 583

寻找路径 583

无权图的最短路径算法 583

加权图中的最短路径 585

ADT图的Java接口 588

第29章 图的实现 597

两种实现的概述 597

邻接矩阵 597

邻接表 598

顶点和边 599

类Vertex的规格说明 599

内部类Edge 601

实现Vertex类 602

ADT图的实现 605

基本操作 605

图算法 608