数据结构与问题求解：Java版

第一部分    Java教程                  
 第1章    Java简介 2                  
 1.1    通用环境 2                  
 1.2    第一个程序 3                  
 1.3    基本数据类型 4                  
 1.4    基本运算符 5                  
 1.5    条件语句 7                  
 1.6    方法 11                  
 1.7    小结 13                  
 1.8    名词解释 13                  
 1.9    常见错误 14                  
 1.10  网上资源 14                  
 习题 15                  
 参考文献 16                  
 第2章    引用类型 17                  
 2.1    什么是引用 17                  
 2.2    对象和引用的基本概念 18                  
 2.3    字符串 21                  
 2.4    数组 23                  
 2.5    异常处理 30                  
 2.6    输入和输出 32                  
 2.7    小结 35                  
 2.8    名词解释 37                  
 2.9    常见错误 38                  
 2.10  网上资源 38                  
 习题 38                  
 参考文献 39                  
 第3章    对象与类 40                  
 3.1    何为面向对象编程 40                  
 3.2    一个简单的例子 41                  
 3.3    JavaDOC 42                  
 3.4    基本方法 43                  
 3.5    附加结构 46                  
 3.6    包 49                  
 3.7    设计模式：复合 52                  
 3.8    小结 52                  
 3.9    名词解释 53                  
 3.10  常见错误 54                  
 3.11  网上资源 55                  
 习题 55                  
 参考文献 57                  
 第4章    继承  58                  
 4.1    什么是继承 58                  
 4.2    层次结构设计 68                  
 4.3    多重继承 71                  
 4.4    接口 72                  
 4.5    Java中的基础继承体系 74                  
 4.6    通用实现组件 77                  
 4.7    函数（函数对象） 82                  
 4.8    动态绑定细节 87                  
 4.9    小结 89                  
 4.10  名词解释 90                  
 4.11  常见错误 91                  
 4.12  网上资源 91                  
 习题 92                  
 参考文献 95                  
 第二部分    算法与程序构建                  
 第5章    算法分析 98                  
 5.1    什么是算法分析 98                  
 5.2    算法运行时间举例 100                  
 5.3    最大连续子序列之和的问题 101                  
 5.4    通用Big-Oh规则 106                  
 5.5    对数 108                  
 5.6    静态搜索问题 109                  
 5.7    检验算法分析 112                  
 5.8    Big-Oh分析法的限制 113                  
 5.9    小结 113                  
 5.10  名词解释 113                  
 5.11  常见错误 114                  
 5.12  网上资源 114                  
 习题 114                  
 参考文献 118                  
 第6章    应用程序接口集 119                  
 6.1    简介 119                  
 6.2    迭代器模式 120                  
 6.3    应用程序接口集：容器和迭代器 123                  
 6.4    通用算法 127                  
 6.5    表接口 131                  
 6.6    栈和队列 134                  
 6.7    集合 137                  
 6.8    映射 142                  
 6.9    优先级队列 145                  
 6.10  小结 148                  
 6.11  名词解释 148                  
 6.12  常见错误 149                  
 6.13  网上资源 149                  
 习题 150                  
 参考文献 151                  
 第7章    递归 152                  
 7.1    什么是递归 152                  
 7.2    背景：通过数学归纳法证明 153                  
 7.3    基本递归 154                  
 7.4    数值应用 163                  
 7.5    分而治之算法 168                  
 7.6    动态规划 174                  
 7.7    回溯 177                  
 7.8    小结 180                  
 7.9    名词解释 181                  
 7.10  常见错误 181                  
 7.11  网上资源 181                  
 习题 182                  
 参考文献 184                  
 第8章   排序算法 185                  
 8.1    排序算法为什么重要 185                  
 8.2    基础知识 186                  
 8.3    插入排序算法和其他简单排序算法的分析 186                  
 8.4    希尔排序 188                  
 8.5    归并排序 190                  
 8.6    快速排序 192                  
 8.7    快速选择 202                  
 8.8    排序的下限 203                  
 8.9    小结 204                  
 8.10  名词解释 204                  
 8.11  常见错误 204                  
 8.12  网上资源 205                  
 习题 205                  
 参考文献 208                  
 第9章    随机化处理 209                  
 9.1    为什么需要随机数字 209                  
 9.2    随机数字发生器 209                  
 9.3    非均匀分布的随机数字 213                  
 9.4    产生随机排序 214                  
 9.5    随机化算法 215                  
 9.6    随机化初试 217                  
 9.7    小结 219                  
 9.8    名词解释 219                  
 9.9    常见错误 220                  
 9.10  网上资源 220                  
 习题 220                  
 参考文献 221                  
 第三部分    应用                  
 第10章    趣味游戏 224                  
 10.1    迷宫索字游戏 224                  
 10.2    Tic-Tac-Toe游戏 230                  
 10.3    小结 236                  
 10.4    名词解释 236                  
 10.5    常见错误 236                  
 10.6    网上资源 236                  
 习题 236                  
 参考文献 238                  
 第11章    栈和编译程序 239                  
 11.1    平衡符校验器 239                  
 11.2    一个简单的计算器 248                  
 11.3    小结 258                  
 11.4    名词解释 258                  
 11.5    常见错误 259                  
 11.6    网上资源 259                  
 习题 259                  
 参考文献 260                  
 第12章    公用程序 261                  
 12.1    文件压缩 261                  
 12.2    交叉引用发生器 276                  
 12.3    小结 279                  
 12.4    名词解释 279                  
 12.5    常见错误 280                  
 12.6    网上资源 280                  
 习题 280                  
 参考文献 282                  
 第13章    仿真 283                  
 13.1    Josephus问题 283                  
 13.2    事件驱动仿真 286                  
 13.3    小结 292                  
 13.4    名词解释 293                  
 13.5    常见错误 293                  
 13.6    网上资源 293                  
 习题 293                  
 第14章    图形和路径 295                  
 14.1    定义 295                  
 14.2    无权值最短路径问题 304                  
 14.3    正权值最短路径问题 307                  
 14.4    负权值最短路径问题 311                  
 14.5    无环图中的路径问题 313                  
 14.6    小结 318                  
 14.7    名词解释 318                  
 14.8    常见错误 319                  
 14.9    网上资源 319                  
 习题 319                  
 参考文献 321                  
 第四部分    实现                  
 第15章    内部类和数组表的实现 324                  
 15.1    迭代和嵌套类 324                  
 15.2    迭代类和内部类 326                  
 15.3    抽象集（AbstractCollection）类 328                  
 15.4    有迭代类的 ArrayList的实现 330                  
 15.5    小结 334                  
 15.6    名词解释 334                  
 15.7    常见错误 335                  
 15.8    网络资源 335                  
 习题 335                  
 第16章    堆栈和队列 337                  
 16.1    动态数组的实现 337                  
 16.2    链表的实现 345                  
 16.3    两种方法的对比 350                  
 16.4    java.util.Stack类 350                  
 16.5    双端队列 351                  
 16.6    小结 352                  
 16.7    名词解释 352                  
 16.8    常见错误 352                  
 16.9    网上资源 352                  
 习题 353                  
 第17章    链表 354                  
 17.1    基本概念 354                  
 17.2    Java 实现 357                  
 17.3    双向链表和循环链表 361                  
 17.4    排序链表 363                  
 17.5    API类库集中的LinkedList 类的实现 364                  
 17.6    小结 373                  
 17.7    名词解释 373                  
 17.8    常见错误 373                  
 17.9    网上资源 373                  
 习题 374                  
 第18章    树 376                  
 18.1    通用树 376                  
 18.2    二叉树 381                  
 18.3    递归和树 385                  
 18.4    树的遍历：iterator类 387                  
 18.5    小结 396                  
 18.6    名词解释 396                  
 18.7    常见错误 397                  
 18.8    网上资源 397                  
 习题 397                  
 第19章    二叉查找树 400                  
 19.1    基本思想 400                  
 19.2    静态顺序 407                  
 19.3    二叉查找树的操作分析 410                  
 19.4    AVL树 412                  
 19.5    红-黑树 418                  
 19.6    AA-树 427                  
 19.7    API类库中的集TreeSet和TreeMap类的实现 434                  
 19.8    B-树 446                  
 19.9    小结 449                  
 19.10  名词解释 450                  
 19.11  常见错误 451                  
 19.12  网上资源 451                  
 习题 451                  
 参考文献 453                  
 第20章    哈希表 455                  
 20.1    基本思想 455                  
 20.2    哈希函数 456                  
 20.3    线性探测 457                  
 20.4    二次探测 460                  
 20.5    单链哈希法 470                  
 20.6    哈希表与二叉查找树 470                  
 20.7    哈希法的应用 471                  
 20.8    小结 471                  
 20.9    名词解释 471                  
 20.10  常见错误 472                  
 20.11  网上资源 472                  
 习题 472                  
 参考文献 474                  
 第21章    优先队列：二分堆 475                  
 21.1    基本思想 475                  
 21.2    基本操作的实现 479                  
 21.3    buildHeap操作：线性时间堆结构 482                  
 21.4    高级操作：decreaseKey和merge 484                  
 21.5    内部排序：堆排序 485                  
 21.6    外部排序 487                  
 21.7    小结 491                  
 21.8    名词解释 491                  
 21.9    常见错误 492                  
 21.10  网上资源 492                  
 习题 492                  
 参考文献 494                  
 第五部分    高级数据结构                  
 第22章    splay树 498                  
 22.1    自动调整和分步偿付 498                  
 22.2    基本的自下而上的splay树 500                  
 22.3    基本的splay树操作 501                  
 22.4    自底而上的splay树的分析 502                  
 22.5    自顶而下的splay树的分析 505                  
 22.6    自顶而下splay树的实现 508                  
 22.7    splay树和其他查找树的比较 512                  
 22.8    小结 512                  
 22.9    名词解释 512                  
 22.10  常见错误 512                  
 22.11  网上资源 512                  
 习题 513                  
 参考文献 513                  
 第23章    归并优先级队列 515                  
 23.1    非对称堆 515                  
 23.2    对称堆 518                  
 23.3    小结 526                  
 23.4    名词解释 527                  
 23.5    常见错误 527                  
 23.6    网上资源 527                  
 习题 527                  
 参考文献 528                  
 第24章    不相交集合类 529                  
 24.1    等价关系 529                  
 24.2    动态等价及应用 529                  
 24.3    快速查找算法 536                  
 24.4    快速合并算法 536                  
 24.5    Java实现 539                  
 24.6    根据层合并和路径压缩的最差情况 541                  
 24.7    小结 545                  
 24.8    名词解释 546                  
 24.9    常见错误 546                  
 24.10  网上资源   546                  
 习题 546                  
 参考文献 548                  
 附录A    运算符 550                  
 附录B    图形用户界面 551                  
 附录 C    位运算符 569