数据结构经典算法实现与习题解答PDF电子书下载

目录 1

第1章　初识数据结构 1

1.1　数据结构回顾 1

1.1.1 数据结构的概念 1

1.1.2　系统的生命周期 2

1.2　算法的定义 3

1.3　算法性能分析和度量 7

1.3.1 算法评价的标准 7

1.3.2　算法复杂度的度量 7

1.4　数据抽象 12

1.5　常用教材习题解答 13

1.6　巩固练习 15

第2章 重要的C语言概念 17

2.1 基本数据类型回顾 17

2.1.1　整型数据 17

2.1.2　实型数据 17

2.1.3　字符型数据 18

2.2　基本控制语句 19

2.2.1　条件语句 19

2.2.2　循环语句 20

2.2.3　开关语句 27

2.3　结构和联合 30

2.3.1 结构 30

2.3.2 联合 35

第3章　数组 37

3.1　顺序数组 37

3.1.1 概念回顾 37

3.1.2　数据结构实现 37

3.2　实例—多项式的数组表示 38

3.3　实例—稀疏矩阵 39

3.3.1 概念回顾 39

3.3.2　矩阵置换 40

3.3.3 矩阵乘法 42

3.3.4　对角矩阵建立 44

3.3.5　三对角矩阵建立 45

3.3.6　三角矩阵建立 46

3.3.7　对称矩阵建立 47

3.4　字符串数组 48

3.4.1 基本操作实现 48

3.4.2　实例—串插入、串匹配及改进、串合并 49

3.5　常用教材习题解答 51

第4章　栈和队列 57

4.1 栈 57

4.1.1 概念回顾 57

4.1.2　数据结构实现 57

4.1.3　基本操作实现 58

4.1.4　实例—进制转换问题 62

4.2.2　数据结构实现 64

4.2 队列 64

4.2.1　概念回顾 64

4.2.3　基本操作实现 65

4.2.4　实例—舞伴问题 71

4.3　经典应用 74

4.3.1 迷宫问题 74

4.3.2 图元识别 76

4.3.3　括号匹配 79

4.3.4　火车车厢重排 81

4.3.5 开关盒布线 85

4.3.6 离线等价类 88

4.4　常用教材习题解答 91

第5章　链表 97

5.1 单链表 97

5.1.1 概念回顾 97

5.1.2　数据结构实现 97

5.1.3 基本操作实现 98

5.1.4　实例—动态堆栈、动态队列 108

5.2　双向链表 113

5.2.1　概念回顾 113

5.2.2　数据结构实现 113

5.2.3　基本操作实现 113

5.3.3　基本操作实现 116

5.3.2　数据结构实现 116

5.3.1　概念回顾 116

5.3　循环链表 116

5.4 实例—循环链表的多项式求解 117

5.5　实例—稀疏矩阵 121

5.5.1 稀疏矩阵的建立 123

5.5.2　稀疏矩阵的删除 125

5.6　经典应用—箱子排序 128

5.7　常用教材习题解答 130

第6章 递归 139

6.1 概念回顾 139

6.2.1　算法实现 140

6.2　实例—汉诺塔 140

6.2.2　递归过程分析 141

6.3 经典应用—八皇后问题 145

6.4　常用教材习题解答 147

第7章　树和森林 150

7.1 树和森林 150

7.1.1 概念回顾 150

7.1.2　数据结构实现 151

7.2　二叉树 154

7.2.1　概念回顾 154

7.2.2　数据结构实现 156

7.3 二叉树的遍历 159

7.3.1 中序遍历 159

7.3.2　前序遍历 160

7.3.3 后序遍历 161

7.3.4 应用实例 162

7.4　线索化二叉树 162

7.5　树与森林的转换 165

7.5.1 森林与二叉树的转换 165

7.5.2 森林的遍历 166

7.6 经典应用 168

7.6.1 信号放大器 168

7.6.2 在线等价类 171

7.7　常用教材习题解答 173

8.1.1 概念回顾 190

8.1 静态搜索 190

第8章 搜索 190

8.1.2　实例—顺序搜索 191

8.1.3　实例—基于有序表的折半搜索 192

8.2 二叉搜索树 194

8.2.1 概念回顾 194

8.2.2　基本操作实现 196

8.3 AVL树 201

8.3.1　概念回顾 201

8.3.2　基本操作实现 202

8.4　经典应用 205

8.4.1 直方图 205

8.4.2　箱子装载问题 206

8.4.3 交叉分布 208

8.5　常用教材习题解答 212

第9章 图 218

9.1 概念回顾 218

9.2　数据结构实现 218

9.2.1 图的邻接矩阵表示法 218

9.2.2 图的邻接表表示法 220

9.3　基本操作实现 223

9.3.1 深度优先搜索 223

9.3.2　广度优先搜索 225

9.3.3　连通分量 228

9.3.4 生成树 230

9.3.5　重连通分量 231

9.4 图的最小生成树 234

9.4.1 Kruskal算法 235

9.4.2 Prim算法 238

9.5 求解最短路径 240

9.5.1 单源全目的地的最短路径 241

9.5.2 所有对的最短路径 243

9.6　实例—活动网络（AOV） 244

9.7 经典应用 246

9.7.1 寻找路径 246

9.7.2 连通图 247

9.8　常用教材习题解答 249

10.1.2　基本操作实现 257

10.1.1　概念回顾 257

第10章　堆和哈希表 257

10.1 堆 257

10.2　哈希表 262

10.2.1　概念回顾 262

10.2.2　基本操作实现 263

10.2.3 静态哈希 267

10.2.4　动态哈希 270

10.3　经典应用 270

10.3.1 机器调度 270

10.3.2　霍夫曼编码 272

10.4 常用教材习题解答 274

11.2　插入排序 276

第11章　排序问题 276

11.1 概念回顾 276

11.3　交换排序 280

11.3.1 冒泡排序 280

11.3.2 快速排序 283

11.4　归并排序 285

11.4.1 概念回顾 285

11.4.2 自底向上的实现 285

11.4.3 自顶向下的实现 287

11.5.1 概念回顾 289

11.5.2　数据结构实现 289

11.5　堆排序 289

11.6　基数排序 290

11.6.1 概念回顾 290

11.6.2　链式排序实现 293

11.7　外排序 295

11.7.1 概念回顾 295

11.7.2　K路平衡归并 295

11.8 常用教材习题解答 297

第12章 经典算法设计 307

12.1　贪心算法 307

12.1.1 算法思想及描述 307

12.1.2　经典应用 309

12.2　分治算法 315

12.2.1 算法思想及描述 315

12.2.2　经典应用 316

12.3 动态规划 322

12.3.1 算法思想及描述 322

12.3.2　经典应用 322

12.4 回溯算法 326

12.4.1 算法思想及描述 326

12.4.2　经典应用 328

12.5　分枝定界算法 336

12.5.1　算法思想及描述 336

12.5.2　经典应用 337