数据抽象和问题求解:C++语言描述

第1部分 问题解决技术.

第1章 编程原理与软件工程

1．1 问题求解与软件工程

1．1．1 问题求解的含义

1．1．2 软件的生命周期

1．1．3 优秀解决方案的含义

1．2 模块化设计

1．2．1 抽象与信息隐藏

1．2．2 面向对象的设计

1．2．3 自上而下的设计

1．2．4 一般设计原则

1．2．5 使用uml为面向对象的设计建模

1．2．6 面向对象方式的优点

1．3 关键编程问题

1．3．1 模块化

1．3．2 可修改

1．3．3 易用

1．3．4 防故障编程

1．3．5 风格

1．3．6 调试

.1．4 小结

1．5 提示

1．6 自我测试题

1．7 练习题

1．8 编程问题

第2章 递归：镜子

2．1 递归解决方案

2．1．1 递归值函数：n的阶乘

2．1．2 递归void函数：逆置字符串

2．2 计数

2．2．1 兔子繁殖(fibonacci序列)

2．2．2 组织游行队伍

2．2．3 spock的困惑

2．3 数组查找

2．3．1 查找数组的最大项

2．3．2 折半查找

2．3．3 查找数组中的第k个最小项

2．4 组织数据

2．5 递归与效率

2．6 小结

2．7 提示

2．8 自我测试题

2．9 练习题

2．10 编程问题

第3章 数据抽象：墙

3．1 抽象数据类型

3．2 指定adt

3．2．1 adt列表

3．2．2 adt有序表

3．2．3 设计adt

3．2．4 公理

3．3 实现adt

3．3．1 c++类

3．3．2 c++命名空间

3．3．3 基于数组的adt列表实现

3．3．4 c++异常

3．3．5 使用异常的adt列表实现

3．4 小结

3．5 提示

3．6 自我测试题

3．7 练习题

3．8 编程问题

第4章 链表

4．1 预备知识

4．1．1 指针

4．1．2 数组的动态分配

4．1．3 基于指针的链表

4．2 链表编程

4．2．1 显示链表的内容

4．2．2 从链表中删除指定的节点

4．2．3 在链表的指定位置插入节点

4．2．4 adt列表的基于指针的实现

4．2．5 比较基于数组的实现和基于引用的实现

4．2．6 使用文件存储和恢复链表

4．2．7 将链表传给函数

4．2．8 递归地处理链表

4．2．9 把对象作为链表的数据

4．3 链表的各种变化

4．3．1 循环链表

4．3．2 虚拟头节点

4．3．3 双向链表

4．4 清单应用程序

4．5 c++标准模板库

4．5．1 容器

4．5．2 迭代器

4．5．3 标准模板库类list

4．6 小结

4．7 提示

4．8 自我测试题

4．9 练习题

4．10 编程问题

第5章 递归问题解决技术

5．1 回溯

5．1．1 八皇后问题

5．1．2 使用stl类vector解决八皇后问题

5．2 定义语言

5．2．1 语法知识基础

5．2．2 两种简单语言

5．2．3 代数表达式

5．3 递归和数学归纳法的关系

5．3．1 factorial递归算法的正确性

5．3．2 hanoi塔的成本

5．4 小结

5．5 提示

5．6 自我测试题

5．7 练习题

5．8 编程问题

第2部分 使用抽象数据类型解决问题

第6章 栈

6．1 抽象数据类型

6．2 adt栈的简单应用

6．2．1 检查括号匹配

6．2．2 识别语言中的字符串

6．3 adt栈的实现

6．3．1 adt栈的基本数组的实现

6．3．2 adt栈的基于指针的实现

6．3．3 使用adt列表的实现

6．3．4 各种实现方式的比较

6．3．5 标准模板库类stack

6．4 应用：代数表达式

6．4．1 计算后缀表达式

6．4．2 中缀表达式与后缀表达式的等价转换

6．5 应用：查找问题

6．5．1 使用栈的非递归解决方案

6．5．2 递归解决方案

6．6 栈和递归的关系

6．7 小结

6．8 提示

6．9 自我测试题

6．10 练习题

6．11 编程问题..

第7章 队列

7．1 adt队列

7．2 adt队列的简单应用

7．2．1 读取字符串

7．2．2 识别回文

7．3 实现adt队列

7．3．1 基于指针的实现

7．3．2 基于数组的实现

7．3．3 使用adt列表的实现

7．3．4 标准模板库类queue

7．3．5 实现的比较

7．4 基于位置的adt总览

7．5 模拟应用

7．6 小结

7．7 提示

7．8 自我测试题

7．9 练习题

7．10 编程问题

第8章 类关系

8．1 继承

8．1．1 公有、私有利受保护的继承

8．1．2 is-a、has-a和as-a关系

8．2 虚函数和后期绑定

8．3 友元

8．4 adt列表和有序表

8．5 类模板

8．6 重载运算符

8．7 迭代器

8．8 小结

8．9 提示

8．10 自我测试题

8．11 练习题

8．12 编程问题

第9章 算法效率和排序

9．1 确定算法效率

9．1．1 算法的执行时间

9．1．2 算法增率

9．1．3 数量阶分析和大o表示法

9．1．4 正确分析问题，

9．1．5 查找算法的效率

9．2 排序算法及其效率

9．2．1 选择排序

9．2．2 起泡排序

9．2．3 插入排序

9．2．4 归并排序

9．2．5 快速排序

9．2．6 基数排序

9．2．7 各种排序算法的比较

9．2．8 标准模板库排序算法

9．3 小结

9．4 提示

9．5 自我测试题

9．6 练习题

9．7 编程问题

第10章 树

10．1 术语

10．2 adt二叉树

10．2．1 二叉树的遍历

10．2．2 二叉树的表示

10．2．3 adt二叉树的基于指针的实现

10．3 adt二叉查找树

10．3．1 adt二叉查找树操作的算法

10．3．2 adt二叉查找树的基于指针的实现

10．3．3 二叉查找树操作的效率

10．3．4 树排序

10．3．5 将二叉查找树保存到文件

10．3．6 stl查找算法

10．4 一般树

10．5 小结

10．6 提示

10．7 自我测试题

10．8 练习题

10．9 编程问题

第11章 表和优先队列

11．1 adt表

11．1．1 选择实现

11．1．2 adt表的基于数组的有序实现

11．1．3 adt表的二叉查找树实现

11．2 adt优先队列：adt表的变体

11．2．1 堆

11．2．2 adt优先队列的堆实现

11．2．3 堆排序

11．3 stl中的表和优先队列

11．3．1 stl关联容器

11．3．2 stl的priority_queue类和堆算法

11．3 小结

11．4 提示

11．5 自我测试题

11．6 练习题

11．7 编程问题

第12章 表的高级实现

12．1 平衡查找树

12．1．1 2-3树

12．1．2 2-3-4树

12．1．3 红-黑树

12．1．4 avl树

12．2 散列

12．2．1 散列函数

12．2．2 解决冲突

12．2．3 散列的效率

12．2．4 如何确立散列函数

12．2．5 表遍历：散列的低效操作

12．2．6 使用stl实现hashmap类

12．3 按多种形式组织数据

12．4 小结

12．5 提示

12．6 自我测试题

12．7 练习题

12．8 编程问题

第13章 图

13．1 术语

13．2 将图作为adt

13．2．1 实现图

13．2．2 使用stl实现graph类

13．3 图的遍历

13．3．1 深度优先查找

13．3．2 广度优先查找

13．3．3 使用stl实现bfs类

13．4 图的应用

13．4．1 拓扑排序

13．4．2 生成树

13．4．3 最小生成树

13．4．4 最短路径

13．4．5 回路

13．4．6 一些复杂问题

13．5 小结

13．6 提示

13．7 自我测试题

13．8 练习题

13．9 编程问题

第14章 外部方法

14．1 了解外部存储

14．2 排序外部文件的数据

14．3 外部表

14．3．1 确定外部文件的索引

14．3．2 外部散列

14．3．3 b-树

14．3．4 遍历

14．3．5 多索引

14．4 小结

14．5 提示

14．6 自我测试题

14．7 练习题

14．8 编程问题

附录a c++基础

附录b ascii字符代码

附录c c++头文件和标准函数

附录d 数学归纳法

附录e 标准模板库

术语表...

自我测试题答案