第1章 绪论 1
1.1本课程讨论的内容 1
1.1.1求解问题举例 1
1.1.2本课程的内容 4
1.2基本概念与术语 4
1.2.1数据与数据结构 4
1.2.2数据类型 9
1.2.3抽象数据类型 11
1.3算法和算法分析 13
1.3.1算法的基本概念 13
1.3.2算法的描述 14
1.3.3算法分析 15
1.3.4算法设计举例 21
1.4 Java提供的泛型方法 24
小结 26
习题1 27
第2章 线性表 30
2.1线性表及其基本操作 30
2.1.1线性表的基本概念 30
2.1.2线性表的抽象数据类型描述 31
2.2线性表的顺序存储及其实现 32
2.2.1线性表的顺序存储 32
2.2.2顺序表上基本操作的实现 34
2.2.3顺序表应用举例 37
2.3线性表的链式存储及其实现 38
2.3.1单链表的表示 39
2.3.2单链表上基本操作的实现 42
2.3.3单链表应用举例 48
2.3.4其他链表 51
2.4顺序表与链表的比较 56
2.5线性表的应用举例 57
小结 65
习题2 65
第3章 栈与队列 69
3.1栈 69
3.1.1栈的概念 69
3.1.2栈的抽象数据类型描述 70
3.1.3顺序栈及其基本操作的实现 70
3.1.4链栈及其基本操作的实现 73
3.1.5栈的应用 76
3.2队列 88
3.2.1队列的概念 88
3.2.2队列的抽象数据类型描述 88
3.2.3顺序队列及其基本操作的实现 89
3.2.4链队列及其基本操作的实现 93
3.2.5队列的应用 95
3.2.6优先级队列 97
3.3栈与队列的比较 101
3.4栈与队列的综合应用举例 103
小结 105
习题3 107
第4章 串与数组 110
4.1串的定义及描述 110
4.1.1串的基本概念 110
4.1.2串的抽象数据类型描述 111
4.2串的存储结构 112
4.2.1串的顺序存储结构 112
4.2.2串的链式存储结构 112
4.3顺序串的实现 113
4.3.1顺序串的类定义 113
4.3.2串的基本操作实现 115
4.4串的模式匹配操作 118
4.4.1 Brute-Force模式匹配算法 118
4.4.2 KMP模式匹配算法 120
4.5串的应用举例 125
4.6数组的概念及其顺序存储结构 131
4.6.1数组的基本概念 132
4.6.2数组的抽象数据类型描述 132
4.6.3数组的顺序存储结构 132
4.7特殊矩阵的压缩存储 134
4.7.1对称矩阵的压缩存储 134
4.7.2三角矩阵的压缩存储 134
4.7.3对角矩阵的压缩存储 135
4.8稀疏矩阵的压缩存储 136
4.8.1稀疏矩阵的三元组表存储 136
4.8.2稀疏矩阵的十字链表存储 142
4.9数组的应用举例 144
小结 146
习题4 147
第5章 树与二叉树 149
5.1树的概念及常用术语 149
5.1.1树的定义 149
5.1.2树的常用术语 151
5.2二叉树 152
5.2.1二叉树的基本概念 152
5.2.2二叉树的性质 154
5.2.3二叉树的存储结构 155
5.3二叉树的遍历 159
5.3.1二叉树的遍历方法及其实现 159
5.3.2二叉树遍历算法的应用举例 166
5.3.3建立二叉树 169
5.4哈夫曼树及哈夫曼编码 174
5.4.1哈夫曼树的基本概念 174
5.4.2哈夫曼树和哈夫曼编码的构造方法 175
5.4.3构造哈夫曼树和哈夫曼编码类的描述 177
5.5树与森林 180
5.5.1树、森林与二叉树之间的转换 181
5.5.2树的存储结构 184
5.5.3树和森林的遍历 187
小结 189
习题5 189
第6章图 192
6.1图的概述 192
6.1.1图的基本概念 192
6.1.2图的抽象数据类型描述 195
6.2图的存储结构 196
6.2.1邻接矩阵 196
6.2.2邻接表 201
6.3图的遍历 207
6.3.1广度优先搜索 208
6.3.2深度优先搜索 210
6.3.3图的遍历方法的应用举例 211
6.4最小生成树 217
6.4.1最小生成树的基本概念 217
6.4.2克鲁斯卡尔算法 218
6.4.3普里姆算法 219
6.5最短路径 222
6.5.1某个源点到其余各顶点的最短路径 223
6.5.2每一对顶点之间的最短路径 225
6.6拓扑排序 229
6.6.1拓扑排序的基本概念 230
6.6.2拓扑排序的实现 230
6.7关键路径 232
小结 236
习题6 237
第7章 排序 240
7.1排序的基本概念 240
7.2插人排序 244
7.2.1直接插人排序 244
7.2.2希尔排序 246
7.3交换排序 247
7.3.1冒泡排序 248
7.3.2快速排序 249
7.4选择排序 252
7.4.1直接选择排序 252
7.4.2树形选择排序 253
7.4.3堆排序 258
7.5归并排序 262
7.6基数排序 265
7.6.1多关键字排序 265
7.6.2链式基数排序 266
小结 268
习题7 272
第8章 查找 274
8.1查找的基本概念 274
8.2静态查找表 275
8.2.1顺序查找 275
8.2.2二分查找 276
8.2.3分块查找 278
8.3动态查找表 281
8.3.1二叉排序树 281
8.3.2平衡二叉树 288
8.3.3 B-树和B+树 291
8.3.4红黑树简介 301
8.4哈希表查找 303
8.4.1哈希表的定义 303
8.4.2常用的哈希函数 304
8.4.3处理冲突的方法 307
8.4.4哈希表的查找和性能分析 312
小结 313
习题8 314
参考文献 317