第1篇 C++语言与面向对象程序设计 1
第1章 C++简介 1
1．1 C++历史 1
1．2 C++语言特点 1
1．3 本篇的组织结构 2
第2章 熟悉C++ 3
2．1 环境 3
2．2 第一个示例程序 3
2．2．1 注释 3
2．2．2 # include语句与预处理 4
2．2．3 main函数 5
2．2．4 从main中返回 5
2．3 第二个示例程序 6
2．2．5 终端输出输入 6
2．3．1 数据类型 7
2．3．2 常量 8
2．3．3 变量 10
2．3．4 表达式与操作符 12
2．3．5 类型转换 17
2．3．6 语句 19
【习题】 25
第3章 进一步熟悉C++ 27
3．1 更多的变量类型 27
3．1．1 指针类型 27
3．1．2 引用类型 30
3．1．3 枚举类型 31
3．1．4 数组类型 32
3．1．5 用typedef定义自己的变量类型 35
3．2 函数 36
3．2．1 函数的参数与返回值 37
3．2．2 内联函数 40
3．2．3 递归函数 41
3．2．4 作用域 41
3．2．5 函数重载 44
3．2．6 函数指针 45
3．3 类与对象 46
3．3．1 类与对象 47
3．3．2 成员变量和成员函数 47
3．3．3 访问权限 48
3．3．4 构造函数与析构函数 51
3．3．5 常量成员变量和函数 58
3．3．6 静态成员变量和函数 58
3．3．7 友元 59
3．3．8 this指针 60
3．4 结构、联合和位域 61
3．4．1 结构 61
3．4．2 联合 62
3．4．3 位域 62
3．4．4 指针与结构 63
【习题】 63
第4章 类与继承 66
4．1 单继承 66
4．1．1 成员访问控制方式 67
4．1．2 一个继承的示例 68
4．1．3 构造函数和析构函数 69
4．1．4 虚函数 70
4．1．5 抽象类与纯虚函数 73
4．1．6 虚析构函数 74
4．2 多继承 75
4．2．1 多继承中的构造函数与析构函数 75
4．2．2 歧义性 77
4．2．3 虚基类 77
4．2．4 多继承的应用 78
【习题】 79
第5章 C++高级应用 80
5．1 模板 80
5．1．1 函数模板 80
5．1．2 类模板 81
5．1．3 模板的应用 82
5．2 I/O流 83
5．2．1 标准I/O流 83
5．2．2 文件I/O 88
5．2．3 字符串I/O流 89
5．2．4 重载操作符 << 和 >> 92
5．3 堆管理 93
5．3．1 动态空间申请与释放 93
5．3．2 重载new和delete 94
5．3．3 异常处理 96
5．4 操作符重载 96
5．4．1 双目运算符重载 97
5．4．2 单目运算符重载 99
5．4．3 引用在运算符重载中的应用 99
5．5 异常 100
5．5．1 异常处理 101
5．5．2 异常发生之后 102
5．5．4 处理未捕捉到的异常 104
5．5．3 嵌套异常 104
【习题】 105
第2篇 数据结构 107
第6章 基本概念 107
6．1 什么是数据结构 107
6．2 抽象数据类型及面向对象概念 108
6．2．1 数据类型 108
6．2．2 抽象与抽象数据类型 108
6．3 数据结构的抽象层次 110
6．4 算法定义 112
6．5 性能分析与度量 112
6．5．1 评价算法的标准 113
6．5．2 算法效率的后期测量 113
6．5．3 算法的事前估计 114
6．5．4 大O表示法 115
【习题】 116
第7章 数组 118
7．1 数组的概念 118
7．1．1 数组的概念与数组抽象数据类型 118
7．1．2 数组元素的定位 121
7．2 顺序表 122
7．2．1 顺序表的概念和定义 122
7．2．2 顺序表的顺序搜索 123
7．2．3 顺序表的插入和删除 124
7．3 稀疏矩阵 125
7．3．1 稀疏矩阵的概念 125
7．3．2 稀疏矩阵的压缩存储表示 125
7．4 字符串 126
7．4．1 字符串的概念及其抽象数据类型 126
7．4．2 字符串的运算 127
7．4．3 字符串的模式匹配 128
【习题】 129
第8章 链表 132
8．1 单链表 132
8．1．1 单链表的概念 132
8．1．2 单链表的类定义 133
8．1．3 单链表的插入与删除 134
8．1．4 带表头结点的单链表 135
8．1．5 单链表的类模板 136
8．1．6 单链表的游标类 138
8．1．7 静态链表 140
8．2 循环链表 141
8．3．2 带表头结点的双向循环链表 142
8．3．1 双向链表的概念 142
8．3 双向链表 142
8．3．3 双向循环链表的搜索、插入和删除算法 143
8．4 稀疏矩阵 145
【习题】 146
第9章 栈和队列 148
9．1 栈 148
9．1．1 栈的定义 148
9．1．2 栈的顺序方式实现（顺序栈） 148
9．1．3 栈的链接方式实现（链式栈） 150
9．2 队列 151
9．2．1 队列的抽象数据类型 151
9．2．2 队列的数组表示（循环队列） 152
9．2．3 队列的链接存储表示（链式队列） 154
9．3．1 优先级队列的定义 156
9．3 优先级队列 156
9．3．2 优先级队列的存储表示和实现 157
【习题】 158
第10章 递归 160
10．1 递归的概念 160
10．2 递归过程与递归工作栈 163
10．3 广义表 166
10．3．1 广义表的概念 166
10．3．2 广义表的表示及操作 168
10．3．3 广义表存储结构的实现 169
10．3．4 广义表的访问算法 171
10．3．5 广义表的递归算法 172
【习题】 177
11．1．1 树的定义与术语 179
11．1 树和森林的概念 179
第11章 树与森林 179
11．1．2 树的抽象数据类型 180
11．2 二叉树 181
11．2．1 二叉树的定义与性质 181
11．2．2 二叉树的类定义 182
11．3 二叉树的表示 182
11．3．1 数组表示 182
11．3．2 链接表示 183
11．4 二叉树遍历 187
11．4．1 遍历二叉树的递归算法 187
11．4．2 二叉树遍历的游标类 189
11．5 线索化二叉树 193
11．5．1 线索 193
11．5．2 中序线索化二叉树 193
11．5．3 前序与后序的线索化二叉树 196
11．6 堆 197
11．6．1 堆的定义 198
11．6．2 堆的建立 199
11．6．3 堆的插入与删除 200
11．7 树与森林 202
11．7．1 树的存储表示 202
11．7．2 森林与二叉树的转换 206
11．7．3 树的遍历 207
11．7．4 森林的遍历 208
11．8 二叉树的计数 209
11．9 霍夫曼树 211
11．9．1 路径长度 211
11．9．2 霍夫曼树 212
11．9．3 霍夫曼编码 214
【习题】 215
第12章 集合与搜索 218
12．1 集合及其表示 218
12．1．1 集合基本概念 218
12．1．2 以集合为基础的抽象数据类型 218
12．1．3 用位向量实现集合抽象数据类型 219
12．1．4 用有序链表实现集合的抽象数据类型 220
12．2 等价类和并查集 223
12．2．1 等价关系与等价类 223
12．4 二叉搜索树 223
12．2．2 并查集 224
12．3 静态搜索表 227
12．3．1 搜索的概念 227
12．3．2 静态搜索结构 227
12．3．3 顺序搜索 229
12．3．4 基于有序顺序表的折半搜索 230
12．4．1 二叉搜索树的定义 233
12．4．2 二叉搜索树上的搜索 234
12．4．3 二叉搜索树的插入 235
12．4．4 二叉搜索树的删除 236
12．4．5 二叉搜索树的性能分析 238
【习题】 238
第13章 图 241
13．1 图的基本概念 241
13．2 图的存储表示 243
13．2．1 邻接矩阵 243
13．2．2 邻接表 245
13．2．3 邻接多重表 247
13．3 图的遍历与连通性 248
13．3．1 深度优先搜索 249
13．3．2 广度优先搜索 250
13．3．3 连通分量 251
13．3．4 重连通分量 252
13．4 最小生成树 253
13．4．1 克鲁斯卡尔算法 253
13．4．2 普里姆算法 255
13．5 最短路径 257
13．5．1 边上权值非负情形的单源最短路径问题 257
13．5．2 边上权值为任意值的单源最短路径问题 259
13．5．3 所有顶点之间的最短路径 262
13．6 活动网络 263
13．6．1 用顶点表示活动的网络（AOV网络） 263
13．6．2 用边表示活动的网络（AOE网络） 266
【习题】 270
第14章 排序 272
14．1 概述 272
14．2 插入排序 273
14．2．1 直接插入排序 273
14．2．2 折半插入排序 274
14．2．3 链表插入排序 275
14．2．4 希尔排序 277
14．3 交换排序 278
14．3．1 起泡排序 278
14．3．2 快速排序 279
14．4 选择排序 282
14．4．1 直接选择排序 282
14．4．2 锦标赛排序 283
14．4．3 堆排序 284
14．5 归并排序 286
14．5．1 归并 286
14．5．2 迭代的归并排序算法 287
14．5．3 递归的表归并排序 288
14．6 基数排序 290
14．6．1 多关键码排序 290
14．6．2 链式基数排序 291
14．7 磁盘排序 292
14．7．1 磁盘排序的基本过程 292
14．7．2 k路平衡归并 294
14．7．3 初始归并段的生成 296
14．7．4 最佳归并树 297
【习题】 299
15．1．1 线性索引 302
15．1 静态索引结构 302
第15章 索引与散列 302
15．1．2 倒排表 303
15．1．3 m路静态搜索树 305
15．2 AVL树 306
15．2．1 AVL树的定义 307
15．2．2 平衡化旋转 307
15．2．3 AVL树的插入和删除 310
15．2．4 AVL树的高度 313
15．3 B_树与B+树 313
15．3．1 动态的m路搜索树 313
15．3．2 B_树 315
15．3．3 B_树的插入 316
15．3．4 B_树的删除 317
15．3．5 B+树 319
15．4．1 词典的抽象数据类型 323
15．4 散列 323
15．4．2 散列表与散列方法 324
15．4．3 散列函数 324
15．4．4 处理溢出的闭散列方法 327
15．4．5处理溢出的开散列方法——链地址法 332
15．4．6 散列表分析 334
【习题】 335
第3篇 软件工程方法 338
第16章 软件工程基本概念 338
16．1 软件的概念、特点和分类 338
16．1．1 软件的概念与特点 338
16．1．2 软件的分类 340
16．2 软件的发展和软件危机 343
16．3．2 软件生存期 345
16．3 软件工程过程和软件生存期 345
16．3．1 软件工程过程 345
16．4 软件生存期模型 346
16．4．1 瀑布模型 346
16．4．2 进化模型 348
16．4．3 螺旋模型 348
16．4．4 喷泉模型 350
16．4．5 智能模型 350
16．5 软件工程的基本目标 351
16．5．1 软件工程的定义 351
16．5．2 软件工程项目的基本目标 351
【习题】 352
17．1 基于计算机的系统 354
第17章 系统分析 354
17．2 计算机系统工程 355
17．2．1 硬件和硬件工程 358
17．2．2 软件和软件工程 359
17．2．3 人与人类工程 361
17．2．4 数据库和数据库工程 362
17．3 系统需求识别 362
17．4 可行性研究 363
17．5 系统结构的模型化 365
17．5．1 结构图 365
17．5．2 系统结构的规格说明定义 367
17．5．3 系统定义与评审 368
【习题】 369
18．1 软件需求分析的任务和过程 370
18．1．1 软件需求分析的任务 370
第18章 面向过程的软件需求分析 370
18．1．2 需求分析的过程 371
18．1．3 软件需求分析的原则 374
18．2 符号表示 376
18．2．1 数据流图中的基本符号 376
18．2．2 数据流与加工之间的关系 377
18．2．3 分层的数据流图 377
18．3 构造数据流模型 378
18．3．1 构造数据流模型的步骤 378
18．3．2 数据流图画法 381
18．4 数据词典 384
18．4．1 词条描述 384
18．4．2 数据结构的描述 386
18．4．3 加工逻辑说明 387
18．5．1 状态迁移图 391
18．5 系统行为描述 391
18．5．2 时序图 392
18．5．3 Petri网 393
18．6 数据及数据库需求 396
18．6．1 有关数据库的基本概念 396
18．6．2 E-R方法和实体模型 397
18．6．3 数据结构的规范化 399
18．6．4 数据库分析的过程 401
【习题】 402
第19章 原型化方法 404
19．1 为什么使用原型化方法 404
19．2 软件原型的分类 404
19．3 快速原型开发模型 406
19．3．1 原型生存期 406
19．3．2 软件开发过程 409
19．4 原型开发技术 411
19．4．1 可执行规格说明 411
19．4．2 基于脚本的设计 412
19．4．3 自动程序设计 412
19．4．4 专用语言 413
19．4．5 简化假设 413
19．5 软件复用技术 413
19．5．1 软件复用概述 413
19．5．2 软件复用技术 414
【习题】 415
第20章 面向过程的软件设计方法 417
20．1 软件设计的目标和任务 417
20．1．1 软件设计在开发阶段中的重要性 417
20．1．2 软件设计任务 418
20．2 软件设计基础 420
20．2．1 自顶向下，逐步细化 420
20．2．2 软件结构 420
20．2．3 程序结构 421
20．2．4 数据结构 423
20．2．5 模块化 424
20．2．6 抽象化 424
20．2．7 信息隐蔽 425
20．3 模块设计 425
20．3．1 模块 425
20．3．2 模块独立性 426
20．3．3 耦合性 426
20．3．4 内聚性 428
20．4 数据设计及文件设计 429
20．4．1 数据设计的原则 430
20．4．2 在设计程序结构时数据结构的选择方法 431
20．4．3 文件设计 431
20．5 结构化设计方法 432
20．5．1 典型的系统结构形式 433
20．5．2 变换分析 435
20．5．3 事务分析 437
20．5．4 软件模块结构的改进 439
【习题】 442
第21章 用户界面设计 444
21．1 用户界面应具备的特性 444
21．1．1 可使用性 444
21．1．2 灵活性 444
21．2 用户界面设计的任务分析 445
21．1．3 复杂性和可靠性 445
21．2．1 用户特性分析 446
21．2．2 用户工作分析 446
21．2．3 用户模型和观点 447
21．3 用户界面任务和工作设计 447
21．3．1 任务分配 447
21．3．2 工作方式和工作设计 448
21．4 界面设计的基本类型 449
21．4．1 界面设计类型 449
21．4．2 菜单界面的设计 449
21．4．3 图像 450
21．4．4 对话 451
21．4．5 问题描述语言POL 451
21．4．6 窗口 451
21．5．1 数据输入的规则 452
21．5 数据输入界面设计 452
21．5．2 输入表格设计 453
21．5．3 其他数据输入的方法 455
21．6 数据显示界面设计 456
21．6．1 数据显示的规则 456
21．6．2 字符数据的显示 457
21．6．3 图形显示 458
21．6．4 报告 461
21．7 控制界面的设计 463
21．7．1 用控制对话选择操作命令 463
21．7．2 用菜单界面进行控制 463
21．7．3 用功能键定义操作命令 465
21．7．4 用图标表示对象或命令 465
21．7．5 直接操纵 465
21．7．6 用窗口划分屏幕 466
21．7．7 命令语言 467
21．7．8 自然语言 468
【习题】 470
第22章 面向对象技术 472
22．1 面向对象的概念 472
22．2 面向对象方法的开发过程 475
22．2．1 应用生存期 476
22．2．2 类生存期 476
22．2．3 应用开发过程 480
22．2．4 系统体系结构 481
【习题】 481
第23章 面向对象分析与模型化 483
23．1 面向对象分析 483
23．1．1 论域分析 483
23．2．1 对象模型 486
23．1．2 应用分析 486
23．2 对象模型技术 486
23．2．2 动态模型 488
23．2．3 功能模型 490
23．2．4 基于三个模型的分析过程 491
23．3 Coad与Yourdon的OOA方法 491
23．3．1 面向对象的分析的考虑 491
23．3．2 标识对象和类 492
23．3．3 标识结构 496
23．3．4 标识属性 498
23．3．5 标识服务 500
23．3．6 标识主题 502
【习题】 503
24．1．1 高层设计模型 504
24．1 高层设计 504
第24章 面向对象设计 504
24．1．2 高层设计的规则 505
24．2 Goad与Yourdon面向对象设计方法 506
24．2．1 问题论域部分的设计 506
24．2．2 用户界面部分的设计 508
24．2．3 任务管理部分的设计 509
24．2．4 数据管理部分的设计 510
24．2．5 程序设计语言的影响 512
24．3 类的设计 513
24．3．1 类设计的目标 513
24．3．2 类设计的方针 514
24．3．3 通过复用设计类 516
24．3．4 计数器类设计的实例 518
【习题】 519