算法与数据结构：C语言版

前言

第1章 概论

1. 1 引言

1. 1. 1 解决问题的步骤

1. 1. 2 一个例子

1. 2 数据结构

1. 2. 1 为什么要学习数据结构

1. 2. 2 有关概念和术语

1. 3 抽象数据类型

1. 4 类C语言描述

1. 5 算法和算法分析

1. 5. 1 算法的定义及算法设计的要求

1. 5. 2 算法与数据结构和程序

1. 5. 3 算法性能分析与度量

1. 5. 4 复杂度函数的增长率

1. 5. 5 复杂度分析的例子

第2章 线性表

2. 1 线性表的类型定义

2. 1. 1 线性表的概念

2. 1. 2 线性表的抽象数据类型

2. 1. 3 线性表的例子

2. 2 线性表的顺序表示和实现

2. 2. 1 线性表的顺序表示

2. 2. 2 顺序表操作的实现

2. 3 线性表的链式表示和实现

2. 3. 1 单链表的表示

2. 3. 2 线性链表操作的实现

2. 4 线性表实现方法的比较

2. 5 循环链表

2. 6 双链表

2. 7 静态链表

*2. 8 算法设计举例

第3章 栈和队列

3. 1 栈

3. 1. 1 栈的类型定义

3. 1. 2 栈的表示和实现

3. 1. 3 顺序栈和链栈的比较

3. 2 队列

3. 2. 1 队列的类型定义

3. 2. 2 循环队列

3. 2. 3 链队--队列的链式表示

和实现

*3. 3 递归

3. 3. 1 递归的定义

3. 3. 2 递归的实现

3. 3. 3 递归和迭代

3. 3. 4 递归的消除

*3. 4 算法设计举例

第4章 串

4. 1 串的类型定义

4. 2 串的表示和实现

4. 2. 1 串的顺序存储结构

4. 2. 2 串的链式存储结构

*4. 3 串的模式匹配

4. 3. 1 朴素的模式匹配算法

4. 3. 2 首尾模式匹配算法

4. 3. 3 KMP算法

4. 4 串的应用举例

*4. 5 算法设计举例

第5章 数组和广义表

5. 1 数组的概念及其基本操作

5. 2 数组的顺序存储

5. 3 矩阵的压缩存储

5. 3. 1 特殊矩阵

5. 3. 2 稀疏矩阵

*5. 4 广义表

5. 4. 1 广义表的定义

5. 4. 2 广义表的存储结构

*5. 5 算法设计举例

第6章 树

6. 1 树的概念及操作

6. 2 二叉树

6. 2. 1 叉树的概念及操作

6. 2. 2 二叉树的性质

6. 2. 3 二叉树的存储结构

6. 3 二叉树的遍历

*6. 4 线索二叉树

6. 5 树和森林

6. 5. 1 树的存储结构

6. 5. 2 森林. 树. 二叉树

的相互转换

6. 5. 3 树和森林的遍历

6. 6 哈夫曼树及其应用

6. 6. 1 最优二叉树(哈夫曼树)

6. 6. 2 哈夫曼编码

*6. 7 算法设计举例

第7章 图

7. 1 图的定义和术语

7. 2 图的存储结构

7. 2. 1 数组表示法

7. 2. 2 邻接表

*7. 2. 3 十字链表

*7. 2. 4 邻接多重表

7. 3 图的遍历

7. 3. 1 深度优先搜索

7. 3. 2 广度优先搜索

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. 7 网络流问题

*7. 8 算法设计举例

第8章 动态存储管理

8. 1 概述

8. 2 可利用空间表及分配方法

8. 3 边界标识法

8. 4 伙伴系统

第9章 集合

9. 1 概述

9. 2 线性表上的查找

9. 2. 1 顺序表的查找

9. 2. 2 有序表的查找

9. 3 索引表上的查找

9. 4 树表上的查找

9. 4. 1 二叉排序树

9. 4. 2 平衡二叉树

*9. 4. 3 B-树

*9. 4. 4 键树

9. 5 哈希表

9. 5. 1 哈希表查找的基本概念

9. 5. 2 构造哈希函数的方法

9. 5. 3 哈希冲突的解决方法

9. 5. 4 哈希表的查找及分析

*9. 6 算法设计举例

第10章 排序

10. 1 概述

10. 2 插入排序

10. 2. 1 直接插入排序

10. 2. 2 折半插入排序

*10. 2. 3 二路插入排序

*10. 2. 4 表插入排序

10. 2. 5 希尔排序

10. 3 交换排序

10. 3. 1 起泡排序

10. 3. 2 快速排序

10. 4 选择排序

10. 4. 1 直接选择排序

10. 4. 2 树形选择排序

10. 4. 3 堆排序

10. 5 归并排序

10. 6 分配排序

10. 7 各种内部排序方法的比较

10. 8 外部排序

10. 8. 1 文件管理

10. 8. 2 外部排序的方法

10. 8. 3 多路平衡归并排序

10. 8. 4 置换选择排序

*10. 8. 5 最佳归并树

*10. 8. 6 磁带排序

*10. 9 算法设计举例

第11章 文件

11. 1 文件的基本概念

11. 2 顺序文件

11. 3 索引文件

11. 4 索引顺序文件

11. 4. 1 ISAM文件

*11. 4. 2 VSAM文件

11. 5 散列文件

*11. 6 多关键字文件

11. 6. 1 多重表文件

11. 6. 2 倒排文件

参考书目