世界著名计算机教材精选：Java软件结构与数据结构（第3版）

图书标准信息

• 作者 [美]路易斯（Lewis J.） 著；金名 译
• 出版社 清华大学出版社
• 出版时间 2009-08
• 版次 1
• ISBN 9787302205951
• 定价 49.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 393页
• 字数 638千字
• 正文语种 简体中文

【内容简介】

　　《Java软件结构与数据结构（第3版）》是著名作者JohnLewis与JosephChase作为其一流的CSI教材“JavaSoftwareSolutions：FoundationsofProgramDesign”的姊妹篇。尽管《Java软件结构与数据结构（第3版）》的英文名为“JavaSoftwareStructures：DesigningandUsingDataStructures”，但正如作者在前言中所说的那样，《Java软件结构与数据结构（第3版）》其实是一本可作为“数据结构与算法”课程的教材。根据使用了前两版的教师和学生的反馈，作者在第3版中进行了重大修改，以适应教学的需要。最重要的修改包括这样几个方面：
　　（1）对《Java软件结构与数据结构（第3版）》的基本结构进行了重新设计，以使得这些内容之间的脉络更加清晰；
　　（2）第3版把对面向对象概念的复习作为一个附录以供参考；
　　（3）上一版给出了几个完整的Java程序设计案例和源代码，在第3版中进行了删除，并把这几个程序案例源代码放在了网上供读者下载。译者认为，这不仅压缩了不少篇幅，而且使得《Java软件结构与数据结构（第3版）》更像是一本数据结构与算法的教材，而不是Java程序设计的教材；
　　（4）第3版扩展了对图的讨论，把“图”与“散列”两章的顺序进行了调换，使得脉络更清晰。本版还添加了一章来专门讨论Set与Map集合。
　　总之，这些修改都是建立在使用以前版本教学的基础上，为教师提供更多的机会和更好的灵活性来使用《Java软件结构与数据结构（第3版）》。

【目录】

第1章概述1
1.1软件质量1
1.1.1正确性2
1.1.2可靠性2
1.1.3健壮性3
1.1.4可用性3
1.1.5可维护性3
1.1.6可重用性4
1.1.7可移植性4
1.1.8运行效率4
1.1.9质量问题5
1.2数据结构5
1.2.1一个物理示例5
1.2.2以集装箱作为对象7
关键概念小结7
自测题8
练习题8
自测题答案8

第2章算法分析9
2.1算法效率分析9
2.2增长函数与大O记法10
2.3增长函数的比较12
2.4时间复杂度分析13
2.4.1循环运行的复杂度分析13
2.4.2嵌套循环的复杂度分析14
2.4.3方法调用的复杂度分析15
关键概念小结16
自测题16
练习题17
自测题答案17
参考文献18

第3章集合19
3.1概述19
3.1.1抽象数据类型20
3.1.2Java集合API21
3.2栈集合22
3.3主要的面向对象概念23
3.3.1继承24
3.3.2类层次25
3.3.3Object类26
3.3.4多态性27
3.3.5引用与类层次28
3.3.6泛型29
3.4栈ADT30
接口30
3.5使用栈计算后缀表达式32
3.6异常38
3.6.1异常消息39
3.6.2try语句39
3.6.3异常传播40
3.7用数组实现栈41
管理容量41
3.8ArrayStack类42
3.8.1构造函数43
3.8.2push操作44
3.8.3pop操作45
3.8.4peek操作46
3.8.5其他操作46
关键概念小结46
自测题47
练习题48
程序设计项目48
自测题答案49

第4章链式结构51
4.1链接作为引用51
4.2管理链表53
4.2.1访问元素53
4.2.2插入结点54
4.2.3删除结点55
4.2.4哑结点55
4.3无链接的元素56
双向链表56

4.4用链表实现栈57
4.4.1LinkedStack类57
4.4.2push操作60
4.4.3pop操作61
4.4.4其他操作62
4.5使用栈来穿越迷宫62
4.6java.util.Stack类实现栈67
4.6.1独有的操作68
4.6.2继承与实现68
关键概念小结69
自测题69
练习题69
程序设计项目70
自测题答案70

第5章队列72
5.1概述72
5.2使用队列：代码密钥75
5.3使用队列：售票口模拟77
5.4用链表实现队列81
5.4.1enqueue操作83
5.4.2dequeue操作84
5.4.3其他操作85
5.5用数组实现队列85
5.5.1enqueue操作88
5.5.2dequeue操作90
5.5.3其他操作90
关键概念小结90
自测题91
练习题91
程序设计项目92
自测题答案92

第6章列表94
6.1概述94
6.1.1迭代器96
6.1.2往列表添加元素97
6.1.3接口与多态性98
6.2有序列表使用示例：联赛主办者104
6.3索引列表使用示例：Josephus问题109

6.4使用数组实现列表111
6.4.1remove操作112
6.4.2contains操作114
6.4.3iterator操作115
6.4.4有序列表的add操作117
6.4.5无序列表的特有操作118
6.4.6无序列表的addAfter操作118
6.5使用链表实现列表119
6.5.1remove操作119
6.5.2双向链表121
6.5.3iterator操作124
6.6Java集合API中的列表126
6.6.1Cloneable接口126
6.6.2Serializable接口127
6.6.3RandomAccess接口127
6.6.4java.util.Vector接口127
6.6.5java.util.ArrayList接口129
6.6.6java.util.LinkedList接口130
关键概念小结132
自测题133
练习题133
程序设计项目134
自测题答案134

第7章递归136
7.1递归地思考136
7.1.1无穷递归137
7.1.2数学中的递归138
7.2递归地编程138
7.2.1递归与迭代140
7.2.2直接递归与间接递归140
7.3使用递归141
7.3.1穿越迷宫141
7.3.2汉诺塔145
7.4递归算法分析149
关键概念小结150
自测题151
练习题151
程序设计项目152
自测题答案153

第8章排序与查找154
8.1查找154
8.1.1静态方法155
8.1.2泛型方法155
8.1.3线性查找法156
8.1.4二分查找法157
8.1.5查找算法的比较159
8.2排序160
8.2.1选择排序法162
8.2.2插入排序法164
8.2.3冒泡排序法165
8.2.4快速排序法167
8.2.5归并排序法170
8.3基数排序法171
关键概念小结175
自测题176
练习题176
程序设计项目177
自测题答案177

第9章树178
9.1概述178
树的分类179
9.2实现树的策略180
9.2.1树的数组实现之计算策略180
9.2.2树的数组实现之模拟链接策略181
9.2.3树的分析182
9.3树的遍历182
9.3.1前序遍历183
9.3.2中序遍历183
9.3.3后序遍历184
9.3.4层序遍历184
9.4二叉树185
9.5使用二叉树：表达式树188
9.6用链表实现二叉树197
9.6.1find方法199
9.6.2iteratorInOrder方法201
9.7用数组实现二叉树202
9.7.1find方法203
9.7.2iteratorInOrder方法204
关键概念小结205
自测题205
练习题206
程序设计项目206
自测题答案206

第10章二叉查找树208
10.1概述208
10.2用链表实现二叉查找树211
10.2.1addElement操作211
10.2.2removeElement操作213
10.2.3removeAllOccurrences操作216
10.2.4removeMin操作217
10.3用数组实现二叉查找树218
10.3.1addElement操作219
10.3.2removeElement操作221
10.3.3replace操作223
10.3.4removeAllOccurrences操作227
10.3.5removeMin操作227
10.4用有序列表实现二叉查找树228
BinarySearchTreeList实现的分析231
10.5平衡二叉查找树232
10.5.1右旋233
10.5.2左旋233
10.5.3右左旋234
10.5.4左右旋234
10.6实现二叉查找树：AVL树235
10.6.1AVL树的右旋235
10.6.2AVL树的左旋236
10.6.3AVL树的右左旋236
10.6.4AVL树的左右旋236
10.7实现二叉查找树：红黑树237
10.7.1红黑树中的元素插入237
10.7.2红黑树中的元素删除239
10.8实现二叉查找树：Java集合API241
关键概念小结243
自测题244
练习题245
程序设计项目245
自测题答案246
参考文献247

第11章优先队列与堆248
11.1堆248
11.1.1addElement操作250
11.1.2removeMin操作251
11.1.3findMin操作252
11.2使用堆：优先级队列252
11.3用链表实现堆256
11.3.1addElement操作257
11.3.2removeMin操作259
11.3.3findMin操作261
11.4用数组实现堆261
11.4.1addElement操作262
11.4.2removeMin操作263
11.4.3findMin操作265
11.5使用堆：堆排序265
关键概念小结266
自测题267
练习题267
程序设计项目268
自测题答案268

第12章多路查找树270
12.1整合树的概念270
12.22-3树270
12.2.1往2-3树中插入元素271
12.2.2从2-3树中删除元素273
12.32-4树275
12.4B树276
12.4.1B*树277
12.4.2B+树277
12.4.3B树的分析278
12.5B树的实现策略278
关键概念小结279
自测题279
练习题279
程序设计项目280
自测题答案280
参考文献281

第13章图282
13.1无向图282
13.2有向图284
13.3网络285
13.4常用的图算法286
13.4.1遍历286
13.4.2测试连通性289
13.4.3最小生成树290
13.4.4判定最短路径293
13.5图的实现策略293
13.5.1邻接列表293
13.5.2邻接矩阵294
13.6用邻接矩阵实现无向图295
13.6.1addEdge方法298
13.6.2addVertex方法299
13.6.3expandCapacity方法300
13.6.4其他方法300
关键概念小结300
自测题301
练习题301
程序设计项目302
自测题答案302
参考文献303

第14章散列304
14.1概述304
14.2散列函数305
14.2.1余数法306
14.2.2折叠法306
14.2.3平方取中法307
14.2.4基数转换法307
14.2.5数字分析法307
14.2.6长度相关法307
14.2.7Java语言中的散列函数308
14.3解决冲突308
14.3.1链地址法308
14.3.2开放地址法310
14.4从散列表删除元素312
14.4.1从链地址实现中删除312
14.4.2从开放地址实现中删除312
14.5Java集合API中的散列表313
14.5.1Hashtable类313
14.5.2HashSet类314
14.5.3HashMap类315
14.5.4IdentityHashMap类316
14.5.5WeakHashMap类317
14.5.6LinkedHashSet与LinkedHashMap318
关键概念小结319
自测题319
练习题320
程序设计项目320
自测题答案321

第15章Set与Map集合323
15.1Set集合323
15.2使用Set：bingo程序326
15.3用数组实现Set329
15.3.1add操作330
15.3.2addAll操作332
15.3.3removeRandom操作332
15.3.4remove操作333
15.3.5union操作334
15.3.6contains操作335
15.3.7equals操作336
15.3.8其他操作337
15.3.9UML描述337
15.4用链表实现Set338
15.4.1add操作338
15.4.2removeRandom操作339
15.4.3remove操作340
15.4.4其他操作341
15.5Map集合与Java集合API341
关键概念小结342
自测题343
练习题343
程序设计项目343
自测题答案344

附录AUML346
A.1统一建模语言346
A.2UML类图346
A.3UML关系347
关键概念小结349
自测题350
练习题350
自测题答案350

附录B面向对象设计351
B.1概述351
B.2使用对象351
B.2.1抽象352
B.2.2创建对象353
B.3类库与包354
import声明355
B.4状态与行为355
B.5类356
实例数据359
B.6封装359
B.6.1可见性修饰符360
B.6.2局部数据361
B.7构造函数361
B.8方法重载362
B.9再谈引用363
B.9.1空引用363
B.9.2this引用364
B.9.3别名365
B.9.4垃圾回收367
B.9.5将对象作为参数传递367
B.10static修饰符368
B.10.1静态变量368
B.10.2静态方法369
B.11包装类369
B.12接口370
B.12.1Comparable接口371
B.12.2Iterator接口372
B.13继承372
B.13.1派生类373
B.13.2protected修饰符375
B.13.3super引用375
B.13.4重载方法376
B.14类的层次结构376
B.14.1Object类377
B.14.2抽象类378
B.14.3接口的层次结构379
B.15多态性379
B.15.1引用和类的层次结构380
B.15.2基于继承的多态性381
B.15.3基于接口的多态性382
B.16泛型384
B.17异常385
B.17.1异常消息385
B.17.2try语句386
B.17.3异常传播387
B.17.4异常类的层次结构387
关键概念小结388
自测题390
练习题390
程序设计项目391
自测题答案392