数据结构PDF电子书下载

第1章 软件工程基本原理和Java类 1

1.1 软件的生命周期 1

目录 1

2.1 继承 6 1

1.2 软件开发阶段 2

1.2.1 分析阶段 2

1.2.2 设计阶段 2

4.4.7 copyList方法 2 1 3

1.2.3 实现阶段 3

4.5.2 删除节点 2 1 5

1.2.4 测试和调试 5

1.3 算法分析：大O表示法 6

1.4 用户定义的类 12

1.4.1 构造函数 14

1.4.2 统一建模语言图 15

1.4.3 变量声明和对象实例化 16

1.4.4 访问类的成员 17

1.4.5 类的内置运算 18

1.4.6 赋值运算符和类 18

1.4.7 类的作用域 20

1.4.8 定义类Clock的构造函数和方法 20

1.4.9 拷贝构造函数 27

1.4.10 类和方法toString 28

1.4.11 类的静态成员 29

1.4.12 类的静态变量（数据成员） 30

1.4.13 析构函数 31

1.4.14 创建自己的包 31

1.4.15 多文件程序 32

1.4.16 引用this 35

1.5 抽象数据类型 37

1.4.17 内部类 37

1.6 编程示例：糖果机 38

1.6.1 问题分析和算法设计 38

1.6.2 收银机 38

1.6.3 自动售货机 41

1.6.4 主程序 45

1.7 标识类、对象和操作 50

1.8 快速总结 50

1.9 练习题 52

3.2.2 方法copyList 1 58

1.10 编程练习 58

第2章 继承和异常处理 61

2.1.1 在子类中使用超类的方法 63

2.1.2 子类与超类的构造函数 68

2.1.3 类的受保护成员 75

2.1.4 类Object 79

2.1.5 超类和子类的对象 80

2.1.6 运算符instanceof 82

2.2 抽象方法和抽象类 86

2.3 聚合 87

2.4 异常处理 92

2.4.1 Java异常层次结构 93

2.4.2 异常层次结构 95

2.4.3 已解析的异常和未解析的异常 97

2.4.4 处理程序中的异常 98

2.4.5 抛出和重新抛出异常 103

2.4.6 异常处理技术 107

2.4.7 创建自己的异常类 108

2.5 编程示例：成绩报告单 110

2.5.1 问题分析与算法设计 112

2.5.2 主程序 125

2.5.3 程序清单 128

2.6 快速总结 130

2.7 练习题 132

2.8 编程练习 140

第3章 基于数组的表 143

3.1 表元素的类型 144

3.1.1 类IntElement 145

3.1.2 类StringElement 147

3.2 类ArrayListClass 149

3.2.1 拷贝构造函数 157

3.3 无序表 158

3.3.1 搜索 160

3.3.2 插入 161

3.3.3 删除 162

3.3.4 各种表操作的时间复杂度 163

3.4 类Vector 169

3.5 编程示例：多项式的运算 174

3.6 快速回顾 185

3.7 练习题 186

3.8 编程练习 187

第4章 链表 190

4.1 链表 190

4.1.1 链表的一些属性 192

4.1.2 遍历链表 194

4.2 链表元素的插入和删除 195

4.2.1 插入 195

4.2.2 删除 198

4.3 构建链表 199

4.3.1 正向构建链表 200

4.3.2 反向构建链表 203

4.4 ADT链表 204

4.4.1 链表的长度 209

4.4.3 在链表头插入节点 209

4.4.2 检索第一个节点和最后一个节点的数据 209

4.4.4 在链表尾插入节点 210

4.4.5 复制链表 211

4.4.6 拷贝构造函数 212

4.4.8 类LinkedListClass的定义 213

4.5 无序链表 213

4.5.1 搜索链表 214

4.6 有序链表 220

4.6.1 搜索链表 222

4.6.2 插入节点 222

4.6.3 删除节点 227

4.7 双向链表 231

4.7.4 链表的长度 234

4.7.3 初始化链表 234

4.7.2 isEmptyList 234

4.7.1 默认构造函数 234

4.7.5 输出链表 235

4.7.6 反向输出链表 235

4.7.7 搜索链表 235

4.7.8 第一个和最后一个元素 236

4.7.9 插入节点 236

4.7.10 删除节点 239

4.8 带有头节点和尾节点的链表 241

4.9 循环链表 242

4.10 编程示例：音像店 243

4.11 快速回顾 264

4.12 练习题 264

4.13 编程练习 269

第5章 递归 272

5.1 递归的定义 272

5.1.2 无穷递归 274

5.1.1 直接递归和间接递归 274

5.2 使用递归法解决问题 275

5.3 编程示例：将十进制数转换为二进制数 287

5.4 编程示例：Sierpinski gasket 289

5.4.1 问题分析和算法设计 290

5.4.2 完整的程序清单 291

5.5 使用递归还是迭代 294

5.6 递归和回溯：8-皇后问题 294

5.6.2 n-皇后问题 295

5.6.1 回溯 295

5.6.3 回溯和4-皇后问题 297

5.6.4 8-皇后问题 297

5.7 快速回顾 301

5.8 练习题 302

5.9 编程练习 304

第6章 堆栈 310

6.1 堆栈 310

6.2 StackException类 312

6.3 使用数组实现堆栈 313

6.3.1 初始化堆栈 316

6.3.2 空堆栈 317

6.3.3 满堆栈 317

6.3.4 入栈 317

6.3.5 返回栈顶元素 318

6.3.6 出栈 319

6.3.7 复制 320

6.3.8 构造函数 320

6.3.10 CopyStack方法 321

6.3.9 拷贝构造函数 321

6.4 编程示例：求最高GPA 323

6.5 把堆栈实现为链表 327

6.5.1 默认构造函数 330

6.5.2 初始化堆栈 330

6.5.3 入栈 331

6.5.4 返回栈顶元素 333

6.5.5 出栈 333

6.6 由类LinkedListClass派生而来的堆栈 335

6.7 堆栈的应用：后缀表达式计算器 336

6.7.2 方法evaluateExpression 340

6.7.1 主算法 340

6.7.3 方法evaluateOpr 342

6.7.4 方法printResult 345

6.7.5 完整的程序清单 345

6.8 后缀表达式计算器：图形用户界面（GUI） 347

6.9 消除递归：反向打印链表的非递归算法 354

6.10 类Stack 359

6.12 练习题 361

6.11 快速回顾 361

6.13 编程练习 365

第7章 队列 368

7.1 队列 368

7.2 队列的异常类 369

7.3 队列的数组实现 370

7.4 队列的链表实现 380

7.5 从类LinkedListClass派生而来的队列 384

7.6 优先队列 386

7.7 队列的应用：模拟 387

7.7.1 设计队列系统 387

7.7.2 客户 388

7.7.3 服务器 391

7.7.4 服务器表 395

7.7.5 等待客户的队列 399

7.7.6 主程序 401

7.9 练习题 408

7.8 快速回顾 408

7.10 编程练习 412

第8章 搜索算法 413

8.1 搜索算法 413

8.1.1 顺序搜索 414

8.1.2 顺序搜索算法分析 415

8.1.3 有序表 416

8.1.4 二叉树搜索 418

8.1.5 二叉树搜索算法的性能 421

8.1.6 将数据项插入有序表 422

8.2 基于比较的搜索算法的下限 425

8.3 散列算法 425

8.3.1 散列函数：示例 426

8.3.2 冲突的解决 427

8.3.3 冲突的解决：开型寻址法 427

8.3.4 二次探测 429

8.3.5 删除：开型寻址法 431

8.3.6 散列算法：使用二次探测来实现 433

8.3.7 冲突的解决：链地址法（开散列方法） 435

8.3.8 散列法性能分析 436

8.4 快速回顾 437

8.5 练习题 439

8.6 编程练习 441

第9章 排序算法 443

9.1 排序算法 443

9.2 选择排序：基于数组的表 444

9.3 插入排序：基于数组的表 449

9.4 插入排序：基于链表的表 454

9.5 基于比较的排序算法的下限 458

9.6 快速排序：基于数组的表 459

9.7 归并排序：基于链表的表 464

9.7.1 划分 466

9.7.2 归并 468

9.7.3 分析：归并排序 471

9.8 堆排序：基于数组的表 471

9.8.1 构建堆 472

9.8.2 分析：堆排序 478

9.9 再论优先级队列 479

9.9.1 在优先级队列中插入一个元素 479

9.9.2 从优先级队列删除一个元素 479

9.10 编程示例：选举结果 479

9.10.1 问题分析和算法设计 481

9.10.2 主程序 485

9.10.4 处理投票数据 488

9.10.3 对姓名排序 488

9.10.5 计算选票数的总和 490

9.10.6 打印标题和结果 491

9.11 快速回顾 495

9.12 练习题 495

9.13 编程练习 497

第10章 二叉树 499

10.1 二叉树 499

10.2.2 前序遍历 505

10.2.3 后序遍历 505

10.2 二叉树的遍历 505

10.2.1 中序遍历 505

10.2.4 二叉树的实现 508

10.3 二叉搜索树 514

10.3.1 search方法 517

10.3.2 Insert方法 518

10.3.3 Delete方法 520

10.4 二叉搜索树分析 526

10.5.1 非递归的中序遍历算法 527

10.5 二叉树的非递归遍历算法 527

10.5.2 非递归的前序遍历算法 528

10.5.3 非递归的后序遍历算法 529

10.6 AVL（平衡）树 530

10.6.1 AVL树的插入操作 532

10.6.2 AVL树的旋转 537

10.6.3 AVL树的删除操作 547

10.6.4 AVL树的性能分析 548

10.7 编程示例：音像店 549

10.8 快速回顾 556

10.9 练习题 557

10.10 编程练习 561

第11章 图 562

11.1 图的简史 562

11.2 图的定义和符号 563

11.3 图的表示方法 565

11.3.1 邻接矩阵 565

11.3.2 邻接表 566

11.4 图的操作 567

11.5 图的ADT定义 568

11.6 图的遍历 571

11.6.1 深度优先遍历 571

11.6.2 广度优先遍历 573

11.7 最短路径算法 575

11.8 最小生成树 580

11.9 拓扑排序 589

11.10 快速回顾 594

11.11 练习题 595

11.12 编程练习 597

附录A 保留字 599

附录B 运算符优先级 600

附录C 字符集 602

附录D 包和用户定义的类 604

附录E Java类 619

附录F 针对C＋＋程序员的JAVA介绍 645

附录G 参考文献 666

附录H 部分习题答案 667