第1章 数据结构入门 1
1.1 本书主要内容 1
1.2 数据结构的抽象形式 4
1.3 作为类的ADT 6
1.3.1 C++类 6
1.3.2 private和public部分 7
1.3.3 封装和信息隐藏 7
1.3.4 time24类 7
1.4 实现C++类 10
1.5 明和使用对象 14
1.6 使用嵌入码实现类 16
1.7 应用程序编程接口(API) 18
1.7.1 随机数 19
1.7.2 randomNumber API 19
1.7.3 应用程序：掷骰子游戏 21
1.8 字符串 23
1.8.1 字符串类 24
1.8.2 附加字符串函数和操作 25
1.9 本章小结 29
1.10 本章使用的类和库 30
1.11 复习题 31
1.12 书面作业 35
1.13 上机题 41
1.14 项目设计 44
第2章 对象设计技术 46
2.1 软件设计 47
2.1.1 需求和问题分析 48
2.1.2 程序设计 48
2.1.3 设计日历类 49
2.1.4 程序实现 52
2.1.5 实现日历类 52
2.1.6 程序测试与调试 54
2.1.7 程序维护 57
2.2 处理运行时错误 57
2.2.1 终止程序 57
2.2.2 设置标志 58
2.2.3 C++异常 59
2.3 对象复合 62
2.3.1 timeCard类 63
2.3.2 实现timeCard类 64
2.4 运算符重载 68
2.4.1 运算符函数 71
2.4.2 自由函数的运算符重载 72
2.4.3 友元函数的运算符重载 72
2.4.4 重载数据流I/O运算符 75
2.4.5 成员函数重载 78
2.5 本章小结 81
2.6 本章使用的类和库 82
2.7 复习题 82
2.8 书面作业 86
2.9 上机题 90
2.10 项目设计 91
第3章 算法概述 96
3.1 选择排序 97
3.2 简单查找算法 101
3.2.1 顺序查找 101
3.2.2 二分查找 103
3.3 算法分析 108
3.3.1 系统/内存性能标准 108
3.3.2 算法性能标准：时间复杂度分析 108
3.3.3 大O符号 111
3.3.4 常见数量级 112
3.4 分析查找算法 114
3.4.1 二分查找时间复杂度 114
3.4.2 查找算法比较 115
3.5 算法的通用性 118
3.5.1 模板语法 119
3.5.2 运行时模板扩展 120
3.5.3 基于模板的查找函数 122
3.6 递归的概念 123
3.6.1 实现递归函数 125
3.6.2 递归的工作方式 127
3.6.3 应用：多进制输出 129
3.7 用递归解决问题 131
3.7.1 汉诺塔 131
3.7.2 数论：最大公约数 134
3.7.3 gcd的应用：有理数 136
3.7.4 计算递归式 139
3.8 本章小结 142
3.9 本章使用的类和库 143
3.10 复习题 143
3.11 书面作业 147
3.12 上机题 153
3.13 项目设计 156
第4章 向量容器 157
4.1 STL容器类概述 158
4.2 模板类 161
4.2.1 构造模板类 161
4.2.2 声明模板类对象 163
4.3 向量类 164
4.3.1 向量容器入门 166
4.3.2 向量API 171
4.4 向量应用 173
4.4.1 合并向量 173
4.4.2 插入排序 173
4.5 本章小结 177
4.6 本章使用的类和库 178
4.7 复习题 178
4.8 书面作业 181
4.9 上机题 186
4.10 项目设计 187
第5章 指针和动态内存 188
5.1 C++指针 189
5.1.1 声明指针变量 190
5.1.2 指针赋值 190
5.1.3 用指针访问数据 191
5.1.4 数组和指针 192
5.1.5 指针和类类型 194
5.2 动态内存 196
5.2.1 内存分配运算符new 196
5.2.2 动态数组分配 198
5.2.3 内存释放运算符delete 199
5.3 使用动态内存的类 200
5.3.1 dynamicClass类 200
5.3.2 析构函数 202
5.4 赋值和初始化 204
5.4.1 赋值问题 205
5.4.2 重载的赋值运算符 206
5.4.3 指针this 207
5.4.4 初始化问题 207
5.4.5 创建复制构造函数 208
5.5 miniVector类 211
5.5.1 miniVector类的设计 212
5.5.2 分配更多的容量 214
5.5.3 miniVector的构造函数、析构函数和赋值 215
5.5.4 从miniVector对象中增加和删除元素 217
5.5.5 重载下标运算符 220
5.6 矩阵类 222
5.6.1 描述矩阵容器 223
5.6.2 实现矩阵函数 226
5.7 本章小结 227
5.8 本章中的类和库 227
5.9 复习题 228
5.10 书面作业 231
5.11 上机题 238
5.12 项目设计 239
第6章 表容器和迭代器 241
6.1 表容器 242
6.1.1 表ADT 243
6.1.2 表API 245
6.1.3 应用：表回文 246
6.2 迭代器 248
6.2.1 迭代器的概念 248
6.2.2 常量迭代器 251
6.2.3 顺序查找表 252
6.2.4 应用：词的出现频率 255
6.3 表插入和删除操作 258
6.3.1 有序表 260
6.3.2 删除重复项 262
6.3.3 合并两个表 264
6.4 实例研究：毕业生表 265
6.4.1 问题分析 265
6.4.2 程序设计 265
6.4.3 程序实现 266
6.5 本章小结 269
6.6 本章使用的类和库 270
6.7 复习题 270
6.8 书面作业 273
6.9 上机题 276
6.10 项目设计 279
第7章 栈 281
7.1 栈ADT 282
7.1.1 多进制输出 285
7.1.2 分解栈元素 288
7.2 递归代码和运行栈 291
7.3 栈的实现 294
7.3.1 miniStack类的实现 296
7.3.2 STL stack类的实现(选学) 297
7.4 后缀表达式 299
7.4.1 后缀计算 300
7.4.2 postfixEval类 301
7.5 实例研究：中缀表达式计算 307
7.5.1 中缀表达式的特征 307
7.5.2 中缀到后缀的转换：算法设计 308
7.5.3 中缀转换为后缀：对象设计 312
7.5.4 infix2Postfix类的实现 314
7.6 本章小结 318
7.7 本章使用的类 319
7.8 复习题 320
7.9 书面作业 323
7.10 上机题 328
7.11 项目设计 328
第8章 队列和优先级队列 330
8.1 队列 ADT 331
8.2 基数排序 335
8.3 实现miniQueue类 339
8.4 实例研究：时间驱动的模拟 343
8.4.1 模拟程序设计 343
8.4.2 模拟程序的具体实现 344
8.5 用数组实现队列 349
8.5.1 设计有界队列 351
8.5.2 有界队列的实现 353
8.6 优先级队列 354
8.6.1 优先级队列ADT 355
8.6.2 优先级队列排序 357
8.6.3 公司内的支持服务 358
8.7 本章小结 362
8.8 本章使用的类和库 363
8.9 复习题 363
8.10 书面作业 367
8.11 上机题 371
8.12 项目设计 373
第9章 链表 376
9.1 链表结点 378
9.1.1 链表结点类 378
9.1.2 添加和删除结点 381
9.2 建立链表 382
9.2.1 定义单向链表 382
9.2.2 在链表表头插入结点 384
9.2.3 在链表表头删除结点 385
9.2.4 删除特定的结点 386
9.3 处理链表表尾 389
9.4 用链表实现队列 393
9.4.1 linkedQueue类 393
9.4.2 实现linkedQueue类 395
9.5 双向链表 398
9.5.1 dnode对象 399
9.5.2 双向循环链表 401
9.6 更新双向链表 403
9.6.1 insert()函数 404
9.6.2 erase()函数 405
9.7 约瑟夫问题 409
9.8 miniList类 411
9.8.1 miniList类的私有成员 412
9.8.2 miniList类的构造函数和析构函数 413
9.8.3 处理表两端元素的函数 414
9.8.4 miniList的迭代器 415
9.8.5 miniList类成员函数begin()和end() 417
9.8.6 miniList类的通用插入函数 418
9.9 选择顺序容器 419
9.10 本章小结 419
9.11 本章使用的类和库 421
9.12 复习题 421
9.13 书面作业 427
9.14 上机题 430
9.15 项目设计 431
第10章 二叉树 434
10.1 树结构 435
10.1.1 术语 436
10.1.2 二叉树 437
10.2 二叉树结点 440
10.3 二叉树遍历算法 443
10.3.1 递归的树遍历 443
10.3.2 迭代层次遍历 446
10.4 使用树遍历算法 450
10.4.1 叶结点计数 450
10.4.2 计算树的深度 450
10.4.3 复制二叉树 453
10.4.4 删除树结点 456
10.4.5 显示二叉树 457
10.5 二叉搜索树 458
10.5.1 二叉搜索树概述 459
10.5.2 创建二叉搜索树 459
10.5.3 二叉搜索树中的数据查找 460
10.5.4 二叉搜索树的删除 461
10.5.5 二叉搜索树类 462
10.5.6 访问和更新操作 463
10.6 二叉搜索树的应用 467
10.6.1 应用：消除重复项 467
10.6.2 应用：录像带商店 469
10.7 stree类的实现 474
10.7.1 stree类数据成员 475
10.7.2 构造函数、析构函数和赋值运算符 475
10.7.3 更新操作 476
10.7.4 二叉搜索树的算法复杂度 483
10.8 stree迭代器(选学) 483
10.9 本章小结 488
10.10 本章使用的类和库 489
10.11 复习题 489
10.12 书面作业 494
10.13 上机题 497
10.14 项目设计 499
第11章 关联容器 503
11.1 关联容器概述 503
11.1.1 关联容器的种类 504
11.1.2 STL关联容器 506
11.1.3 实现关联容器 506
11.2 集合 507
11.2.1 使用迭代器显示容器元素 508
11.2.2 集合的访问和更新函数 508
11.2.3 简单的拼写检查程序 511
11.2.4 应用：埃拉托斯特尼筛法 514
11.2.5 集合运算 517
11.2.6 应用：更新计算机账号 520
11.3 映射 522
11.3.1 map类接口 523
11.3.2 映射的操作函数 525
11.3.3 映射的下标运算符 526
11.3.4 实例学习：单词统计 529
11.4 多重集 534
11.5 实现集合和映射 538
11.5.1 实现miniSet的操作函数 539
11.5.2 miniMap类 540
11.5.3 实现miniMap类 542
11.5.4 miniMap的下标运算符 543
11.6 本章小结 543
11.7 本章使用的类和库 544
11.8 复习题 545
11.9 书面作业 548
11.10 上机题 551
11.11 项目设计 552
第12章 高级关联结构 555
12.1 哈希法 557
12.2 设计哈希函数 559
12.2.1 函数对象 559
12.2.2 函数对象举例 561
12.2.3 整型哈希函数 563
12.2.4 字符串哈希函数 564
12.2.5 定制哈希函数 565
12.3 哈希表 566
12.3.1 线性探测开放寻址法 566
12.3.2 独立表链地址法 568
12.4 hash类 569
12.4.1 应用：使用哈希表 571
12.4.2 hash类的实现 574
12.4.3 实现哈希迭代器 577
12.4.4 无序关联容器 580
12.5 哈希表的性能 581
12.6 2-3-4树 586
12.6.1 2-3-4树的插入算法 588
12.6.2 2-3-4树操作函数的时间复杂度 591
12.7 红黑树 592
12.7.1 红黑树的属性 593
12.7.2 向红黑树中添加结点 595
12.7.3 构造红黑树 599
12.7.4 查找算法的时间复杂度(选学) 601
12.7.5 从红黑树中删除结点 602
12.8 rbtree类 603
12.8.1 rbtree类的私有部分 606
12.8.2 拆分4-结点 606
12.8.3 insert()操作函数 608
12.9 本章小结 609
12.10 本章用到的类和库 610
12.11 复习题 610
12.12 书面作业 615
12.13 上机题 621
12.14 项目设计 623
第13章 继承和抽象类 625
13.1 C++中的继承 626
13.1.1 明员工层次关系 628
13.1.2 派生类的构造函数 631
13.1.3 实现成员函数 632
13.2 图形层次 635
13.2.1 circleShape类 637
13.2.2 其他图形类和文本类 639
13.2.3 polyShape类的实现 641
13.3 图形系统 644
13.4 安全向量 647
13.5 有序表 649
13.6 多态属性和虚函数 651
13.6.1 动态绑定 653
13.6.2 应用：用多态性机制编写支付员工薪金的程序 655
13.6.3 C++的多态实现 657
13.6.4 虚函数和析构函数 659
13.7 抽象类 661
13.7.1 抽象类接口 662
13.7.2 栈接口 662
13.8 本章小结 663
13.9 本章使用的类和库 664
13.10 复习题 664
13.11 书面作业 669
13.12 上机题 675
13.13 项目设计 677
第14章 堆、2进制文件和位组 679
14.1 基于数组的二叉树 680
14.2 堆 681
14.2.1 堆的插入操作 682
14.2.2 从堆中删除元素 684
14.2.3 堆排序 688
14.2.4 向量堆化 691
14.3 优先级队列的实现 693
14.4 2进制文件 696
14.4.1 文件结构 696
14.4.2 直接读写文件 697
14.4.3 读写2 进制文件 698
14.4.4 应用：银行账户记录 698
14.5 位组 702
14.5.1 bitVector类 703
14.5.2 实现bitVector类 706
14.6 实例研究：霍夫曼压缩 709
14.6.1 创建霍夫曼树 712
14.6.2 霍夫曼压缩的实现 714
14.6.3 霍夫曼解压缩 720
14.7 本章小结 722
14.8 本章使用的类和库 724
14.9 复习题 724
14.10 书面作业 728
14.11 上机题 735
14.12 项目设计 738
第15章 递归算法 740
15.1 分而治之算法 741
15.1.1 创建标尺 741
15.1.2 并排序 743
15.1.3 快速排序 750
15.1.4 排序算法的比较 758
15.1.5 应用：搜索第k大的元素 760
15.2 组合学 762
15.2.1 查找所有子集 763
15.2.2 排列 766
15.3 动态编程 769
15.3.1 自顶向下的动态编程 770
15.3.2 应用：组合 772
15.3.3 自底向上动态编程 774
15.3.4 背包问题 775
15.4 回溯法：八皇后问题 782
15.4.1 问题分析 783
15.4.2 程序设计 785
15.4.3 显示棋盘 788
15.4.4 八皇后问题实例分析 789
15.5 本章小结 790
15.6 本章使用的类和库 791
15.7 复习题 792
15.8 书面作业 797
15.9 上机题 800
15.10 项目设计 804
第16章 图 807
16.1 图论术语 808
16.1.1 有向图 809
16.1.2 加权图 810
16.2 图类 810
16.2.1 图的API清单 810
16.2.2 图的表示 815
16.3 图类设计 816
16.3.1 顶点信息表示 817
16.3.2 顶点映射和Vinfo表 818
16.3.3 图类声明 821
16.3.4 图类的实现 822
16.4 图的遍历算法 826
16.4.1 广度优先搜索算法 827
16.4.2 深度优先访问算法 830
16.4.3 深度优先搜索 834
16.5 图遍历的应用 835
16.5.1 无环图 835
16.5.2 拓扑排序 838
16.5.3 强连通分量 841
16.6 图的最小化算法 845
16.6.1 最短路径算法 845
16.6.2 Dijkstra最小路径算法 849
16.6.3 最小生成树 855
16.7 本章小结 862
16.8 本章使用的类和库 862
16.9 复习题 863
16.10 书面作业 865
16.11 上机题 873
16.12 项目设计 874