数据结构与算法 第3版PDF电子书下载

第1章 绪论 1

1.1引言 1

1.1.1学习数据结构的目的 1

1.1.2“数据结构”课程的内容 3

1.2数据结构的概念 4

1.2.1基本概念和术语 4

1.2.2抽象数据类型 7

1.3算法 8

1.3.1算法的特性 8

1.3.2算法的描述 8

1.3.3算法的性能分析与度量 9

1.4递归 11

1.4.1递归的概念 11

1.4.2递归调用的实现原理 12

1.4.3递归转换为非递归 14

1.4.4递归应用举例 16

1.5本章知识点小结 17

练习题 17

实验题 20

第2章 基本线性结构 22

2.1线性表 22

2.1.1问题提出 22

2.1.2线性表的定义 23

2.1.3线性表的基本运算 23

2.2线性表的顺序存储与实现 24

2.2.1顺序表 24

2.2.2顺序表上基本运算的实现 25

2.2.3顺序表应用举例 29

2.3线性表的链式存储 31

2.3.1单链表 31

2.3.2单链表上基本运算的实现 33

2.3.3循环链表 39

2.3.4双向链表 40

2.3.5链表应用举例 41

2.4顺序表和链表的比较 44

2.5堆栈 45

2.5.1堆栈的定义 45

2.5.2堆栈的存储及基本运算的实现 46

2.5.3堆栈应用举例 49

2.6队列 57

2.6.1队列的定义 57

2.6.2队列的存储及运算的实现 58

2.6.3队列应用举例 64

2.7本章知识点小结 66

练习题 67

实验题 71

第3章 线性结构的扩展 74

3.1字符串 74

3.1.1字符串的基本概念 74

3.1.2顺序串 75

3.1.3模式匹配 78

3.2多维数组与特殊矩阵 83

3.2.1多维数组 83

3.2.2特殊矩阵 86

3.2.3稀疏矩阵 89

3.3广义表 99

3.3.1广义表的基本概念 99

3.3.2广义表的存储 100

3.4本章知识点小结 103

练习题 103

实验题 106

第4章 树结构 109

4.1引言 109

4.1.1问题提出 109

4.1.2相关概念 110

4.2二叉树 111

4.2.1二叉树的概念 112

4.2.2二叉树的主要性质 113

4.2.3二叉树的存储 115

4.2.4二叉树基本运算的实现 118

4.3二叉树的遍历 120

4.3.1递归方法实现二叉树的遍历 120

4.3.2非递归方法实现二叉树的遍历 122

4.3.3队列方法实现二叉树的层次遍历 125

4.4二叉树遍历的应用 126

4.4.1构造二叉树的二叉链表存储 126

4.4.2在二叉树中查找值为x的数据元素 127

4.4.3统计给定二叉树中叶子结点的数目 127

4.4.4由遍历序列恢复二叉树 127

4.5线索二叉树 129

4.5.1线索二叉树的定义及结构 129

4.5.2线索二叉树的构建 131

4.5.3线索二叉树的遍历 132

4.6最优二叉树 135

4.6.1最优二叉树的概念 135

4.6.2最优二叉树的构造 137

4.6.3最优二叉树的应用——哈夫曼编码 139

4.7树和森林 142

4.7.1树的基本操作与表示 142

4.7.2树的存储 143

4.7.3树和森林与二叉树之间的转换 146

4.7.4树和森林的遍历 148

4.7.5树的应用 149

4.8本章知识点小结 151

练习题 153

实验题 158

第5章 图结构 160

5.1引言 160

5.1.1问题提出 160

5.1.2相关概念 160

5.1.3图的基本操作 163

5.2图的存储方法 164

5.2.1邻接矩阵 164

5.2.2邻接表 166

5.2.3十字链表 168

5.2.4邻接多重表 170

5.3图的遍历 171

5.3.1深度优先搜索 172

5.3.2广度优先搜索 173

5.3.3应用图的遍历判定图的连通性 175

5.4生成树与最小生成树 176

5.4.1生成树和生成森林 176

5.4.2最小生成树 178

5.4.3构造最小生成树的Prim算法 179

5.4.4构造最小生成树的Kruskal算法 181

5.5最短路径 184

5.5.1单源点最短路径——Dijkstra算法 184

5.5.2每一对顶点之间的最短路径——Floyd算法 187

5.6拓扑排序 188

5.6.1有向无环图的概念 188

5.6.2 AOV网上的拓扑排序 189

5.7关键路径 193

5.7.1 AOE网上的关键路径 193

5.7.2关键路径的确定 194

5.8本章知识点小结 198

练习题 200

实验题 203

第6章 查找 205

6.1引言 205

6.1.1问题提出 205

6.1.2相关概念 205

6.2线性表查找 206

6.2.1顺序查找 207

6.2.2在顺序存储的有序表上查找 209

6.3树表查找 213

6.3.1二叉排序树 213

6.3.2平衡二叉树 219

6.3.3 B树和B+树 226

6.4散列表查找 232

6.4.1散列表 232

6.4.2常用的散列函数 233

6.4.3处理冲突的方法及散列表的构造 234

6.4.4散列表上的查找 238

6.4.5散列表上的删除 240

6.5本章知识点小结 240

练习题 241

实验题 245

第7章 排序 247

7.1引言 247

7.1.1问题提出 247

7.1.2相关概念 247

7.2插入排序 249

7.2.1直接插入排序 249

7.2.2折半插入排序 251

7.2.3希尔排序 251

7.3交换排序 253

7.3.1冒泡排序 253

7.3.2快速排序 254

7.4选择排序 256

7.4.1简单选择排序 256

7.4.2树型选择排序 258

7.4.3堆排序 258

7.5归并排序 262

7.5.1两个有序表的合并 262

7.5.2二路归并排序的迭代算法 263

7.5.3二路归并排序的递归算法 264

7.6基数排序 264

7.6.1多关键码排序 264

7.6.2链式基数排序 265

7.7排序方法比较 269

7.8本章知识点小结 270

练习题 271

实验题 274

第8章 扩展应用举例 275

8.1求最大子段和 275

8.1.1问题描述 275

8.1.2问题分析与解决 275

8.2表达式树的构造 279

8.2.1问题描述 279

8.2.2问题分析与解决 279

8.3由等价关系求划分 283

8.3.1问题描述 283

8.3.2问题分析与解决 283

8.4本章知识点小结 285

练习题 286

实验题 286

附录 288

附录A实验要求 288

附录B模拟试卷 291

模拟试卷一（本科水平） 291

模拟试卷二（本科水平） 293

模拟试卷三（研究生入学考试水平） 295

模拟试卷四（研究生入学考试水平） 297

参考文献 300