第1章 绪论 1
1.1数据结构的起源 1
1.2数据结构的基本概念 2
1.3算法和算法分析 4
1.3.1算法描述 4
1.3.2算法分析 7
1.4 STL与数据结构 11
1.4.1 STL简介 11
1.4.2 STL与数据结构的关系 12
1.4.3 STL应用举例 13
1.5实例分析 14
习题1 16
第2章 线性表 19
2.1线性表的逻辑结构 19
2.1.1线性表的定义 19
2.1.2线性表的运算 20
2.2线性表的顺序存储结构 20
2.2.1顺序表 20
2.2.2顺序表的基本运算 21
2.2.3顺序表应用举例 26
2.3线性表的链式存储结构 27
2.3.1单链表 28
2.3.2单链表的基本运算 30
2.3.3循环链表 38
2.3.4双向链表 40
2.3.5静态链表 42
2.4顺序表与链表的比较 46
2.4.1时间性能比较 46
2.4.2空间性能比较 46
2.4.3高级语言的支持 47
2.5应用举例 47
2.5.1一元多项式的求和 47
2.5.2动态内存管理 53
2.6 STL中的相关模板类 58
2.6.1向量 58
2.6.2列表 62
习题2 63
第3章栈、队列和串 69
3.1栈 69
3.1.1栈的逻辑结构 69
3.1.2栈的顺序存储结构 70
3.1.3栈的链式存储结构 72
3.2队列 74
3.2.1队列的逻辑结构 74
3.2.2循环队列 75
3.2.3链队列 78
3.3串 81
3.3.1串的逻辑结构 81
3.3.2串的存储结构 83
3.3.3串的模式匹配 86
3.4实例分析 93
3.4.1函数调用与递归 93
3.4.2优先级队列的调度 98
3.5 STL中的相关模板类 101
3.5.1双端队列 101
3.5.2栈适配器 102
3.5.3 STL中的队列 103
3.5.4串类型 106
习题3 108
第4章 多维数组和广义表 110
4.1多维数组 110
4.2矩阵的压缩存储 112
4.2.1特殊矩阵压缩存储 112
4.2.2稀疏矩阵压缩存储 114
4.3广义表 120
4.3.1广义表的逻辑结构 120
4.3.2广义表的存储结构 122
4.4实例分析 123
4.4.1 BMP文件结构分析 123
4.4.2简单图像处理——平滑技术 133
4.5使用STL操作多维数组 135
习题4 138
第5章 树 141
5.1概述 141
5.1.1基本概念 142
5.1.2树的存储结构 143
5.1.3树的遍历 146
5.2二叉树 147
5.2.1二叉树的性质 148
5.2.2二叉树的存储 150
5.2.3二叉树的遍历 152
5.2.4二叉树的实现 154
5.3树和森林 165
5.3.1树、森林与二叉树的转换 165
5.3.2森林的遍历 167
5.4哈夫曼树和编码 168
5.4.1算法原理 168
5.4.2算法实现 171
习题5 175
第6章 图 179
6.1图的逻辑结构 179
6.1.1图的定义 179
6.1.2图的基本术语 180
6.2图的存储结构 183
6.2.1邻接矩阵 183
6.2.2邻接表 185
6.2.3十字链表 188
6.2.4邻接多重表 189
6.2.5边集数组 190
6.2.6图的存储结构比较 191
6.3图的遍历 191
6.3.1深度优先遍历 191
6.3.2广度优先遍历 195
6.4最小生成树 198
6.4.1普里姆算法 199
6.4.2克鲁斯卡尔算法 204
6.5最短路径 208
6.5.1 Dijkstra算法 209
6.5.2 Floyd算法 212
6.6图的应用举例——运动会安排 214
习题6 218
第7章 查找 220
7.1概述 220
7.1.1基本概念 220
7.1.2查找算法的性能 221
7.2线性表查找 221
7.2.1顺序查找 221
7.2.2折半查找 223
7.2.3分块查找 225
7.3树表的查找技术 226
7.3.1二叉排序树 227
7.3.2平衡二叉树 234
7.4散列表的查找技术 237
7.4.1散列技术 238
7.4.2散列函数设计 238
7.4.3冲突处理 240
7.4.4算法的性能 243
7.5查找的应用 243
7.5.1布隆过滤器 243
7.5.2中文分词技术中的词搜索算法 245
7.6 STL中的相关模板类 247
7.6.1集合 247
7.6.2 pair 252
7.6.3映射 254
7.6.4位集合 256
7.6.5中文分词技术中词搜索算法——STL实现 257
7.6.6 STL容器总结 259
习题7 261
第8章 排序 263
8.1概述 263
8.1.1基本概念 263
8.1.2排序的分类 264
8.1.3算法性能 264
8.2插入排序 264
8.2.1概述 264
8.2.2直接插入排序 265
8.2.3希尔排序 267
8.3交换排序 269
8.3.1概述 269
8.3.2起泡排序 269
8.3.3快速排序 272
8.4选择排序 274
8.4.1概述 274
8.4.2简单选择排序 274
8.4.3堆排序 276
8.5归并排序 281
8.5.1概述 281
8.5.2二路归并排序 281
8.6排序的比较 285
8.7外部排序 286
8.8排序的应用 287
8.9 STL中相关排序算法 290
8.9.1排序中的比较函数 290
8.9.2全排序 291
8.9.3局部排序 292
8.9.4指定元素排序 293
习题8 294
附录 297
参考文献 302