目录

第1章 编程原则

1.1 引言

1.2 Life游戏

1.2.1 Life游戏规则

1.2.2 示例

1.2.3 解决方案

1.2.4 Life游戏主程序

1.3 编程风格

1.3.1 命名

1.3.2 文档及其格式

1.3.3 程序的细化和模块化

1.3.4 小节练习

1.4.1 占位程序

1.4 编码、测试及进一步细化

1.4.2 计算相邻元胞的数目

1.4.3 输入和输出

1.4.4 驱动程序

1.4.5 程序的跟踪

1.4.6 测试程序的原则

1.4.7 小节练习

1.4.8 编程项目

1.5 注意事项

1.6 复习题

1.7 参考文献

1.7.1 C语言

1.7.2 编程原则

1.7.3 Life游戏

2.1.1 Life程序回顾

第2章 软件工程介绍

2.1 程序维护

2.1.2 关于Life程序的新起点和新方法

2.1.3 小节练习

2.1.4 编程项目

2.2 算法研究：Life程序的第二个版本

2.2.1 列表：数据结构的说明

2.2.2 主程序

2.2.3 信息隐藏

2.2.4 细化：子程序的开发

2.2.5 算法的验证

2.2.6 小节练习

2.3 编码

2.3.1 列表函数

2.3.2 错误处理

2.3.3 演示和测试

2.3.4 小节练习

2.3.5 编程项目

2.4 Life函数的编码

2.4.1 Vivify函数

2.4.2 AddNeighbors函数

2.4.3 混合函数

2.4.4 初始化

2.4.5 编程项目

2.5 程序分析与比较

2.5.1 语句数

2.5.2 比较

2.6 总结和展望

2.5.5 编程项目

2.5.4 小节练习

2.5.3 时间和空间的平衡

2.6.1 Life游戏

2.6.2 程序设计

2.6.3 C语言

2.6.4 编程项目

2.7 注意事项

2.8 复习题

2.9 参考文献

2.9.1 软件工程

2.9.2 算法验证

2.9.3 问题解决

第3章 堆栈和递归

3.1 堆栈

3.1.1 引言

3.1.2 第一个示例：线性颠倒

3.1.3 信息隐藏

3.1.4 堆栈的说明

3.1.5 堆栈的实现

3.1.6 链接堆栈

3.1.7 小节练习

3.1.8 编程项目

3.2 递归

3.2.1 子程序的堆栈图解

3.2.2 子程序调用树

3.2.3 阶乘：一个递归定义

3.2.4 分而治之：汉诺（HANOI）塔

3.2.5 小节练习

3.2.6 编程项目

3.3.1 解决8 王后难题

3.3 回溯：推迟工作

3.3.2 示例：4王后

3.3.3 回溯

3.3.4 细化：选择数据结构

3.3.5 回溯分析

3.3.6 小节练习

3.3.7 编程项目

3.4 递归法则

3.4.1 设计递归算法

3.4.2 递归如何工作

3.4.3 尾部递归

3.4.4 何时不使用递归

3.4.5 指南和总结

3.4.6 小节练习

3.5 注意事项

3.6 复习题

3.7 参考文献

第4章 队列和链表

4.1 定义

4.2 队列的实现

4.3 C语言中的环形队列

4.3.1 小节练习

4.3.2 编程项目

4.4 队列的应用：模拟

4.4.1 引言

4.4.2 机场的模拟

4.4.3 主程序

4.4.4 模拟的步骤

4.4.5 伪随机数

4.4.6 示例结果

4.4.7 编程项目

4.5 指针和链表

4.5.1 引言和综述

4.5.2 指针和C语言中的动态内存

4.5.3 链表基础

4.5.4 小节练习

4.6 链接队列

4.6.1 小节练习

4.6.2 编程项目

4.7 应用：多项式算术

4.7.1 项目的目的

4.7.2 主程序

4.7.3 数据结构及其实现

4.7.4 读取和写出多项式

4.7.5 多项式加法

4.7.6 完成项目

4.7.7 小节练习

4.7.8 编程项目

4.8 抽象数据类型及其实现

4.8.1 引言

4.8.2 通用定义

4.8.3 数据说明的细化

4.8.4 小节练习

4.9 注意事项

4.10 复习题

4.11 参考文献

第5章通 用列表

5.1 列表说明

5.2.1 连续实现

5.2 列表的实现

5.2.2 简单的链接实现

5.2.3 变更：保持当前位置

5.2.4 双向链表

5.2.5 实现的比较

5.2.6 小节练习

5.2.7 编程项目

5.3 字符串

5.4 应用：文本编辑器

5.4.1 说明

5.4.2 实现

5.4.3 编程项目

5.5 数组中的链表

5.5.1 方法

5.5.2 操作：空间管理

5.5.3 其他操作

5.5.4 链表的变化

5.5.5 小节练习

5.6 排列

5.6.1 思想

5.6.2 细化

5.6.3 通用函数

5.6.4 数据结构：优化

5.6.5 最终的程序

5.6.6 编程项目

5.7 注意事项

5.8 复习题

5.9 参考文献

6.1.2 分析

6.1.1 键

第6章 搜索

6.1 搜索：介绍及其表示

6.1.3 外部搜索和内部搜索

6.1.4 C语言实现

6.1.5 参数

6.2 顺序搜索

6.2.1 算法及函数

6.2.2 算法分析

6.2.3 测试

6.2.4 小节练习

6.2.5 编程项目

6.3 寄物处：项目

6.3.1 介绍和说明

6.3.2 演示及测试程序

6.3.3 编程项目

6.4 二叉搜索

6.4.1 算法研究

6.4.2 忽略版本

6.4.3 识别等式

6.4.4 小节练习

6.4.5 编程项目

6.5 比较树

6.5.1 分析n＝10的情况

6.5.2 算法推广

6.5.3 方法的比较

6.5.4 普遍关系

6.6.1 优化程序

6.6 下限

6.5.6 编程项目

6.5.5 小节练习

6.6.2 任意搜索算法

6.6.3 观察2-树

6.6.4 搜索下限

6.6.5 其他的搜索算法

6.6.6 小节练习

6.6.7 编程项目

6.7 渐近线

6.7.1 介绍

6.7.2 Big-O表示法

6.7.3 Big-O表示法的不精确性

6.7.4 通用函数的排序

6.8 注意事项

6.7.6 编程项目

6.7.5 小节练习

6.9 复习题

6.10 参考文献

第7章 排序

7.1 介绍和符号

7.2 插入排序

7.2.1 顺序列表

7.2.2 通常的插入排序

7.2.3 链接版本

7.2.4 分析

7.2.5 小节练习

7.2.6 编程项目

7.3 选择排序

7.3.1 算法

7.3.2 连续实现

7.3.3 分析

7.3.4 比较

7.3.5 小节练习

7.3.6 编程项目

7.4 希尔排序

7.4.1 小节练习

7.4.2 编程项目

7.5 下限

7.5.1 小节练习

7.5.2 编程项目

7.6 “分而治之”排序

7.6.1 主要思想

7.6.2 示例

7.6.3 小节练习

7.7 链表的归并排序

7.7.1 函数

7.7.2 合并分析

7.7.3 小节练习

7.7.4 编程项目

7.8 连续列表的快速排序

7.8.1 主函数

7.8.2 列表的划分

7.8.3 快速排序分析

7.8.4 快速排序的平均情形分析

7.8.5 与归并排序的比较

7.8.6 小节练习

7.9 堆和堆排序

7.9.1 2-树的列表

7.8.7 编程项目

7.9.2 堆排序

7.9.3 堆排序分析

7.9.4 优先级队列

7.9.5 小节练习

7.9.6 编程项目

7.10 回顾：方法的比较

7.10.1 使用的存储空间

7.10.2 计算机时间

7.10.3 编程量

7.10.4 统计分析

7.10.5 实验测试

7.10.6 小节练习

7.12 复习题

7.11 注意事项

7.13 参考文献

第8章 表和信息检索

8.1 引言：突破lgn障碍

8.2 矩形数组

8.2.1 行优先和列优先顺序

8.2.2 下标矩形数组

8.2.3 访问表

8.2.4 小节练习

8.3 各种形状的表

8.3.1 三角表

8.3.2 不规则表

8.3.3 反向表

8.3.4 小节练习

8.4 表：一种新的抽象数据类型

8.4.1 函数

8.3.5 编程项目

8.4.2 抽象数据类型

8.4.3 实现

8.4.4 比较

8.5 应用：基数排序

8.5.1 思想

8.5.2 实现

8.5.3 分析

8.5.4 小节练习

8.5.5 编程项目

8.6 散列

8.6.1 稀疏表

8.6.2 选择散列函数

8.6.3 利用开放寻址的解决方案

8.6.4 冲突的链式解决方案

8.6.5 小节练习

8.6.6 编程项目

8.7 散列分析

8.7.1 一个数学娱乐问题的分析

8.7.2 计数搜索次数

8.7.3 链式方式的分析

8.7.4 开放寻址方式的分析

8.7.5 理论比较

8.7.6 经验比较

8.7.7 小节练习

8.7.8 编程项目

8.8 总结：方法的比较

8.9 应用：回顾Life游戏

8.9.2 数据结构的声明

8.9.1 算法的选择

8.9.3 主程序

8.9.4 函数

8.9.5 编程项目

8.10 注意事项

8.11 复习题

8.12 参考文献

第9章 二叉树

9.1 二叉树的介绍

9.1.1 定义

9.1.2 二叉树的遍历

9.1.3 二叉树的链接实现

9.1.4 小节练习

9.2 二叉搜索树

9.2.1 顺序列表和实现

9.2.2 树搜索

9.2.3 二叉搜索树的插入

9.2.4 树排序

9.2.5 二叉搜索树的删除

9.2.6 小节练习

9.2.7 编程项目

9.3 构建二叉搜索树

9.3.1 开始构建

9.3.2 声明和主函数

9.3.3 插入节点

9.3.4 完成任务

9.3.5 评估

9.3.6 随机搜索树和优化

9.3.7 小节练习

9.4.1 定义

9.4 高度平衡：AVL树

9.4.2 节点的插入

9.4.3 节点的删除

9.4.4 AVL树的高度

9.4.5 小节练习

9.4.6 编程项目

9.5 分裂树：一个自调整数据结构

9.5.1 引言

9.5.2 分裂步骤

9.5.3 分裂算法

9.5.4 平摊算法分析：介绍

9.5.5 分裂的平摊分析

9.5.6 小节练习

9.6 注意事项

9.5.7 编程项目

9.7 复习题

9.8 参考文献

第10章 多路径树

10.1 果园、树和二叉树

10.1.1 树的分类

10.1.2 顺序树

10.1.3 森林和果园

10.1.4 形式映射

10.1.5 旋转

10.1.6 总结

10.1.7 小节练习

10.2 字典搜索树：trie

10.2.1 trie

10.2.3 C语言算法

10.2.2 键的搜索

10.2.4 trie中的插入

10.2.5 trie中的删除

10.2.6 trie的评论

10.2.7 小节练习

10.2.8 编程项目

10.3 外部搜索：B-树

10.3.1 访问时间

10.3.2 多路搜索树

10.3.3 多路平衡树

10.3.4 B-树的插入

10.3.5 C语言算法：搜索和插入

10.3.6 B-树中的删除

10.3.7 小节练习

10.3.8 编程项目

10.4 红黑树

10.4.1 引言

10.4.2 定义和分析

10.4.3 插入

10.4.4 插入的C语言表示

10.4.5 小节练习

10.4.6 编程项目

10.5 树结构程序：游戏中的预测

10.5.1 游戏树

10.5.2 极大极小方法

10.5.3 算法开发

10.5.4 细化

10.5.5 小节练习

10.6 注意事项

10.5.6 编程项目

10.7 复习题

10.8 参考文献

第11章 图

11.1 数学背景

11.1.1 定义和示例

11.1.2 无向图

11.1.3 有向图

11.2 计算机表示

11.3 图的遍历

11.3.1 方法

11.3.2 深度优先算法

11.3.3 宽度优先算法

11.4.1 问题

11.4 拓扑排序

11.4.2 深度优先算法

11.4.3 宽度优先算法

11.5 寻找最短路径的算法

11.5.1 问题

11.5.2 方法

11.5.3 示例

11.5.4 实现

11.6 作为数据结构的图

11.6.1 小节练习

11.6.2 编程项目

11.7 注意事项

11.8 复习题

11.9 参考文献

12.1 问题

第12章 案例分析：波兰表示法

12.2 思想

12.2.1 表达式树

12.2.2 波兰表示法

12.2.3 C语言方法

12.2.4 小节练习

12.3 波兰表达式的求值

12.3.1 前缀表达式的求值

12.3.2 C语言约定

12.3.3 前缀式求值的C函数

12.3.4 后缀表达式的求值

12.3.5 程序的证明：统计堆栈的入口数

12.3.6 后缀表达式的递归求值

12.3.7 小节练习

12.4 从中缀式转换为波兰式

12.4.1 小节练习

12.4.2 编程项目

12.5 交互式表达式求值程序

12.5.1 总体结构

12.5.2 数据的表示方法

12.5.3 初始化和辅助任务

12.5.4 表达式的转换

12.5.5 求解表达式的值

12.5.6 绘制表达式的图形

12.5.7 小节练习

12.5.8 编程项目

12.6 参考文献

附录A 数学方法

附录B 递归的消除

附录C C语言介绍