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

第1章 绪论 1

1.1什么是数据结构 1

1.1.1数据结构的定义 1

1.1.2逻辑结构类型 4

1.1.3存储结构类型 6

1.1.4数据类型和数据结构 7

1.2算法及其描述 10

1.2.1什么是算法 10

1.2.2算法描述 11

1.3算法分析 13

1.3.1算法设计的目标 13

1.3.2算法效率分析 13

1.3.3算法存储空间分析 16

1.4数据结构+算法=程序 17

1.4.1程序和数据结构 17

1.4.2算法和程序 17

1.4.3算法和数据结构 17

1.4.4数据结构的发展 23

本章小结 24

练习题1 24

上机实验题1 26

第2章 线性表 27

2.1线性表及其逻辑结构 27

2.1.1线性表的定义 27

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

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

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

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

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

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

2.3.2单链表 40

2.3.3双链表 47

2.3.4循环链表 51

2.4线性表的应用 52

2.5有序表 56

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

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

2.5.3有序表的归并算法 57

2.5.4有序表的应用 59

本章小结 61

练习题2 61

上机实验题2 61

第3章 栈和队列 64

3.1栈 64

3.1.1栈的定义 64

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

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

3.1.4栈的应用 70

3.2队列 80

3.2.1队列的定义 80

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

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

3.2.4队列的应用 89

3.2.5双端队列 93

本章小结 95

练习题3 95

上机实验题3 96

第4章串 99

4.1串的基本概念 99

4.2串的存储结构 100

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

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

4.3串的模式匹配 110

4.3.1 Brute-Force算法 110

4.3.2 KMP算法 112

本章小结 119

练习题4 119

上机实验题4 119

第5章 递归 121

5.1什么是递归 121

5.1.1递归的定义 121

5.1.2何时使用递归 122

5.1.3递归模型 123

5.1.4递归与数学归纳法 124

5.2递归调用的实现原理 125

5.3递归算法的设计 127

5.3.1递归算法设计的步骤 127

5.3.2递归数据结构的递归算法设计 128

5.3.3递归求解方法的递归算法设计 130

本章小结 131

练习题5 132

上机实验题5 132

第6章 数组和广义表 133

6.1数组 133

6.1.1数组的基本概念 133

6.1.2数组的存储结构 134

6.1.3特殊矩阵的压缩存储 136

6.2稀疏矩阵 138

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

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

6.3广义表 145

6.3.1广义表的定义 145

6.3.2广义表的存储结构 147

6.3.3广义表的运算 148

本章小结 151

练习题6 151

上机实验题6 152

第7章 树和二叉树 154

7.1树的基本概念 154

7.1.1树的定义 154

7.1.2树的逻辑表示方法 155

7.1.3树的基本术语 156

7.1.4树的性质 157

7.1.5树的基本运算 158

7.1.6树的存储结构 159

7.2二叉树的基本概念 162

7.2.1二叉树的定义 162

7.2.2二叉树的性质 163

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

7.3二叉树的存储结构 167

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

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

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

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

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

7.5二叉树的遍历 172

7.5.1二叉树遍历的概念 172

7.5.2二叉树遍历递归算法 173

7.5.3二叉树遍历非递归算法 177

7.5.4层次遍历算法 182

7.6二叉树的构造 184

7.7线索二叉树 189

7.7.1线索二叉树的概念 189

7.7.2线索化二叉树 191

7.7.3遍历线索化二叉树 192

7.8哈夫曼树 193

7.8.1哈夫曼树概述 193

7.8.2哈夫曼树的构造算法 194

7.8.3哈夫曼编码 195

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

7.9.1什么叫并查集 197

7.9.2并查集的算法实现 199

本章小结 201

练习题7 201

上机实验题7 202

第8章图 204

8.1图的基本概念 204

8.1.1图的定义 204

8.1.2图的基本术语 205

8.2图的存储结构 207

8.2.1邻接矩阵存储方法 207

8.2.2邻接表存储方法 208

8.3图的遍历 211

8.3.1图的遍历的概念 211

8.3.2深度优先遍历 211

8.3.3广度优先遍历 213

8.3.4非连通图的遍历 214

8.3.5图遍历算法的应用 215

8.4生成树和最小生成树 223

8.4.1生成树的概念 223

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

8.4.3普里姆算法 225

8.4.4克鲁斯卡尔算法 227

8.5最短路径 231

8.5.1路径的概念 231

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

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

8.6拓扑排序 240

8.7 AOE网与关键路径 242

本章小结 246

练习题8 246

上机实验题8 247

第9章 查找 249

9.1查找的基本概念 249

9.2线性表的查找 250

9.2.1顺序查找 250

9.2.2折半查找 251

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

9.3树表的查找 256

9.3.1二叉排序树 256

9.3.2平衡二叉树 264

9.3.3 B—树 270

9.3.4 B+树 275

9.4哈希表查找 276

9.4.1哈希表的基本概念 276

9.4.2哈希函数构造方法 277

9.4.3哈希冲突解决方法 278

9.4.4哈希表上的运算 281

本章小结 285

练习题9 285

上机实验题9 286

第10章 内排序 287

10.1排序的基本概念 287

10.2插入排序 288

10.2.1直接插入排序 288

10.2.2折半插入排序 290

10.2.3希尔排序 291

10.3交换排序 293

10.3.1冒泡排序 293

10.3.2快速排序 295

10.4选择排序 299

10.4.1直接选择排序 299

10.4.2堆排序 301

10.5归并排序 305

10.6基数排序 307

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

本章小结 311

练习题10 311

上机实验题10 312

第11章 外排序 313

11.1外排序概述 313

11.2磁盘排序 314

11.2.1生成初始归并段 315

11.2.2多路平衡归并 317

11.2.3最佳归并树 320

11.3磁带排序 322

11.3.1多路平衡归并排序 322

11.3.2多阶段归并排序 323

本章小结 325

练习题11 325

上机实验题11 325

第12章 文件 327

12.1文件的基本概念 327

12.1.1什么是文件 327

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

12.1.3文件的存储结构 328

12.2顺序文件 328

12.3索引文件 329

12.3.1 ISAM文件 330

12.3.2 VSAM文件 333

12.4哈希文件 335

12.5多关键字文件 335

12.5.1多重表文件 335

12.5.2倒排文件 336

本章小结 337

练习题12 337

上机实验题12 337

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

13.1面向对象的概念 339

13.2用C++描述面向对象的程序 341

13.2.1类 341

13.2.2类对象 343

13.2.3构造函数和析构函数 344

13.2.4派生类 347

13.3用C++描述数据结构算法 349

13.3.1顺序表类 349

13.3.2链栈类 352

13.3.3二叉树类 354

附录A综合实验题 358

综合实验题1链表综合算法设计 358

综合实验题2求复杂表达式的值 358

综合实验题3用二叉树实现家谱的相关运算 358

综合实验题4求无向图中满足约束条件的路径 359

综合实验题5分析二分查找成功时的平均查找长度 359

综合实验题6求各种排序算法的执行时间 359

附录B实验报告格式 360

附录C引用型参数的说明 361

附录D顺序表、顺序栈和顺序队列使用指针引用型参数的说明 363

附录E书中部分算法清单 366

附录F全国计算机专业数据结构2012年联考大纲 369

参考文献 372