数据结构与经典算法PDF电子书下载

第1章 基础知识 1

1.1 数据结构研究什么 1

1.2 基本概念和有关术语 3

1.3 数据类型与抽象数据类型 4

1.3.1 数据类型 4

1.3.2 抽象数据类型 4

1.4 算法描述与算法分析 6

1.4.1 算法的描述 6

1.4.2 算法的时间复杂度分析 7

1.4.3 算法的空间复杂度分析 8

1.5 小结 8

1.6 经典题库 9

1.6.1 要点提醒 9

1.6.2 经典剖析 9

1.7 练习 11

第2章 线性存储结构 13

2.1 线性表的定义及基本操作 13

2.1.1 线性表的基本概念 13

2.1.2 线性表的抽象数据类型 14

2.2 线性表顺序存储结构的定义 15

2.2.1 线性表顺序存储结构的定义 15

2.2.2 顺序表的基本操作及实现 16

2.2.3 顺序表的应用 18

2.3 线性表链式存储结构与实现 20

2.3.1 线性表链式存储结构 21

2.3.2 单链表及其基本操作 21

2.3.3 循环链表的基本操作及实现 29

2.3.4 双链表的基本操作及实现 33

2.3.5 循环双链表 37

2.4 实验 38

实验一：顺序表的操作 38

实验二：单链表连接 40

实验三：循环链表连接 43

实验四：循环双链表操作 47

2.5 小结 52

2.6 经典题库 52

2.6.1 要点提醒 52

2.6.2 经典剖析 53

2.7 练习 61

第3章 栈 65

3.1 栈 65

3.1.1 栈的基本概念 65

3.1.2 栈的抽象数据类型 65

3.1.3 栈的顺序存储结构及实现 66

3.1.4 栈的链式存储结构与实现 70

3.2 栈的应用 74

3.2.1 表达式求值 74

3.2.2 数制转换 76

3.2.3 括号匹配检验 77

3.2.4 栈与递归的实现 78

3.3 实验 79

实验：利用栈寻找迷宫路径 79

3.4 小结 82

3.5 经典题库 82

3.5.1 要点提醒 82

3.5.2 经典剖析 83

3.6 练习 86

第4章 队列 90

4.1 队列 90

4.1.1 什么是队列 90

4.1.2 队列的抽象数据类型 90

4.1.3 队列的顺序存储结构与实现 91

4.1.4 队列的链式存储结构与实现 97

4.2 队列的应用 101

4.3 实验 105

实验：利用队列模拟病人看病 105

4.4 小结 109

4.5 经典题库 109

4.5.1 要点提醒 109

4.5.2 经典剖析 109

4.6 练习 112

第5章 串 116

5.1 串的定义 116

5.1.1 串的定义 116

5.1.2 串的抽象数据类型 116

5.2 串的存储结构与实现 118

5.2.1 串的顺序存储结构与实现 118

5.2.2 串的堆存储结构与实现 121

5.2.3 串的块链存储结构与实现 122

5.3 串的模式匹配算法 123

5.3.1 简单的模式匹配算法——BF算法 123

5.3.2 改进的模式匹配算法——KMP算法 125

5.4 串的应用 127

5.5 实验 128

实验一：显示多位数数字字符 128

实验二：块链的基本操作 130

实验三：统计串中最长的重复子串 135

5.6 小结 137

5.7 经典题库 138

5.7.1 要点提醒 138

5.7.2 经典剖析 138

5.8 练习 140

第6章 数组与广义表 142

6.1 数组的定义 142

6.1.1 数组的概念与性质 142

6.1.2 抽象数据类型 143

6.2 数组相关结构的实现 143

6.2.1 数组的顺序存储 143

6.2.2 数组的基本操作实现 144

6.3 矩阵的压缩存储探究 147

6.3.1 特殊矩阵 147

6.3.2 稀疏矩阵 149

6.4 广义表 153

6.4.1 广义表相关概念 153

6.4.2 抽象数据类型 154

6.4.3 广义表存储结构详解 155

6.4.4 广义表的相关应用 156

6.5 实验 157

实验一：矩阵乘法 157

实验二：三元组实现两个矩阵的乘法 160

实验三：广义表的基本运算 163

6.6 小结 168

6.7 经典题库 169

6.7.1 要点提醒 169

6.7.2 经典剖析 169

6.8 练习 172

第7章 树型结构 175

7.1 树的基本概念和术语 175

7.1.1 树的基本概念 175

7.1.2 基本术语 175

7.2 二叉树 176

7.2.1 二叉树的基本概念 176

7.2.2 二叉树性质的探究 178

7.2.3 抽象数据类型 179

7.2.4 存储结构 181

7.3 遍历二叉树的方法 185

7.3.1 遍历的定义 185

7.3.2 遍历算法探究 186

7.4 线索二叉树 189

7.5 树和森林 192

7.5.1 树的存储结构 192

7.5.2 二叉树与森林 194

7.5.3 树和森林的遍历探究 195

7.6 哈夫曼树 196

7.6.1 哈夫曼树的基本概念 196

7.6.2 哈夫曼树的构造算法 197

7.6.3 哈夫曼树和哈夫曼编码 199

7.7 实验 201

实验一：运算二叉树 201

实验二：统计二叉树结点的个数 203

实验三：统计二叉树的宽度 205

实验四：按层遍历二叉树 207

7.8 小结 210

7.9 经典题库 210

7.9.1 要点提醒 210

7.9.2 经典剖析 210

7.10 练习 217

第8章 图状结构 220

8.1 图的相关定义和术语 220

8.1.1 图的基本概念 220

8.1.2 图的基本术语 220

8.1.3 抽象数据类型 222

8.2 图的存储结构探究 223

8.2.1 邻接矩阵 223

8.2.2 邻接表 225

8.2.3 十字链表 227

8.2.4 多重邻接表 228

8.3 图的遍历 229

8.3.1 深度优先遍历 229

8.3.2 广度优先遍历 230

8.4 最小生成树 231

8.4.1 生成树的概念 231

8.4.2 最小生成树 231

8.4.3 Prim算法 235

8.5 最短路径探究 238

8.5.1 单源点最短路径问题分析 238

8.5.2 所有顶点对应最短路径问题分析 240

8.6 拓扑排序探究 241

8.7 关键路径 244

8.8 实验 244

实验一：遍历算法 244

实验二：Prim算法 248

8.9 小结 253

8.10 经典题库 253

8.10.1 要点提醒 253

8.10.2 经典剖析 253

8.11 练习 264

第9章 查找 269

9.1 查找的基本概念 269

9.2 静态查找表 269

9.2.1 顺序表的查找 269

9.2.2 有序表的查找 270

9.2.3 索引顺序表的查找 271

9.2.4 静态树表的查找 273

9.3 动态查找表 274

9.3.1 二叉排序树 274

9.3.2 平衡二叉树 276

9.3.3 B－和B＋树 280

9.3.4 键树 288

9.4 哈希表 289

9.4.1 哈希表的概念 289

9.4.2 哈希表的构造方法 289

9.4.3 处理冲突的方法 290

9.4.4 哈希表的查找及分析 293

9.5 实验 294

实验一：二叉排序树的查找 294

实验二：哈希查找 298

9.6 小结 300

9.7 经典题库 301

9.7.1 要点提醒 301

9.7.2 经典剖析 301

9.8 练习 308

第10章 内部排序 310

10.1 插入排序 310

10.1.1 直接插入排序 310

10.1.2 希尔排序 311

10.2 交换排序 313

10.2.1 冒泡排序 313

10.2.2 快速排序 315

10.3 选择排序 316

10.3.1 简单选择排序 316

10.3.2 堆排序 317

10.4 归并排序 320

10.5 基数排序 321

10.6 各种内排序方法的比较 324

10.7 实验 325

实验一：双向冒泡排序 325

实验二：数组归并排序 328

实验三：计数排序 331

实验四：字符串排序 332

实验五：最高位关键字排序MSD 335

10.8 小结 338

10.9 经典题库 338

10.9.1 要点提醒 338

10.9.2 经典剖析 339

10.10 练习 343

第11章 经典算法 345

11.1 基础算法 345

11.1.1 河内之塔 345

11.1.2 八皇后 346

11.1.3 背包问题 348

11.2 数、运算 352

11.2.1 筛选求质数 352

11.2.2 最大公因数、最小公倍数、因式分解 353

11.2.3 最大访客数 356

11.3 关于博弈 358

11.3.1 洗扑克牌（乱数排列） 358

11.3.2 Craps赌博游戏 360

11.4 集合问题 362

11.4.1 格雷码（Gray Code） 362

11.4.2 m元素集合的n元子集 364

11.5 矩阵 365

11.5.1 稀疏矩阵存储 365

11.5.2 上三角、下三角、对称矩阵存储 367

11.5.3 奇数魔方阵 369

第12章 数据分析与挖掘 371

12.1 大数据时代的挖掘 371

12.1.1 数据挖掘 371

12.1.2 从数据挖掘应用的角度看大数据 372

12.2 挖掘技术发展和历史 373

12.3 十大挖掘算法简介 374

参考文献 378