《数据结构与算法分析》Frank.M.Carrano | PDF下载|ePub下载

第0章 引言 1
第1章 Java类 2
1.1 对象与类 2
1.2 在Java类中使用方法 5
1.3 定义Java类 7
1.3.1 方法定义 8
1.3.2 实参与形参 10
1.3.3 传递实参 11
1.3.4 Name类的定义 14
1.3.5 构造函数 16
1.3.6 toString方法 18
1.3.7 调用其他方法的方法 18
1.3.8 返回所属类实例的方法 20
1.3.9 静态域与静态方法 20
1.3.10 方法的重载 22
1.4 枚举类 23
1.5 包 26
本章小结 27
练习 28
项目设计 31
第2章 从已有类创建新类 35
2.1 合成 35
2.1.1 通用类型 38
2.1.2 适配器 41
2.2 继承 42
2.2.1 从构造函数中调用构造函数 45
2.2.2 基类的私有域与私有方法 46
2.2.3 受保护的访问 47
2.2.4 方法的覆盖与重载 47
2.2.5 多重继承 52
2.3 类型兼容性与基类 53
2.3.1 Object类 54
2.3.2 抽象类与抽象方法 56
2.4 多态性 58
本章小结 63
练习 64
项目设计 68
第3章 类的设计 70
3.1 封装 70
3.2 方法的说明 72
3.3 接口 76
3.3.1 编写接口 76
3.3.2 实现接口 78
3.3.3 作为数据类型的接口 79
3.3.4 接口的通用类型 80
3.3.5 Comparable接口 80
3.3.6 扩展接口 82
3.3.7 接口与抽象类 83
3.3.8 符号常量 85
3.4 类的选择 86
3.4.1 类的确定 87
3.4.2 CRC卡片 88
3.5 类的复用 91
本章小结 91
练习 92
项目设计 93
第4章 线性表 96
4.1 ADT线性表说明 96
4.2 使用ADT线性表 103
4.3 像使用自动售货机一样使用线性表 107
4.4 Java类库：List接口 109
本章小结 109
练习 110
项目设计 112
第5章 用数组实现线性表 114
5.1 使用定长数组实现ADT线性表 114
5.1.1 类比 114
5.1.2 Java实现 116
5.2 使用动态扩展数组实现ADT线性表 124
5.2.1 扩展数组 125
5.2.2 线性表的新实现 127
5.3 Java类库：ArrayList与Vector类 128
5.4 用数组实现ADT线性表的优缺点 132
本章小结 133
练习 134
项目设计 135
第6章 用链表实现线性表 136
6.1 链表 136
6.1.1 在表头添加来创建链表 137
6.1.2 在表末添加来创建链表 138
6.1.3 在不同位置添加来创建链表 140
6.2 使用链表实现ADT线性表 142
6.2.1 私有类Node 142
6.2.2 数据域与构造函数 144
6.2.3 选择要实现的核心方法组 145
6.2.4 在线性表的末端插入元素 146
6.2.5 在线性表的指定位置插入元素 148
6.2.6 私有方法getNodeAt 152
6.2.7 断言与isEmpty方法 153
6.2.8 display方法 154
6.3 测试不完整的实现 155
本章小结 157
练习 158
项目设计 159
第7章 完成线性表的链表实现 160
7.1 从链表中删除一个元素 160
7.2 完成ADT线性表的链表实现 162
7.2.1 方法remove 162
7.2.2 方法replace 165
7.2.3 方法getEntry 165
7.2.4 方法contains 166
7.2.5 其他方法 166
7.3 使用具有设置与获取方法的Node类 167
7.4 表尾引用 170
7.5 用链表实现ADT线性表的优缺点 175
7.6 Java类库：LinkedList类 175
本章小结 176
练习 176
项目设计 177
第8章 迭代器 179
8.1 什么是迭代器 179
8.2 Iterator接口 180
8.3 独立类迭代器 186
8.4 内部类迭代器 189
8.4.1 基于链表实现 190
8.4.2 基于数组实现 194
8.5 迭代器方法为何在自己的类中 197
8.6 ListIterator接口 198
8.7 基于数组实现ListIterator接口 204
8.8 Java类库：Iterable接口 211
8.8.1 Iterable与for-each循环 212
8.8.2 重温List接口 212
本章小结 213
练习 213
项目设计 216
第9章 算法的效率 218
9.1 动机 218
9.2 度量算法的效率 220
9.3 形式化 226
9.4 效率的图形表示 229
9.5 ADT线性表不同实现的效率 232
9.5.1 基于数组实现 232
9.5.2 基于链表实现 234
9.5.3 比较上述实现 237
本章小结 238
练习 238
项目设计 240
第10章 递归 243
10.1 何谓递归 243
10.2 跟踪递归方法 248
10.3 有返回值的递归方法 250
10.4 递归处理数组 253
10.5 递归处理链表 255
10.6 递归方法的时间效率 257
10.6.1 countDown的时间效率 257
10.6.2 计算xn的时间效率 258
10.7 困难问题的简单解法 259
10.8 简单问题的拙劣解法 264
10.9 尾递归 266
10.10 协同递归 268
本章小结 268
练习 270
项目设计 271
第11章 排序入门 275
11.1 组织用于数组排序的Java方法 276
11.2 选择排序 277
11.2.1 迭代选择排序 278
11.2.2 递归选择排序 280
11.2.3 选择排序的效率 281
11.3 插入排序 282
11.3.1 迭代插入排序 283
11.3.2 递归插入排序 284
11.3.3 插入排序的效率 286
11.3.4 链表的插入排序 286
11.4 希尔排序 289
11.4.1 Java代码 291
11.4.2 希尔排序的效率 292
11.5 算法比较 293
本章小结 293
练习 293
项目设计 296
第12章 快速排序算法 298
12.1 归并排序 298
12.1.1 数组的归并 298
12.1.2 递归归并排序 299
12.1.3 归并排序的效率 302
12.1.4 迭代归并排序 303
12.1.5 Java类库中的归并排序 304
12.2 快速排序 304
12.2.1 快速排序的效率 305
12.2.2 创建划分 305
12.2.3 快速排序的Java代码 308
12.2.4 Java类库中的快速排序 311
12.3 基数排序 311
12.3.1 基数排序的伪代码 313
12.3.2 基数排序的效率 313
12.4 算法比较 314
本章小结 314
练习 315
项目设计 316
第13章 有序表 319
13.1 ADT有序表的说明 319
13.2 链表实现 323
13.2.1 add方法 324
13.2.2 链表实现的效率 331
13.3 使用ADT线性表的实现 331
本章小结 336
练习 336
项目设计 337
第14章 继承与线性表 339
14.1 使用继承实现有序表 339
14.2 设计一个基类 342
14.3 有序表的一种高效实现 348
本章小结 349
练习 350
项目设计 350
第15章 可变对象、不可变对象与可克隆对象 352
15.1 可变对象与不可变对象 352
15.1.1 创建只读类 355
15.1.2 同伴类 356
15.2 可克隆对象 358
15.2.1 克隆数组 364
15.2.2 克隆链表 366
15.2.3 克隆体的有序表 370
本章小结 373
练习 373
项目设计 376
第16章 查找 377
16.1 问题描述 377
16.2 查找无序数组 378
16.2.1 迭代顺序查找无序数组 378
16.2.2 递归顺序查找无序数组 379
16.2.3 顺序查找数组的效率 381
16.3 查找有序数组 381
16.3.1 顺序查找有序数组 381
16.3.2 折半查找有序数组 382
16.3.3 Java类库：binarySearch方法 386
16.3.4 折半查找数组的效率 387
16.4 查找无序链表 388
16.4.1 迭代顺序查找无序链表 388
16.4.2 递归顺序查找无序链表 389
16.4.3 顺序查找链表的效率 390
16.5 查找有序链表 390
16.5.1 顺序查找有序链表 390
16.5.2 折半查找有序链表 391
16.6 查找方法的选择 391
本章小结 392
练习 392
项目设计 394
第17章 词典 396
17.1 ADT词典的说明 396
17.1.1 Java接口 399
17.1.2 迭代器 400
17.2 使用ADT词典 402
17.2.1 电话号码簿 402
17.2.2 词频 407
17.2.3 词的索引 411
17.3 Java类库：Map接口 414
本章小结 415
练习 415
项目设计 416
第18章 词典的实现 418
18.1 基于数组的实现 418
18.1.1 基于数组的无序词典 419
18.1.2 基于数组的有序词典 424
18.2 基于向量的实现 428
18.3 基于链表的实现 433
18.3.1 基于链表的无序词典 434
18.3.2 基于链表的有序词典 434
本章小结 438
练习 438
项目设计 439
第19章 散列概述 440
19.1 什么是散列 440
19.2 散列函数 442
19.2.1 计算散列码 443
19.2.2 将散列码压缩为散列表的索引 445
19.3 处理冲突 446
19.3.1 线性探测开放定址 446
19.3.2 二次探测开放定址 451
19.3.3 双散列开放定址 451
19.3.4 开放定址的潜在问题 453
19.3.5 链地址 453
本章小结 456
练习 457
项目设计 458
第20章 用散列实现词典 459
20.1 效率 459
20.1.1 装填因子 460
20.1.2 开放定址的开销 460
20.1.3 链地址的开销 462
20.2 再散列 463
20.3 处理冲突的各方案比较 464
20.4 使用散列的词典实现 465
20.4.1 散列表中的元素 465
20.4.2 数据域与构造函数 466
20.4.3 方法getValue、remove和add 467
20.4.4 迭代器 473
20.5 Java类库：类HashMap 475
本章小结 475
练习 476
项目设计 476
第21章 栈 478
21.1 ADT栈的说明 478
21.2 利用栈处理代数表达式 481
21.2.1 检查中缀代数表达式的括号是否平衡 482
21.2.2 将中缀表达式转化为后缀表达式 487
21.2.3 后缀表达式求值 493
21.2.4 中缀表达式求值 495
21.3 程序栈 497
21.4 使用栈代替递归 498
21.5 Java类库：类Stack 501
本章小结 502
练习 502
项目设计 504
第22章 栈的实现 506
22.1 基于链表的实现 506
22.2 基于数组的实现 509
22.3 基于向量的实现 513
本章小结 515
练习 515
项目设计 516
第23章 队列、双端队列与优先队列 517
23.1 ADT队列的描述 517
23.2 使用队列模拟排队 521
23.3 使用队列计算股份销售的资本收益 527
23.4 Java类库：Queue接口 530
23.5 ADT双端队列的描述 530
23.6 使用双端队列计算股份销售的资本收益 532
23.7 ADT优先队列的描述 534
23.8 使用优先队列跟踪委派任务 535
本章小结 537
练习 537
项目设计 539
第24章 队列、双端队列与优先队列的实现 541
24.1 基于链表的队列实现 541
24.2 基于数组的队列实现 545
24.2.1 循环数组 546
24.2.2 含有一个未用位置的循环数组 547
24.3 基于向量的队列实现 552
24.4 基于循环链表的队列实现 554
24.5 Java类库：AbstractQueue类 560
24.6 基于双向链表的双端队列实现 560
24.7 实现优先队列的可用方法 564
24.8 Java类库：PriorityQueue类 564
本章小结 565
练习 566
项目设计 567
第25章 树 569
25.1 树的概念 569
25.1.1 层次化的组织 569
25.1.2 树的术语 571
25.2 树的遍历 574
25.2.1 二叉树的遍历 575
25.2.2 树的遍历 576
25.3 树的Java接口 577
25.3.1 所有树的接口 577
25.3.2 二叉树的接口 578
25.4 二叉树举例 579
25.4.1 表达式树 580
25.4.2 决策树 581
25.4.3 二叉查找树 585
25.4.4 堆 587
25.5 树举例 589
25.5.1 语法分析树 589
25.5.2 博弈树 590
本章小结 590
练习 591
项目设计 593
第26章 树的实现 595
26.1 二叉树的结点 595
26.1.1 结点的接口 596
26.1.2 BinaryNode的实现 597
26.2 ADT二叉树的实现 599
26.2.1 创建基本二叉树 599
26.2.2 方法privateSetTree 600
26.2.3 访问者与修改者方法 603
26.2.4 计算高度与统计结点 604
26.2.5 遍历 605
26.3 表达式二叉树的实现 610
26.4 树 612
26.4.1 树的结点 612
26.4.2 用二叉树表示树 613
本章小结 614
练习 614
项目设计 616
第27章 二叉查找树的实现 617
27.1 预备知识 617
27.1.1 二叉查找树接口 618
27.1.2 重复元素 620
27.1.3 开始类定义 621
27.2 查找与检索 622
27.3 遍历 624
27.4 插入元素 624
27.4.1 递归实现 625
27.4.2 迭代实现 628
27.5 删除元素 631
27.5.1 删除叶子结点中的元素 631
27.5.2 删除有一个孩子的结点中的元素 631
27.5.3 删除有两个孩子的结点中的元素 631
27.5.4 删除根结点中的元素 635
27.5.5 递归实现 635
27.5.6 迭代实现 639
27.6 操作的效率 643
27.6.1 平衡的重要性 644
27.6.2 插入结点的顺序 644
27.7 ADT词典的实现 645
本章小结 648
练习 649
项目设计 651
第28章 堆的实现 653
28.1 再论ADT堆 653
28.2 用数组表示堆 654
28.3 插入元素 656
28.4 删除根 659
28.5 创建堆 662
28.6 堆排序 664
本章小结 667
练习 668
项目设计 669
第29章 平衡查找树 670
29.1 AVL树 670
29.1.1 单旋转 671
29.1.2 双旋转 673
29.1.3 实现细节 676
29.2 2-3树 681
29.2.1 2-3树的查找 681
29.2.2 往2-3树插入元素 682
29.2.3 插入期间分裂结点 683
29.3 2-4树 685
29.3.1 往2-4树插入元素 685
29.3.2 比较AVL树、2-3树和2-4树 686
29.4 红黑树 687
29.4.1 红黑树的特性 688
29.4.2 往红黑树插入元素 689
29.4.3 Java类库：类TreeMap 693
29.5 B树 693
本章小结 694
练习 695
项目设计 696
第30章 图 697
30.1 一些例子与术语 697
30.1.1 公路地图 697
30.1.2 航线 700
30.1.3 迷宫 700
30.1.4 先修课程 701
30.1.5 树 701
30.2 遍历 701
30.2.1 广度优先遍历 702
30.2.2 深度优先遍历 704
30.3 拓扑顺序 705
30.4 路径 707
30.4.1 寻找路径 708
30.4.2 无权图的最短路径 708
30.4.3 加权图的最短路径 710
30.5 ADT图的Java接口 714
本章小结 717
练习 718
项目设计 720
第31章 图的实现 722
31.1 两种实现的概述 722
31.1.1 邻接矩阵 722
31.1.2 邻接表 723
31.2 顶点与边 724
31.2.1 说明类Vertex 724
31.2.2 内部类Edge 726
31.2.3 实现Vertex类 727
31.3 ADT图的实现 731
31.3.1 基本操作 731
31.3.2 图的算法 735
本章小结 737
练习 738
项目设计 739
附录A Java基础 741
A.1 引言 741
A.1.1 应用程序和小程序 741
A.1.2 对象和类 741
A.1.3 第一个Java应用程序 741
A.2 Java基础 744
A.2.1 标识符 744
A.2.2 保留字 744
A.2.3 变量 745
A.2.4 基本类型 745
A.2.5 常量 746
A.2.6 赋值语句 746
A.2.7 赋值兼容性 747
A.2.8 类型转换 748
A.2.9 算术运算符和表达式 749
A.2.10 括号和优先规则 750
A.2.11 自增和自减运算符 751
A.2.12 特殊赋值运算符 752
A.2.13 符号常量 752
A.2.14 Math类 753
A.3 用键盘和屏幕进行简单的输入和输出 754
A.3.1 屏幕输出 754
A.3.2 用Scanner类进行键盘输入 755
A.4 if-else语句 757
A.4.1 布尔表达式 758
A.4.2 嵌套语句 761
A.4.3 多重if-else语句 763
A.4.4 条件运算符（可选） 764
A.5 switch语句 764
A.6 枚举 766
A.7 作用域 768
A.8 循环 769
A.8.1 while语句 769
A.8.2 for语句 770
A.8.3 do-while语句 772
A.8.4 关于循环的其他信息 773
A.9 String类 774
A.9.1 字符串中的字符 775
A.9.2 字符串的联接 776
A.9.3 String方法 777
A.10 StringBuilder类 779
A.11 使用Scanner抽取字符串的一部分 780
A.12 数组 783
A.12.1 数组形参和返回值 785
A.12.2 初始化数组 786
A.12.3 数组索引出界 786
A.12.4 对数组使用＝与＝＝ 786
A.12.5 数组与for-each循环 788
A.12.6 多维数组 788
A.12 封装类 790
附录B 异常处理 796
B.1 基本的异常处理 796
B.2 Java类库的异常类 799
B.3 定义自己的异常类 800
B.4 复合catch代码块 802
B.5 finally代码块 803
B.6 抛出但不捕获异常的方法 804
B.7 不需要捕获的异常 805
附录C 文件输入与输出 807
C.1 概述 807
C.1.1 数据流 807
C.1.2 文件的优点 807
C.1.3 文件的类型 808
C.1.4 文件名 809
C.1.5 包java.io 809
C.2 使用PrintWriter写文本文件 809
C.3 读取文本文件 812
C.3.1 使用Scanner读取文本文件 812
C.3.2 使用BufferedReader读取文本文件 814
C.3.3 定义打开数据流的方法 816
C.4 二进制文件的I/O 817
C.4.1 使用DataOutputStream写二进制文件 817
C.4.2 使用DataInputStream读取二进制文件 821
C.5 File类 823
C.6 对象串行化 824
附录D 文档与程序设计风格 828
D.1 命名变量与类 828
D.2 缩排 828
D.3 注释 829
D.3.1 单行注释 829
D.3.2 注释块 830
D.3.3 何时写注释 830
D.3.4 Java文档注释 830
D.3.5 运行javadoc 832
附录E 自测题答案 833
· · · · · ·