算法与数据结构 C与C++描述PDF电子书下载

第1章 绪论 1

1.1 基本概念与术语 1

1.1.1 数据和数据结构 1

1.1.2 数据结构的研究内容 4

1.2 抽象数据类型 4

1.3 算法与算法分析 6

1.3.1 问题、算法和程序 6

1.3.2 算法分析 7

习题 11

第2章 线性结构 13

2.1 线性结构及其抽象数据类型ADT定义 13

2.1.1 线性表的定义 13

2.1.2 线性表的基本运算 14

2.1.3 线性表的ADT定义 16

2.2 线性表的存储和操作的实现 17

2.2.1 线性表的顺序存储 17

2.2.2 顺序存储结构下线性表运算的实现 19

2.2.3 线性表的链式存储结构 26

2.2.4 线性链表的操作 27

2.2.5 线性表的应用 28

2.3 数组的定义和存储 34

2.3.1 一维数组 34

2.3.2 多维数组 35

2.3.3 数组的存储结构 37

2.3.4 矩阵运算的实现 39

2.4 特殊矩阵的存储及其运算的实现 41

2.4.1 稀疏矩阵 41

2.4.2 稀疏矩阵的三元组表示 41

2.4.3 稀疏矩阵的抽象数据类型ADT定义 42

2.4.4 稀疏矩阵的存储结构 43

2.4.5 特殊矩阵的压缩存储 52

习题 54

第3章 堆栈和队列 56

3.1 堆栈的概念及其运算 56

3.1.1 堆栈的定义 56

3.1.2 栈的抽象数据类型ADT定义 57

3.1.3 堆栈的存储结构 59

3.2 队列的概念及其运算 64

3.2.1 队列的定义 64

3.2.2 队列的抽象数据类型ADT 65

3.2.3 队列的存储结构 66

3.3 应用实例 73

3.3.1 栈与递归 74

3.3.2 表达式的求值 78

3.3.3 离散事件模拟 85

习题 86

第4章 链表 88

4.1 线性链表 88

4.1.1 结点和链表概念 88

4.1.2 单向链表的存储和操作实现 89

4.1.3 线性链表举例 98

4.1.4 静态链表及其操作实现 101

4.1.5 链式堆栈和队列的操作实现 109

4.1.6 循环链表 114

4.1.7 双向链表及其运算 115

4.2 非线性链表 120

4.2.1 超文本模型 120

4.2.2 十字链表 120

4.2.3 广义表 123

4.3 链表应用 131

4.4 文件概念及其操作 136

4.4.1 文件概述 136

4.4.2 文件的存储媒介 137

4.4.3 文件的基本操作 140

4.4.4 文件的基本物理存储方式 140

习题 141

第5章 串 143

5.1 串的概念及其ADT定义 143

5.1.1 串的概念 143

5.1.2 串的ADT定义 144

5.2 串的存储结构 144

5.2.1 串的顺序存储结构 145

5.2.2 堆分配存储结构 145

5.2.3 块链存储结构 147

5.3 串的模式匹配算法 148

5.3.1 模式匹配函数的实现 148

5.3.2 模式匹配的一种改进算法 149

习题 153

第6章 树和二叉树 154

6.1 树的定义和基本术语 154

6.1.1 树的形式定义 154

6.1.2 树的基本术语 155

6.1.3 树的ADT定义 155

6.2 树的存储结构 157

6.2.1 树的线性存储 157

6.2.2 树的链式存储 159

6.2.3 基本操作的实现 160

6.3 二叉树 161

6.3.1 二叉树定义及其基本性质 161

6.3.2 二叉树的存储实现 162

6.3.3 基本操作的实现 164

6.4 二叉树的遍历 164

6.4.1 二叉树的遍历 164

6.4.2 二叉树的非递归实现 167

6.4.3 线索树 168

6.4.4 树的遍历 170

6.4.5 树、森林和二叉树的相互转换 171

6.5 Huffman树与Huffman编码 173

6.5.1 最优二叉树 173

6.5.2 Huffman编码 175

6.5.3 Huffman编码的存储和算法实现 177

习题 179

第7章 图 181

7.1 图的基本概念和ADT定义 181

7.1.1 图的定义 181

7.1.2 图的术语 182

7.1.3 图的ADT定义 184

7.2 图的存储结构 185

7.2.1 图的数组存储结构——邻接矩阵 185

7.2.2 图的链式存储结构(一)——邻接表 186

7.2.3 图的链式存储结构(二)——邻接多重表 188

7.3 图的遍历 190

7.3.1 深度优先搜索 190

7.3.2 广度优先搜索 191

7.4 最小生成树 192

7.4.1 最小生成树概念 193

7.4.2 Prim算法 194

7.4.3 Kruskal算法 195

7.5 拓扑排序 196

7.5.1 有向无环图 196

7.5.2 拓扑排序 197

7.5.3 关键路径 198

7.6 图的最短路径 204

7.6.1 从某个源点到其余各顶点的最短路径 204

7.6.2 所有顶点间的最短路径 207

习题 209

第8章 排序 213

8.1 概述 213

8.2 插入排序 214

8.2.1 直接插入排序 214

8.2.2 折半插入排序 215

8.2.3 希尔排序 216

8.3 交换排序 218

8.3.1 冒泡排序 218

8.3.2 快速排序 219

8.4 选择排序 221

8.5 基数排序 226

8.6 归并排序 230

8.7 各种内部排序算法的比较 231

8.7.1 稳定性比较 231

8.7.2 时间及空间复杂度比较 232

8.8 外部排序方法简介 233

习题 233

第9章 查找 235

9.1 查找表 235

9.1.1 查找表 235

9.1.2 查找表的ADT定义 236

9.2 查找算法 237

9.2.1 顺序表的查找 237

9.2.2 静态树表的查找 239

9.2.3 索引顺序表的查找 242

9.2.4 二叉排序树 243

9.3 Hash表 246

9.3.1 Hash表的概念 246

9.3.2 Hash函数的构造方法 248

9.3.3 处理冲突的方法 249

9.3.4 Hash表的查找 251

习题 251

参考文献 252