新世纪计算机类本科规划教材 数据结构与算法PDF电子书下载

第1章 绪论 1

1.1 一个问题求解实例 1

1.1.1 交叉路口问题及分析 1

1.1.2 算法设计 3

1.2 数据结构的基本概念及研究内容 4

1.2.1 数据结构的相关概念 4

1.2.2 数据结构的基本内容 5

1.3 算法及算法分析 7

1.3.1 算法的定义 7

1.3.2 算法设计的要求 7

1.3.3 对算法的描述 8

1.3.4 算法的时间分析 8

1.3.5 算法的空间分析 9

习题1 10

第2章 线性表 11

2.1 线性表的逻辑结构 11

2.2 线性表的顺序存储及基本运算的实现 12

2.2.1 线性表的顺序存储结构 12

2.2.2 顺序表上基本运算的实现 13

2.3 线性表的链式存储及基本运算的实现 16

2.3.1 单链表 16

2.3.2 单链表上的基本运算 18

2.3.3 循环链表 23

2.3.4 双向链表 23

2.4 应用举例：一元多项式的表示及相加运算 25

习题2 27

第3章 栈和队列 29

3.1 栈 29

3.1.1 栈的定义及基本运算 29

3.1.2 栈的顺序存储 30

3.1.3 栈的链式存储 32

3.1.4 顺序栈与链栈的比较 34

3.1.5 栈的应用举例 34

3.2 队列 37

3.2.1 队列的定义及基本运算 38

3.2.2 顺序队列 38

3.2.3 链队列 41

3.2.4 队列的应用 43

习题3 48

第4章 串、数组和广义表 50

4.1 串 50

4.1.1 串的基本概念 50

4.1.2 串的存储结构 51

4.1.3 串的基本操作 53

4.2 串的模式匹配 55

4.2.1 BF算法 55

4.2.2 KMP算法 57

4.3 数组 59

4.3.1 数组的基本概念 59

4.3.2 数组的存储结构 60

4.4 矩阵的存储 61

4.4.1 特殊矩阵的压缩存储 62

4.4.2 稀疏矩阵的压缩存储 65

4.5 广义表 68

4.5.1 广义表的基本概念 68

4.5.2 广义表的存储结构 69

习题4 72

第5章 树与二叉树 73

5.1 树的定义及基本概念 73

5.2 二叉树 75

5.2.1 二叉树的定义 75

5.2.2 二叉树的性质 75

5.2.3 二叉树的存储结构 77

5.3 二叉树的遍历及线索二叉树 78

5.3.1 二叉树的遍历 78

5.3.2 线索二叉树 80

5.4 应用举例：哈夫曼树及其应用 83

5.4.1 最优二叉树（哈夫曼树） 83

5.4.2 哈夫曼编码 87

5.5 树、森林与二叉树的转换关系 89

5.5.1 树的存储结构 89

5.5.2 树、森林与二叉树的转换 90

习题5 92

第6章 图 95

6.1 图的基本概念 95

6.1.1 图的定义 95

6.1.2 基本术语 96

6.2 图的存储结构 97

6.2.1 邻接矩阵表示法 97

6.2.2 邻接链表表示法 98

6.3 图的遍历 100

6.3.1 深度优先遍历 100

6.3.2 广度优先遍历 101

6.4 生成树与最小生成树 103

6.4.1 生成树 103

6.4.2 最小生成树 103

6.5 拓扑排序和关键路径 109

6.5.1 拓扑排序 109

6.5.2 关键路径 111

6.6 单源最短路径 115

习题6 118

第7章 查找 120

7.1 基本概念 120

7.2 静态查找 121

7.2.1 顺序查找 121

7.2.2 二分查找 122

7.2.3 分块查找 125

7.3 动态查找 125

7.3.1 二叉排序树 126

7.3.2 平衡二叉树 133

7.3.3 B树和B＋树的基本概念 136

7.4 哈希表查找 138

7.4.1 哈希表的定义 138

7.4.2 哈希函数的构造 139

7.4.3 解决冲突的方法 141

7.4.4 哈希表的查找及性能分析 143

习题7 144

第8章 排序 146

8.1 基本概念 146

8.2 插入排序 147

8.2.1 直接插入排序 147

8.2.2 希尔排序 149

8.3 交换排序 150

8.3.1 冒泡排序 150

8.3.2 快速排序 151

8.4 选择排序 154

8.4.1 简单选择排序 154

8.4.2 堆排序 155

8.5 归并排序 160

8.6 基数排序 161

8.6.1 多关键字排序 161

8.6.2 链式基数排序 162

8.7 各种内部排序方法的比较 165

8.8 外部排序 165

8.8.1 外存信息的存取 166

8.8.2 外部排序的基本方法 166

习题8 167

第9章 文件 170

9.1 文件的基本概念 170

9.1.1 文件的逻辑结构及操作 171

9.1.2 文件的存储结构 171

9.2 顺序文件 172

9.3 索引文件 174

9.4 散列文件 175

9.5 多关键字文件 176

9.5.1 多重表文件 176

9.5.2 倒排文件 178

习题9 179

第10章 算法设计方法 180

10.1 穷举法 180

10.2 递推法 181

10.3 迭代法 181

10.4 递归法 182

10.5 分治法 183

10.6 回溯法 184

10.7 分支限界法 186

10.8 动态规划法 187

10.9 贪心法 188

习题10 189

参考文献 191