Java软件结构：设计和使用数据结构

第1章 软件开发 1
1.1 软件工程 1
专业水准与道德规范 2
1.2 软件质量 3
正确性 3
可靠性 3
健壮性 4
可用性 4
可维护性 4
可重用性 5
可移植性 5
效率 6
质量问题 6
1.3 开发生命周期模型 6
瀑布模型（Waterfall Model） 8
螺旋模型（Spiral Model） 9
演化开发模型 10
1.4 统一建模语言（Unified Modeling
Language，UML） 10
UML关系 11
1.5 错误处理 14
1.6 算法分析 15
增长函数（Growth Function）及
Big O( )记法 15
增长函数的比较 16
循环执行分析 17
嵌套循环 18
1.7 软件工程与数据结构 19
第2章 面向对象设计 23
2.1 面向对象内容综述 23
2.2 对象的使用 24
抽象 24
对象的创建 25
2.3 类的库与包 26
import（导入）声明 27
2.4 状态与行为 28
2.5 类 29
实例数据 31
2.6 封装 31
可见性修饰符 32
局部数据 33
2.7 构造函数 34
2.8 方法重载 34
2.9 再论引用 35
空（null）引用 36
this引用 36
别名 38
垃圾回收 39
将对象作为参数传递 40
2.10 static（静态）修饰符 40
静态变量 40
静态方法 41
2.11 包装类 41
2.12 接口 42
Comparable接口 44
Iterator接口 44
2.13 继承 44
派生类 45
protected（保护）修饰符 47
super（超级）引用 47
方法的重写 48
2.14 类的层次结构 48
Object类 49
抽象类 50
接口的层次结构 51
2.15 多态 52
引用和类的层次结构 53
基于继承的多态 53
基于接口的多态 55
2.16 泛型 56
2.17 异常 57
异常消息 58
try语句 58
异常传播 59
异常类的层次结构 60
第3章 集合 66
3.1 集合介绍 66
抽象数据类型 67
Java集合API 69
3.2 set集合 69
接口 70
迭代器 72
异常 72
3.3 使用set：bingo 73
3.4 实现set：利用数组 76
容量的管理 77
3.5 ArraySet类 77
size运算和isEmpty运算 79
add运算 80
addAll运算 82
removeRandom运算 82
remove运算 83
union运算 84
contains运算 85
equals运算 85
iterator运算 86
toString运算 88
UML描述 88
3.6 ArraySet的分析 88
add的分析 89
remove的分析 90
removeRandom的分析 90
addAll的分析 90
find、contains的分析 90
union的分析 90
equals的分析 91
第4章 链式结构 94
4.1 用做链接的引用 94
4.2 管理链表 96
插入节点 96
删除节点 97
哑节点 98
4.3 没有链接的元素 98
双向链表 99
4.4 实现set：利用链接 99
LinkedSet类 100
add运算 102
removeRandom运算 103
remove运算 104
iterator运算 105
4.5 LinkedSet的分析 107
add的分析 107
remove的分析 108
removeRandom的分析 108
第5章 Black Jack 111
5.1 Black Jack游戏 111
5.2 初始设计 111
5.3 实现Black Jack游戏 115
Card类 115
Deck类 117
Hand类 122
BlackJack类 125
BlackJackGUI类 128
BlackJackDemo类 135
第6章 堆栈 137
6.1 堆栈ADT 137
6.2 堆栈的使用：计算后缀表达式
的值 140
6.3 堆栈的使用：穿越迷宫 146
6.4 堆栈的实现：链接实现 151
push操作 151
pop操作 152
其他操作 153
6.5 堆栈的实现：数组实现 153
push操作 154
pop操作 154
其他操作 155
6.6 堆栈的实现：java.util.Stack类 156
惟一操作 156
继承和实现 156
6.7 堆栈实现的分析 157
push操作的分析 157
pop操作的分析 158
第7章 队列 162
7.1 队列ADT 162
7.2 使用队列：代码密钥 164
7.3 使用队列：售票口模拟 167
7.4 使用队列：基数排序 171
7.5 实现队列：利用链接 175
enqueue运算 175
dequeue运算 176
其他运算 178
7.6 实现队列：利用数组 178
enqueue运算 178
dequeue运算 179
其他运算 180
7.7 实现队列：利用环形数组 181
7.8 分析各种队列实现 184
enqueue 184
递增count 184
dequeue 185
第8章 列表 190
8.1 列表ADT（Abstract Data Type，
抽象数据类型） 190
8.2 运用有序列表：锦标赛主办者 196
8.3 运用索引表：Josephus问题 201
8.4 实现列表：利用数组 203
remove操作 204
Contains操作 206
有序列表的添加（add）操作 206
无序列表的特有操作 207
索引列表的特有操作 207
8.5 实现列表：利用链接 208
remove操作 208
双向链表 209
8.6 列表的实现分析 212
有序列表的实现分析 214
无序列表的实现分析 214
索引列表的实现分析 216
第9章 计算器 220
9.1 计算器 220
9.2 初始设计 220
9.3 实现计算器 224
infixToPostfix类 224
listPostfixEvaluator类 228
CalculatorGUI类 230
CalculatorDemo类 235
第10章 递归 238
10.1 递归地思考 238
无穷递归 239
数学中的递归 240
10.2 递归地编程 240
递归与迭代 242
直接递归与间接递归 243
10.3 使用递归 243
游历迷宫 243
河内塔 247
10.4 分析递归算法 251
第11章 排序和查找 256
11.1 查找 256
线性查找法 257
二分查找法 258
查找算法的比较 260
11.2 排序 261
选择排序法 263
插入排序法 265
冒泡排序法 266
快速排序法 268
归并排序法 270
第12章 树 275
12.1 树 275
树的分类 276
12.2 树的实现策略 278
树的数组实现之计算策略 278
树的数组实现之模拟链接策略 279
树的分析 279
12.3 树的遍历 280
前序遍历 280
中序遍历 281
后序遍历 282
层序遍历 282
12.4 二叉树的实现 283
removeLeftSubtree方法 288
find方法 289
iteratorInOrder方法 290
12.5 二叉树的使用：表达式树 291
第13章 二叉查找树 302
13.1 二叉查找树 302
13.2 实现二叉查找树：利用链接 304
addElement运算 304
removeElement运算 306
removeAllOccurrences运算 309
removeMin运算 310
13.3 使用二叉查找树：实现有序
列表 310
BinarySearchTreeList实现的
分析 313
13.4 平衡二叉查找树 314
右旋 314
左旋 315
右左旋 315
左右旋 316
13.5 实现二叉查找树：AVL树 317
AVL树中的右旋 317
AVL树中的左旋 317
AVL树中的右左旋 318
AVL树中的左右旋 318
13.6 实现二叉查找树：红黑树 319
红黑树中的插入 320
红黑树中的元素删除 322
13.7 实现二叉查找树：Java集合
API 324
第14章 祖先树 331
14.1 祖先树 331
14.2 初始设计 331
14.3 祖先树的实现 335
Person类 335
AncestorTreeNode类 335
AncestorTree类 336
AncestorGUI类 345
AncestorDemo类 358
第15章 堆 361
15.1 堆 361
addElement操作 362
removeMin操作 363
findMin操作 364
15.2 堆的使用：堆排序 365
15.3 堆的使用：优先级队列 365
15.4 堆的实现：利用链接 368
addElement操作 368
removeMin操作 371
findMin操作 373
15.5 堆的实现：利用数组 373
addElement操作 373
removeMin操作 374
findMin 操作 376
15.6 堆实现的分析 376
addElement操作 376
removeMin操作 376
findMin 操作 377
堆排序 377
第16章 多路查找树 381
16.1 整合树的概念 381
16.2 2-3树 381
向2-3树中插入元素 382
从2-3树中删除元素 384
16.3 2-4树 387
16.4 B树 388
16.5 创建和使用B树的动因 388
B*树 389
B+树 389
B树的分析 390
16.6 B树的实现策略 390
第17章 散列（Hashing） 394
17.1 散列 394
17.2 散列函数 396
除法方法 396
折叠法 397
平方取中间值法 397
基数转换法 397
数字分析法 398
长度依赖法 398
Java语言中的散列函数 398
17.3 解决冲突 398
链锁法 399
开地址 400
17.4 从散列表删除元素 402
从链锁式实现中删除 402
从开地址实现中删除 403
17.5 Java集合API中的散列表 403
Hashtable类 404
HashSet类 405
HashMap类 406
IdentityHashMap类 406
WeakHashMap类 407
LinkedHashSet与
LinkedHashMap 408
第18章 图 413
18.1 无向图 413
18.2 有向图 415
18.3 网络 416
18.4 常见的图算法 417
遍历 417
测试连通性 421
最小生成树 422
判定最短路径 424
18.5 图的实现策略 425
邻接表 425
邻接矩阵 426
第19章 Web爬虫工具 430
19.1 Web爬虫工具 430
19.2 初始设计 430
19.3 实现Web爬虫工具 432
WebCrawler类 433
WebcrawlerGUI类 439
WebCrawlerDemo类 441