第1章 基本概念 1
1．1概述：系统生命周期 1
1．2面向对象的程序设计 3
1．2．1算法分解与面向对象分解 3
1．2．2基本定义和面向对象编程的概念 3
1．2．3程序设计语言的演化和C＋＋语言历史 4
1．3数据抽象和封装 4
1．4 C＋＋语言基础 8
1．4．1 C＋＋程序的组织结构 8
1．4．2 C＋＋语言的作用域 9
1．4．3 C＋＋的语句与操作符 10
1．4．4 C＋＋语言中的数据声明 10
1．4．5 C＋＋语言的注释 11
1．4．6 C＋＋语言的输入输出 11
1．4．7 C＋＋语言的函数 13
1．4．8 C＋＋语言的参数传递 13
1．4．9 C＋＋语言的函数名重载 14
1．4．10内联函数 14
1．4．11 C＋＋语言的动态内存分配 15
1．4．12例外 15
1．5算法规范 17
1．5．1概述 17
1．5．2递归算法 20
1．6标准模板库 24
1．7性能分析和度量 27
1．7．1性能分析 28
1．7．2性能度量 45
1．7．3测试数据的生成 50
1．8参考文献和推荐读物 54
第2章 数组 55
2．1抽象数据类型和C＋＋类 55
2．1．1 C＋＋类介绍 55
2．1．2 C＋＋语言中的数据抽象和封装 56
2．1．3声明类对象和调用成员函数 56
2．1．4特别类操作 57
2．1．5其他主题 60
2．1．6 ADT和C＋＋类 60
2．2将数组作为一种抽象数据类型 62
2．3多项式抽象数据类型 64
2．3．1多项式的表示 65
2．3．2多项式的加法 67
2．4稀疏矩阵 71
2．4．1绪论 71
2．4．2稀疏矩阵的表示法 72
2．4．3转置一个矩阵 73
2．4．4矩阵的乘法 76
2．5多维数组的表示 81
2．6字符串抽象数据类型 84
2．6．1一种简单的字符串模式匹配算法 85
2．6．2字符串模式匹配：Knuth-Morris-Pratt算法 85
2．7参考文献和推荐读物 89
2．8附加习题 89
第3章 栈和队列 94
3．1 C＋＋模板 94
3．1．1模板函数 94
3．1．2用模板表示容器类 96
3．2栈的抽象数据类型 99
3．3队列抽象数据类型 103
3．4 C＋＋中的子类型和继承 109
3．5一个迷宫问题 112
3．6计算表达式 116
3．6．1表达式 116
3．6．2后缀表达式 118
3．6．3中缀表达式转换成后缀表达式 119
3．7附加习题 122
第4章 链表 124
4．1单链表和链 124
4．2用C＋＋语言表示链表 126
4．2．1在C＋＋语言中定义结点 126
4．2．2用C＋＋语言设计一个链表类 127
4．2．3 C＋＋语言中的指针操作 130
4．2．4链表的控制操作 131
4．3链的模板类 134
4．3．1用模板实现链表 134
4．3．2链表迭代器 135
4．3．3链表操作 138
4．3．4类的重用 140
4．4循环链表 141
4．5可用空间链表 143
4．6链式栈和链式队列 144
4．7多项式 146
4．7．1多项式的表示 146
4．7．2多项式相加 147
4．7．3用循环链表表示多项式 150
4．8等价类 152
4．9稀疏矩阵 157
4．9．1稀疏矩阵的表示 157
4．9．2稀疏矩阵的输入 159
4．9．3删除稀疏矩阵 160
4．10双向链表 162
4．11广义表 165
4．11．1广义表的表示 165
4．11．2表的递归算法 168
4．11．3引用计数、共享和递归表 171
第5章 树 176
5．1概述 176
5．1．1术语表 176
5．1．2树的表示 178
5．2二叉树 180
5．2．1抽象数据类型 180
5．2．2二叉树的性质 181
5．2．3二叉树的表示 183
5．3二叉树的遍历和迭代程序 185
5．3．1概述 185
5．3．2中序遍历 185
5．3．3先序遍历 187
5．3．4后序遍历 187
5．3．5迭代中序遍历 188
5．3．6层次遍历 190
5．3．7不使用栈的遍历 191
5．4补充的二叉树操作 193
5．4．1复制二叉树 193
5．4．2检测相等 193
5．4．3满足性问题 194
5．5线索二叉树 196
5．5．1线索 196
5．5．2线索二叉树的中序遍历 197
5．5．3在线索二叉树上插入一个结点 198
5．6堆 200
5．6．1优先队列 200
5．6．2大顶堆的定义 201
5．6．3大顶堆的插入 202
5．6．4大顶堆的删除 203
5．7二叉查找树 205
5．7．1定义 205
5．7．2二叉查找树的查找 206
5．7．3二叉查找树的插入 208
5．7．4二叉查找树的删除 209
5．7．5二叉树的连接和分裂 210
5．7．6二叉查找树的高度 212
5．8选择树 213
5．8．1概述 213
5．8．2胜者树 213
5．8．3败者树 214
5．9森林 215
5．9．1将森林转换成二叉树 215
5．9．2森林的遍历 216
5．10离散集合表示 217
5．10．1概述 217
5．10．2并和查找操作 217
5．10．3等价类的应用 223
5．11二叉树计数 225
5．11．1不同的二叉树 225
5．11．2栈排列 226
5．11．3矩阵相乘 227
5．11．4不同二叉树的个数 228
5．12参考文献和推荐读物 229
第6章 图 230
6．1图的抽象数据类型 230
6．1．1概述 230
6．1．2定义 231
6．1．3图的表示 234
6．2图的基本操作 240
6．2．1深度优先搜索 240
6．2．2广度优先搜索 241
6．2．3连通分量 242
6．2．4生成树 243
6．2．5重连通分量 244
6．3最小代价生成树 248
6．3．1克鲁斯卡尔算法 248
6．3．2普里姆算法 251
6．3．3索林算法 252
6．4最短路径和传递闭包 253
6．4．1单源／多目标：非负权值 253
6．4．2单源／多目标：任意权值 257
6．4．3多源最短路径 259
6．4．4传递闭包 260
6．5活动网络 263
6．5．1顶点表示活动的网络（AOV网） 263
6．5．2用边表示活动的网络（AOE网） 267
6．5．3事件最早发生时间的计算 269
6．5．4事件最迟发生时间的计算 269
6．6参考文献和推荐读物 272
6．7附加习题 273
第7章 排序 275
7．1目的 275
7．2插入排序 278
7．3快速排序 280
7．4排序算法能够多快 283
7．5归并排序 284
7．5．1归并 284
7．5．2迭代归并 285
7．5．3递归归并 287
7．6堆排序 289
7．7多关键字排序 292
7．8链和列表排序 295
7．9内部排序总结 302
7．10外部排序 306
7．10．1概述 306
7．10．2 k路归并 308
7．10．3并行操作的缓存处理 309
7．10．4顺串产生 313
7．10．5顺串的最佳归并 315
7．11参考文献和推荐读物 318
第8章 散列 319
8．1绪论 319
8．2静态散列 319
8．2．1哈希表 319
8．2．2哈希函数 320
8．2．3安全哈希函数 323
8．2．4溢出处理 325
8．2．5溢出技术的理论分析 329
8．3动态散列 331
8．3．1动态散列的目的 331
8．3．2使用目录的动态散列 332
8．3．3不使用目录的动态散列 334
8．4布隆过滤器 335
8．4．1勘误文件的应用 335
8．4．2设计布隆过滤器 337
8．5参考文献和推荐读物 338
第9章 优先队列 340
9．1单端和双端优先队列 340
9．2左偏树 342
9．2．1高度左偏树 342
9．2．2重量左偏树 346
9．3二项式堆 349
9．3．1代价分摊 349
9．3．2二项式堆的定义 350
9．3．3二项式堆的插入操作 351
9．3．4合并两个二项式堆 352
9．3．5删除最小元素 352
9．3．6分析 354
9．4斐波那契堆 356
9．4．1定义 356
9．4．2从斐波那契堆中删除元素 356
9．4．3减小键值 357
9．4．4级联剪切 357
9．4．5分析 358
9．4．6在最短路径问题上的应用 360
9．5配对堆 361
9．5．1定义 361
9．5．2合并和插入操作 362
9．5．3减小键值 363
9．5．4删除最小元素 363
9．5．5删除任意元素 365
9．5．6实现问题 365
9．5．7复杂度 366
9．6对称最小-最大堆 366
9．6．1定义及性质 366
9．6．2 SMMH的表示 367
9．6．3插入操作 368
9．6．4删除操作 371
9．7区间堆 373
9．7．1定义及性质 373
9．7．2区间堆的插入操作 374
9．7．3删除最小元素 376
9．7．4初始化区间堆 377
9．7．5区间堆操作的复杂度 377
9．7．6互补范围搜索问题 377
9．8参考文献和推荐读物 379
第10章 高效二叉查找树 382
10．1最优二叉查找树 382
10．2 AVL树 388
10．3红黑树 398
10．3．1定义 398
10．3．2红黑树的表示 399
10．3．3查找 400
10．3．4插入 400
10．3．5删除 403
10．3．6红黑树的合并 403
10．3．7红黑树的分裂 404
10．4伸展树 406
10．4．1自底向上的伸展树 406
10．4．2自顶向下的伸展树 409
10．5参考文献和推荐读物 413
第11章 多路查找树 415
11．1 m路查找树 415
11．1．1定义和性质 415
11．1．2对m路查找树进行查找 416
11．2 B-树 417
11．2．1定义和性质 417
11．2．2 B-树的元素个数 417
11．2．3插入 418
11．2．4删除 420
11．3 B＋树 427
11．3．1定义 427
11．3．2查找 428
11．3．3插入 428
11．3．4删除 429
11．4参考文献和推荐读物 433
第12章 数字查找结构 434
12．1数字查找树 434
12．1．1定义 434
12．1．2查找、插入和删除 434
12．2二叉Trie树和Patricia树 435
12．2．1二叉Trie树 435
12．2．2压缩二叉Trie树 436
12．2．3 Patricia树 436
12．3多路Trie树 440
12．3．1定义 440
12．3．2查找Trie树 442
12．3．3抽样策略 442
12．3．4插入Trie树 444
12．3．5从Trie树中删除 444
12．3．6不同长度的关键字 444
12．3．7 Trie树的高度 445
12．3．8空间需求与其他结点结构 445
12．3．9前缀查找和应用 448
12．3．10压缩Trie树 449
12．3．11带跳过字段的压缩Trie树 451
12．3．12带标号边的压缩Trie树 452
12．3．13压缩Trie树需要的空间 453
12．4后缀树 454
12．4．1你是否见过这个字符串 454
12．4．2后缀树数据结构 455
12．4．3查找子串（查找后缀树） 457
12．4．4后缀树上的其他技巧 458
12．5 Trie树和Internet包转发 460
12．5．1 IP路由 460
12．5．2 1-比特Trie树 460
12．5．3固定跨度Trie树 461
12．5．4可变跨度Trie树 463
12．6参考文献和推荐读物 465
术语表 466