书籍详情
程序设计抽象思想：C语言描述
作者：（美）Eric S.Roberts著；闪四清译；闪四清译
出版社：清华大学出版社
出版时间：2005-06-01
ISBN：9787302101659
定价：¥78.00
购买这本书可以去
内容简介
本书全面介绍了数据结构的基础内容，帮助学生深入了解软件工程的思想和技术。学生还可以通过对一些高级编程概念（如接口、抽象和封装）的了解，为进一步深入学习高级编程知识打下坚实的基础。本书观点清晰明了、语言风格鲜明独特，深入浅出地介绍了一些高级主题。本书特色：◆介绍了多个库包，可用于简化编程流程，使学生可以专注于高层次理论问题的研究，避免了C语言编程的繁琐细节；◆详细讨论了递归编程的用法，包括大量难度各异的编程示例和练习，如简单的递归函数，分析双人游戏的最小最大（minimax）策略，等等；◆帮助读者培养编写健壮、可重用代码的良好编程习惯。本书前言写给教师本教程适用于大学编程课程，它覆盖了AMCCurriculum78报告中所定义的计算机科学2标准课程的材料，并且包括ComputingCurriculum1991算法与数据结构课程中的大部分知识。本书将教会学生现代软件工程方法论。本书的内容建立在我于1995年写的TheArtandScienceofC教科书的基础上，并将抽象和接口设计作为核心主题。虽然我写作这两本书是有先后顺序的，但是读者完全可以单独使用本书。本书的第Ⅰ部分包括了TheArtandScienceofC中学生应该掌握的所有背景知识。这些背景知识对于理解本课程其他部分中的例子和方法已经绰绰有余了。由于第Ⅰ部分的介绍是比较简单，因此学生必须熟悉计算机基础课程中涉及的基本编程概念。但是，读者不需要对C语言有所了解，因为在本书的前几章中将介绍C语言的基础。学习过TheArtandScienaofC课程的学生完全可以跳过第Ⅰ部分的内容。在学习完了第Ⅰ部分的预备知识之后，学生可以继续该课程的学习。第Ⅱ部分将讨论递归算法。在第Ⅱ部分的4章内容中，穿插了大量的实例。根据我个人的经验，介绍递归算法的最合理时刻是在第Ⅱ门编程课程开始学习的时候。很多学生都会觉得递归是一个难以理解的概念，必须花很多时间才能较好地掌握它。如果在新学期的一开始就面临递归这个难点，那么学生将有更多的时间来掌握它。在本书中，尽可能早地介绍递归概念，其目的是让读者在作业和考试中运用这种知识。期中考试可以检查学生对递归概念的掌握情况，对于那些确确实实理解递归概念比较差的学生，可以给他们以警示，以便他们及时采取相应的补救措施。如果想压缩学习递归的时间，那么可以跳过第Ⅱ部分的6.1节，这对整个课程的讲述没有什么影响。也许鞍点算法对于部分学生来说有点儿太复杂了，但是它却很好地说明递归算法可以使用很少的代码来解决非常困难的问题。类似地，第7章中大O的理论基础也不是该课程的重点内容。第Ⅲ部分有双重目的：一方面，它介绍了数据结构课程中涉及的非递归算法的概念，包括堆栈、队列以及符号表；另一方面，这部分为学生提供了一些工具，从而帮助学生理解其他部分中涉及的基于接口编程的数据抽象概念。与这个概念相一致的是抽象数据类型（ADT），它是由行为而不是由表现形式定义。本书的一个重要特点是，它不完全使用ANSIC的工具来定义ADT，其中ADT的内部表示对于客户端来说是不可访问的。由于这样的编程风格强调了抽象的难度，因此可以培养学生具有编写良好结构的程序和模块的习惯。我认为在本书中学习的接口是个实用的工具。在许多情况下，学生可以在他们自己的代码中包含和实现这些接口。在第Ⅲ部分的最后一章，即第11章，将介绍几个重要的概念，例如，函数指针、映射函数以及迭代器。相对来说，迭代器在斯坦福大学的课程中是新近加入的，但是教学效果相当好。根据我们的经验，减少客户代码的复杂性所带来的收益远远超过建立迭代器抽象所做工作的代价。第Ⅲ和第Ⅳ部分的重点是抽象数据类型。在某种程度上，这是人为划分的结果。这两部分的不同之处在于，第Ⅳ部分中的抽象数据类型是用递归实现的，而第Ⅲ部分则不是。这样安排的好处是第Ⅳ部分在本书中起到综合的作用，将前两部分的递归和ADT进行综合。尽管第14章中关于表达式树的内容可以跳过，但是我发现尽早地在课程中包括这些内容是很有价值的，因为这样可以减少对C语言编译器操作的神秘感，可以帮助学生更好地理解和控制程序。第17章确实不是本课程的主要内容，而是为学生继续接下来的学习作的预备。本章主要使用Java语言介绍面向对象编程，讲述主要的概念。尽管有些机构已经开始采用由浅入深的顺序方式介绍Java，但是我们认为，由于下列一些原因，先介绍结构化编程方法再介绍面向对象编程方法是很有意义的：1.Java环境的变化太快了，无法为教学提供稳固的基础；2.学生有必要理解结构化编程方法；3.如果在基础课程中强调数据抽象和接口，那么学生学习面向对象编程将更加容易。在斯坦福大学的经验给我们的启示是，这种策略很有效，它能够使学生相对容易地接受面向对象的概念。
作者简介
EricS.Roberts于1980年在哈佛大学获取了应用数学的博士学位，毕业后在Wellesley大学创建了计算机科学系并担任主任，随后在加利福尼亚的DigitalEquipemntCorporation的系统研发中心担任了5年的调研员，现就职于斯坦福大学计算机科学系，并担任斯坦福大学教务部主任。作为一位知名教授，Roberts还编写过TheArtandScienceofC等经典教材。闪四清，大学教师，长期从事数据库、数据挖掘、数据结构等方面的数学、学术研究。已经发表学术论文30多篇，翻译、编写了《数据库系统原理和应用》等多部著作。相关图书C++精解和程序设计（第4版）数据库原理（第2版）C++简明教程精通Office商务应用完美C++教程C语言教程：模块化程序设计（第2版）TCP/IP网络互联技术（卷3）：客户-服务器编程与应用（Windows套接字版）信息技术基础（第3版）
目录
第Ⅰ部分 预备知识
第1章 ANSI C概述 1
1.1 什么是C 1
1.2 C程序的结构 3
1.2.1 注释 4
1.2.2 库包含 5
1.2.3 程序级定义 5
1.2.4 函数原型 5
1.2.5 main程序 6
1.2.6 函数定义 7
1.3 变量、值和类型 7
1.3.1 变量 7
1.3.2 命名规则 8
1.3.3 局部变量和全局变量 9
1.3.4 数据类型的概念 9
1.3.5 整数类型 9
1.3.6 浮点类型 10
1.3.7 文本类型 11
1.3.8 布尔类型 12
1.3.9 简单的输入与输出 12
1.4 表达式 14
1.4.1 优先级与结合性 14
1.4.2 表达式中的类型混合 15
1.4.3 整数除法和求余运算符 16
1.4.4 类型转换 17
1.4.5 赋值运算符 17
1.4.6 递增与递减运算符 19
1.4.7 布尔运算符 20
1.5 语句 22
1.5.1 简单语句 22
1.5.2 块 22
1.5.3 if语句 23
1.5.4 switch语句 23
1.5.5 while语句 25
1.5.6 for语句 28
1.6 函数 29
1.6.1 返回函数结果 29
1.6.2 函数定义和原型 30
1.6.3 函数调用过程的机制 30
1.6.4 逐步求精 31
1.7 小结 31
1.8 复习题 32
1.9 编程练习 33
第2章 C的数据类型 38
2.1 枚举类型 38
2.1.1 枚举类型的内部表示 39
2.1.2 标量类型 40
2.1.3 理解typedef 41
2.2 数据和内存 41
2.2.1 位、字节、字 42
2.2.2 内存地址 42
2.3 指针 44
2.3.1 把地址当作数值 44
2.3.2 声明指针变量 45
2.3.3 基本的指针运算 45
2.3.4 特殊指针NULL 47
2.3.5 通过引用传递参数 48
2.4 数组 51
2.4.1 声明数组 51
2.4.2 数组选择 52
2.4.3 有效空间和已分配空间 53
2.4.4 作为参数传递数组 54
2.4.5 初始化数组 56
2.4.6 多维数组 57
2.5 指针和数组 59
2.5.1 指针运算 60
2.5.2 指针的自加和自减 62
2.5.3 指针和数组的关系 62
2.6 记录 64
2.6.1 定义一种新的结构类型 65
2.6.2 声明结构变量 66
2.6.3 记录选择 66
2.6.4 初始化纪录 66
2.6.5 记录的指针 67
2.7 动态分配 68
2.7.1 类型void* 68
2.7.2 应对内存限制 70
2.7.3 动态数组 71
2.7.4 动态记录 72
2.8 小结 73
2.9 复习题 74
2.10 编程练习 76
第3章 库和接口 83
3.1 接口的概念 83
3.1.1 接口和实现 84
3.1.2 包和抽象 84
3.1.3 良好的接口设计规则 85
3.2 随机数字 85
3.2.1 random.h接口的结构 86
3.2.2 构建客户程序 89
3.2.3 有关随机数字的ANSI函数 91
3.2.4 实现random.c 93
3.3 字符串 96
3.3.1 字符串的底层表示 96
3.3.2 数据类型string 97
3.3.3 ANSI字符串库 98
3.3.4 接口strlib.h 102
3.4 标准的I/O库 108
3.4.1 数据文件 108
3.4.2 在C中使用文件 109
3.4.3 标准文件 110
3.4.4 字符I/O 110
3.4.5 从输入文件中重读字符 111
3.4.6 更新文件 112
3.4.7 面向行的I/O 113
3.4.8 格式化的I/O 114
3.4.9 scanf函数 115
3.5 其他ANSI库 116
3.6 小结 118
3.7 复习题 118
3.8 编程练习 120
第Ⅱ部分 递归和算法分析
第4章 递归入门 127
4.1 一个简单的递归示例 128
4.2 阶乘函数 129
4.2.1 Fact的递归公式 130
4.2.2 追踪递归过程 130
4.2.3 递归跳跃的信任 134
4.3 费波那契函数 134
4.3.1 计算费波那契序列 135
4.3.2 增进实现递归的信心 136
4.3.3 递归实现的效率 137
4.3.4 不应该责备递归 138
4.4 其他递归示例 139
4.4.1 探测回文 139
4.4.2 二分查找 142
4.4.3 交互递归 143
4.5 以递归的方式思考 144
4.5.1 保持整体观 145
4.5.2 避免常见的错误 145
4.6 小结 146
4.7 复习题 147
4.8 编程练习 149
第5章 递归过程 152
5.1 汉诺塔 152
5.1.1 分解问题 153
5.1.2 寻找递归策略 153
5.1.3 验证递归策略 155
5.1.4 解决方案的编码 156
5.1.5 追踪递归过程 156
5.2 产生排列 160
5.3 递归在绘图中的应用 162
5.3.1 图形库 162
5.3.2 电脑艺术示例 165
5.3.3 不规则碎片形 169
5.4 小结 173
5.5 复习题 174
5.6 编程练习 175
第6章 回溯算法 183
6.1 用递归回溯解决迷宫问题 183
6.1.1 右手规则 183
6.1.2 寻找递归方法 184
6.1.3 识别简单情景 185
6.1.4 编写迷宫解决方案算法 186
6.1.5 确信解决方案可以正确运行 190
6.2 回溯与游戏 192
6.2.1 拿子游戏 193
6.2.2 常规化的双人游戏程序 199
6.2.3 最小最大策略 200
6.2.4 实现最小最大化算法 202
6.2.5 在具体的游戏中采用常规策略 204
6.3 小结 216
6.4 复习题 217
6.5 编程练习 218
第7章 算法分析 225
7.1 排序问题 225
7.1.1 选择排序算法 226
7.1.2 性能的经验度量 227
7.1.3 分析选择排序的性能 228
7.2 计算复杂度 230
7.2.1 大O符号 230
7.2.2 大O的标准简化 230
7.2.3 排序算法的计算复杂度 231
7.2.4 根据代码结构预测计算复杂度 232
7.2.5 最差情况复杂度与平均情况复杂度 233
7.2.6 大O的正式定义 233
7.3 递归帮助 235
7.3.1 分治策略的威力 235
7.3.2 合并两个数组 236
7.3.3 合并排序算法 237
7.3.4 合并排序的计算复杂度 239
7.3.5 比较N2和NlogN的性能 240
7.4 标准复杂度类型 241
7.5 快速排序算法 242
7.5.1 分割数组 244
7.5.2 分析快速排序的性能 246
7.6 数学归纳法 247
7.7 小结 250
7.8 复习题 250
7.9 编程练习 252
第Ⅲ部分 数据抽象
第8章 抽象数据类型 257
8.1 堆栈 258
8.1.1 基本的堆栈比喻 258
8.1.2 堆栈和函数调用 258
8.1.3 堆栈和袖珍计算器 259
8.2 定义堆栈的ADT 259
8.2.1 定义堆栈抽象的类型 260
8.2.2 不透明类型 261
8.2.3 定义stack.h接口 262
8.3 在应用程序中使用堆栈 265
8.4 实现堆栈抽象 269
8.4.1 定义具体类型 269
8.4.2 实现堆栈操作 269
8.4.3 不透明类型的优点 271
8.4.4 改进stack.c的实现 272
8.5 定义扫描器ADT 273
8.5.1 封装状态的危险 274
8.5.2 抽象数据类型作为封装状态的替代 274
8.5.3 实现扫描器抽象 279
8.6 小结 283
8.7 复习题 284
8.8 编程练习 285
第9章 效率与ADT 297
9.1 编辑器缓冲区的概念 297
9.2 定义缓冲区抽象 298
9.2.1 接口buffer.h中的函数 299
9.2.2 为编辑器应用程序编写代码 301
9.3 用数组实现编辑器 303
9.3.1 定义具体类型 303
9.3.2 实现缓冲区的操作 304
9.3.3 数组实现的计算复杂度 308
9.4 用堆栈实现编辑器 309
9.4.1 定义基于堆栈的缓冲区的具体结构 310
9.4.2 实现缓冲区的操作 310
9.4.3 比较计算复杂度 313
9.5 用链表实现编辑器 313
9.5.1 链表的概念 314
9.5.2 设计链表数据结构 314
9.5.3 使用链表表示缓冲区 316
9.5.4 链表缓冲区中的插入 317
9.5.5 链表缓冲区中的删除 320
9.5.6 链表表示中的光标移动 321
9.5.7 链表的习惯用法 323
9.5.8 完成缓冲区实现 324
9.5.9 链表缓冲区的计算复杂度 328
9.5.10 双向链表 328
9.5.11 时间-空间的权衡 329
9.6 小结 329
9.7 复习题 330
9.8 编程练习 331
第10章 线性结构 337
10.1 堆栈回顾 337
10.2 队列 344
10.2.1 接口queue.h的结构 344
10.2.2 基于数组的队列实现 347
10.2.3 队列的链表实现 351
10.3 使用队列的仿真 355
10.3.1 仿真与模型 356
10.3.2 排队模型 356
10.3.3 离散时间 356
10.3.4 仿真时间中的事件 357
10.3.5 实现仿真 357
10.4 小结 364
10.5 复习题 365
10.6 编程练习 366
第11章 符号表 371
11.1 定义符号表抽象 371
11.1.1 选择值和键的类型 372
11.1.2 表示未定义项 373
11.1.3 符号表接口的初始版本 373
11.2 散列 375
11.2.1 实现散列表策略 375
11.2.2 选择散列函数 380
11.2.3 确定桶的数量 381
11.3 初级接口的限制 382
11.4 使用函数作为数据 384
11.4.1 通用绘图函数 384
11.4.2 声明函数指针与函数类 385
11.4.3 实现PlotFunction 386
11.4.4 qsort函数 387
11.5 映射函数 391
11.5.1 映射符号表中的所有项 391
11.5.2 实现MapSymbolTable 394
11.5.3 向回调函数传递客户数据 395
11.6 迭代器 396
11.6.1 使用迭代器 396
11.6.2 定义迭代器接口 397
11.6.3 实现针对符号表的迭代器抽象 398
11.7 命令分派表 401
11.8 小结 404
11.9 复习题 405
11.10 编程练习 406
第Ⅳ部分 递 归 数 据
第12章 递归链表 411
12.1 链表的递归表述 412
12.2 定义抽象链表类型 413
12.2.1 不变类型 416
12.2.2 操纵链表结构的函数 417
12.2.3 连接多个链表 419
12.2.4 不变类型间的内部共享 421
12.3 使用链表表示大整数 422
12.3.1 bigint.h接口 423
12.3.2 表示类型bigIntADT 425
12.3.3 实现bigint包 426
12.3.4 使用bigint.h包 430
12.4 小结 432
12.5 复习题 433
12.6 编程练习 434
第13章 树 438
13.1 家谱树 438
13.1.1 描述树的术语 439
13.1.2 树的递归特性 439
13.1.3 用C语言表示家谱树 440
13.2 二叉搜索树 441
13.2.1 使用二叉搜索树的底层动机 442
13.2.2 在二叉搜索树中查找节点 443
13.2.3 在二叉搜索树中插入新节点 444
13.2.4 树的遍历 447
13.3 平衡树 449
13.3.1 树的平衡策略 450
13.3.2 举例说明AVL的思想 451
13.3.3 单旋转 452
13.3.4 双旋转 454
13.3.5 实现AVL算法 455
13.4 为二叉搜索树定义通用接口 458
13.4.1 允许客户定义节点结构 462
13.4.2 泛化键的类型 465
13.4.3 删除节点 465
13.4.4 实现二叉搜索树包 467
13.4.5 使用二叉树实现symtab.h接口 472
13.5 小结 474
13.6 复习题 474
13.7 编程练习 477
第14章 表达式树 484
14.1 解释器概述 484
14.2 表达式的抽象结构 487
14.2.1 表达式的递归定义 487
14.2.2 歧义性 488
14.2.3 表达式树 489
14.2.4 定义表达式的抽象接口 490
14.3 定义具体表达式类型 494
14.3.1 联合类型 494
14.3.2 用带标记联合表示表达式 496
14.3.3 可视化具体表示 498
14.3.4 实现构造器和选择器函数 500
14.4 分析表达式 502
14.4.1 语法分析和语法 502
14.4.2 不考虑优先级的语法分析 503
14.4.3 在语法分析器中加入优先级 507
14.5 计算表达式 509
14.6 小结 511
14.7 复习题 512
14.8 编程练习 513
第15章 集合 525
15.1 作为数学抽象的集合 525
15.1.1 成员资格 526
15.1.2 集合运算 526
15.1.3 集合恒等式 527
15.2 设计集合接口 529
15.2.1 定义元素类型 529
15.2.2 编写set.h 接口 531
15.2.3 字符集合 534
15.2.4 使用指针集合来避免重复 535
15.3 实现集合包 537
15.4 设计多态迭代器 544
15.4.1 泛化迭代器函数的原型 544
15.4.2 在迭代器中实现多态性 545
15.4.3 导出聚集类型 546
15.4.4 编码迭代器包 550
15.4.5 foreach的习惯用法 554
15.5 提高整数集合的效率 554
15.5.1 特征向量 555
15.5.2 压缩的位数组 555
15.5.3 位运算符 556
15.5.4 使用位运算符实现特征向量 559
15.5.5 实现高级集合操作 561
15.5.6 使用混合实现 561
15.6 小结 561
15.7 复习题 563
15.8 编程练习 565
第16章 图 570
16.1 图的结构 570
16.1.1 有向图和无向图 572
16.1.2 路径和环 573
16.1.3 连通性 573
16.2 图的实现策略 574
16.2.1 使用邻接列表表示连接 575
16.2.2 使用邻接矩阵表示连接 578
16.3 扩展图抽象 581
16.3.1 将数据与节点和图关联 581
16.3.2 显式弧 581
16.3.3 迭代和图 582
16.3.4 分层抽象 583
16.3.5 基于集合的图接口 584
16.4 图的遍历 592
16.4.1 深度优先遍历 593
16.4.2 广度优先搜索 595
16.5 寻找最短路径 597
16.6 小结 604
16.7 复习题 605
16.8 编程练习 607
第17章 展望Java 614
17.1 面向对象范式 614
17.1.1 面向对象编程的历史 615
17.1.2 对象、类和方法 616
17.1.3 类层次结构与继承 616
17.2 Java简介 618
17.2.1 Web结构 618
17.2.2 applet 619
17.2.3 执行Java applet 623
17.3 Java结构 624
17.3.1 Java的语法 625
17.3.2 Java中的原子类型 626
17.3.3 定义一个新类 626
17.3.4 构造器方法 628
17.3.5 this关键字 628
17.3.6 定义方法 629
17.3.7 定义子类 631
17.4 Java中的预定义类 637
17.4.1 String类 637
17.4.2 Hashtable类 638
17.4.3 原子类型的对象包装器 641
17.4.4 Vector类 641
17.4.5 Stack类 643
17.5 创建交互式applet的工具 644
17.5.1 组件与容器 644
17.5.2 action方法 645
17.5.3 用于绘制简单图形的applet 646
17.5.4 更进一步 654
17.6 小结 654
17.8 复习题 654
17.9 编程练习 656
第1章 ANSI C概述 1
1.1 什么是C 1
1.2 C程序的结构 3
1.2.1 注释 4
1.2.2 库包含 5
1.2.3 程序级定义 5
1.2.4 函数原型 5
1.2.5 main程序 6
1.2.6 函数定义 7
1.3 变量、值和类型 7
1.3.1 变量 7
1.3.2 命名规则 8
1.3.3 局部变量和全局变量 9
1.3.4 数据类型的概念 9
1.3.5 整数类型 9
1.3.6 浮点类型 10
1.3.7 文本类型 11
1.3.8 布尔类型 12
1.3.9 简单的输入与输出 12
1.4 表达式 14
1.4.1 优先级与结合性 14
1.4.2 表达式中的类型混合 15
1.4.3 整数除法和求余运算符 16
1.4.4 类型转换 17
1.4.5 赋值运算符 17
1.4.6 递增与递减运算符 19
1.4.7 布尔运算符 20
1.5 语句 22
1.5.1 简单语句 22
1.5.2 块 22
1.5.3 if语句 23
1.5.4 switch语句 23
1.5.5 while语句 25
1.5.6 for语句 28
1.6 函数 29
1.6.1 返回函数结果 29
1.6.2 函数定义和原型 30
1.6.3 函数调用过程的机制 30
1.6.4 逐步求精 31
1.7 小结 31
1.8 复习题 32
1.9 编程练习 33
第2章 C的数据类型 38
2.1 枚举类型 38
2.1.1 枚举类型的内部表示 39
2.1.2 标量类型 40
2.1.3 理解typedef 41
2.2 数据和内存 41
2.2.1 位、字节、字 42
2.2.2 内存地址 42
2.3 指针 44
2.3.1 把地址当作数值 44
2.3.2 声明指针变量 45
2.3.3 基本的指针运算 45
2.3.4 特殊指针NULL 47
2.3.5 通过引用传递参数 48
2.4 数组 51
2.4.1 声明数组 51
2.4.2 数组选择 52
2.4.3 有效空间和已分配空间 53
2.4.4 作为参数传递数组 54
2.4.5 初始化数组 56
2.4.6 多维数组 57
2.5 指针和数组 59
2.5.1 指针运算 60
2.5.2 指针的自加和自减 62
2.5.3 指针和数组的关系 62
2.6 记录 64
2.6.1 定义一种新的结构类型 65
2.6.2 声明结构变量 66
2.6.3 记录选择 66
2.6.4 初始化纪录 66
2.6.5 记录的指针 67
2.7 动态分配 68
2.7.1 类型void* 68
2.7.2 应对内存限制 70
2.7.3 动态数组 71
2.7.4 动态记录 72
2.8 小结 73
2.9 复习题 74
2.10 编程练习 76
第3章 库和接口 83
3.1 接口的概念 83
3.1.1 接口和实现 84
3.1.2 包和抽象 84
3.1.3 良好的接口设计规则 85
3.2 随机数字 85
3.2.1 random.h接口的结构 86
3.2.2 构建客户程序 89
3.2.3 有关随机数字的ANSI函数 91
3.2.4 实现random.c 93
3.3 字符串 96
3.3.1 字符串的底层表示 96
3.3.2 数据类型string 97
3.3.3 ANSI字符串库 98
3.3.4 接口strlib.h 102
3.4 标准的I/O库 108
3.4.1 数据文件 108
3.4.2 在C中使用文件 109
3.4.3 标准文件 110
3.4.4 字符I/O 110
3.4.5 从输入文件中重读字符 111
3.4.6 更新文件 112
3.4.7 面向行的I/O 113
3.4.8 格式化的I/O 114
3.4.9 scanf函数 115
3.5 其他ANSI库 116
3.6 小结 118
3.7 复习题 118
3.8 编程练习 120
第Ⅱ部分 递归和算法分析
第4章 递归入门 127
4.1 一个简单的递归示例 128
4.2 阶乘函数 129
4.2.1 Fact的递归公式 130
4.2.2 追踪递归过程 130
4.2.3 递归跳跃的信任 134
4.3 费波那契函数 134
4.3.1 计算费波那契序列 135
4.3.2 增进实现递归的信心 136
4.3.3 递归实现的效率 137
4.3.4 不应该责备递归 138
4.4 其他递归示例 139
4.4.1 探测回文 139
4.4.2 二分查找 142
4.4.3 交互递归 143
4.5 以递归的方式思考 144
4.5.1 保持整体观 145
4.5.2 避免常见的错误 145
4.6 小结 146
4.7 复习题 147
4.8 编程练习 149
第5章 递归过程 152
5.1 汉诺塔 152
5.1.1 分解问题 153
5.1.2 寻找递归策略 153
5.1.3 验证递归策略 155
5.1.4 解决方案的编码 156
5.1.5 追踪递归过程 156
5.2 产生排列 160
5.3 递归在绘图中的应用 162
5.3.1 图形库 162
5.3.2 电脑艺术示例 165
5.3.3 不规则碎片形 169
5.4 小结 173
5.5 复习题 174
5.6 编程练习 175
第6章 回溯算法 183
6.1 用递归回溯解决迷宫问题 183
6.1.1 右手规则 183
6.1.2 寻找递归方法 184
6.1.3 识别简单情景 185
6.1.4 编写迷宫解决方案算法 186
6.1.5 确信解决方案可以正确运行 190
6.2 回溯与游戏 192
6.2.1 拿子游戏 193
6.2.2 常规化的双人游戏程序 199
6.2.3 最小最大策略 200
6.2.4 实现最小最大化算法 202
6.2.5 在具体的游戏中采用常规策略 204
6.3 小结 216
6.4 复习题 217
6.5 编程练习 218
第7章 算法分析 225
7.1 排序问题 225
7.1.1 选择排序算法 226
7.1.2 性能的经验度量 227
7.1.3 分析选择排序的性能 228
7.2 计算复杂度 230
7.2.1 大O符号 230
7.2.2 大O的标准简化 230
7.2.3 排序算法的计算复杂度 231
7.2.4 根据代码结构预测计算复杂度 232
7.2.5 最差情况复杂度与平均情况复杂度 233
7.2.6 大O的正式定义 233
7.3 递归帮助 235
7.3.1 分治策略的威力 235
7.3.2 合并两个数组 236
7.3.3 合并排序算法 237
7.3.4 合并排序的计算复杂度 239
7.3.5 比较N2和NlogN的性能 240
7.4 标准复杂度类型 241
7.5 快速排序算法 242
7.5.1 分割数组 244
7.5.2 分析快速排序的性能 246
7.6 数学归纳法 247
7.7 小结 250
7.8 复习题 250
7.9 编程练习 252
第Ⅲ部分 数据抽象
第8章 抽象数据类型 257
8.1 堆栈 258
8.1.1 基本的堆栈比喻 258
8.1.2 堆栈和函数调用 258
8.1.3 堆栈和袖珍计算器 259
8.2 定义堆栈的ADT 259
8.2.1 定义堆栈抽象的类型 260
8.2.2 不透明类型 261
8.2.3 定义stack.h接口 262
8.3 在应用程序中使用堆栈 265
8.4 实现堆栈抽象 269
8.4.1 定义具体类型 269
8.4.2 实现堆栈操作 269
8.4.3 不透明类型的优点 271
8.4.4 改进stack.c的实现 272
8.5 定义扫描器ADT 273
8.5.1 封装状态的危险 274
8.5.2 抽象数据类型作为封装状态的替代 274
8.5.3 实现扫描器抽象 279
8.6 小结 283
8.7 复习题 284
8.8 编程练习 285
第9章 效率与ADT 297
9.1 编辑器缓冲区的概念 297
9.2 定义缓冲区抽象 298
9.2.1 接口buffer.h中的函数 299
9.2.2 为编辑器应用程序编写代码 301
9.3 用数组实现编辑器 303
9.3.1 定义具体类型 303
9.3.2 实现缓冲区的操作 304
9.3.3 数组实现的计算复杂度 308
9.4 用堆栈实现编辑器 309
9.4.1 定义基于堆栈的缓冲区的具体结构 310
9.4.2 实现缓冲区的操作 310
9.4.3 比较计算复杂度 313
9.5 用链表实现编辑器 313
9.5.1 链表的概念 314
9.5.2 设计链表数据结构 314
9.5.3 使用链表表示缓冲区 316
9.5.4 链表缓冲区中的插入 317
9.5.5 链表缓冲区中的删除 320
9.5.6 链表表示中的光标移动 321
9.5.7 链表的习惯用法 323
9.5.8 完成缓冲区实现 324
9.5.9 链表缓冲区的计算复杂度 328
9.5.10 双向链表 328
9.5.11 时间-空间的权衡 329
9.6 小结 329
9.7 复习题 330
9.8 编程练习 331
第10章 线性结构 337
10.1 堆栈回顾 337
10.2 队列 344
10.2.1 接口queue.h的结构 344
10.2.2 基于数组的队列实现 347
10.2.3 队列的链表实现 351
10.3 使用队列的仿真 355
10.3.1 仿真与模型 356
10.3.2 排队模型 356
10.3.3 离散时间 356
10.3.4 仿真时间中的事件 357
10.3.5 实现仿真 357
10.4 小结 364
10.5 复习题 365
10.6 编程练习 366
第11章 符号表 371
11.1 定义符号表抽象 371
11.1.1 选择值和键的类型 372
11.1.2 表示未定义项 373
11.1.3 符号表接口的初始版本 373
11.2 散列 375
11.2.1 实现散列表策略 375
11.2.2 选择散列函数 380
11.2.3 确定桶的数量 381
11.3 初级接口的限制 382
11.4 使用函数作为数据 384
11.4.1 通用绘图函数 384
11.4.2 声明函数指针与函数类 385
11.4.3 实现PlotFunction 386
11.4.4 qsort函数 387
11.5 映射函数 391
11.5.1 映射符号表中的所有项 391
11.5.2 实现MapSymbolTable 394
11.5.3 向回调函数传递客户数据 395
11.6 迭代器 396
11.6.1 使用迭代器 396
11.6.2 定义迭代器接口 397
11.6.3 实现针对符号表的迭代器抽象 398
11.7 命令分派表 401
11.8 小结 404
11.9 复习题 405
11.10 编程练习 406
第Ⅳ部分 递 归 数 据
第12章 递归链表 411
12.1 链表的递归表述 412
12.2 定义抽象链表类型 413
12.2.1 不变类型 416
12.2.2 操纵链表结构的函数 417
12.2.3 连接多个链表 419
12.2.4 不变类型间的内部共享 421
12.3 使用链表表示大整数 422
12.3.1 bigint.h接口 423
12.3.2 表示类型bigIntADT 425
12.3.3 实现bigint包 426
12.3.4 使用bigint.h包 430
12.4 小结 432
12.5 复习题 433
12.6 编程练习 434
第13章 树 438
13.1 家谱树 438
13.1.1 描述树的术语 439
13.1.2 树的递归特性 439
13.1.3 用C语言表示家谱树 440
13.2 二叉搜索树 441
13.2.1 使用二叉搜索树的底层动机 442
13.2.2 在二叉搜索树中查找节点 443
13.2.3 在二叉搜索树中插入新节点 444
13.2.4 树的遍历 447
13.3 平衡树 449
13.3.1 树的平衡策略 450
13.3.2 举例说明AVL的思想 451
13.3.3 单旋转 452
13.3.4 双旋转 454
13.3.5 实现AVL算法 455
13.4 为二叉搜索树定义通用接口 458
13.4.1 允许客户定义节点结构 462
13.4.2 泛化键的类型 465
13.4.3 删除节点 465
13.4.4 实现二叉搜索树包 467
13.4.5 使用二叉树实现symtab.h接口 472
13.5 小结 474
13.6 复习题 474
13.7 编程练习 477
第14章 表达式树 484
14.1 解释器概述 484
14.2 表达式的抽象结构 487
14.2.1 表达式的递归定义 487
14.2.2 歧义性 488
14.2.3 表达式树 489
14.2.4 定义表达式的抽象接口 490
14.3 定义具体表达式类型 494
14.3.1 联合类型 494
14.3.2 用带标记联合表示表达式 496
14.3.3 可视化具体表示 498
14.3.4 实现构造器和选择器函数 500
14.4 分析表达式 502
14.4.1 语法分析和语法 502
14.4.2 不考虑优先级的语法分析 503
14.4.3 在语法分析器中加入优先级 507
14.5 计算表达式 509
14.6 小结 511
14.7 复习题 512
14.8 编程练习 513
第15章 集合 525
15.1 作为数学抽象的集合 525
15.1.1 成员资格 526
15.1.2 集合运算 526
15.1.3 集合恒等式 527
15.2 设计集合接口 529
15.2.1 定义元素类型 529
15.2.2 编写set.h 接口 531
15.2.3 字符集合 534
15.2.4 使用指针集合来避免重复 535
15.3 实现集合包 537
15.4 设计多态迭代器 544
15.4.1 泛化迭代器函数的原型 544
15.4.2 在迭代器中实现多态性 545
15.4.3 导出聚集类型 546
15.4.4 编码迭代器包 550
15.4.5 foreach的习惯用法 554
15.5 提高整数集合的效率 554
15.5.1 特征向量 555
15.5.2 压缩的位数组 555
15.5.3 位运算符 556
15.5.4 使用位运算符实现特征向量 559
15.5.5 实现高级集合操作 561
15.5.6 使用混合实现 561
15.6 小结 561
15.7 复习题 563
15.8 编程练习 565
第16章 图 570
16.1 图的结构 570
16.1.1 有向图和无向图 572
16.1.2 路径和环 573
16.1.3 连通性 573
16.2 图的实现策略 574
16.2.1 使用邻接列表表示连接 575
16.2.2 使用邻接矩阵表示连接 578
16.3 扩展图抽象 581
16.3.1 将数据与节点和图关联 581
16.3.2 显式弧 581
16.3.3 迭代和图 582
16.3.4 分层抽象 583
16.3.5 基于集合的图接口 584
16.4 图的遍历 592
16.4.1 深度优先遍历 593
16.4.2 广度优先搜索 595
16.5 寻找最短路径 597
16.6 小结 604
16.7 复习题 605
16.8 编程练习 607
第17章 展望Java 614
17.1 面向对象范式 614
17.1.1 面向对象编程的历史 615
17.1.2 对象、类和方法 616
17.1.3 类层次结构与继承 616
17.2 Java简介 618
17.2.1 Web结构 618
17.2.2 applet 619
17.2.3 执行Java applet 623
17.3 Java结构 624
17.3.1 Java的语法 625
17.3.2 Java中的原子类型 626
17.3.3 定义一个新类 626
17.3.4 构造器方法 628
17.3.5 this关键字 628
17.3.6 定义方法 629
17.3.7 定义子类 631
17.4 Java中的预定义类 637
17.4.1 String类 637
17.4.2 Hashtable类 638
17.4.3 原子类型的对象包装器 641
17.4.4 Vector类 641
17.4.5 Stack类 643
17.5 创建交互式applet的工具 644
17.5.1 组件与容器 644
17.5.2 action方法 645
17.5.3 用于绘制简单图形的applet 646
17.5.4 更进一步 654
17.6 小结 654
17.8 复习题 654
17.9 编程练习 656
猜您喜欢
