数据结构教程 抽象数据类型描述 C语言版PDF电子书下载

第1章 抽象数据类型和算法描述 1

1.1 抽象和实现 1

1.1.1 数和变量 1

1.1.2 两维数组 2

1.1.3 过程与抽象 3

1.2 术语和概念 4

1.2.1 数据、数据元素和数据对象 4

1.2.2 数据类型 5

1.2.3 抽象数据类型 5

1.2.4 数据结构 6

1.3 抽象数据类型 7

1.3.1 抽象数据类型的描述 7

1.3.2 抽象数据类型的说明 7

1.3.3 抽象数据类型的表示 10

1.3.4 实现的独立性 12

1.3.5 一个复数抽象数据类型 13

1.4 算法分析 16

1.4.1 算法的概念 17

1.4.2 算法的时间复杂性 19

1.4.3 大○运算规则 21

1.4.4 时间复杂性分析 23

1.4.5 再论增长率的决定作用 27

1.4.6 算法的空间复杂性 28

习题一 29

第2章 线性表、数组和串 30

2.1 抽象数据类型List 30

2.2.1 数组实现 34

2.2 线性表的实现 34

2.2.2 指针实现——链表 40

2.2.3 记住当前位置的线性表 47

2.2.4 游标实现 48

2.3 特殊链表 51

2.3.1 循环链表 51

2.3.2 双向链表 54

2.4 应用举例——模拟存储管理 56

2.4.1 存储空间的分配 57

2.4.2 存储空间的释放 59

2.4.3 存储管理的堆实现 62

2.5 数组 70

2.5.1 数组的结构 70

2.5.2 矩阵的压缩存储 71

2.6 串 79

2.6.1 抽象数据类型String 79

2.6.2 串的表示和实现 81

2.6.3 串的模式匹配算法 84

习题二 91

第3章 栈和队列 93

3.1 栈的数据类型 93

3.1.1 栈的概念 93

3.1.2 抽象数据类型Stack 94

3.1.3 栈与子程序调用 96

3.2 栈的实现 98

3.2.1 栈的数组实现 98

3.2.2 栈的链接实现 101

3.2.3 多个栈共享一个存储区 103

3.3 队列 108

3.3.1 抽象数据类型Queue 108

3.3.2 队列的数组实现 110

3.3.3 队列的链接实现 114

3.4 算术表达式的计算 116

3.4.1 计算后缀表达式 116

3.4.2 将中缀表达式转变为后缀表达式 119

习题三 123

第4章 树 125

4.1 树的基本概念和术语 126

4.1.1 树的定义 126

4.1.2 树的术语 127

4.2.1 树的存储形式 129

4.2 一般树 129

4.2.2 树的遍历 131

4.2.3 树的表示 132

4.3 二叉树 133

4.3.1 二叉树的概念 133

4.3.2 二叉树的存储形式 134

4.3.3 有序树与二叉树的转化 135

4.3.4 抽象数据类型BinaryTree 137

4.3.5 二叉树的表示和实现 140

4.4 遍历二叉树 142

4.4.1 前序遍历 142

4.4.2 中序遍历 146

4.4.3 后序遍历 148

4.5.2 抽象数据类型BST 151

4.5.1 二叉排序树的概念 151

4.5 二叉排序树 151

4.5.3 二叉排序树的查找 153

4.5.4 在二叉排序树中插入一个结点 155

4.5.5 在二叉排序树中删除结点 156

4.6 穿线二叉树 159

4.6.1 穿线树的概念 159

4.6.2 构造中序穿线树 162

4.6.3 在穿线树上插入一个结点 163

4.6.4 用游标实现的穿线二叉树 165

4.7 最优二叉搜索树 166

4.7.1 最优二叉搜索树概念 166

4.7.2 哈夫曼编码树 167

4.7.3 哈夫曼算法的实现 170

4.8 堆和优先队列 172

4.8.1 堆的数据结构 173

4.8.2 抽象数据类型PQueue 174

4.8.3 用堆实现优先队列 175

4.9 背包问题 179

4.9.1 问题的提出 179

4.9.2 查找解答树 180

4.9.3 用回溯法解背包问题 183

4.9.4 用约束查找法解背包问题 186

习题四 187

第5章 无向图 190

5.1 基本概念 190

5.1.1 引言 190

5.1.2 定义和术语 191

5.2 抽象数据类型Graph 193

5.3 图的表示和实现 194

5.3.1 图的邻接矩阵的表示和实现 195

5.3.2 代价邻接矩阵 199

5.3.3 图的邻接表的表示和实现 199

5.3.4 图的邻接多重表表示 205

5.3.5 图的边表表示 207

5.4 图的遍历 208

5.4.1 深度优先搜索DFS 208

5.4.2 广度优先搜索BFS 210

5.4.3 优先度优先搜索PFS 211

5.5 生成树和最小代价生成树 212

5.5.1 生成树 212

5.5.2 最小代价生成树 215

5.6 割点和双连通分量 223

5.7 货郎担问题 227

5.7.1 问题的提出 227

5.7.2 用贪心法解TSP问题 228

5.7.3 局部搜索法 229

习题五 232

第6章 有向图 235

6.1 有向图的概念和表示 235

6.1.1 有向图的概念 235

6.1.2 有向图的表示和遍历 235

6.1.3 状态表 236

6.2 单源最短路径 237

6.2.1 迪杰斯特拉算法的正确性 237

6.2.2 迪杰斯特拉算法的实现和分析 238

6.3 所有顶点间的最短路径和传递闭包 241

6.3.1 弗洛伊德算法 241

6.3.2 传递闭包 244

6.3.3 求赋权有向图的中心 244

6.4 强连通分量 246

6.5 无圈有向图 248

6.5.1 拓扑排序 248

6.5.2 关键路径 249

习题六 253

第7章 集合和查找技术 254

7.1 抽象数据类型Set 254

7.2 集合的表示和实现 257

7.2.1 用位向量实现集合 257

7.2.2 用有序链接表实现集合 259

7.3 查找表 261

7.3.1 查找表的概念 261

7.3.2 顺序查找表 262

7.3.3 有序表的查找 264

7.3.4 分块查找 266

7.4 散列技术 267

7.4.1 字典和哈希表 267

7.4.2 哈希表的表示和实现 269

7.4.3 哈希函数的选择 274

7.4.4 冲突处理 276

7.5 MergeFind抽象数据类型 279

7.5.1 定义和概述 279

7.5.2 MergeFind的树实现 280

7.5.3 加权合并 282

7.5.4 路径压缩 284

7.5.5 MFSet的应用 285

习题七 286

第8章 排序 288

8.1 排序的概念 288

8.2 简单排序方法 289

8.2.1 选择排序 290

8.2.2 冒泡排序 291

8.2.3 插入排序 294

8.3 分治法排序 297

8.3.1 合并排序 297

8.3.2 快速排序 303

8.4.1 堆排序 309

8.4 其他的比较型排序方法 309

8.4.2 希尔排序 313

8.4.3 二次选择排序 316

8.5 分布型排序方法 317

8.5.1 基数排序 317

8.5.2 散列排序 321

8.6 内部排序算法的比较 324

8.7 外部排序 325

8.7.1 多路合并 326

8.7.2 简单合并排序 329

8.7.3 自然分配 331

8.7.4 多阶段合并排序 332

8.7.5 菲波那契分布的多阶段合并排序 333

习题八 337

9.1.1 各级基本术语 339

第9章 文件 339

9.1 文件的基本概念 339

9.1.2 文件的操作 340

9.2 顺序文件 343

9.3 索引文件 348

9.3.1 索引非顺序文件 348

9.3.2 索引顺序文件 349

9.4 散列文件 351

9.5 多关键字文件 352

9.5.1 链表文件和多重链表文件 352

9.5.2 倒排文件 354

习题九 355

10.1.1 实习的目的和要求 356

10.1 数据结构实习指导 356

第10章 数据结构实习 356

10.1.2 实习步骤 357

10.2 实习报告范例——迷宫问题 360

10.2.1 问题定义 360

10.2.2 系统开发 361

10.2.3 源程序清单、输入数据及运行结果 367

10.3 实习题 376

10.3.1 线性结构 376

10.3.2 树形结构 380

10.3.3 图形结构 381

10.3.4 集合与查找技术 382

10.3.5 排序 383

参考文献 385