阅读权限200
最后登录2024-3-29
在线时间10359 小时
积分101870
注册时间2013-7-19
精华186
主题3132
UID1
帖子6509
金币642268
威望840
贡献565
技术432
活跃950
管理团队
人民公仆
- 贡献
- 565
- 技术
- 432
- 活跃
- 950
- 在线时间
- 10359 小时
|
数据结构与算法(JAVA语言版) 非常经典的JAVA学习PDF 216页
1.1.3 字符串...............................................................................................................3
1.1.4 数组...................................................................................................................5
1.2 Java的面向对象特性................................................................................................7
1.2.1 类与对象...........................................................................................................7
1.2.2 继承...................................................................................................................9
1.2.3 接口.................................................................................................................10
1.3 异常.........................................................................................................................11
1.4 Java与指针..............................................................................................................12
第二章 数据结构与算法基础.............................................................................................15
2.1 数据结构.................................................................................................................15
2.1.1 基本概念.........................................................................................................15
2.1.2 抽象数据类型.................................................................................................17
2.1.3 小结.................................................................................................................19
2.2 算法及性能分析.....................................................................................................19
2.2.1 算法.................................................................................................................19
2.2.2 时间复杂性.....................................................................................................20
2.2.3 空间复杂性.....................................................................................................24
2.2.4 算法时间复杂度分析.....................................................................................25
2.2.5 最佳、最坏与平均情况分析.........................................................................27
2.2.6 均摊分析.........................................................................................................29
第三章 线性表.....................................................................................................................32
3.1 线性表及抽象数据类型.........................................................................................32
3.1.1 线性表定义.....................................................................................................32
3.1.2 线性表的抽象数据类型.................................................................................32
3.1.3 List接口..........................................................................................................34
3.1.4 Strategy接口...................................................................................................35
3.2 线性表的顺序存储与实现.....................................................................................36
3.3 线性表的链式存储与实现.....................................................................................42
3.3.1 单链表.............................................................................................................42
3.3.2 双向链表.........................................................................................................46
3.3.3 线性表的单链表实现.....................................................................................48
3.4 两种实现的对比.....................................................................................................53
3.4.1 基于时间的比较.............................................................................................53
3.4.2 基于空间的比较.............................................................................................53
3.5 链接表.....................................................................................................................54
3.5.1 基于结点的操作.............................................................................................54
3.5.2 链接表接口.....................................................................................................54
3.5.3 基于双向链表实现的链接表.........................................................................56
3.6 迭代器.....................................................................................................................59
第四章 栈与队列.................................................................................................................62
4.1 栈.............................................................................................................................62
4.1.1 栈的定义及抽象数据类型.............................................................................62
4.1.2 栈的顺序存储实现.........................................................................................63
4.1.3 栈的链式存储实现.........................................................................................65
4.2 队列.........................................................................................................................66
4.2.1 队列的定义及抽象数据类型.........................................................................66
4.2.2 队列的顺序存储实现.....................................................................................68
4.2.3 队列的链式存储实现.....................................................................................71
4.3 堆栈的应用.............................................................................................................72
4.3.1 进制转换.........................................................................................................72
4.3.2 括号匹配检测.................................................................................................73
4.3.3 迷宫求解.........................................................................................................74
第五章 递归.........................................................................................................................78
5.1 递归与堆栈.............................................................................................................78
5.1.1 递归的概念.....................................................................................................78
5.1.2 递归的实现与堆栈.........................................................................................80
5.2 基于归纳的递归.....................................................................................................81
5.3 递推关系求解.........................................................................................................83
5.3.1 求解递推关系的常用方法.............................................................................83
5.3.2 线性齐次递推式的求解.................................................................................85
5.3.3 非齐次递推关系的解.....................................................................................86
5.3.4 Master Method ................................................................................................87
5.4 分治法.....................................................................................................................89
5.4.1 分治法的基本思想.........................................................................................89
5.4.2 矩阵乘法.........................................................................................................91
5.4.3 选择问题.........................................................................................................93
第六章 树.............................................................................................................................96
6.1 树的定义及基本术语.............................................................................................96
6.2 二叉树.....................................................................................................................99
6.2.1 二叉树的定义.................................................................................................99
6.2.2 二叉树的性质.................................................................................................99
6.2.3 二叉树的存储结构.......................................................................................101
6.3 二叉树基本操作的实现.......................................................................................105
6.4 树、森林...............................................................................................................112
6.4.1 树的存储结构...............................................................................................112
6.4.2 树、森林与二叉树的相互转换...................................................................114
6.4.3 树与森林的遍历...........................................................................................115
6.4.4 由遍历序列还原树结构...............................................................................116
6.5 Huffman树............................................................................................................117
6.5.1 二叉编码树...................................................................................................117
6.5.2 Huffman树及Huffman编码..........................................................................118
第七章 图...........................................................................................................................123
4.4 图的定义...............................................................................................................123
4.4.1 图及基本术语...............................................................................................123
4.4.2 抽象数据类型...............................................................................................127
4.5 图的存储方法.......................................................................................................129
4.5.1 邻接矩阵.......................................................................................................129
4.5.2 邻接表...........................................................................................................131
4.5.3 双链式存储结构...........................................................................................132
4.6 图ADT实现设计..................................................................................................138
4.7 图的遍历...............................................................................................................139
4.7.1 深度优先搜索...............................................................................................139
4.7.2 广度优先搜索...............................................................................................142
4.8 图的连通性...........................................................................................................143
4.8.1 无向图的连通分量和生成树.......................................................................143
4.8.2 有向图的强连通分量...................................................................................144
4.8.3 最小生成树...................................................................................................145
4.9 最短距离...............................................................................................................151
4.9.1 单源最短路径...............................................................................................151
4.9.2 任意顶点间的最短路径...............................................................................155
4.10 有向无环图及其应用...........................................................................................157
4.10.1 拓扑排序.......................................................................................................157
4.10.2 关键路径.......................................................................................................159
第八章 查找.......................................................................................................................164
8.1 查找的定义...........................................................................................................164
8.1.1 基本概念.......................................................................................................164
8.1.2 查找表接口定义...........................................................................................165
8.2 顺序查找与折半查找...........................................................................................165
8.3 查找树...................................................................................................................168
8.3.1 二叉查找树...................................................................................................168
8.3.2 AVL树...........................................................................................................175
8.3.3 B-树...............................................................................................................183
8.4 哈希.......................................................................................................................188
8.4.1 哈希表...........................................................................................................189
8.4.2 哈希函数.......................................................................................................190
8.4.3 冲突解决.......................................................................................................191
第九章 排序.......................................................................................................................194
9.1 排序的基本概念...................................................................................................194
9.2 插入类排序...........................................................................................................195
9.2.1 直接插入排序...............................................................................................195
9.2.2 折半插入排序...............................................................................................196
9.2.3 希尔排序.......................................................................................................197
9.3 交换类排序...........................................................................................................199
9.3.1 起泡排序.......................................................................................................199
9.3.2 快速排序.......................................................................................................200
9.4 选择类排序...........................................................................................................202
9.4.1 简单选择排序...............................................................................................202
9.4.2 树型选择排序...............................................................................................203
9.4.3 堆排序...........................................................................................................204
9.5 归并排序...............................................................................................................208
9.6 基于比较的排序的对比.......................................................................................209
9.7 在线性时间内排序...............................................................................................211
9.7.1 计数排序.......................................................................................................211
9.7.2 基数排序.......................................................................................................212
|
|