数据结构与算法(JAVA语言版)-2.docx

目录
第一章
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
1

3.6
第四章
4.1
迭代器.....................................................................................................................59
栈与队列.................................................................................................................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.1
4.1.2
4.1.3
4.2
4.3
4.2.1
4.2.2
4.2.3
4.3.1
4.3.2
4.3.3
第五章
5.1
5.1.1
5.1.2
5.2
5.3
5.3.1
5.3.2
5.3.3
5.3.4
5.4
5.4.1
5.4.2
5.4.3
第六章
6.1
6.2
6.2.1
6.2.2
6.2.3
6.3
6.4
6.4.1
6.4.2
6.4.3
6.4.4
6.5
6.5.1
6.5.2
第七章
2

4.4
4.5
图的定义...............................................................................................................123
图及基本术语...............................................................................................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
选择类排序..............................................................