数据抽象和问题求解 Java语言描述PDF电子书下载

目录 3

第Ⅰ部分 问题求解技术 3

第1章　编程原理与软件工程 3

1.1 问题求解与软件工程 3

1.1.1 问题求解的含义 3

1.1.2　软件的生命周期 4

1.1.3　优秀解决方案的定义 10

1.2.1　抽象与信息隐藏 11

1.2　模块化设计 11

1.2.2　面向对象的设计 13

1.2.3 自上而下的设计 14

1.2.4　一般设计原则 15

1.3　关键编程问题 15

1.3.1　模块化 15

1.3.2　可修改 16

1.3.3 易用 17

1.3.4　防故障编程 18

1.3.5　风格 22

1.3.6　调试 25

1.4 小结 27

1.5 提示 28

1.6 自我测试题 28

1.7　练习题 28

1.8　编程问题 30

第2章　递归：镜子 32

2.1　递归解决方案 32

2.1.1　递归值方法：n的阶乘 34

2.1.2　递归void方法：逆置字符串 40

2.2　计数 47

2.2.1　兔子繁殖 47

2.2.2　组织游行队伍 50

2.2.3　Spock的困惑 51

2.3　数组查找 52

2.3.1 查找数组最大项 53

2.3.2　折半查找 54

2.3.3 查找数组中第k个最小项 57

2.4　组织数据 59

2.5　递归与效率 64

2.6 小结 66

2.7　提示 67

2.8 自我测试题 67

2.9　练习题 68

2.10　编程问题 73

第3章　数据抽象：墙 74

3.1　抽象数据类型 74

3.2 指定ADT 77

3.2.1　ADT列表 78

3.2.2　ADT有序表 81

3.2.3 设计ADT 82

3.2.4 公理 85

3.3 实现ADT 87

3.3.1 Java类 88

3.3.2　Java接口 94

3.3.3　Java异常 95

3.3.4　基于数组的ADT列表实现 96

3.4 小结 102

3.6 自我测试题 103

3.5 提示 103

3.7　练习题 104

3.8　编程问题 105

第4章　链表 107

4.1 预备知识 107

4.1.1　对象引用 108

4.1.2　变长数组 111

4.1.3　基于引用的链表 112

4.2.1　显示链表内容 115

4.2　链表编程 115

4.2.2　从链表中删除指定节点 117

4.2.3　在链表特殊位置插入节点 118

4.2.4　ADT列表的基于引用的实现 123

4.2.5 比较基于数组的实现和基于引用的实现 127

4.2.6　将链表传给方法 128

4.2.7　递归地处理链表 129

4.3　链表的各种变化 133

4.3.1　尾引用 133

4.3.2　循环链表 134

4.3.3　虚拟头节点 135

4.3.4　双向链表 136

4.4　清单应用程序 138

4.5 小结 142

4.6　提示 144

4.7 自我测试题 144

4.8　练习题 145

4.9　编程问题 147

5.1 回溯 150

第5章　递归问题求解技术 150

5.2　定义语言 154

5.2.1　语法知识基础 155

5.2.2　两种简单语言 156

5.2.3　代数表达式 158

5.3 递归和数学归纳法的关系 165

5.3.1　factorial递归算法的正确性 165

5.3.2　Hanoi塔的成本 166

5.4 小结 167

5.7　练习题 168

5.6 自我测试题 168

5.5 提示 168

5.8　编程问题 171

第Ⅱ部分　使用抽象数据类型解决问题 177

第6章　栈 177

6.1　抽象数据类型 177

6.2　ADT栈的简单应用 181

6.2.1　检查括号匹配 181

6.2.2　识别语言中的字符串 184

6.3 ADT栈的实现 185

6.3.1　ADT栈的基本数组的实现 186

6.3.2　ADT栈的基于引用的实现 188

6.3.3 使用ADT列表的实现 190

6.3.4　各种实现方式的比较 191

6.4　应用：代数表达式 191

6.4.1 计算后缀表达式 192

6.4.2 中缀表达式与后缀表达式的等价转换 193

6.5　应用：查找问题 195

6.5.1 使用栈的非递归解决方案 196

6.5.2　递归解决方案 202

6.6　栈和递归的关系 204

6.7 小结 205

6.8　提示 206

6.9 自我测试题 206

6.10　练习题 207

6.11 编程问题 209

第7章 队列 214

7.1 ADT队列 214

7.2.1　读取字符串 215

7.2　ADT队列的简单应用 215

7.2.2　识别同文 216

7.3 实现ADT队列 217

7.3.1 基于引用的实现 217

7.3.2　基于数组的实现 221

7.3.3 用ADT列表的实现 225

7.3.4　实现比较 226

7.4 基于位置的ADT总览 227

7.5　模拟应用 227

7.8 自我测试题 235

7.7　提示 235

7.6 小结 235

7.9　练习题 236

7.10　编程问题 238

第8章　类关系 241

8.1 继承 241

8.1.1　Java包 245

8.1.2　Java访问修饰符 246

8.1.3　is-a和has-a关系 247

8.2　动态绑定和抽象类 248

8.2.1　抽象类 251

8.2.2　Java接口 254

8.3　ADT列表和有序表 255

8.3.1 列表迭代器的实现 256

8.3.2　使用ADT列表的ADT有序表的实现 259

8.4　面向对象方法的优势 262

8.5 小结 263

8.6　提示 263

8.7 自我测试题 263

8.8　练习题 264

8.9　编程问题 265

第9章　算法效率和排序 268

9.1　确定算法效率 268

9.1.1 算法的执行时间 269

9.1.2　算法增率 270

9.1.3 数量阶分析和大O表示法 271

9.1.4　正确分析问题 273

9.1.5　查找算法的效率 275

9.2.1　选择排序 276

9.2　排序算法及其效率 276

9.2.2　起泡排序 279

9.2.3　插入排序 280

9.2.4　归并排序 282

9.2.5　快速排序 287

9.2.6　基数排序 295

9.2.7　各种排序算法的比较 297

9.3 小结 297

9.4　提示 298

9.5 自我测试题 298

9.6　练习题 299

9.7　编程问题 301

第10章 树 303

10.1 术语 303

10.2　ADT二叉树 309

10.2.1 ADT二叉树的基本操作 309

10.2.2　ADT二叉树的一般操作 310

10.2.3　二叉树的遍历 311

10.2.4　二叉树的表示 313

10.2.5　ADT二叉树的基于引用的实现 316

10.2.6　用迭代器遍历树 320

10.3 ADT二叉查找树 326

10.3.1 ADT二叉查找树的操作算法 329

10.3.2　ADT二叉查找树的基于引用的实现 341

10.3.3　二叉查找树操作的效率 344

10.3.4　树排序 347

10.3.5　将二叉查找树保存到文件 347

1 0.4　一般树 350

10.5 小结 351

10.7 自我测试题 352

10.6　提示 352

10.8　练习题 353

10.9　编程问题 358

第11章　表和优先队列 361

11.1 ADT表 361

11.1.1　选择实现 365

11.1.2　ADT表的基于数组的有序实现 370

11.1.3 ADT表的二叉查找树实现 372

11.2　ADT优先队列：ADT表的变体 374

11.2.1　堆 376

11.2.2　ADT优先队列的堆实现 382

11.2.3　堆排序 383

11.3 小结 387

11.4　提示 387

11.5 自我测试题 387

11.6　练习题 388

11.7　编程问题 390

第12章　表的高级实现 391

12.1　平衡查找树 391

12.1.1　2-3树 392

12.1.2　2-3-4树 407

12.1.3　红-黑树 412

12.1.4　AVL树 415

12.2　散列 418

12.2.1　散列函数 421

12.2.2　解决冲突 423

12.2.3　散列效率 429

12.2.4　如何确立散列函数 431

12.3　按多种形式组织数据 433

12.2.5　表遍历：散列的低效操作 433

12.4 小结 437

12.5　提示 438

12.6 自我测试题 438

12.7　练习题 438

12.8　编程问题 440

第13章 图 442

13.1 术语 442

13.2 将图作为ADT 444

13.3 图的遍历 447

13.3.1　深度优先查找 448

13.3.2　广度优先查找 450

13.4　图的应用 451

13.4.1　拓扑排序 451

13.4.2　生成树 454

13.4.3　最小生成树 456

13.4.4　最短路径 459

13.4.5　回路 462

13.4.6　一些复杂问题 464

13.5 小结 465

13.6　提示 465

13.7 自我测试题 465

13.8　练习题 466

13.9　编程问题 468

第14章　外部方法 469

14.1 了解外部存储 469

14.2　排序外部文件的数据 471

14.3 外部表 477

14.3.1 确定外部文件的索引 478

14.3.2　外部散列 481

14.3.3　B-树 484

14.3.4　遍历 491

14.3.5　多索引 492

14.4 小结 493

14.5　提示 494

14.6 自我测试题 494

14.7　练习题 494

14.8　编程练习 496

A.1　程序结构 497

附录A　Java基本原理 497

A.1.1　包 498

A.1.2　类 498

A.1.3　数据字段 499

A.1.4　方法 499

A.1.5　对象成员的访问方法 501

A.2　Java语言基础知识 501

A.2.1 注释 501

A.2.4　基本数据类型 502

A.2.3 变量 502

A.2.2　标识符和关键词 502

A.2.5 引用 503

A.2.6　字面常量 503

A.2.7　命名常量 504

A.2.8　赋值和表达式 504

A.2.9　数组 506

A.3 有用的Java类 509

A.3.1 Obiect类 509

A.3.2　字符串类 509

A.4.1 捕获异常 513

A.4　Java异常 513

A.4.2　抛出异常 517

A.5 文本输入和输出 519

A.5.1　输入 519

A.5.2　输出 519

A.6　选择语句 520

A.6.1 if语句 520

A.6.2　switch语句 521

A.7.1　while语句 522

A.7　迭代语句 522

A.7.2　for语句 523

A.7.3　do语句 525

A.8 文件输入和输出 526

A.8.1　文本文件 527

A.8.2　对象串行化 532

A.9 比较Java和C++ 533

A.10 小结 536

A.11 提示 539

附录B　统一字符代码 540

附录C　Java资源 542

C.1　Java Web站点 542

C.2　使用Java 2软件开发包 542

附录D　数学归纳法 544

D.1 公理1 544

D.2 公理2 545

D.3 自我测试题 547

D.4　练习题 547

附录E　Java操作符 548