Java软件结构与数据结构(第3版)

基本信息

名称： Java软件结构与数据结构(第3版)
作者信息： 作者: John Lewis [ 中文 pdf ]

简单介绍

《Java软件结构与数据结构(第3版)》的写作方法是建立在一些我们强烈推荐的重要原则之上的。首先，我们以一种连贯叙述的方式介绍在《Java软件结构与数据结构(第3版)》中将要考察的各种集合。其次，我们强调完美软件设计技巧的重要性。第三，我们对《Java软件结构与数据结构(第3版)》结构加以组织以支持和强化《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.2 Java集合API 21 3.2 栈集合 22 3.3 主要的面向对象概念 23 3.3.1 继承 24 3.3.2 类层次 25 3.3.3 Object类 26 3.3.4 多态性 27 3.3.5 引用与类层次 28 3.3.6 泛型 29 3.4 栈ADT 30 接口 30 3.5 使用栈计算后缀表达式 32 3.6 异常 38 3.6.1 异常消息 39 3.6.2 try语句 39 3.6.3 异常传播 40 3.7 用数组实现栈 41 管理容量 41 3.8 ArrayStack类 42 3.8.1 构造函数 43 3.8.2 push操作 44 3.8.3 pop操作 45 3.8.4 peek操作 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.1 LinkedStack类 57 4.4.2 push操作 60 4.4.3 pop操作 61 4.4.4 其他操作 62 4.5 使用栈来穿越迷宫 62 4.6 java.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.1 enqueue操作 83 5.4.2 dequeue操作 84 5.4.3 其他操作 85 5.5 用数组实现队列 85 5.5.1 enqueue操作 88 5.5.2 dequeue操作 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.1 remove操作 112 6.4.2 contains操作 114 6.4.3 iterator操作 115 6.4.4 有序列表的add操作 117 6.4.5 无序列表的特有操作 118 6.4.6 无序列表的addAfter操作 118 6.5 使用链表实现列表 119 6.5.1 remove操作 119 6.5.2 双向链表 121 6.5.3 iterator操作 124 6.6 Java集合API中的列表 126 6.6.1 Cloneable接口 126 6.6.2 Serializable接口 127 6.6.3 RandomAccess接口 127 6.6.4 java.util.Vector接口 127 6.6.5 java.util.ArrayList接口 129 6.6.6 java.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.1 find方法 199 9.6.2 iteratorInOrder方法 201 9.7 用数组实现二叉树 202 9.7.1 find方法 203 9.7.2 iteratorInOrder方法 204 关键概念小结 205 自测题 205 练习题 206 程序设计项目 206 自测题答案 206

 第10章 二叉查找树 208 10.1 概述 208 10.2 用链表实现二叉查找树 211 10.2.1 addElement操作 211 10.2.2 removeElement操作 213 10.2.3 removeAllOccurrences操作 216 10.2.4 removeMin操作 217 10.3 用数组实现二叉查找树 218 10.3.1 addElement操作 219 10.3.2 removeElement操作 221 10.3.3 replace操作 223 10.3.4 removeAllOccurrences操作 227 10.3.5 removeMin操作 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.1 AVL树的右旋 235 10.6.2 AVL树的左旋 236 10.6.3 AVL树的右左旋 236 10.6.4 AVL树的左右旋 236 10.7 实现二叉查找树：红黑树 237 10.7.1 红黑树中的元素插入 237 10.7.2 红黑树中的元素删除 239 10.8 实现二叉查找树：Java集合API 241 关键概念小结 243 自测题 244 练习题 245 程序设计项目 245 自测题答案 246 参考文献 247

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

 第12章 多路查找树 270 12.1 整合树的概念 270 12.2 2-3树 270 12.2.1 往2-3树中插入元素 271 12.2.2 从2-3树中删除元素 273 12.3 2-4树 275 12.4 B树 276 12.4.1 B*树 277 12.4.2 B+树 277 12.4.3 B树的分析 278 12.5 B树的实现策略 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.1 addEdge方法 298 13.6.2 addVertex方法 299 13.6.3 expandCapacity方法 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.7 Java语言中的散列函数 308 14.3 解决冲突 308 14.3.1 链地址法 308 14.3.2 开放地址法 310 14.4 从散列表删除元素 312 14.4.1 从链地址实现中删除 312 14.4.2 从开放地址实现中删除 312 14.5 Java集合API中的散列表 313 14.5.1 Hashtable类 313 14.5.2 HashSet类 314 14.5.3 HashMap类 315 14.5.4 IdentityHashMap类 316 14.5.5 WeakHashMap类 317 14.5.6 LinkedHashSet与LinkedHashMap 318 关键概念小结 319 自测题 319 练习题 320 程序设计项目 320 自测题答案 321

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

 附录A UML 346 A.1 统一建模语言 346 A.2 UML类图 346 A.3 UML关系 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.2 this引用 364 B.9.3 别名 365 B.9.4 垃圾回收 367 B.9.5 将对象作为参数传递 367 B.10 static修饰符 368 B.10.1 静态变量 368 B.10.2 静态方法 369 B.11 包装类 369 B.12 接口 370 B.12.1 Comparable接口 371 B.12.2 Iterator接口 372 B.13 继承 372 B.13.1 派生类 373 B.13.2 protected修饰符 375 B.13.3 super引用 375 B.13.4 重载方法 376 B.14 类的层次结构 376 B.14.1 Object类 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.2 try语句 386 B.17.3 异常传播 387 B.17.4 异常类的层次结构 387 关键概念小结 388 自测题 390 练习题 390 程序设计项目 391 自测题答案 392

亚马逊链接