第Ⅰ部分 预备知识 1
第1章 ANSI C概述 1
1.1 什么是C 1
目录 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.3 变量、值和类型 7
1.3.1 变量 7
1.2.6 函数定义 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.5 赋值运算符 17
1.4.4 类型转换 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.3 函数调用过程的机制 30
1.6.2 函数定义和原型 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.1 把地址当作数值 44
2.3 指针 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
第Ⅱ部分 递归和算法分析 127
第4章 递归入门 127
4.1 一个简单的递归示例 128
4.2 阶乘函数 129
4.2.1 Fact的递归公式 130
4.2.2 追踪递归过程 130
4.3 费波那契函数 134
4.2.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.2 大O的标准简化 230
7.2.1 大O符号 230
7.2 计算复杂度 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
第Ⅲ部分 数据抽象 257
第8章 抽象数据类型 257
8.1 堆栈 258
8.1.1 基本的堆栈比喻 258
8.1.2 堆栈和函数调用 258
8.2 定义堆栈的ADT 259
8.1.3 堆栈和袖珍计算器 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.10 双向链表 328
9.5.9 链表缓冲区的计算复杂度 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.3 离散时间 356
10.3.2 排队模型 356
10.3.1 仿真与模型 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.1 使用迭代器 396
11.6 迭代器 396
11.6.2 定义迭代器接口 397
11.6.3 实现针对符号表的迭代器抽象 398
11.7 命令分派表 401
11.8 小结 404
11.9 复习题 405
11.10 编程练习 406
第Ⅳ部分 递归数据 411
第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.2 树的递归特性 439
13.1.1 描述树的术语 439
13.1.3 用C语言表示家谱树 440
13.2 二叉搜索树 441
1 3.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.1 泛化迭代器函数的原型 544
15.4 设计多态迭代器 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.3 类层次结构与继承 616
17.1.2 对象、类和方法 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.1 String类 637
17.4 Java中的预定义类 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