数据结构教程 第5版PDF电子书下载

第1章 绪论 1

1.1什么是数据结构 2

1.1.1数据结构的定义 2

1.1.2逻辑结构 3

1.1.3存储结构 6

1.1.4数据运算 8

1.1.5数据类型和抽象数据类型 9

1.2算法及其描述 14

1.2.1什么是算法 14

1.2.2算法设计的目标 15

1.2.3算法描述 16

1.3算法分析 18

1.3.1算法分析概述 18

1.3.2算法时间性能分析 18

1.3.3算法空间性能分析 22

1.4数据结构＋算法＝程序 24

1.4.1程序和数据结构 24

1.4.2算法和程序 24

1.4.3算法和数据结构 24

1.4.4数据结构的发展 25

本章小结 26

练习题1 26

上机实验题1 28

验证性实验 28

设计性实验 29

第2章线性表 30

2.1线性表及其逻辑结构 31

2.1.1线性表的定义 31

2.1.2线性表的抽象数据类型描述 31

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

2.2.1线性表的顺序存储结构——顺序表 33

2.2.2顺序表基本运算的实现 35

2.3线性表的链式存储结构 43

2.3.1线性表的链式存储结构——链表 43

2.3.2单链表 45

2.3.3双链表 54

2.3.4循环链表 59

2.4线性表的应用 61

2.5有序表 65

2.5.1有序表的抽象数据类型描述 65

2.5.2有序表的存储结构及其基本运算算法 66

2.5.3有序表的归并算法 66

2.5.4有序表的应用 69

本章小结 70

练习题2 71

上机实验题2 74

验证性实验 74

设计性实验 76

综合性实验 76

第3章 栈和队列 78

3.1栈 79

3.1.1栈的定义 79

3.1.2栈的顺序存储结构及其基本运算的实现 80

3.1.3栈的链式存储结构及其基本运算的实现 83

3.1.4栈的应用 87

3.2队列 97

3.2.1队列的定义 97

3.2.2队列的顺序存储结构及其基本运算的实现 98

3.2.3队列的链式存储结构及其基本运算的实现 103

3.2.4队列的应用举例 108

3.2.5双端队列 113

本章小结 115

练习题3 115

上机实验题3 117

验证性实验 117

设计性实验 119

综合性实验 119

第4章串 121

4.1串的基本概念 122

4.2串的存储结构 122

4.2.1串的顺序存储结构——顺序串 123

4.2.2串的链式存储结构——链串 128

4.3串的模式匹配 134

4.3.1 Brute-Force算法 134

4.3.2 KMP算法 136

本章小结 143

练习题4 143

上机实验题4 144

验证性实验 144

设计性实验 145

综合性实验 145

第5章 递归 146

5.1什么是递归 147

5.1.1递归的定义 147

5.1.2何时使用递归 148

5.1.3递归模型 149

5.1.4递归与数学归纳法 152

5.2栈和递归 152

5.2.1函数调用栈 152

5.2.2递归调用的实现 153

5.2.3递归到非递归的转换 155

5.3递归算法的设计 156

5.3.1递归算法设计的步骤 156

5.3.2基于递归数据结构的递归算法设计 158

5.3.3基于递归求解方法的递归算法设计 159

本章小结 161

练习题5 162

上机实验题5 162

验证性实验 162

设计性实验 163

综合性实验 163

第6章 数组和广义表 164

6.1数组 165

6.1.1数组的基本概念 165

6.1.2数组的存储结构 166

6.1.3特殊矩阵的压缩存储 168

6.2稀疏矩阵 171

6.2.1稀疏矩阵的三元组表示 172

6.2.2稀疏矩阵的十字链表表示 175

6.3广义表 177

6.3.1广义表的定义 177

6.3.2广义表的存储结构 179

6.3.3广义表的运算 180

本章小结 185

练习题6 186

上机实验题6 186

验证性实验 186

设计性实验 187

综合性实验 187

第7章 树和二叉树 189

7.1树的基本概念 190

7.1.1树的定义 190

7.1.2树的逻辑表示方法 190

7.1.3树的基本术语 191

7.1.4树的性质 192

7.1.5树的基本运算 194

7.1.6树的存储结构 195

7.2二叉树的概念和性质 198

7.2.1二叉树的定义 198

7.2.2二叉树的性质 199

7.2.3二叉树与树、森林之间的转换 200

7.3二叉树的存储结构 203

7.3.1二叉树的顺序存储结构 204

7.3.2二叉树的链式存储结构 205

7.4二叉树的基本运算及其实现 206

7.4.1二叉树的基本运算概述 206

7.4.2二叉树的基本运算算法实现 207

7.5二叉树的遍历 211

7.5.1二叉树遍历的概念 211

7.5.2先序、中序和后序遍历递归算法 212

7.5.3先序、中序和后序遍历非递归算法 218

7.5.4层次遍历算法 226

7.6二叉树的构造 228

7.7线索二叉树 233

7.7.1线索二叉树的概念 233

7.7.2线索化二叉树 233

7.7.3遍历线索化二叉树 236

7.8哈夫曼树 237

7.8.1哈夫曼树概述 237

7.8.2哈夫曼树的构造算法 238

7.8.3哈夫曼编码 239

7.9用并查集求解等价问题 241

7.9.1什么叫并查集 241

7.9.2并查集的算法实现 243

本章小结 245

练习题7 245

上机实验题7 247

验证性实验 247

设计性实验 248

综合性实验 249

第8章 图 252

8.1图的基本概念 253

8.1.1图的定义 253

8.1.2图的基本术语 254

8.2图的存储结构和基本运算算法 256

8.2.1邻接矩阵存储方法 256

8.2.2邻接表存储方法 258

8.2.3图基本运算算法设计 260

8.2.4其他存储方法 262

8.3图的遍历 264

8.3.1图的遍历的概念 264

8.3.2深度优先遍历 265

8.3.3广度优先遍历 266

8.3.4非连通图的遍历 267

8.3.5图遍历算法的应用 269

8.4生成树和最小生成树 279

8.4.1生成树的概念 279

8.4.2无向图的连通分量和生成树 280

8.4.3普里姆算法 281

8.4.4克鲁斯卡尔算法 285

8.5最短路径 290

8.5.1路径的概念 290

8.5.2从一个顶点到其余各顶点的最短路径 290

8.5.3每对顶点之间的最短路径 296

8.6拓扑排序 301

8.7 AOE网与关键路径 303

8.7.1相关概念 303

8.7.2求AOE网的关键活动 306

本章小结 307

练习题8 308

上机实验题8 310

验证性实验 310

设计性实验 311

综合性实验 313

第9章 查找 314

9.1查找的基本概念 315

9.2线性表的查找 316

9.2.1顺序查找 316

9.2.2折半查找 317

9.2.3索引存储结构和分块查找 321

9.3树表的查找 324

9.3.1二叉排序树 324

9.3.2平衡二叉树 333

9.3.3 B_树 339

9.3.4 B＋树 345

9.4哈希表的查找 346

9.4.1哈希表的基本概念 346

9.4.2哈希函数的构造方法 348

9.4.3哈希冲突的解决方法 350

9.4.4哈希表的运算算法 352

本章小结 360

练习题9 360

上机实验题9 362

验证性实验 362

设计性实验 363

综合性实验 364

第10章内排序 365

10.1排序的基本概念 366

10.2插入排序 368

10.2.1直接插入排序 368

10.2.2折半插入排序 370

10.2.3希尔排序 371

10.3交换排序 374

10.3.1冒泡排序 374

10.3.2快速排序 376

10.4选择排序 380

10.4.1简单选择排序 380

10.4.2堆排序 382

10.5归并排序 386

10.6基数排序 389

10.7各种内排序方法的比较和选择 392

本章小结 394

练习题10 394

上机实验题10 396

验证性实验 396

设计性实验 397

综合性实验 397

第11章 外排序 399

11.1外排序概述 400

11.2磁盘排序 400

11.2.1磁盘排序概述 400

11.2.2生成初始归并段 402

11.2.3多路平衡归并 404

11.2.4最佳归并树 407

11.3磁带排序 409

11.3.1多路平衡归并排序 409

11.3.2多阶段归并排序 411

本章小结 412

练习题11 412

上机实验题11 413

验证性实验 413

设计性实验 413

第12章 文件 414

12.1文件的基本概念 415

12.1.1什么是文件 415

12.1.2文件的逻辑结构及操作 415

12.1.3文件的存储结构 416

12.2顺序文件 416

12.3索引文件 417

12.3.1 ISAM文件 418

12.3.2 VSAM文件 421

12.4哈希文件 422

12.5多关键字文件 423

12.5.1多重表文件 423

12.5.2倒排文件 424

本章小结 425

练习题12 425

上机实验题12 425

验证性实验 425

设计性实验 426

第13章 采用面向对象的方法描述算法 427

13.1面向对象的概念 428

13.2用C＋＋描述面向对象的程序 429

13.2.1类 429

13.2.2类对象 432

13.2.3构造函数和析构函数 433

13.2.4模板类 436

13.3用C＋＋描述数据结构算法 438

13.3.1顺序表类模板 439

13.3.2链栈类模板 441

13.4使用STL设计数据结构算法 443

附录A实验报告格式 450

一、设计人员相关信息 450

二、程序设计相关信息 450

三、实验提交内容 450

附录B引用型参数和指针引用型参数的说明 451

附录C算法索引 453

附录D名词索引 457

附录E全国计算机专业数据结构2016年联考大纲 461

参考文献 463