C程序设计的抽象思维

写给学生
写给教师
致谢
第一部分 预备知识
第1章 ANSI C概述
1.1 什么是C
1.2 C程序的结构
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.3 if语句
1.5.4 switch语句
1.5.5 while语句
1.5.6 for语句
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.1 random.h接口的结构
3.2.2 构造一个客户程序
3.2.3 ANSI中有关随机数字的函数
3.2.4 实现random.c
3.3 字符串
3.3.1 字符的底层表示
3.3.2 数据类型string
3.3.3 ANSI字符串库
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.9 scanf函数
3.5 其他ANSI库
3.6 总结
3.7 复习题
3.8 编程练习

第二部分 递归和算法分析
第4章 递归入门
4.1 一个简单的递归示例
4.2 阶乘函数
4.2.1 Fact的递归公式
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.4 qsort函数
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.1 bigint.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.5 foreach的习惯用法
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.2 Java入门
17.2.1 Web结构
17.2.2 applet
17.2.3 执行Java applet
17.3 Java的结构
17.3.1 Java的语法
17.3.2 Java中的原子类型
17.3.3 定义新类
17.3.4 构造器方法
17.3.5 this关键字
17.3.6 定义方法
17.3.7 定义子类
17.4 Java中的预定义类
17.4.1 String类
17.4.2 Hashtable类
17.4.3 原子类型的对象包装器
17.4.4 Vector类
17.4.5 Stack类
17.5 创建交互applet的工具
17.5.1 组件与容器
17.5.2 action方法
17.5.3 用于画图形的简单applet
17.5.4 更进一步
17.6 总结
17.7 复习题
17.8 编程练习
……