第1章 绪论 1
1.1 数据与数据结构 2
1.1.1 数据及其类型 2
1.1.2 数据结构简介 4
1.2 算法 6
1.2.1 算法的概念 6
1.2.2 算法的分析 8
1.2.3 算法的设计 12
1.3 C++语言简介 18
1.3.1 C++的产生与发展 18
1.3.2 C++与面向对象思想 20
1.3.3 C++中的类和对象 23
1.4 本章小结 28
第2章 C++编程基础 29
2.1 开始C++编程 30
2.1.1 输入输出 30
2.1.2 预处理 38
2.1.3 名字空间 44
2.2 深入的类编程 50
2.2.1 访问控制 50
2.2.2 初始化与清除 53
2.2.3 动态创建对象 57
2.2.4 友元函数 60
2.2.5 拷贝构造函数 61
2.3 丰富的C++特性 65
2.3.1 常量 65
2.3.2 函数重载 68
2.3.3 运算符重载 71
2.3.4 异常处理 77
2.4 代码重用机制 79
2.4.1 继承 80
2.4.2 多态 87
2.4.3 模板 90
2.5 标准模板库 93
2.5.1 STL简介 94
2.5.2 STL构成 95
2.5.3 STL的不同版本 97
2.6 本章小结 98
第3章 指针、数组与字符串 99
3.1 指针 100
3.1.1 指针的概念 100
3.1.2 指针的语法 102
3.1.3 函数与参数传递 103
3.2 数组 108
3.2.1 数组定义与初始化 109
3.2.2 数组与指针 113
3.2.3 数组的抽象数据类型 116
3.2.4 大整数乘法问题 120
3.2.5 荷兰国旗问题 121
3.3 字符串 124
3.3.1 C++中的字符串 124
3.3.2 字符串抽象数据类型 126
3.3.3 字符串的匹配算法 128
3.3.4 字符串指数问题 141
3.4 动态内存管理 142
3.4.1 关键词new和delete 143
3.4.2 避免内存错误 146
3.5 本章小结 152
第4章 链表 153
4.1 单向链表 154
4.1.1 单向链表的结构 154
4.1.2 单向链表类的实现 155
4.1.3 有序链表的合并 162
4.1.4 多项式加法问题 163
4.2 单向循环链表 164
4.2.1 单向循环链表的结构 164
4.2.2 单向循环链表类的实现 166
4.2.3 约瑟夫问题 169
4.2.4 魔术师发牌问题 170
4.2.5 拉丁方阵问题 172
4.3 双向循环链表 173
4.3.1 双向循环链表的结构 173
4.3.2 双向循环链表类的实现 174
4.3.3 Vigenere加密问题 182
4.3.4 选美比赛问题 184
4.4 游标类的设计与实现 186
4.4.1 游标类的结构 186
4.4.2 游标类的实现 187
4.5 STL与链表 191
4.5.1 STL中链表类的接口 191
4.5.2 遍历 194
4.5.3 元素的插入与删除 196
4.6 本章小结 196
第5章 栈与队列 197
5.1 栈 198
5.1.1 栈的结构 198
5.1.2 栈的实现 199
5.1.3 括号匹配问题 203
5.1.4 停车场模拟问题 204
5.2 队列 208
5.2.1 队列的结构 208
5.2.2 队列的实现 210
5.2.3 舞伴问题 214
5.2.4 杨辉三角形问题 215
5.2.5 游程编码问题 216
5.3 优先级队列 218
5.3.1 优先级队列的结构 218
5.3.2 优先级队列的实现 220
5.4 STL中的栈与队列 222
5.4.1 STL中的stack 222
5.4.2 STL中的queue 224
5.4.3 STL中的priority_queue 226
5.5 本章小结 229
第6章 递归 231
6.1 递归的概念 232
6.1.1 递归的定义 232
6.1.2 应用递归的原则 235
6.1.3 递归和非递归的转化 240
6.2 分治法 243
6.2.1 分治法简述 243
6.2.2 汉诺塔问题 244
6.2.3 传染病问题 246
6.3 回溯法 250
6.3.1 回溯法简述 251
6.3.2 迷宫问题 251
6.3.3 八皇后问题 255
6.3.4 骑士周游问题 258
6.4 本章小结 265
第7章 树 267
7.1 树的概念 268
7.1.1 树的定义 268
7.1.2 树的术语 271
7.1.3 树的抽象数据类型 272
7.2 二叉树 273
7.2.1 二叉树的定义 273
7.2.2 二叉树的性质 275
7.2.3 二叉树的实现 276
7.2.4 二叉树的遍历 285
7.2.5 二叉树的线索化 289
7.3 树与森林 291
7.3.1 树的存储表示 291
7.3.2 树的实现 294
7.3.3 树与森林的遍历 298
7.3.4 森林与二叉树的转换 300
7.4 霍夫曼树 304
7.4.1 霍夫曼树的概念 304
7.4.2 霍夫曼树的构造方法 305
7.4.3 霍夫曼编码及其实现 307
7.5 堆 313
7.5.1 堆的概念 314
7.5.2 堆的建立 314
7.5.3 堆的操作 316
7.6 基于STL实现树结构 317
7.6.1 STL中的vector 317
7.6.2 STL中的map 321
7.7 医院建模问题 323
7.8 本章小结 328
第8章 图 329
8.1 图的基本概念 330
8.1.1 图的定义 330
8.1.2 图的术语 331
8.1.3 图的运算 334
8.1.4 图的抽象数据类型 336
8.2 图的存储与表示 337
8.2.1 图的邻接矩阵表示 337
8.2.2 图的邻接表表示 339
8.2.3 两种表示法的比较 342
8.3 图的遍历 342
8.3.1 欧拉路径与欧拉回路 343
8.3.2 哈密尔顿路径与哈密尔顿回路 345
8.3.3 广度优先遍历 346
8.3.4 深度优先遍历 349
8.4 最短路径问题 353
8.4.1 固定起点最短路问题 353
8.4.2 非固定起点最短路问题 355
8.4.3 最短路径的动态规划解法 358
8.4.4 旅游交通路线问题 364
8.5 最小生成树 372
8.5.1 最小生成树的定义 372
8.5.2 克鲁斯卡尔算法 373
8.5.3 普里姆算法 375
8.6 经典问题举例 379
8.6.1 文字游戏问题 380
8.6.2 道路修建问题 382
8.6.3 回家路线问题 385
8.6.4 水塘计算问题 387
8.6.5 棍子还原问题 389
8.7 本章小结 392
第9章 树形搜索结构 393
9.1 二叉搜索树 394
9.1.1 二叉搜索树的概念 394
9.1.2 二叉搜索树的操作 395
9.1.3 二叉搜索树的实现 397
9.1.4 二叉搜索树的分析 400
9.2 AVL树 403
9.2.1 AVL树的概念 404
9.2.2 AVL树的旋转 405
9.2.3 AVL树的实现 410
9.3 红黑树 418
9.3.1 红黑树的概念 418
9.3.2 红黑树的操作 421
9.3.3 红黑树的实现 428
9.4 Trie树 433
9.4.1 Trie树的概念 433
9.4.2 Trie树的表示 434
9.4.3 Trie树的实现 435
9.5 本章小结 439
第10章 集合与字典 441
10.1 集合论基础 442
10.1.1 集合的概念 442
10.1.2 集合的运算 444
10.2 集合的实现 445
10.2.1 位向量集合 445
10.2.2 链表集合 451
10.3 字典 460
10.3.1 字典的概念 461
10.3.2 搜索运算 463
10.4 散列 467
10.4.1 散列的概念 467
10.4.2 散列函数 469
10.4.3 处理散列冲突 471
10.4.4 散列的应用 475
10.5 经典问题举例 476
10.5.1 拼写检查问题 476
10.5.2 无线网络问题 485
10.5.3 第K个数问题 488
10.6 STL中的set 490
10.7 本章小结 493
第11章 排序 495
11.1 排序问题概述 496
11.1.1 基本概念和定义 496
11.1.2 排序算法的分类 497
11.1.3 排序算法分析与选择 497
11.2 插入排序 498
11.2.1 直接插入排序 498
11.2.2 二分法插入排序 501
11.2.3 希尔排序 503
11.3 选择排序 506
11.3.1 直接选择排序 506
11.3.2 堆排序 508
11.4 交换排序 512
11.4.1 冒泡法排序 512
11.4.2 Shaker排序 514
11.4.3 快速排序 517
11.5 归并排序 522
11.6 计数排序 526
11.7 本章小结 531
参考文献 532
· · · · · · (收起)