A practical introduction to data structures and algorithm analysis

前言

第一部分 预备知识

第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 参考书目