新编数据结构及算法教程PDF电子书下载

第1章 绪论 1

1.1数据结构的起源与发展 1

1.2基本概念和术语 2

1.3理解数据结构 3

1.4数据的逻辑结构和存储结构 4

1.4.1逻辑结构 5

1.4.2存储结构 6

1.5抽象数据类型 8

1.5.1数据类型 8

1.5.2抽象数据类型 8

1.6算法分析与评价 11

1.6.1数据结构与算法的关系 11

1.6.2算法的定义 11

1.6.3算法的5大特性 11

1.6.4算法设计的要求 12

1.6.5算法效率分析 13

1.6.6算法的时间复杂度 14

1.6.7算法存储空间需求 16

1.7本章小结 17

1.8习题 17

第2章 线性表 20

2.1问题的提出 20

2.1.1问题中的数据分析 20

2.1.2问题中的功能分析 21

2.1.3问题中的数据结构 22

2.2线性表 22

2.2.1线性表的定义 22

2.2.2线性表的存储结构和基本操作的实现 24

2.2.3线性表的两种存储结构的区别 47

2.3案例实现 48

2.3.1基于顺序表的新生成绩管理系统 48

2.3.2基于单向链表的新生成绩管理系统 52

2.4其他形式的链表 54

2.4.1单向循环链表 54

2.4.2双向循环链表 57

2.5线性表的应用 60

2.5.1两个线性表的合并 60

2.5.2一元多项式的应用 63

2.6本章小结 69

2.7习题与实验 70

第3章 栈与队列 74

3.1问题的提出 74

3.1.1问题中的数据分析 74

3.1.2问题中的功能分析 74

3.1.3问题中的数据结构 75

3.2栈 76

3.2.1栈的定义 76

3.2.2栈的存储结构和基本操作的实现 77

3.2.3栈的两种存储结构的区别 87

3.2.4案例实现：基于栈的括号匹配 87

3.3栈的应用 89

3.3.1表达式求值 89

3.3.2栈与递归 94

3.4队列 103

3.4.1队列的定义 103

3.4.2队列的存储结构和基本操作的实现 105

3.4.3队列的两种存储结构的区别 116

3.4.4案例实现：基于队列的医院挂号模拟系统 116

3.5队列的应用 120

3.6共用栈和双队列 124

3.6.1共用栈 124

3.6.2双端队列 126

3.7本章小结 127

3.8习题与实验 127

第4章 数组和特殊矩阵 133

4.1多维数组 133

4.1.1数组的逻辑结构 133

4.1.2数组的内存映像 133

4.2特殊矩阵的压缩存储 136

4.2.1对称矩阵 136

4.2.2三角矩阵 138

4.2.3带状矩阵 139

4.3稀疏矩阵 140

4.3.1稀疏矩阵的三元组表存储 140

4.3.2稀疏矩阵的十字链表存储 146

4.4本章小结 152

4.5习题 152

第5章 树和二叉树 155

5.1问题的提出 155

5.1.1问题中的数据分析 155

5.1.2问题中的功能分析 156

5.1.3问题中的数据结构 156

5.2树的定义和基本术语 156

5.2.1树的递归定义 156

5.2.2树的基本术语 156

5.2.3树的表示 158

5.2.4树的抽象数据类型描述 159

5.3二叉树 159

5.3.1二叉树的定义 159

5.3.2二叉树的性质 161

5.3.3二叉树的抽象数据类型 162

5.3.4二叉树的存储结构 163

5.3.5二叉树的遍历及其应用 166

5.3.6案例实现：基于表达式二叉树的动态表达式计算 192

5.4线索二叉树 192

5.4.1线索二叉树的定义 193

5.4.2线索二叉树的基本操作实现 194

5.4.3基于中序线索二叉树的遍历算法 200

5.5树、森林与二叉树的转换及其应用 203

5.5.1树、森林与二叉树的转换 203

5.5.2树的存储结构 204

5.5.3树和森林的遍历 209

5.5.4树的简单应用 210

5.5.5案例实现：基于树结构的行政机构管理 217

5.6哈夫曼树及其应用 220

5.6.1最优二叉树——哈夫曼树 220

5.6.2哈夫曼树及哈夫曼编码的构建算法 224

5.7本章小结 229

5.8习题与实验 229

第6章图 234

6.1问题的提出 234

6.1.1问题中的数据分析 235

6.1.2问题中的功能分析 235

6.1.3问题中的数据结构 235

6.2图的定义和基本术语 235

6.2.1图的定义 235

6.2.2图的基本术语 235

6.2.3图的分类与连通性 237

6.2.4图的抽象数据类型定义 238

6.3图的存储结构 239

6.3.1图的邻接矩阵表示 240

6.3.2图的邻接表表示 243

6.3.3有向图的十字链表表示 246

6.3.4无向图的邻接多重表表示 247

6.4图的遍历 249

6.4.1连通图的深度优先搜索（Depth-First Search） 249

6.4.2连通图的广度优先搜索（Breadth-First Search） 253

6.4.3非连通图的深度（广度）优先遍历 255

6.4.4图的遍历算法应用 255

6.5图的连通性 261

6.5.1无向图的连通分量和生成树 261

6.5.2最小生成树及应用 261

6.6最短路径 272

6.6.1求从某个源点到其余各点的最短路径 272

6.6.2每一对顶点之间的最短路径 278

6.7有向无环图及其应用 283

6.7.1拓扑排序 284

6.7.2关键路径 287

6.7.3案例实现：教学计划编排系统 290

6.7.4案例实现：基于有向无环图的表达式计算 295

6.8本章小结 300

6.9习题与实验 301

第7章 查找 305

7.1问题的提出 305

7.2基本概念与描述 306

7.2.1查找的基本概念 306

7.2.2性能分析 307

7.2.3内部查找和外部查找 308

7.2.4 C语言描述 308

7.3线性表查找 308

7.3.1顺序查找 309

7.3.2二分查找 310

7.3.3分块查找 314

7.3.4案例实现：基于顺序查找的学生信息表查询 316

7.4树表查找 320

7.4.1二叉排序树 320

7.4.2平衡二叉树 328

7.4.3 B-树和B+树 344

7.4.4案例实现：基于二叉排序树的学生信息管理 352

7.5哈希表 357

7.5.1哈希表概念 357

7.5.2常用的哈希函数 358

7.5.3解决冲突的方法 359

7.5.4哈希表的查找及其性能分析 362

7.6本章小结 364

7.7习题与实验 365

第8章 排序 369

8.1问题的提出 369

8.2基本概念 369

8.3插入排序 371

8.3.1直接插入排序 371

8.3.2折半插入排序 373

8.3.3希尔排序 374

8.4交换排序 375

8.4.1冒泡排序 375

8.4.2快速排序 377

8.5选择排序 379

8.5.1简单选择排序 380

8.5.2堆排序 381

8.6归并排序 384

8.7基数排序 386

8.7.1多关键字排序 386

8.7.2链式基数排序 387

8.8案例实现：学生基本信息表的排序 390

8.9各种内部排序方法的比较 397

8.10本章小结 398

8.11习题 399

参考文献 402