数据结构与抽象 Java语言版PDF|Epub|txt|kindle电子书版本网盘下载

数据结构与抽象 Java语言版PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

目录1

第1章　Java类1

1.1 对象与类1

1.2　在Java类中使用方法3

1.2.1 引用与别名4

1.2.2　实参与形参5

1.3　定义Java类6

1.3.1　方法定义7

1.3.2　传递实参9

1.3.3 Name类的定义12

1.3.4　构造函数13

1.3.5 toString方法15

1.3.6　静态的域与方法16

1.4　包17

第2章　从已有类创建新类23

2.1 合成23

2.2　继承27

2.2.1 在构造函数中调用构造函数30

2.2.2　基类的私有域与私有方法31

2.2.3　方法的覆盖与重载32

2.2.4　保护访问35

2.3　类型兼容性与基类36

2.2.5　多重继承36

2.3.1 Object类37

2.3.2　抽象类与抽象方法39

2.4　多态性40

第3章　类的设计50

3.1 封装50

3.2　方法的说明52

3.3 Java接口55

3.3.1　编写接口55

3.3.2　实现接口57

3.3.4　接口实现中的类型转换58

3.3.3　作为数据类型的接口58

3.3.5　扩展接口59

3.3.6　接口中的符号常量60

3.3.7　接口与抽象类的比较61

3.4　类的选择63

3.4.1　类的确定64

3.4.2 CRC卡片64

3.5　类的复用66

第4章　线性表70

4.1　ADT线性表说明70

4.2　使用ADT线性表78

4.4　使用线性表如同使用自动售货机82

4.3 Java类库：List接口82

5.1　使用定长数组实现ADT线性表87

5.1.1 类比87

第5章　用数组实现线性表87

5.1.2 Java实现89

5.2　使用动态扩展数组实现ADT线性表96

5.2.1　扩展数组97

5.2.2　线性表新的实现98

5.3　使用向量实现ADT线性表100

5.5 Java类库104

5.5.1 ArrayList类104

5.4　用数组实现ADT线性表的优缺点104

5.5.2 Serializable接口105

第6章　用链表实现线性表108

6.1　链表108

6.1.1　创建一个链表109

6.1.2　创建另一个链表111

6.1.3　仍创建一个链表113

6.2 Node类116

6.3　使用链表实现ADT线性表118

6.3.1 在线性表的末端插入元素119

6.3.2　在线性表的指定位置插入元素122

6.3.3　私有方法getNodeAt125

6.3.4　方法remove126

6.3.5　方法replace128

6.3.6　方法getEntry129

6.3.7　方法contains130

6.3.8　其余方法130

6.3.9　使用具有设置与获取方法的Node类131

6.4　表尾引用131

6.5　用链表实现ADT线性表的优缺点136

6.6　Java类库：LinkedList类136

7.1　迭代器是什么139

第7章　迭代器139

7.1.1　基本迭代器140

7.1.2　对ADT进行修改的迭代器方法143

7.2 内部迭代器的实现145

7.3　将迭代器本身实现为一个类150

7.3.1　外部迭代器153

7.3.2　内部类迭代器154

第8章　Java的迭代器接口160

8.1 Iterator接口160

8.2　实现Iterator接口163

8.2.1　基于链表实现163

8.2.2　基于数组实现165

8.3 ListIterator接口168

8.4　基于数组实现ListIterator接口174

8.5 Java类库：重温ArrayList和LinkedList181

第9章　算法的效率184

9.1　动机184

9.2　度量算法的效率186

9.3　形式化192

9.4　效率的图形表示194

9.5 ADT线性表不同实现的效率198

9.5.1　基于数组实现198

9.5.2　基于链表实现199

9.5.3 比较上述实现201

第10章　递归206

10.1　何谓递归206

10.2　跟踪递归方法211

10.3　有返回值的递归方法213

10.4　递归处理数组216

10.5　递归处理链表218

10.6　递归方法的时间效率220

10.6.1 countDown的时间效率220

10.6.2　计算xn的时间效率222

10.7 困难问题的简单解法223

10.8　简单问题的拙劣解法228

10.9　尾递归230

10.10　协同递归232

第11章　排序入门238

11.1　选择排序239

11.1.1　迭代选择排序240

11.1.2　递归选择排序242

11.1.3　选择排序的效率243

11.2　插入排序243

11.2.1　迭代插入排序244

11.2.2　递归插入排序246

11.2.4　链表的插入排序248

11.2.3　插入排序的效率248

11.3　希尔排序251

11.3.1　Java代码253

11.3.2　希尔排序的效率254

11.4　算法比较255

第12章　更快的排序算法259

12.1　归并排序259

12.1.1 数组的归并259

12.1.2　递归归并排序260

12.1.3 归并排序的效率262

12.1.5　Java类库中的归并排序264

12.1.4　迭代归并排序264

12.2　快速排序265

12.2.1　快速排序的效率265

12.2.2　创建划分266

12.2.3　快速排序的Java代码268

12.2.4　Java类库中的快速排序272

12.3　基数排序272

12.3.1　基数排序的伪代码274

12.3.2　基数排序的效率274

12.4　算法比较275

13.1 ADT有序表的说明280

第13章　有序表280

13.2　链表实现284

13.2.1 add方法285

13.2.2　链表实现的效率291

13.3 使用ADT线性表的实现292

第14章　继承与线性表299

14.1　使用继承实现有序表299

14.2　基类的设计302

14.3 有序表的一种高效实现306

第15章　可变对象、不可变对象及可克隆对象310

15.1 可变对象与不可变对象310

15.1.1　同伴类313

15.1.2　使用继承构建同伴类315

15.2　可克隆对象317

15.3　克隆体的有序表323

15.4　克隆数组325

15.5　克隆链表327

第16章　查找334

16.1　问题描述334

16.2　查找无序数组335

16.2.1　迭代顺序查找无序数组335

16.2.2　递归顺序查找无序数组336

16.3.1　顺序查找有序数组338

16.2.3　顺序查找数组的效率338

16.3　查找有序数组338

16.3.2　折半查找有序数组339

16.3.3　Java类库：方法binarySearch343

16.3.4　折半查找数组的效率343

16.4　查找无序链表345

16.4.1 迭代顺序查找无序链表345

16.4.2　递归顺序查找无序链表346

16.4.3　顺序查找链表的效率347

16.5　查找有序链表347

16.5.1　顺序查找有序链表347

16.6　查找方法的选择348

16.5.2　折半查找有序链表348

第17章　词典352

17.1 ADT词典的说明352

17.1.1 Java接口355

17.1.2　迭代器356

17.2　使用ADT词典357

17.2.1 电话号码簿357

17.2.2　词频361

17.2.3　词的索引363

17.3 Java类库：Map接口365

18.1　基于数组的实现368

第18章　词典的实现368

18.1.1　元素369

18.1.2　基于数组的无序词典370

18.1.3　基于数组的有序词典371

18.2　基于向量的实现375

18.3　基于链表的实现377

18.3.1　元素377

18.3.2　基于链表的无序词典378

18.3.3　基于链表的有序词典379

第19章　用散列实现词典385

19.1　什么是散列386

19.2.1　计算散列码388

19.2　散列函数388

19.2.2　将散列码压缩为散列表的索引391

19.3　处理冲突392

19.3.1　线性探测开放定址392

19.3.2　二次探测开放定址396

19.3.3　双散列开放定址397

19.3.4　开放定址的潜在问题398

19.3.5 链地址398

19.4　效率401

19.4.1　装填因子401

19.4.2　开放定址的开销402

19.4.3　链地址的开销403

19.5　再散列404

19.6　处理冲突的各方案比较405

19.7　使用散列的词典实现406

19.7.1 散列表中的元素406

19.7.2　数据域与构造函数407

19.7.3　方法getValue、remove及add408

19.7.4　迭代器415

19.8 Java类库：类HashMap416

第20章　栈421

20.1 ADT栈的说明421

20.2.1　检查中缀代数表达式中括号是否平衡425

20.2　利用栈处理代数表达式425

20.2.2　将中缀表达式转化为后缀表达式430

20.2.3　后缀表达式求值437

20.2.4　中缀表达式求值439

20.3　程序栈441

20.4　使用栈代替递归443

20.5 Java类库：类Stack445

第21章　栈的实现449

21.1　基于链表的实现449

21.2　基于数组的实现452

21.3　基于向量的实现456

第22章 队列、双端队列及优先队列460

22.1　ADT队列的说明460

22.2　使用队列模拟排队464

22.3 使用队列计算股份销售的资本收益470

22.4 ADT双端队列的说明473

22.5　使用双端队列计算股份销售的资本收益475

22.6　ADT优先队列的说明476

22.7　使用优先队列计算股份销售的资本收益477

第23章 队列、双端队列及优先队列的实现481

23.1　基于链表实现队列481

23.2.1　循环数组485

23.2　基于数组实现队列485

23.2.2　含有一个不用位置的循环数组488

23.3　基于向量实现队列493

23.4　基于循环链表实现队列495

23.5　基于双向链表实现双端队列500

23.6　实现优先队列可用方法504

第24章　树507

24.1　树的概念507

24.1.1　层次化的组织507

24.1.2　树的术语509

24.2.1　二叉树的遍历513

24.2　树的遍历513

24.2.2　树的遍历515

24.3　树的Java接口516

24.3.1　所有树的接口516

24.3.2　二叉树接口517

24.4　二叉树举例519

24.4.1　表达式树519

24.4.2　决策树521

24.4.3　二叉查找树524

24.4.4　堆526

24.5　树举例528

24.5.1　语法分析树528

24.5.2　博弈树530

第25章　树的实现534

25.1　二叉树的节点534

25.1.1 节点的接口535

25.1.2 BinaryNode的实现536

25.2 ADT二叉树的实现537

25.2.1　创建基本二叉树537

25.2.2　方法privateSetTree539

25.2.3　访问者与修改者方法542

25.2.4 计算高度与统计节点543

25.2.5　遍历544

25.3　表达式二叉树的实现549

25.4　树550

25.4.1 树的节点550

25.4.2　用二叉树表示树551

第26章　二叉查找树的实现555

26.1 预备知识555

26.1.1　二叉查找树接口556

26.1.2　相同的元素558

26.1.3　开始类定义559

26.2　查找与提取560

26.3 遍历561

26.4　插入元素561

26.4.1　迭代实现562

26.4.2　递归实现564

26.5　删除元素569

26.5.1 删除叶子节点中的元素569

26.5.2　删除有一个孩子的节点中的元素570

26.5.3　删除有两个孩子的节点中的元素570

26.5.4　删除根节点中的元素573

26.5.5　迭代实现574

26.5.6　递归实现579

26.6　操作的效率582

26.6.1　平衡的重要性583

26.6.2　插入节点的顺序584

26.7 ADT词典的实现585

第27章　堆的实现591

27.1　再论ADT堆591

27.2　用数组表示堆592

27.3　插入元素594

27.4　删除根597

27.5　创建堆600

27.6　堆排序602

第28章　平衡查找树606

28.1 AVL树606

28.1.1　单旋转607

28.1.2　双旋转608

28.1.3 实现细节612

28.2 2-3树615

28.2.1 2-3树的查找616

28.2.2　向2-3树插入元素617

28.2.3　插入期间分裂节点619

28.3 2-4树620

28.3.1 向2-4树插入元素620

28.3.2 比较AVL树、2-3树及2-4树622

28.4　红黑树623

28.4.1　红黑树的特性624

28.4.2　向红黑树插入元素625

28.4.3 Java类库：类TreeMap629

28.5 B树629

第29章　图633

29.1　一些例子与术语633

29.1.1　公路地图633

29.1.2　航线636

29.1.3　迷宫636

29.1.4　先修课程637

29.1.5　树637

29.2　遍历638

29.2.2　深度优先遍历639

29.2.1　广度优先遍历639

29.3　拓扑顺序642

29.4　路径644

29.4.1　寻找路径644

29.4.2　无权图中的最短路径644

29.4.3 带权图中的最短路径647

29.5 ADT图的Java接口650

第30章　图的实现657

30.1 两种实现的概述657

30.1.1　邻接矩阵657

30.1.2　邻接表658

30.2.1　说明类Vertex659

30.2　顶点与边659

30.2.2　类Edge661

30.2.3　实现类Vertex663

30.3 ADT图的实现664

30.3.1 基本操作665

30.3.2　图的算法668

附录A Java基础673

附录B　异常处理723

附录C　文件输入与输出732

附录D　文档与程序设计风格748

附录E 自测题答案754