Java软件结构与数据结构 第3版PDF电子书下载

第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 Obiect类 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