数据结构与算法分析

前言

第一部分 预备知识

第1章 数据结构和算法

1. 1 数据结构的原则

1. 1. 1 学习数据结构的必要性

1. 1. 2 代价与效益

1, 1. 3 本书的日的

1. 2 抽象数据类型和数据结构

l. 3 问题. 算法和程序

1. 4 算法的效率

1. 5 深入学习导读

1. 6 习题

第2章 数学预备知识

2. 1 集合

2. 2 常用数学术语

2. 3 对数

2. 4 递归

2. 5 级数求和与递归

2. 6 数学证明方法

2. 6. 1 反证法

2. 6. 2 数学归纳法

2. 7 评估

2. 8 深入学习导读

2. 9 习题

第3章 算法分析

3. 1 概述

3. 2 最佳. 最差和平均情况

3. 3 换一台更快的计算机, 还是换一种更快的算法?

3. 4 渐近分析

3. 4. 1 上限

3. 4. 2 厂限

3. 4. 3 表示法

3. 4. 4 简化法则

3. 5 程序运行时间的计算

3. 6 问题的分析

3. 7 多参数问题

3. 8 空间代价

3. 9 实际操作中的一些因素

3. 10 深入学习导读

3. 11 习题

3. 12 项目设计

第二部分 基本数据结构

第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. 3 队列

4. 3. 1 顺序队列

4. 3. 2 链式队列

4. 2. 3 顺序队列与链式队列的比较

4. 4 习题

4. 5 项目设计

第5章 二叉树

5. 1 定义及主要特性

5. 1. 1 满二叉树定理

5. 1. 2 二叉树结点的抽象数据类型

5. 2 周游二叉树

5. 3 二叉树的实现

5. 3. 1 使用指针实现二叉树

5. 3. 2 空间开销

5. 3. 3 使用数组实现完全二叉树

5. 4 Huffman编码树

5. 4. 1 建立Huffman编码树

5. 4. 2 Huffman编码及其用法

5. 5 二叉检索树

5. 6 堆与优先队列

5. 7 深入学习导读

5. 8 习题

5. 9 项目设计

第6章 树

6. 1 树的定义与术语

6. 1. 1 树结点的抽象数据类型

6. 1. 2 树的周游

6. 2 父指针表示法

6. 3 树的实现

6. 3. 1 子结点表表示法

6. 3. 2 左子结点／右兄弟结点表示法

6. 3. 3 动态结点表示法

6. 3. 4 动态“左子结点／右兄弟结点”表示法

6. 4 K叉树

6. 5 树的顺序表示法

6. 6 深入学习导读

6. 7 习题

6. 8 项目设计

第7章 图

7. 1 术语和表示法

7. 2 图的实现

7. 3 图的周游

7. 3. 1 深度优先搜索

7. 3. 2 广度优先搜索

7. 3. 3 拓扑排序

7. 4 最短路径问题

7. 4. 1 单源最短路径

7. 4. 2 每对顶点间的最短路径

7. 5 最小支撑树

7. 5. 1 Prim算泌

7. 5. 2 Kruskal算法

7. 6 深入学习导读

7. 7 习题

7. 8 项目设计

第三部分 排序和检索

第8章 内排序

8. 1 排序的术语及记号

8. 2 三种代价为(n)的排序算法

8. 2. 1 插入排序

8. 2. 2 起泡排序

8. 2. 3 选择排序

8. 2. 4 交换排序算法的时间代价

8. 3 Shell排序

8. 4 快速排序

8. 5 归并排序

8. 6 堆排序

8. 7 分配排序和基数排序

8. 8 对各种排序算法的实验比较

8. 9 排序算法的下限

8. 10 深入学习导读

8. 11 习题

8. 12 项目设计

第9章 文件管理和外排序

9. 1 主存储器和辅助存储器

9. 2 磁盘和磁带

9. 2. 1 磁盘访问开销

9. 2. 2 磁带

9. 3 缓冲区和缓冲池

9. 4 程序员的文件视图

9. 5 外排序

9. 6 外排序的简单方法

9. 7 置换选择排序

9. 8 多路归并

9. 9 深入学习导读

9. 10 习题

9. 11 项目设计

第10章 检索

10. 1 检索已排序的数组

l0. 2 自组织线性表

l0. 3 集合的检索

10. 4 散列方法

l0. 4. 1 散列函数

10. 4. 2 开散列方法

10. 4. 3 闭散列方法

10. 5 深入学习导读

10. 6 习题

10. 7 项日设计

第ll章 索引技术

11. 1 线性索引

11. 2 ISAM

11. 3 树形索引

11. 4 2—3树

11. 5 B树

11. 5. 1 B村

11. 5. 2 B树分析

11. 6 深入学习导读

11. 7 习题

11. 8 2 项目设计

第四部分 应用与高级技术

第12章 线性表和数组的深入研究

12. 1 跳跃表

12. 2 广义表

12. 3 矩阵的表示方法

12. 4 存储管理

12. 4. 1 动态存储分配

12. 4. 2 失败策略和无用单元收集

12. 5 深入学习导读

12. 6 习题

12. 7 项目设计

第13章 高级树结构

13. 1 Trie结构

13. 2 伸展树

13. 3 空间数据结构

13. 3. 1 k—d树

13. 3. 2 PR四分树

t3. 3. 3 其他空间数据结构

13. 4 深入学习导读

13. 5 习题

13. 6 项目设计

第14章 算法分析技术

14. 1 求和技术

14. 2 递归关系

14. 2. 1 估计上下限

14. 2. 2 扩展递归

14. 2. 3 分治法递归

14. 2. 4 快速排序平均情况分析

14. 3 缓冲分析

14. 4 深入学习导读

14. 5 习题

14. 6 项目设计

第15章 计算的限制

15. 1 概述

15. 2 归约

15. 3 难解问题

15. 3. 1 NP完全性

15. 3. 2 绕过NP完全性问题

15. 4 不可解问题

15. 4. 1 不可数性

15. 4. 2 停机问题的不可解性

15. 4. 3 确定程序行为是不可解的

15. 5 深入学习导读

15. 6 习题

15. 7 项目设计

附录A C和Pascal程序员的C十十导引

A. 1 例1：线性表的ADT

A. 2 例2：顺序表的实现

A. 3 例3：链表的实现

A. 4 例4：可利用空间表

A. 5 例5：转化为模板

A. 6 例6：虚函数

附录B 参考书目