计算机软件技术基础：高级程序设计

第1章 概述

1. 1 软件的基本概念

1. 1. 1 软件应用

1. 1. 2 软件危机与神话

1. 2 软件技术

1. 3 程序设计技术

1. 3. 1 明确需求

1. 3. 2 设计

1. 3. 3 编码

1. 3. 4 测试

1. 4 程序性能考虑

1. 5 数据结构与算法设计

1. 5. 1 数据结构的引入

1. 5. 2 数据结构的基本概念

1. 5. 3 数据结构与算法

1. 5. 4 算法及其复杂性

1. 6 设计程序所需的基础知识和基本能力

习题

第2章 高级程序设计方法

2. 1 引言

2. 2 程序设计的关键技术

2. 2. 1 程序结构设计

2. 2. 2 模块设计

2. 3 程序设计步骤

2. 4 程序设计实例

2. 4. 1 问题与分析

2. 4. 2 处理问题的流程与问题分解

2. 4. 3 程序结构

2. 4. 4 模块设计

2. 4. 5 数据结构设计

2. 4. 6 程序的实现

2. 4. 7 完整程序

习题

第3章 编写好程序

3. 1 命名

3. 2 表达式和语句

3. 3 一致性和习惯用法

3. 4 函数宏

3. 5 神秘的数

3. 6 注释

3. 7 界面

3. 7. 1 一个原型库

3. 7. 2 通用函数库设计

3. 7. 3 界面原则

3. 7. 4 资源管理

3. 7. 5 用户界面

习题

第4章 排错与测试

4. 1 排错

4. 1. 1 排错系统

4. 1. 2 寻找错误线索

4. 1. 3 无线索, 难办的错误

4. 1. 4 最后的手段

4. 1. 5 不可重现的错误

4. 1. 6 其他人的程序错误

4. 2 测试

4. 2. 1 在编码过程中测试

4. 2. 2 系统化测试

4. 2. 3 测试自动化

4. 2. 4 测试环境

4. 2. 5 应力测试

4. 2. 6 测试秘诀

4. 2. 7 测试用例设计的一般原则

4. 2. 8 测试用例设计的具体方法

习题

第5章 程序性能

5. 1 瓶颈

5. 2 计时与轮廓

5. 2. 1 自动计时测量

5. 2. 2 使用轮廓程序

5. 3 加速策略

5. 4 代码调整

5. 5 存储优化

习题

第6章 线性表

6. 1 线性表的基本概念及运算

6. 2 顺序表

6. 2. 1 顺序表的基本运算

6. 2. 2 顺序表的应用实例--学生学籍档案管理

6. 3 链表

6. 3. 1 单链表

6. 3. 2 单链表的基本运算

6. 3. 3 循环链表

6. 3. 4 向链表

6. 3. 5 链表应用实例--多项式的表示及运算

习题

第7章 串和数组

7. 1 串及其运算

7. 2 串的存储结构

7. 3 串运算的实现

7. 3. 1 基本运算的实现

7. 3. 2 改进的模式匹配算法

7. 4 数组的定义和运算

7. 5 数组的顺序存储结构

7. 6 矩阵的压缩存储

7. 6. 1 特殊矩阵

7. 6. 2 稀疏矩阵

习题

第8章 栈和队列

8. 1 栈

8. 1. 1 栈的顺序存储表示--顺序栈

8. 1. 2 栈的链式存储结构--链栈

8. 1. 3 栈的应用

8. 2 队列

8. 2. 1 队列的存储结构

8. 2. 2 队列应用举例

习题

第9章 树

9. 1 树的基本概念

9. 2 二叉树

9. 3 二叉树的存储结构

9. 3. 1 顺序存储结构

9. 3. 2 链式存储结构

9. 3. 3 二叉树建立

9. 4 二叉树的遍历

9. 4. 1 二叉树的深度优先遍历

9. 4. 2 二叉树的广度优先遍历

9. 4. 3 深度优先的非递归算法

9. 4. 4 从遍历序列恢复二叉树

9. 4. 5 遍历算法的应用

9. 5 树和森林

9. 5. 1 树的存储结构

9. 5. 2 树. 森林和二叉树之间的转换

9. 6 线索二叉树

9. 6. 1 线索二叉树的建立

9. 6. 2 访问线索二叉树

9. 7 二叉树的应用

9. 7. 1 哈夫曼树及应用

9. 7. 2 二叉排序树

习题

第10章 图

10. 1 图的基本概念

10. 2 图的存储方法

10. 2. 1 邻接矩阵

10. 2. 2 邻接表

10. 3 图的遍历

10. 3. 1 深度优先搜索遍历

10. 3. 2 广度优先搜索遍历

10. 4 生成树和最小生成树

10. 5 最短路径

10. 5. 1 从某个源点到其余各顶点的最短路径

10. 5. 2 每一对顶点之间的最短路径

10. 6 拓扑排序

10. 7 关键路径

习题

第11章 索引结构与散列技术

11. 1 索引结构

11. 1. 1 线性索引

11. 1. 2 倒排表

11. 1. 3 多级索引

11. 2 散列技术

11. 2. 1 散列表的概念

11. 2. 2 散列函数的构造

11. 2. 3 解决冲突的几种方法

11. 2. 4 散列表的查找及分析

习题

第12章 缩小规模算法

12. 1 分治与递归算法

12. 1. 1 递归算法设计

12. 1. 2 分治算法设计

12. 2 动态规划

12. 2. 1 动态规划算法的基本要素

12. 2. 2 动态规划应用--图像压缩

12. 2. 3 最优二叉搜索树

12. 3 贪心算法

12. 3. 1 贪心算法与动态规划算法的差异

12. 3. 2 贪心算法应用之哈夫曼编码

12. 3. 3 贪心算法应用之单源最短路径

习题

第13章 搜索算法

13. 1 回溯法

13. 1. 1 回溯法的算法框架

13. 1. 2 最大团问题

13. 1. 3 图的m着色问题

13. 1. 4 旅行售货员问题

13. 2 分支界限法

13. 2. 1 分支界限法的基本思想

13. 2. 2 装载问题

13. 2. 3 布线问题

习题

第14章 难问题求解算法

14. 1 概率算法

14. 1. 1 数值概率算法

14. 1. 2 舍伍德算法

14. 1. 3 拉斯维加斯算法

14. 1. 4 蒙特卡罗算法

14. 2 近似算法

14. 2. 1 顶点覆盖问题的近似算法

14. 2. 2 旅行售货员问题的近似算法

14. 2. 3 集合覆盖问题的近似算法

习题

参考文献