数据结构基础 C版PDF|Epub|txt|kindle电子书版本网盘下载

数据结构基础 C版PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

目录1

出版者的话1

专家指导委员会1

译者序1

前言1

第1章 基本概念1

1.1 综述：系统生命周期1

1.2 算法描述3

1.2.1 引言3

1.2.2 递归算法6

1.3 数据抽象9

1.4.1 空间复杂性12

1.4 算法的性能分析12

1.4.2 时间复杂性14

1.4.3 渐近记号（O,Ω,Θ）19

1.4.4 实际可行的复杂性24

1.5 性能测量26

1.6 参考文献和文献选读31

第2章 数组与结构32

2.1 ADT数组32

2.2 结构与共用体34

2.2.1 结构34

2.2.2 共用体36

2.2.3 结构的内部实现37

2.2.4 自引用结构37

2.3 ADT多项式38

2.4.1 概述43

2.4 ADT稀疏矩阵43

2.4.2 矩阵转置44

2.4.3 矩阵乘法47

2.5 多维数组的存储表示50

2.6 ADT字符串52

2.6.1 概述52

2.6.2 模式匹配55

2.7 参考文献和文献选读59

2.8 附加习题59

第3章 栈与队列65

3.1 ADT栈65

3.2 ADT队列68

3.3 迷宫问题72

3.4.1 概述75

3.4 表达式求值75

3.4.2 后缀表达式求值77

3.4.3 中缀表达式到后缀表达式的转换79

3.5 多栈和多队列81

3.6 参考文献和文献选读84

3.7 附加习题84

第4章 链表86

4.1 指针86

4.1.1 指针的危险性87

4.1.2 动态存储分配87

4.2 单向链表88

4.3 动态链栈与动态链队列93

4.4 多项式96

4.4.1 多项式的单向链表表示96

4.4.2 多项式加法97

4.4.3 多项式删除99

4.4.4 多项式的循环链表表示100

4.4.5 小结103

4.5 链表的其他操作104

4.5.1 单向链表的操作104

4.5.2 循环链表的操作105

4.6 等价关系106

4.7 稀疏矩阵109

4.8 双向链表114

4.9 参考文献和文献选读116

4.10 附加习题117

5.1 概述118

5.1.1 术语118

第5章 树118

5.1.2 树的存储表示119

5.2 二叉树121

5.2.1 抽象数据型121

5.2.2 二叉树的性质123

5.2.3 二叉树的存储表示124

5.3 二叉树的遍历126

5.4 二叉树的其他操作130

5.5 线索二叉树133

5.6 堆137

5.6.1 ADT堆137

5.6.2 优先级队列138

5.6.3 最大堆的插入操作139

5.6.4 最大堆的删除操作140

5.7.1 概述142

5.7 二叉查找树142

5.7.2 二叉查找树的查找143

5.7.3 二叉查找树的插入144

5.7.4 二叉查找树的删除145

5.7.5 二叉查找树的高度145

5.8 选择树146

5.9 森林148

5.9.1 森林转换为二叉树148

5.9.2 森林的遍历149

5.10 集合表示149

5.10.1 Union和Find操作150

5.10.2 等价类155

5.11.1 不同的二叉树156

5.11.2 栈排列156

5.11 二叉树计数156

5.11.3 矩阵乘法158

5.11.4 不同的二叉树数量159

5.12 参考文献和文献选读159

5.13 附加习题160

第6章 图162

6.1 ADT图162

6.1.1 概述162

6.1.2 定义163

6.1.3 图的存储表示165

6.2 图的基本操作170

6.2.1 深度优先搜索171

6.2.2 广度优先搜索171

6.2.3 连通分支173

6.2.4 生成树174

6.2.5 双连通分支与关节点175

6.3 最小代价生成树179

6.4 最短路径与传递闭包183

6.4.1 单源多目标最短路径184

6.4.2 所有顶点对之间的最短路径187

6.4.3 传递闭包188

6.5 活动网络190

6.5.1 AOV网190

6.5.2 AOE网194

6.6 参考文献和文献选读200

6.7 附加习题200

7.1.1 概述202

7.1.2 顺序查找202

7.1 查找与表验证202

第7章 排序202

7.1.3 折半查找203

7.1.4 表验证204

7.2 定义206

7.3 插入排序207

7.4 快速排序208

7.5 最优的排序时间211

7.6 归并排序212

7.6.1 归并212

7.6.2 归并排序的迭代算法216

7.6.3 归并排序的递归算法217

7.7 堆排序220

7.8 基数排序223

7.9 利用链表和映射表进行排序227

7.10 内部排序总结233

7.11 外部排序236

7.11.1 概述236

7.11.2 k路归并239

7.11.3 并行操作的缓冲区处理240

7.11.4 归并段的生成244

7.11.5 归并段的最优归并246

7.12 参考文献和文献选读249

7.13 附加习题249

第8章 散列251

8.1 ADT符号表251

8.2 静态散列252

8.2.1 散列表252

8.2.2 散列函数253

8.2.3 溢出处理254

8.2.4 溢出处理技术的理论分析259

8.3 动态散列262

8.3.1 带目录的动态散列263

8.3.2 带目录的动态散列的分析268

8.3.3 无目录的动态散列269

8.4 参考文献和文献选读272

第9章 堆结构274

9.1 最小-最大堆274

9.1.1 定义274

9.1.2 最小-最大堆插入274

9.1.3 删除最小元素277

9.2 双端堆279

9.2.1 定义279

9.2.2 插入操作280

9.2.3 删除最小元素操作282

9.3 左高树284

9.4 二项堆289

9.4.1 分摊代价289

9.4.2 二项堆的定义290

9.4.3 插入操作291

9.4.4 合并操作291

9.4.5 删除最小元素操作291

9.4.6 代价分摊分析293

9.5 斐波那契堆294

9.5.1 定义294

9.5.2 删除操作295

9.5.3 关键字减值操作295

9.5.4 级联剪枝操作296

9.5.5 分析297

9.5.6 F堆的应用298

9.6 参考文献和文献选读299

第10章 查找结构301

10.1 最优二叉查找树301

10.2 AVL树307

10.3 2-3树317

10.3.1 定义与性质317

10.3.2 2-3树的查找操作318

10.3.3 2-3树的插入操作318

10.3.4 2-3树的删除操作321

10.4 2-3-4树325

10.4.1 定义与性质325

10.4.2 2-3-4树的插入操作327

10.4.3 2-3-4树的删除操作329

10.5 红黑树331

10.5.1 定义与性质331

10.5.2 红黑树的查找332

10.5.3 自顶向下的插入333

10.5.4 自底向上的插入334

10.5.5 从红黑树删除结点335

10.6 B树337

10.6.1 m路查找树的定义337

10.6.2 m路查找树的查找338

10.6.3 B树的定义和性质338

10.6.4 B树的插入操作340

10.6.5 B树的删除操作342

10.6.6 可变长的关键字值343

10.7 伸展树345

10.8 数字查找树349

10.8.1 数字查找树349

10.8.2 二叉检索树350

10.8.3 Patricia树351

10.9 检索树355

10.9.1 定义355

10.9.2 检索树的查找操作356

10.9.3 采样策略356

10.9.4 检索树的插入操作358

10.9.5 检索树的删除操作358

10.10 差分文件359

10.11 参考文献和文献选读362

附录 ANSI C和K R C364

索引370