写给学生
写给教师
致　　谢
第一部分　预备知识
第1章　ANSI C概述2
1.1　什么是C2
1.2　C程序的结构4
1.2.1　注释5
1.2.2　包含的库文件5
1.2.3　程序级的定义6
1.2.4　函数原型6
1.2.5　主程序6
1.2.6　函数定义7
1.3　变量、值和类型8
1.3.1　变量8
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　表达式13
1.4.1　优先级与结合性14
1.4.2　表达式中的类型混合15
1.4.3　整数除法和求余运算15
1.4.4　类型转换16
1.4.5　赋值运算符16
1.4.6　递增与递减运算符17
1.4.7　布尔运算符18
1.5　语句20
1.5.1　简单语句20
1.5.2　块20
1.5.3　if语句21
1.5.4　switch语句21
1.5.5　while语句23
1.5.6　for语句25
1.6　函数26
1.6.1　返回函数结果27
1.6.2　函数定义和原型27
1.6.3　函数调用过程的机制28
1.6.4　逐步求精28
1.7　总结28
1.8　复习题29
1.9　编程练习30
第2章　C的数据类型34
2.1　枚举类型34
2.1.1　枚举类型的内部表示35
2.1.2　标量类型36
2.1.3　理解typedef36
2.2　数据和内存37
2.2.1　位、字节、字37
2.2.2　内存地址38
2.3　指针39
2.3.1　把地址当作数值40
2.3.2　声明指针变量40
2.3.3　基本的指针运算41
2.3.4　特殊指针NULL43
2.3.5　传递引用43
2.4　数组46
2.4.1　声明数组46
2.4.2　数组选择47
2.4.3　分配的空间和利用的空间48
2.4.4　把数组作为参数48
2.4.5　初始化数组51
2.4.6　多维数组52
2.5　指针和数组53
2.5.1　指针运算54
2.5.2　指针的自加和自减56
2.5.3　指针和数组的关系56
2.6　记录58
2.6.1　定义一种新的结构类型58
2.6.2　声明结构变量59
2.6.3　记录选择59
2.6.4　初始化纪录59
2.6.5　记录的指针60
2.7　动态分配61
2.7.1　类型void61
2.7.2　对内存限制的处理62
2.7.3　动态数组63
2.7.4　动态记录64
2.8　总结65
2.9　复习题66
2.10　编程练习68
第3章　库和接口74
3.1　接口的概念74
3.1.1　接口和实现75
3.1.2　包和抽象75
3.1.3　良好的接口设计规则76
3.2　随机数字76
3.2.1　random.h接口的结构77
3.2.2　构造一个客户程序80
3.2.3　ANSI中有关随机数字的函数82
3.2.4　实现random.c83
3.3　字符串86
3.3.1　字符的底层表示86
3.3.2　数据类型string88
3.3.3　ANSI字符串库89
3.3.4　接口strlib.h92
3.4　标准的I/O库98
3.4.1　数据文件98
3.4.2　在C中使用文件99
3.4.3　标准文件100
3.4.4　字符I/O100
3.4.5　从输入文件中重读字符101
3.4.6　更新文件102
3.4.7　面向行的I/O103
3.4.8　格式化的I/O103
3.4.9　scanf函数104
3.5　其他ANSI库105
3.6　总结107
3.7　复习题107
3.8　编程练习109
第二部分　递归和算法分析
第4章　递归入门116
4.1　一个简单的递归示例116
4.2　阶乘函数118
4.2.1　Fact的递归公式118
4.2.2　追踪递归过程119
4.2.3　递归跳跃的信任122
4.3　费波那契函数123
4.3.1　计算费波那契序列123
4.3.2　增进实现递归的信心125
4.3.3　递归实现的效率125
4.3.4　不应该责备递归126
4.4　其他递归示例127
4.4.1　探测回文128
4.4.2　二分查找130
4.4.3　交互递归131
4.5　递归的思考133
4.5.1　保持整体观133
4.5.2　避免常见的陷阱133
4.6　总结134
4.7　复习题135
4.8　编程练习137
第5章　递归过程140
5.1　汉诺塔140
5.1.1　分解问题141
5.1.2　寻找递归策略142
5.1.3　证实递归策略143
5.1.4　编码解决方案144
5.1.5　追踪递归过程144
5.2　产生排列148
5.3　递归的绘图应用150
5.3.1　绘图库150
5.3.2　电脑艺术示例152
5.3.3　不规则碎片形155
5.4　总结159
5.5　复习题160
5.6　编程练习161
第6章　回溯算法168
6.1　用递归回溯解决迷宫问题168
6.1.1　右手规则168
6.1.2　寻找递归方法169
6.1.3　识别简单情景170
6.1.4　迷宫解决方案算法编码171
6.1.5　确信解决方案可以正确运行175
6.2　回溯与对策176
6.2.1　拿子游戏177
6.2.2　一般化的双人游戏程序183
6.2.3　最小最大策略184
6.2.4　实现最小最大化算法185
6.2.5　在具体的游戏中采用一般化策略187
6.3　总结199
6.4　复习题199
6.5　编程练习200
第7章　算法分析206
7.1　排序问题206
7.1.1　选择排序算法207
7.1.2　性能的经验度量208
7.1.3　分析选择排序的性能209
7.2　计算复杂度210
7.2.1　大O符号210
7.2.2　大O的标准简化211
7.2.3　排序算法的计算复杂度211
7.2.4　根据代码结构预测计算复杂度212
7.2.5　最差情况复杂度与平均情况复杂度213
7.2.6　大O的正式定义214
7.3　递归帮助215
7.3.1　分治策略的威力215
7.3.2　合并两个数组216
7.3.3　合并排序算法216
7.3.4　合并排序的计算复杂度218
7.3.5　比较N2和NlogN的性能219
7.4　标准复杂度类型220
7.5　快速排序算法221
7.5.1　分割数组223
7.5.2　分析快速排序的性能225
7.6　数学归纳法225
7.7　总结227
7.8　复习题228
7.9　编程练习230
第三部分　数据抽象
第8章　抽象数据类型236
8.1　栈236
8.1.1　栈的基本概念237
8.1.2　栈和函数调用237
8.1.3　栈和袖珍计算器237
8.2　定义栈的ADT238
8.2.1　定义栈抽象的类型238
8.2.2　不透明类型240
8.2.3　定义stack.h接口240
8.3　在应用中使用栈244
8.4　实现栈抽象247
8.4.1　定义具体类型247
8.4.2　实现栈操作247
8.4.3　不透明类型的优点249
8.4.4　改进stack.c的实现250
8.5　定义一个scannerADT251
8.5.1　封装状态的危险252
8.5.2　抽象数据类型作为封装状态的替代252
8.5.3　实现扫描器抽象256
8.6　总结261
8.7　复习题262
8.8　编程练习263
第9章　效率与ADT273
9.1　编辑器缓冲区的概念273
9.2　定义缓冲区抽象274
9.2.1　接口buffer.h中的函数275
9.2.2　为编辑器应用编写代码277
9.3　用数组实现编辑器279
9.3.1　定义具体类型279
9.3.2　实现缓冲区的操作280
9.3.3　数组实现的计算复杂度283
9.4　用栈实现编辑器284
9.4.1　定义基于栈的缓冲区的具体结构284
9.4.2　实现缓冲区的操作284
9.4.3　比较计算复杂度287
9.5　用链表实现编辑器288
9.5.1　链表的概念288
9.5.2　设计链表数据结构289
9.5.3　使用链表表示缓冲区290
9.5.4　链表缓冲区中的插入291
9.5.5　链表缓冲区中的删除292
9.5.6　链表表示中的光标移动293
9.5.7　链表的习惯用法295
9.5.8　完成缓冲区实现296
9.5.9　链表缓冲区的计算复杂度299
9.5.10　双向链表300
9.5.11　时间空间的权衡300
9.6　总结301
9.7　复习题301
9.8　编程练习302
第10章　线性结构307
10.1　栈回顾307
10.2　队列313
10.2.1　接口queue.h的结构313
10.2.2　基于数组的队列实现316
10.2.3　队列的链表实现320
10.3　使用队列的仿真324
10.3.1　仿真与模型324
10.3.2　排队模型324
10.3.3　离散时间325
10.3.4　仿真时间中的事件325
10.3.5　实现仿真325
10.4　总结331
10.5　复习题332
10.6　编程练习333
第11章　符号表338
11.1　定义符号表抽象338
11.1.1　选择值和键的类型339
11.1.2　表示未定义项340
11.1.3　符号表接口的初始版本340
11.2　散列342
11.2.1　实现散列表策略342
11.2.2　选择散列函数347
11.2.3　确定桶的数量348
11.3　初级接口的限制348
11.4　使用函数作为数据350
11.4.1　一个一般测绘函数351
11.4.2　声明函数指针与函数类352
11.4.3　实现PlotFunction352
11.4.4　qsort函数352
11.5　映射函数356
11.5.1　映射符号表中的所有项357
11.5.2　实现MapSymbolTable359
11.5.3　向回调函数传递客户数据360
11.6　迭代器361
11.6.1　使用迭代器361
11.6.2　定义迭代器接口362
11.6.3　实现符号表的迭代器抽象363
11.7　命令分派表366
11.8　总结368
11.9　复习题369
11.10　编程练习370
第四部分　递归数据
第12章　递归列表376
12.1　链表的递归表述377
12.2　定义抽象链表类型378
12.2.1　不变类型380
12.2.2　操纵链表结构的函数381
12.2.3　连接多个链表383
12.2.4　不变类型间的内部共享385
12.3　使用链表表示大整数386
12.3.1　bigint.h 接口386
12.3.2　表示类型bigIntADT388
12.3.3　实现bigint包389
12.3.4　使用bigint.h包394
12.4　总结395
12.5　复习题396
12.6　编程练习397
第13章　树400
13.1　家谱树401
13.1.1　描述树的术语401
13.1.2　树的递归特性401
13.1.3　用C语言表示家谱树402
13.2　二叉搜索树403
13.2.1　使用二叉搜索树的底层动机403
13.2.2　在二叉搜索树中查找节点405
13.2.3　在二叉搜索树中插入新节点405
13.2.4　树的遍历408
13.3　平衡树409
13.3.1　树的平衡策略410
13.3.2　举例说明AVL的思想411
13.3.3　单旋转412
13.3.4　双旋转414
13.3.5　实现AVL算法414
13.4　为二叉搜索树定义一般化接口418
13.4.1　允许用户定义节点结构421
13.4.2　一般化用作键的类型424
13.4.3　删除节点424
13.4.4　实现二叉搜索树包425
13.4.5　使用二叉树实现symtab.h接口431
13.5　总结432
13.6　复习题433
13.7　编程练习435
第14章　表达式树442
14.1　解释器概述443
14.2　表达式的抽象结构445
14.2.1　表达式的递归定义445
14.2.2　多义性446
14.2.3　表达式树447
14.2.4　定义表达式的抽象接口448
14.3　定义具体表达式类型451
14.3.1　联合类型451
14.3.2　使用标记的联合表示表达式453
14.3.3　可视化具体表示454
14.3.4　实现构建器和选择器函数456
14.4　语法分析表达式458
14.4.1　语法分析和语法458
14.4.2　不考虑优先级的语法分析459
14.4.3　在语法分析器中加入优先级462
14.5　计算表达式464
14.6　总结467
14.7　复习题467
14.8　编程练习468
第15章　集合479
15.1　为数学抽象的集合479
15.1.1　成员资格480
15.1.2　集合运算480
15.1.3　集合恒等式481
15.2　设计集合接口482
15.2.1　定义元素类型483
15.2.2　编写set.h 接口484
15.2.3　字符集合488
15.2.4　使用指针集合来避免重复488
15.3　实现集合包490
15.4　设计多态迭代器497
15.4.1　泛化迭代器函数的原型497
15.4.2　在迭代器实现中加入多态性497
15.4.3　导出聚集类型498
15.4.4　编码迭代器包502
15.4.5　foreach的习惯用法506
15.5　提高整型集合的效率506
15.5.1　特征向量507
15.5.2　压缩的位数组507
15.5.3　位运算符508
15.5.4　使用位操作符实现特征向量510
15.5.5　实现高级集合操作512
15.5.6　使用混合实现513
15.6　总结513
15.7　复习题514
15.8　编程练习517
第16章　图521
16.1　图的结构521
16.1.1　有向图和无向图523
16.1.2　路径和环524
16.1.3　连通性524
16.2　图的实现策略525
16.2.1　使用邻接列表表示连接526
16.2.2　使用邻接矩阵表示连接529
16.3　扩展图抽象532
16.3.1　将数据与节点和图关联532
16.3.2　显式弧532
16.3.3　迭代和图533
16.3.4　分层抽象534
16.3.5　基于集合的图接口534
16.4　图的遍历543
16.4.1　深度优先遍历543
16.4.2　广度优先搜索545
16.5　寻找最短路径548
16.6　总结554
16.7　复习题555
16.8　编程练习556
第17章　Java的未来563
17.1　面向对象范例563
17.1.1　面向对象编程的历史564
17.1.2　对象、类和方法565
17.1.3　类层次与继承566
17.2　Java入门567
17.2.1　Web结构567
17.2.2　applet568
17.2.3　执行Java applet572
17.3　Java的结构573
17.3.1　Java的语法574
17.3.2　Java中的原子类型575
17.3.3　定义新类575
17.3.4　构造器方法576
17.3.5　this关键字577
17.3.6　定义方法577
17.3.7　定义子类579
17.4　Java中的预定义类586
17.4.1　String类586
17.4.2　Hashtable类587
17.4.3　原子类型的对象包装器589
17.4.4　Vector类590
17.4.5　Stack类591
17.5　创建交互applet的工具592
17.5.1　组件与容器592
17.5.2　action方法593
17.5.3　用于画图形的简单applet594
17.5.4　更进一步602
17.6　总结602
17.7　复习题602
17.8　编程练习604