7.5 堆栈应用：后缀表达式计算器 38 1
目 录 1
7.2.7出栈 36 1
1.1软件的生命周期 1
第1章软件工程基本原理和C++类 1
1.2软件开发阶段 2
1.2.1 分析阶段 2
1.2.2设计阶段 2
1.2.3实现阶段 3
1.2.4测试和调试 5
1.3 算法分析：大O表示法 6
1.4类 12
1.4.1统一建模语言图 15
1.4.2变量（对象）的声明 15
1.4.3访问类的成员 16
1.4.4类的内置运算 17
1.4.5赋值运算符和类 17
1.4.6类的作用域 17
1.4.7函数和类 18
1.4.8引用参数和类对象（变量） 18
1.4.9成员函数的实现 19
1.4.10构造函数 23
1.4.1 1调用构造函数 26
1.4.12构造函数和默认参数 26
1.4.13析构函数 27
1.4.14结构 27
1.5数据抽象、类和抽象数据类型 27
1.6编程示例：糖果机 36
1.6.2收银机 36
1.6.1 问题分析和算法设计 36
1.6.3控制装置 38
1.6.4主程序 40
1.8快速回顾 45
1.7标识类、对象和操作 45
1.9练习题 47
1.10编程练习 51
第2章 面向对象的设计方法和C++ 54
2.1 继承 54
2.1.1重新定义基类的成员函数 57
2.1.2派生类与基类的构造函数 58
2.1.3派生类的头文件 64
2.1.4头文件的多重包含 64
2.1.6三种继承方式：公有继承，保护继承或私有继承 66
2.1.5类的保护成员 66
2.2聚合 67
2.3 多态：运算符和函数重载 71
2.4运算符重载 71
2.4.1为什么要重载运算符 71
2.4.2运算符重载 72
2.4.5 this指针 73
2.4.4重载运算符的限制 73
2.4.3运算符函数的语法 73
2.4.6类的友元函数 77
2.4.7定义友元函数 77
2.4.8运算符函数的两种形式：成员函数和非成员函数 80
2.5重载二元运算符 81
2.5.1 重载二元运算符（算术运算符和关系运算符）为成员函数 81
2.5.2重载二元运算符（算术运算符和关系运算符）为非成员函数 83
2.5.4重载输出运算符（＜＜） 84
2.5.3重载输出（＜＜）和输入（＞＞）运算符 84
2.5.5重载输入运算符（＞＞） 85
2.5.6重载运算符形式的选择：成员函数和非成员函数 87
2.6编程示例：复数 87
2.7 函数重载 92
2.8模板 92
2.8.1函数模板 93
2.8.2类模板 95
2.8.3头文件和类模板的实现文件 97
2.9快速回顾 97
2.1 0练习题 99
2.11 编程练习 109
第3章指针和基于数组的表 113
3.1指针数据类型和指针变量 113
3.1.1声明指针变量 113
3.1.2取地址运算符（ ） 114
3.1.3取值运算符（*） 115
3.1.4类、结构和指针变量 120
3.1.6动态变量 123
3.1.5初始化指针变量 123
3.1.7指针变量的运算 125
3.2 动态数组 126
3.2.1 函数和指针 128
3.2.2指针和函数返回值 128
3.3 浅复制、深复制与指针 129
3.4类和指针：一些特例 131
3.4.1析构函数 132
3.4.2赋值运算符 133
3.4.3重载赋值运算符 135
3.4.4复制构造函数 138
3.5 重载数组索引（下标）运算符（［］） 144
3.6编程示例：newString 145
3.7基于数组的表 151
3.7.1复制构造函数 160
3.7.2重载赋值运算符 161
3.7.3搜索 161
3.7.4插入 163
3.7.5删除 163
3.7.6各种表操作的时间复杂度 164
3.8编程示例：多项式的运算 168
3.9快速回顾 175
3.10练习题 177
3.11 编程练习 182
第4章标准模板类库 185
4.1 STL的组成部分 185
4.2顺序容器：向量容器 186
4.1.2顺序容器 186
4.1.1容器类型 186
4.2.1 声明vector对象 187
4.2.2为向量容器声明一个迭代器 189
4.2.3 容器以及begin和end函数 190
4.2.4对所有容器通用的成员函数 193
4.2.5顺序容器公共的成员函数 194
4.2.6 copy算法 194
4.2.7 ostream迭代器和copy函数 196
4.3顺序容器：双端队列 198
4.4迭代器 201
4.4.1迭代器的类型 202
4.4.3输出迭代器 202
4.4.2输入迭代器 202
4.4.5双向迭代器 203
4.4.6随机访问迭代器 203
4.4.4前向迭代器 203
4.4.7流迭代器 205
4.5编程示例：成绩报告单 206
4.5.1 问题分析与算法设计 208
4.5.2 主程序 219
4.5.3程序清单 221
4.6快速回顾 226
4.7练习题 227
4.8 编程练习 231
5.1 链表 234
第5章链表 234
5.2链表的属性 236
5.3项的插入和删除 239
5.3.1 插入 239
5.3.2删除 241
5.4构建链表 243
5.4.1 正向构建链表 243
5.4.2反向构建链表 247
5.5 ADT链表 248
5.5.1默认构造函数 251
5.5.3初始化表 252
5.5.2销毁表 252
5.5.4重载输出运算符 253
5.5.5表的长度 253
5.5.6检索第一个节点的数据 253
5.5.7检索最后一个节点的数据 254
5.5.8搜索表 254
5.5.9在表头插入节点 255
5.5.11删除节点 256
5.5.10在表尾插入节点 256
5.5.12复制表 261
5.5.13析构函数 262
5.5.14复制构造函数 262
5.5.15重载赋值运算符 263
5.6有序链表 264
5.6.1 搜索表 265
5.6.2插入节点 266
5.6.3删除节点 270
5.6.4有序链表的头文件 271
5.7双向链表 273
5.7.1默认构造函数 276
5.7.2 isEmptyList 276
5.7.4 初始化表 277
5.7.5表的长度 277
5.7.3 销毁表 277
5.7.7反向打印表 278
5.7.6重载输出运算符 278
5.7.8 搜索表 279
5.7.9第一个和最后一个元素 279
5.7.10插入节点 280
5.7.11删除节点 282
5.8 STL顺序容器：list 284
5.9带有头节点和尾节点的链表 289
5.10循环链表 290
5.11 编程示例：Video Store 291
5.12 快速回顾 309
5.13练习题 310
5.14编程练习 315
第6章递归 319
6.1递归的定义 319
6.1.1直接递归和间接递归 321
6.1.2无穷递归 321
6.2递归法解决问题 322
6.3递归还是迭代 337
6.4递归和回溯：n－皇后问题 338
6.4.1回溯 338
6.4.2回溯和4皇后问题 340
6.4.3 8皇后问题 341
6.5 快速回顾 345
6.6练习题 346
6.7 编程练习 348
第7章堆栈 353
7.1 堆栈 353
7.2使用数组实现堆栈 355
7.2.1初始化堆栈 358
7.2.5入栈 359
7.2.4满堆栈 359
7.2.3空堆栈 359
7.2.2销毁堆栈 359
7.2.6返回栈顶元素 361
7.2.8复制堆栈 362
7.2.9构造函数和析构函数 363
7.2.10复制构造函数 364
7.2.1 1 重载赋值运算符（＝） 364
7.2.12堆栈的头文件 365
7.3 编程示例：求最高GPA 366
7.4堆栈的链表实现 370
7.4.1默认构造函数 372
7.4.3初始化堆栈 373
7.4.2销毁堆栈 373
7.4.4入栈 374
7.4.5返回栈顶元素 377
7.4.6出栈 377
7.4.7 由类linkedListType派生而来的堆栈 379
7.5.1 主算法 385
7.5.2完整的程序清单 387
7.6消除递归：反向打印一个链表的非递归算法 391
7.7 STL堆栈类（堆栈容器适配器） 396
7.8快速回顾 398
7.9练习题 398
7.10编程练习 402
第8章队列 404
8.1 队列 404
8.1.1 队列操作 404
8.1.2队列的数组实现 405
8.2队列的链式实现 416
8.3 从类linkedListType派生而来的队列 420
8.4 STL类queue（队列容器适配器） 423
8.5优先级队列 425
8.6队列的应用：模拟 426
8.6.1设计队列系统 427
8.6.2客户 427
8.6.3 服务器 430
8.6.4服务器表 433
8.6.5等待客户的队列 438
8.6.6 主程序 440
8.7快速回顾 447
8.8练习题 447
8.9编程练习 451
第9章搜索算法 453
9.1 搜索算法 453
9.1.1 顺序搜索 456
9.1.2顺序搜索算法分析 457
9.1.3有序表 458
9.1.4折半搜索 459
9.1.5折半搜索算法的性能 462
9.1.6将数据项插入到一个有序表 463
9.2基于比较的搜索算法的下限 465
9.3 散列算法 466
9.3.1 散列函数：示例 467
9.3.2冲突解决 467
9.3.3 冲突解决：开型寻址法 467
9.3.4二次探测 469
9.3.5 删除：开型寻址法 472
9.3.6散列法：使用二次探测来实现 473
9.3.7冲突解决：链地址法（开散列方法） 476
9.3.8散列法性能分析 477
9.4快速回顾 478
9.5 练习题 480
9.6编程练习 481
第10章排序算法 484
10.1 排序算法 484
10.2选择排序：基于数组的表 484
10.3插入排序：基于数组的表 490
10.4插入排序：基于链表的表 495
10.5基于比较的排序算法的下限 499
10.6快速排序：基于数组的表 500
10.7归并排序：基于链表的表 505
10.7.1划分 507
10.7.2归并 509
10.7.3分析：归并排序 512
10.8堆排序：基于数组的表 512
10.8.1 构建堆 513
10.8.2分析：堆排序 520
10.9再论优先级队列 520
10.9.1在优先级队列中插入一个元素 521
10.9.2从优先级队列删除一个元素 521
10.10编程示例：选举结果 521
10.10.1 问题分析和算法设计 522
10.10.2主程序 528
10.10.3对姓名排序 530
10.10.4处理投票数据 532
10.10.5计算选票数的总和 534
10.10.6打印标题和结果 534
10.11 快速回顾 538
1 0.1 2 练习题 539
10.13编程练习 540
第1 1章二叉树 543
11.1 二叉树 543
11.2二叉树的遍历 549
11.2.1 中序遍历 549
11.2.2前序遍历 549
11.2.3 后序遍历 549
11.2.4二叉树的实现 552
11.3 二叉搜索树 560
11.3.1 search函数 562
11.3.2 Insert函数 564
11.3.3 Delete函数 565
11.4二叉搜索树分析 572
11.5 二叉树的非递归遍历算法 573
11.5.1 非递归中序遍历 573
11.5.2非递归前序遍历 574
11.5.3非递归后序遍历 576
11.6 二叉树遍历和作为参数的函数 577
11.7 AVL（平衡）树 580
11.7.1 AVL树的插入操作 582
11.7.2 AVL树的旋转 587
11.7.3 AVL树的删除操作 598
11.7.4 AVL树的性能分析 599
11.8 编程示例：Video Store 600
11.9快速回顾 608
11.10练习题 609
11.1 1编程练习 612
第12章图 614
12.1 初识图 614
12.2 图的定义和符号 615
12.3 图的表示方法 617
12.3.1邻接矩阵 617
12.3.2邻接表 618
12.4 图的操作 619
12.6 图的ADT定义 620
12.5 回顾模板 620
12.7 图的遍历 624
12.7.1深度优先遍历 624
12.7.2 广度优先遍历 626
12.8最短路径算法 628
12.9最小生成树 634
12.10拓扑排序 641
12.11快速回顾 647
12.12练习题 648
12.1 3 编程练习 650
13.1 pair类 652
第1 3章标准模板库（STL）Ⅱ 652
13.1.1 比较pair类型的对象 654
13.1.2 pair类型和make pair函数 654
13.2关联容器 656
13.2.1关联容器：集合和多重集合 657
13.2.2关联容器：映射和多重映射 661
13.3 容器、相关头文件和迭代器支持 666
13.4算法 666
13.5 STL算法分类 667
13.5.1非修改算法 667
13.5.2修改算法 667
13.5.4堆算法 668
13.5.3数值算法 668
13.5.5函数对象 669
13.5.6谓词 674
13.5.7插入迭代器 674
1 3.6 STL算法 676
13.6.1 fill和filn函数 676
13.6.2 generate和generate_n函数 678
13.6.3 find、find if、find end和find first of函数 679
13.6.4 remove、remove_if、remove_copy和remove_copy_if函数 681
13.6.5 replace、replace_if、replace_copy和replace_copy_if函数 685
13.6.6 swap、iter_swap和swap_ranges函数 687
13.6.7 search、search n、sort和binary search函数 690
13.6.8 adjacent_find、merge和inplace_merge函数 694
13.6.9 reverse、reverse_copy、rotate、rotate_copy函数 696
13.6.10 count、count if、max、max element、min、min element和random shuffle函数 699
13.6.1l for each和transform函数 702
13.6.12 includes、set_intersection、set_union、set_difference和set_symmetric_difference函数 705
13.6.13 accumulate、adjacent_difference、inner_product和partial_sum函数 713
13.7快速回顾 718
13.8 练习题 720
13.9编程练习 722
附录A保留字 724
附录B运算符优先级 725
附录C字符集 726
附录D 运算符重载 728
E.1 头文件cassert 729
E.2头文件cctype 729
附录E头文件 729
E.3 头文件cmath 730
E.4头文件cstddef 731
E.5 头文件cstring 731
E.6头文件string 732
附录F其他C++主题 734
F.1继承、指针和虚函数 734
F.2类和虚析构函数 740
F.3取地址运算符和类 740
G.1数据类型 744
附录G针对JAVA程序员的C++介绍 744
G.2名称常量、变量以及赋值语句 745
G.3预处理指令 746
G.4 C++程序 746
G.5输入和输出 747
G.6控制结构 756
G.7命名空间 757
G.8函数及其参数 761
G.9数组 765
附录H参考文献 768
附录I精选习题答案 769