数据结构PDF电子书下载

第一章绪论 1

1.1为什么要学习数据结构 1

1.2数据结构概念 2

1.2.1数据的逻辑结构 3

1.2.2数据的存储结构 4

1.2.3对数据结构的操作 6

1.2.4数据结构示例 6

1.3算法 6

1.3.1算法及其特性 6

1.3.2算法的描述 7

1.3.3算法的评价准则 9

1.4算法的正确性证明 10

1.5算法分析基础 13

1.5.1算法时间复杂性的分析方法 13

1.5.2复杂性函数的渐近表示 16

1.5.3算法时间与空间分析 18

1.5.4计算复杂性和算法的效率 19

小结 20

参考文献与推荐读物 21

习题 22

第二章线性表、堆栈和队列 24

2.1线性表的定义和基本操作 24

2.2线性表的顺序存储结构 24

2.3线性表的链接存储结构 27

2.3.1单链表 27

2.3.2循环链表 32

2.3.3双向链表 33

2.4复杂性分析 36

2.5堆栈 36

2.5.1堆栈的定义和基本操作 36

2.5.2顺序栈 37

2.5.3链式栈 39

2.5.4顺序栈与链式栈的比较 40

2.5.5堆栈应用——括号匹配 41

2.6队列 42

2.6.1队列的定义和基本操作 42

2.6.2顺序队列 43

2.6.3链式队列 45

2.6.4顺序队列与链式队列的比较 47

2.6.5 队列与堆栈的扩展 47

小结 48

参考文献与推荐读物 48

习题 49

第三章数组和字符串 52

3.1数组 52

3.1.1数组的存储和寻址 52

3.1.2一维数组类 54

3.2矩阵 55

3.2.1矩阵类 55

3.2.2特殊矩阵 57

3.2.3三元组表 59

3.2.4十字链表 61

3.3字符串 64

3.3.1字符串的定义与字符串类 64

3.3.2模式匹配算法 67

小结 71

参考文献与推荐读物 72

习题 73

第四章树 76

4.1树的基本概念 76

1.1.1树的定义 76

4.1.2树的相关术语 77

4.2二叉树 79

4.2.1二叉树定义和主要性质 79

4.2.2二叉树顺序存储 83

4.2.3二叉树链接存储 84

4.2.4二叉树遍历 86

4.2.5创建二叉树 92

4.2.6复制二叉树 93

4.3线索二叉树 94

4.3.1线索二叉树定义 94

4.3.2线索二叉树存储 95

4.3.3线索二叉树基本算法 97

4.4树和森林 104

4.4.1树与二叉树的转换 104

4.4.2树的顺序存储 108

4.4.3树的链接存储 110

4.4.4树和森林的遍历 115

4.5压缩与哈夫曼树 117

4.5.1文件编码 117

4.5.2扩充二叉树 118

4.5.3哈夫曼树和哈夫曼编码 119

4.6应用 122

4.6.1表达式求值 122

4.6.2分类与决策树 124

小结 128

参考文献与推荐读物 128

习题 129

第五章图 131

5.1图的基本概念 132

5.2图的存储结构与类定义 134

5.2.1存储结构 134

5.2.2Graph类 137

5.3图的遍历算法 140

5.3.1深度优先遍历 140

5.3.2广度优先遍历 142

5.5.4拓扑排序 143

5.5关键路径 147

5.6最短路径问题 152

5.6.1无权最短路径问题 153

5.6.2正权最短路径问题 154

5.6.3每对顶点之间的最短路径 158

5.7最小支撑树 160

5.7.1普里姆算法 161

5.7.2克鲁斯卡尔算法 164

5.8图的应用 165

5.8.1可及性与Warshall算法 165

5.8.2连通分量 166

5.8.3图在网络分析和信息检索中的应用 167

小结 171

参考文献与推荐读物 172

习题 173

第六章递归 177

6.1递归的定义 177

6.2基本递归过程 180

6.3递归过程实现与堆栈 182

6.4递归法求解问题 186

6.4.1委员会问题 186

6.4.2回溯 188

6.5递归的效率 191

小结 193

参考文献与推荐读物 194

习题 194

第七章排序 198

7.1排序问题的基本概念 198

7.2插入排序 200

7.2.1直接插入排序 200

7.2.2Shell排序 202

7.3交换排序 204

7.3.1冒泡排序 204

7.3.2快速排序 207

7.4选择排序 215

7.4.1直接选择排序 215

7.4.2堆排序 215

7.5合并排序 220

7.6基于关键词比较的排序算法分析 223

7.6.1平方阶排序算法及改进算法 223

7.6.2线性对数阶排序算法 223

7.6.3分治排序的一般方法 225

7.6.4基于关键词比较的排序算法下界 226

7.7分布排序 227

7.7.1基数分布 228

7.7.2值分布 230

7.8外排序 231

7.8.1外存储器 231

7.8.2磁带排序 232

7.8.3磁盘排序 241

小结 245

参考文献与推荐读物 246

习题 247

第八章查找 253

8.1顺序查找 254

8.1.1无序表的顺序查找 254

8.1.2有序表的顺序查找 256

8.2基于关键词比较的查找 256

8.2.1对半查找 257

8.2.2.致对半查找 260

8.2.3斐波那契查找 263

8.2.4插值查找 266

8.3二叉查找树 268

8.3.1基本概念和性质 268

8.3.2查找、插入和删除 269

8.3.3平均情况时间分析 273

8.4最优二叉查找树 274

8.4.1访问频率 274

8.4.2最优二叉查找树 275

8.4.3近似最优树的构造 281

8.5平衡树 284

8.5.1高度平衡树 285

8.5.2重量平衡树 294

8.6红黑树 300

8.6.1红黑树的性质 300

8.6.2旋转 301

8.6.3插入 303

8.6.4删除 306

8.7B树及其变形树 311

8.7.1多叉树 311

8.7.2 B树 312

8.7.3 B树变形树 318

8.8数字查找 323

8.8.1检索结构查找 323

8.8.2数字树查找 330

8.9散列 332

8.9.1散列函数 333

8.9.2冲突调节 337

8.9.3删除 346

8.9.4重量平衡树的应用——按位置查找 347

小结 347

参考文献与推荐读物 349

习题 353

第九章 内存管理 357

9.1概述 357

9.2均匀大小记录的分配和回收算法 359

9.2.1记录分配算法 359

9.2.2访问计数器法 360

9.2.3 废料收集方法 362

9.3不同大小记录的分配和回收算法 367

9.3.1查找分配策略 368

9.3.2边界标识法 371

9.3.3压缩分配 374

9.4伙伴系统 376

9.4.1伙伴系统概述 376

9.4.2分配记录和释放记录算法 379

小结 381

参考文献与推荐读物 383

习题 385

第十章 文件 388

10.1文件的基本概念 388

10.1.1文件及其分类 388

10.1.2文件的逻辑结构与存储结构 390

10.2顺序文件 391

10.2.1顺序无序文件 393

10.2.2顺序有序文件 396

10.2.3增补文件 397

10.3散列文件 398

10.3.1散列文件 398

10.3.2可扩充的散列文件 399

10.4索引文件 403

10.4.1动态索引结构和静态索引结构 404

10.4.2ISAM文件 405

10.4.3VSAM文件 409

10.5多关键字文件 412

10.5.1多重链表文件 413

10.5.2倒排文件 416

小结 416

参考文献与推荐读物 417

习题 417

第十一章随机数 419

11.1生成随机数 419

11.1.1均匀分布随机数 420

11.1.2其他分布随机数 427

11.2随机数检验 429

11.2.1.般检验方法 430

11.2.2经验检验方法 434

11.3随机排列与随机组合 436

11.3.1随机排列 436

11.3.2随机组合 437

11.4应用 439

11.4.1随机算法 439

11.1.2使用随机数的快速排序算法 441

小结 441

参考文献与推荐读物 441

习题 442

附录 444

附录1各章算法的C++实现 444

附录2习题参考答案或解题思路 579