C程序设计的抽象思维

《C语言经典译丛：C程序设计的抽象思维》是一本关于C语言的经典图书。本书共计17章，分为4部分，第一部分概述计算机导论课程中涉及的基本编程概念；第二部分讨论递归算法，其中结合大量示例，有助于读者轻松理解和掌握晦涩的概念；第三部分不仅介绍了用非递归算法实现的抽象数据类型，还提供了一些工具，有助于读者理解数据抽象的概念；第四部分重点介绍采用递归算法实现的抽象数据类型。本书重点突出，全面讲解了C语言的基本概念，深入剖析了具体的编程思路，揭示了独特的编程策略和技术细节。本书旨在通过介绍编程过程中遇到的难点和问题，来拓宽视野。本书结合具体的示例代码，由浅入深，介绍解决编程问题的策略和方法，有助于读者快速入门C语言编程。同时，每一章后面都有配套的复习题和编程练习，便于读者理论练习实践，通过编程实践查漏补缺，温故而知新。

《C语言经典译丛：C程序设计的抽象思维》适合希望学习C语言的初学者和中高级程序员阅读。

写给学生

写给教师

致谢

第一部分预备知识

第1章ANSIC概述

1.1什么是C

1.2C程序的结构

1.2.1注释

1.2.2包含的库文件

1.2.3程序级的定义

1.2.4函数原型

1.2.5主程序

1.2.6函数定义

1.3变量、值和类型

1.3.1变量

1.3.2命名规则

1.3.3局部变量和全局变量

1.3.4数据类型的概念

1.3.5整数类型

1.3.6浮点类型

1.3.7文本类型

1.3.8布尔类型

1.3.9简单输入输出

1.4表达式

1.4.1优先级与结合性

1.4.2表达式中的类型混合

1.4.3整数除法和求余运算

1.4.4类型转换

1.4.5赋值运算符

1.4.6递增与递减运算符

1.4.7布尔运算符

1.5语句

1.5.1简单语句

1.5.2块

1.5.3if语句

1.5.4switch语句

1.5.5while语句

1.5.6for语句

1.6函数

1.6.1返回函数结果

1.6.2函数定义和原型

1.6.3函数调用过程的机制

1.6.4逐步求精

1.7总结

1.8复习题

1.9编程练习

第2章C的数据类型

2.1枚举类型

2.1.1枚举类型的内部表示

2.1.2标量类型

2.1.3理解typedef

2.2数据和内存

2.2.1位、字节、字

2.2.2内存地址

2.3指针

2.3.1把地址当作数值

2.3.2声明指针变量

2.3.3基本的指针运算

2.3.4特殊指针NULL

2.3.5传递引用

2.4数组

2.4.1声明数组

2.4.2数组选择

2.4.3分配的空间和利用的空间

2.4.4把数组作为参数

2.4.5初始化数组

2.4.6多维数组

2.5指针和数组

2.5.1指针运算

2.5.2指针的自加和自减

2.5.3指针和数组的关系

2.6记录

2.6.1定义一种新的结构类型

2.6.2声明结构变量

2.6.3记录选择

2.6.4初始化纪录

2.6.5记录的指针

2.7动态分配

2.7.1类型void

2.7.2对内存限制的处理

2.7.3动态数组

2.7.4动态记录

2.8总结

2.9复习题

2.10编程练习

第3章库和接口

3.1接口的概念

3.1.1接口和实现

3.1.2包和抽象

3.1.3良好的接口设计规则

3.2随机数字

3.2.1random.h接口的结构

3.2.2构造一个客户程序

3.2.3ANSI中有关随机数字的函数

3.2.4实现random.c

3.3字符串

3.3.1字符的底层表示

3.3.2数据类型string

3.3.3ANSI字符串库

3.3.4接口strlib.h

3.4标准的I/O库

3.4.1数据文件

3.4.2在C中使用文件

3.4.3标准文件

3.4.4字符I/O

3.4.5从输入文件中重读字符

3.4.6更新文件

3.4.7面向行的I/O

3.4.8格式化的I/O

3.4.9scanf函数

3.5其他ANSI库

3.6总结

3.7复习题

3.8编程练习

第二部分递归和算法分析

第4章递归入门

4.1一个简单的递归示例

4.2阶乘函数

4.2.1Fact的递归公式

4.2.2追踪递归过程

4.2.3递归跳跃的信任

4.3费波那契函数

4.3.1计算费波那契序列

4.3.2增进实现递归的信心

4.3.3递归实现的效率

4.3.4不应该责备递归

4.4其他递归示例

4.4.1探测回文

4.4.2二分查找

4.4.3交互递归

4.5递归的思考

4.5.1保持整体观

4.5.2避免常见的陷阱

4.6总结

4.7复习题

4.8编程练习

第5章递归过程

5.1汉诺塔

5.1.1分解问题

5.1.2寻找递归策略

5.1.3证实递归策略

5.1.4编码解决方案

5.1.5追踪递归过程

5.2产生排列

5.3递归的绘图应用

5.3.1绘图库

5.3.2电脑艺术示例

5.3.3不规则碎片形

5.4总结

5.5复习题

5.6编程练习

第6章回溯算法

6.1用递归回溯解决迷宫问题

6.1.1右手规则

6.1.2寻找递归方法

6.1.3识别简单情景

6.1.4迷宫解决方案算法编码

6.1.5确信解决方案可以正确运行

6.2回溯与对策

6.2.1拿子游戏

6.2.2一般化的双人游戏程序

6.2.3最小最大策略

6.2.4实现最小最大化算法

6.2.5在具体的游戏中采用一般化策略

6.3总结

6.4复习题

6.5编程练习

第7章算法分析

7.1排序问题

7.1.1选择排序算法

7.1.2性能的经验度量

7.1.3分析选择排序的性能

7.2计算复杂度

7.2.1大O符号

7.2.2大O的标准简化

7.2.3排序算法的计算复杂度

7.2.4根据代码结构预测计算复杂度

7.2.5最差情况复杂度与平均情况复杂度

7.2.6大O的正式定义

7.3递归帮助

7.3.1分治策略的威力

7.3.2合并两个数组

7.3.3合并排序算法

7.3.4合并排序的计算复杂度

7.3.5比较N2和NlogN的性能

7.4标准复杂度类型

7.5快速排序算法

7.5.1分割数组

7.5.2分析快速排序的性能

7.6数学归纳法

7.7总结

7.8复习题

7.9编程练习

第三部分数据抽象

第8章抽象数据类型

8.1栈

8.1.1栈的基本概念

8.1.2栈和函数调用

8.1.3栈和袖珍计算器

8.2定义栈的ADT

8.2.1定义栈抽象的类型

8.2.2不透明类型

8.2.3定义stack.h接口

8.3在应用中使用栈

8.4实现栈抽象

8.4.1定义具体类型

8.4.2实现栈操作

8.4.3不透明类型的优点

8.4.4改进stack.c的实现

8.5定义一个scannerADT

8.5.1封装状态的危险

8.5.2抽象数据类型作为封装状态的替代

8.5.3实现扫描器抽象

8.6总结

8.7复习题

8.8编程练习

第9章效率与ADT

9.1编辑器缓冲区的概念

9.2定义缓冲区抽象

9.2.1接口buffer.h中的函数

9.2.2为编辑器应用编写代码

9.3用数组实现编辑器

9.3.1定义具体类型

9.3.2实现缓冲区的操作

9.3.3数组实现的计算复杂度

9.4用栈实现编辑器

9.4.1定义基于栈的缓冲区的具体结构

9.4.2实现缓冲区的操作

9.4.3比较计算复杂度

9.5用链表实现编辑器

9.5.1链表的概念

9.5.2设计链表数据结构

9.5.3使用链表表示缓冲区

9.5.4链表缓冲区中的插入

9.5.5链表缓冲区中的删除

9.5.6链表表示中的光标移动

9.5.7链表的习惯用法

9.5.8完成缓冲区实现

9.5.9链表缓冲区的计算复杂度

9.5.10双向链表

9.5.11时间空间的权衡

9.6总结

9.7复习题

9.8编程练习

第10章线性结构

10.1栈回顾

10.2队列

10.2.1接口queue.h的结构

10.2.2基于数组的队列实现

10.2.3队列的链表实现

10.3使用队列的仿真

10.3.1仿真与模型

10.3.2排队模型

10.3.3离散时间

10.3.4仿真时间中的事件

10.3.5实现仿真

10.4总结

10.5复习题

10.6编程练习

第11章符号表

11.1定义符号表抽象

11.1.1选择值和键的类型

11.1.2表示未定义项

11.1.3符号表接口的初始版本

11.2散列

11.2.1实现散列表策略

11.2.2选择散列函数

11.2.3确定桶的数量

11.3初级接口的限制

11.4使用函数作为数据

11.4.1一个一般测绘函数

11.4.2声明函数指针与函数类

11.4.3实现PlotFunction

11.4.4qsort函数

11.5映射函数

11.5.1映射符号表中的所有项

11.5.2实现MapSymbolTable

11.5.3向回调函数传递客户数据

11.6迭代器

11.6.1使用迭代器

11.6.2定义迭代器接口

11.6.3实现符号表的迭代器抽象

11.7命令分派表

11.8总结

11.9复习题

11.10编程练习

第四部分递归数据

第12章递归列表

12.1链表的递归表述

12.2定义抽象链表类型

12.2.1不变类型

12.2.2操纵链表结构的函数

12.2.3连接多个链表

12.2.4不变类型间的内部共享

12.3使用链表表示大整数

12.3.1bigint.h接口

12.3.2表示类型bigIntADT

12.3.3实现bigint包

12.3.4使用bigint.h包

12.4总结

12.5复习题

12.6编程练习

第13章树

13.1家谱树

13.1.1描述树的术语

13.1.2树的递归特性

13.1.3用C语言表示家谱树

13.2二叉搜索树

13.2.1使用二叉搜索树的底层动机

13.2.2在二叉搜索树中查找节点

13.2.3在二叉搜索树中插入新节点

13.2.4树的遍历

13.3平衡树

13.3.1树的平衡策略

13.3.2举例说明AVL的思想

13.3.3单旋转

13.3.4双旋转

13.3.5实现AVL算法

13.4为二叉搜索树定义一般化接口

13.4.1允许用户定义节点结构

13.4.2一般化用作键的类型

13.4.3删除节点

13.4.4实现二叉搜索树包

13.4.5使用二叉树实现symtab.h接口

13.5总结

13.6复习题

13.7编程练习

第14章表达式树

14.1解释器概述

14.2表达式的抽象结构

14.2.1表达式的递归定义

14.2.2多义性

14.2.3表达式树

14.2.4定义表达式的抽象接口

14.3定义具体表达式类型

14.3.1联合类型

14.3.2使用标记的联合表示表达式

14.3.3可视化具体表示

14.3.4实现构建器和选择器函数

14.4语法分析表达式

14.4.1语法分析和语法

14.4.2不考虑优先级的语法分析

14.4.3在语法分析器中加入优先级

14.5计算表达式

14.6总结

14.7复习题

14.8编程练习

第15章集合

15.1为数学抽象的集合

15.1.1成员资格

15.1.2集合运算

15.1.3集合恒等式

15.2设计集合接口

15.2.1定义元素类型

15.2.2编写set.h接口

15.2.3字符集合

15.2.4使用指针集合来避免重复

15.3实现集合包

15.4设计多态迭代器

15.4.1泛化迭代器函数的原型

15.4.2在迭代器实现中加入多态性

15.4.3导出聚集类型

15.4.4编码迭代器包

15.4.5foreach的习惯用法

15.5提高整型集合的效率

15.5.1特征向量

15.5.2压缩的位数组

15.5.3位运算符

15.5.4使用位操作符实现特征向量

15.5.5实现高级集合操作

15.5.6使用混合实现

15.6总结

15.7复习题

15.8编程练习

第16章图

16.1图的结构

16.1.1有向图和无向图

16.1.2路径和环

16.1.3连通性

16.2图的实现策略

16.2.1使用邻接列表表示连接

16.2.2使用邻接矩阵表示连接

16.3扩展图抽象

16.3.1将数据与节点和图关联

16.3.2显式弧

16.3.3迭代和图

16.3.4分层抽象

16.3.5基于集合的图接口

16.4图的遍历

16.4.1深度优先遍历

16.4.2广度优先搜索

16.5寻找最短路径

16.6总结

16.7复习题

16.8编程练习

第17章Java的未来

17.1面向对象范例

17.1.1面向对象编程的历史

17.1.2对象、类和方法

17.1.3类层次与继承

17.2Java入门

17.2.1Web结构

17.2.2applet

17.2.3执行Javaapplet

17.3Java的结构

17.3.1Java的语法

17.3.2Java中的原子类型

17.3.3定义新类

17.3.4构造器方法

17.3.5this关键字

17.3.6定义方法

17.3.7定义子类

17.4Java中的预定义类

17.4.1String类

17.4.2Hashtable类

17.4.3原子类型的对象包装器

17.4.4Vector类

17.4.5Stack类

17.5创建交互applet的工具

17.5.1组件与容器

17.5.2action方法

17.5.3用于画图形的简单applet

17.5.4更进一步

17.6总结

17.7复习题

17.8编程练习

……