目录第一章 Java 与面向对象程序设计........................................................................................1 Java 语言基础知识....................................................................................................1 基本数据类型及运算.......................................................................................1 流程控制语句...................................................................................................3 字符串...............................................................................................................3 数组...................................................................................................................5 Java 的面向对象特性................................................................................................7 类与对象...........................................................................................................7 继承...................................................................................................................9 接口.................................................................................................................10 异常.........................................................................................................................11 Java 与指针..............................................................................................................12 数据结构与算法基础.............................................................................................15 数据结构.................................................................................................................15 基本概念.........................................................................................................15 抽象数据类型.................................................................................................17 小结.................................................................................................................19 算法及性能分析.....................................................................................................19 算法.................................................................................................................19 时间复杂性.....................................................................................................20 空间复杂性.....................................................................................................24 算法时间复杂度分析.....................................................................................25 最佳、最坏与平均情况分析.........................................................................27 均摊分析.........................................................................................................29 线性表.....................................................................................................................32 线性表及抽象数据类型.........................................................................................32 线性表定义.....................................................................................................32 线性表的抽象数据类型.................................................................................32 List 接口 ..........................................................................................................34 Strategy 接口 ...................................................................................................35 线性表的顺序存储与实现.....................................................................................36 线性表的链式存储与实现.....................................................................................42 单链表.............................................................................................................42 双向链表.........................................................................................................46 线性表的单链表实现.....................................................................................48 两种实现的对比.....................................................................................................53 基于时间的比较.............................................................................................53 基于空间的比较.............................................................................................53 链接表.....................................................................................................................54 基于结点的操作.............................................................................................54 链接表接口.....................................................................................................54 基于双向链表实现的链接表.........................................................................56 1.1 1.1.1 1.1.2 1.1.3 1.1.4 1.2 1.2.1 1.2.2 1.2.3 1.3 1.4 第二章 2.1 2.1.1 2.1.2 2.1.3 2.2 2.2.1 2.2.2 2.2.3 2.2.4 2.2.5 2.2.6 第三章 3.1 3.1.1 3.1.2 3.1.3 3.1.4 3.2 3.3 3.3.1 3.3.2 3.3.3 3.4 3.5 3.4.1 3.4.2 3.5.1 3.5.2 3.5.3第四章4.1栈与队列 (62)栈 (62)栈的定义及抽象数据类型 (62)栈的顺序存储实现 (63)栈的链式存储实现 (65)队列 (66)队列的定义及抽象数据类型 (66)队列的顺序存储实现 (68)队列的链式存储实现 (71)堆栈的应用 (72)进制转换 (72)括号匹配检测 (73)迷宫求解 (74)递归 (78)递归与堆栈 (78)递归的概念 (78)递归的实现与堆栈 (80)基于归纳的递归 (81)递推关系求解 (83)求解递推关系的常用方法 (83)线性齐次递推式的求解 (85)非齐次递推关系的解 (86)Master Method (87)分治法 (89)分治法的基本思想 (89)矩阵乘法 (91)选择问题 (93)树 (96)树的定义及基本术语 (96)二叉树 (99)二叉树的定义 (99)二叉树的性质 (99)二叉树的存储结构 (101)二叉树基本操作的实现 (105)树、森林 (112)树的存储结构 (112)树、森林与二叉树的相互转换 (114)树与森林的遍历 (115)由遍历序列还原树结构 (116)Huffman树 (117)二叉编码树 (117)Huffman树及Huffman编码 (118)图 (123)4.1.14.1.24.1.34.24.3 4.2.1 4.2.2 4.2.34.3.1 4.3.2 4.3.3第五章5.15.1.15.1.25.25.35.3.15.3.25.3.35.3.45.45.4.15.4.25.4.3 第六章6.16.26.2.16.2.26.2.36.36.46.4.16.4.26.4.36.4.46.56.5.16.5.2 第七章4.5 图及基本术语...............................................................................................123 抽象数据类型...............................................................................................127 图的存储方法.......................................................................................................129 邻接矩阵.......................................................................................................129 邻接表...........................................................................................................131 双链式存储结构...........................................................................................132 图ADT 实现设计 ..................................................................................................138 图的遍历...............................................................................................................139 深度优先搜索...............................................................................................139 广度优先搜索...............................................................................................142 图的连通性...........................................................................................................143 无向图的连通分量和生成树.......................................................................143 有向图的强连通分量...................................................................................144 最小生成树...................................................................................................145 最短距离...............................................................................................................151 单源最短路径...............................................................................................151 任意顶点间的最短路径...............................................................................155 有向无环图及其应用...........................................................................................157 4.4.1 4.4.2 4.5.1 4.5.2 4.5.3 4.6 4.7 4.7.1 4.7.2 4.8 4.8.1 4.8.2 4.8.3 4.9 4.9.1 4.9.2 4.10 4.10.1 4.10.2 拓扑排序.......................................................................................................157 关键路径.......................................................................................................159 第八章 查找.......................................................................................................................164 查找的定义...........................................................................................................164 基本概念.......................................................................................................164 查找表接口定义...........................................................................................165 顺序查找与折半查找...........................................................................................165 查找树...................................................................................................................168 二叉查找树...................................................................................................168 AVL 树...........................................................................................................175 B-树...............................................................................................................183 哈希.......................................................................................................................188 哈希表...........................................................................................................189 哈希函数.......................................................................................................190 冲突解决.......................................................................................................191 排序.......................................................................................................................194 排序的基本概念...................................................................................................194 插入类排序...........................................................................................................195 直接插入排序...............................................................................................195 折半插入排序...............................................................................................196 希尔排序.......................................................................................................197 交换类排序...........................................................................................................199 起泡排序.......................................................................................................199 快速排序.......................................................................................................200 选择类排序...........................................................................................................202 8.1 8.1.1 8.1.2 8.2 8.3 8.3.1 8.3.2 8.3.3 8.4 8.4.1 8.4.2 8.4.3 第九章 9.1 9.2 9.2.1 9.2.2 9.2.3 9.3 9.4 9.3.1 9.3.29.4.1 9.4.2 9.4.3 简单选择排序 (202)树型选择排序 (203)堆排序 (204)归并排序...............................................................................................................208 基于比较的排序的对比 (209)在线性时间内排序 (211)计数排序.......................................................................................................211 基数排序.......................................................................................................212 9.59.6 9.7 9.7.19.7.2周鹏第一章Java 与面向对象程序设计在这一章中向读者简要介绍有关Java 的基本知识。