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

第1章 数据结构和算法 1

1.1 数据和数据类型 1

1.1.1 数据和数据元素 1

1.1.2 数据类型 2

1.1.3 抽象数据类型 4

1.1.4 抽象数据类型程序应用实例 5

1.1.5 数据对象 6

1.2 数据结构 6

1.2.1 数据的逻辑结构 6

1.2.2 数据元素的存储结构 8

1.2.3 常用的数据运算 10

1.3 算法描述工具——C语言 12

1.3.1 指针类型与指针变量 13

1.3.2 结构类型与结构变量 15

1.3.3 函数与参数 17

1.3.4 递归定义和递归函数 18

1.3.5 动态存储分配 19

1.3.6 文件操作 21

1.3.7 程序测试与测试集 23

1.3.8 测试数据的设计 23

1.3.9 程序调试问题 25

1.4 算法和算法评价 25

1.4.1 算法的概念 25

1.4.2 算法的性质 27

1.4.3 算法的评价标准 28

1.5 算法性能分析 29

1.5.1 算法的时间性能分析 29

1.5.2 算法的空间性能分析 33

小结 33

习题 34

第2章 顺序表及其应用 38

2.1 顺序表的基本概念 38

2.1.1 顺序表的定义 38

2.1.2 顺序表的数据结构分析 38

2.1.3 顺序表的数据类型描述 39

2.2 顺序表基本算法 40

2.3 顺序表基本算法性能分析 43

2.3.1 时间性能分析 43

2.3.2 空间性能分析 44

2.4 顺序表的应用1——查找问题 44

2.4.1 查找的概念 44

2.4.2 简单顺序查找算法 45

2.4.3 有序表的二分查找算法 47

2.4.4 分块查找算法 51

2.4.5 3种查找算法的性能比较 52

2.5 顺序表的应用2——排序问题 53

2.5.1 排序的概念 53

2.5.2 顺序表的数据类型 54

2.5.3 插入排序——直接插入排序算法 54

2.5.4 插入排序——希尔排序算法 57

2.5.5 交换排序——冒泡排序算法 59

2.5.6 交换排序——快速排序算法 61

2.5.7 选择排序——直接选择排序算法 65

2.5.8 归并排序算法 67

2.5.9 排序算法的性能分析与比较 71

2.6 顺序表的应用3——字符处理问题 71

2.6.1 串和顺序串的定义及相关概念 71

2.6.2 顺序串的数据结构分析 72

2.6.3 顺序串的基本运算 72

2.6.4 顺序串的数据类型定义 74

2.6.5 顺序串的基本运算算法 74

2.6.6 串的模式匹配算法 77

小结 78

习题 78

第3章 链表及其应用 83

3.1 链表的基本概念 83

3.1.1 链表的定义 83

3.1.2 链表的逻辑结构 83

3.1.3 链表的存储结构 84

3.1.4 静态链表和动态链表 85

3.1.5 链表基本运算 86

3.2 单链表的数据结构 86

3.2.1 单链表的逻辑结构 86

3.2.2 单链表的存储结构 86

3.3 单链表基本算法 88

3.3.1 单链表的基本算法 88

3.3.2 单链表基本算法性能分析 93

3.4 循环链表 94

3.4.1 单循环链表 94

3.4.2 双向循环链表 95

3.4.3 双向循环链表的结点插入算法 96

3.4.4 双向循环链表的结点删除算法 97

3.5 链表的应用 98

3.5.1 多项式相加问题 98

3.5.2 两个链表的归并问题 101

3.5.3 箱子排序问题 103

3.5.4 链表在字符处理方面的应用——链串 105

小结 107

习题 107

第4章 堆栈及其应用 112

4.1 堆栈的基本概念 112

4.1.1 堆栈的定义 112

4.1.2 堆栈的逻辑结构 112

4.1.3 堆栈的基本算法 113

4.2 顺序栈及其基本算法 113

4.2.1 顺序栈的概念及数据类型 113

4.2.2 顺序栈的基本算法 114

4.2.3 顺序栈基本算法性能分析 115

4.3 链栈及其基本算法 116

4.3.1 链栈的概念及数据类型 116

4.3.2 链栈的基本算法 117

4.3.3 链栈基本算法性能分析 118

4.4 堆栈的应用 118

4.4.1 数制转换问题 118

4.4.2 简单的文字编辑器问题 119

4.4.3 表达式计算问题 120

4.4.4 括号匹配问题 126

4.4.5 汉诺塔问题 128

4.4.6 火车车厢重排问题 132

4.4.7 开关盒布线问题 136

4.4.8 离线等价类问题 139

4.4.9 迷宫老鼠问题 142

小结 145

习题 146

第5章 队列及其应用 149

5.1 队列的基本概念 149

5.1.1 队列的定义 149

5.1.2 队列的逻辑结构 150

5.1.3 队列的基本算法 150

5.2 顺序队列及其基本算法 150

5.2.1 顺序队列的概念及数据类型 150

5.2.2 顺序循环队列 151

5.2.3 循环队列基本算法 153

5.2.4 循环队列基本算法性能分析 154

5.3 链队列及其基本算法 155

5.3.1 链队列的概念及数据类型 155

5.3.2 链队列基本算法 156

5.3.3 链队列基本算法性能分析 157

5.4 基数排序问题 157

5.4.1 多关键字排序问题 158

5.4.2 链式基数排序算法思想 158

5.4.3 链式基数排序算法实现的技术要点 160

5.4.4 链表基数排序算法及其性能分析 160

5.5 火车车厢重排问题 162

5.5.1 问题分析及算法思想 162

5.5.2 火车车厢重排算法设计 162

5.5.3 火车车厢重排算法及其性能分析 163

5.6 电路布线问题 165

5.6.1 电路布线问题分析 165

5.6.2 电路布线问题算法思想 165

5.6.3 电路布线问题算法设计 166

5.6.4 电路布线问题算法及其性能分析 166

5.7 识别图元问题 168

5.7.1 识别图元问题分析 168

5.7.2 识别图元算法设计 168

5.7.3 识别图元算法及其分析 169

5.8 工厂仿真问题 170

5.8.1 工厂仿真问题分析 170

5.8.2 工厂仿真问题算法设计 171

5.8.3 工厂仿真问题算法及其性能分析 173

小结 174

习题 174

第6章 特殊矩阵、广义表及其应用 178

6.1 数组与矩阵 178

6.1.1 数组与矩阵的概念及其相互关系 178

6.1.2 数组的存储结构 179

6.2 特殊矩阵的压缩存储 180

6.2.1 对称矩阵及其存储结构 181

6.2.2 三角矩阵及其存储结构 181

6.2.3 对角矩阵及其存储结构 182

6.2.4 稀疏矩阵及其存储结构和建表算法 183

6.3 矩阵的应用实例 187

6.3.1 稀疏矩阵的转置问题 187

6.3.2 稀疏矩阵的加法运算问题 189

6.4 广义表 193

6.4.1 广义表的概念 193

6.4.2 广义表的存储结构 194

6.4.3 广义表的应用——m元多项式的表示 196

小结 198

习题 198

第7章 二叉树及其应用 201

7.1 二叉树的基本概念 201

7.1.1 二叉树的定义 201

7.1.2 二叉树的基本术语 202

7.1.3 两种特殊的二叉树 202

7.1.4 二叉树的性质 203

7.2 二叉树的存储结构 205

7.2.1 二叉树的顺序存储结构 205

7.2.2 二叉树的链接存储结构 205

7.2.3 建立二叉树的算法 206

7.3 二叉树的遍历算法 208

7.3.1 二叉树遍历的概念 208

7.3.2 二叉树遍历递归算法 209

7.3.3 二叉树先序遍历非递归算法 211

7.3.4 二叉树中序遍历非递归算法 212

7.3.5 二叉树后序遍历非递归算法 213

7.4 线索二叉树 214

7.4.1 线索二叉树的概念 214

7.4.2 二叉树的线索化 215

7.4.3 线索二叉树的查找算法 216

7.5 二叉树的应用1——基本算法 217

7.6 二叉树的应用2——哈夫曼树 220

7.6.1 基本概念 220

7.6.2 哈夫曼树 221

7.6.3 哈夫曼树的构造过程 221

7.6.4 哈夫曼树的存储结构及哈夫曼算法 222

7.6.5 哈夫曼算法 223

7.6.6 哈夫曼树的应用——哈夫曼编码 223

7.7 二叉树的应用3——二叉排序树 225

7.7.1 二叉排序树及其性质 225

7.7.2 二叉排序树的存储结构 226

7.7.3 二叉排序树的结点查找算法 226

7.7.4 二叉排序树的结点插入算法 227

7.7.5 二叉排序树的生成算法 228

7.7.6 二叉排序树的结点删除算法 229

7.7.7 二叉排序树结点查找算法性能分析 231

7.7.8 平衡二叉排序树 232

7.8 二叉树的应用4——堆和堆排序 239

7.8.1 堆和堆排序的概念 239

7.8.2 堆的调整算法 240

7.8.3 建堆 242

7.8.4 堆排序算法及性能分析 243

小结 244

习题 244

第8章 树和森林及其应用 253

8.1 树和森林的基本概念 253

8.1.1 树和森林的定义 253

8.1.2 树的性质 254

8.1.3 树和森林的遍历 255

8.1.4 树、森林与二叉树的关系 256

8.2 树的存储结构 258

8.2.1 树的顺序存储结构 258

8.2.2 树的链接存储结构 259

8.3 树的基本算法及性能分析 261

8.3.1 树转换为二叉树算法及性能分析 261

8.3.2 森林转换为二叉树算法及性能分析 262

8.3.3 二叉树转换为树算法及性能分析 263

8.3.4 二叉树转换为森林算法及性能分析 265

8.3.5 树的遍历算法 265

8.3.6 森林的遍历算法 266

8.4 树的应用——B树 267

8.4.1 B树的概念 267

8.4.2 B树的数据存储类型 267

8.4.3 B树的查找算法 268

8.4.4 B树的插入算法 270

8.4.5 B树的删除算法及实例 275

小结 278

习题 278

第9章 散列结构及其应用 282

9.1 散列结构的基本概念 282

9.1.1 散列结构的概念 282

9.1.2 散列存储结构——散列表 283

9.1.3 散列函数 284

9.1.4 冲突处理方法——开放定址法 287

9.1.5 冲突处理方法——链地址法 289

9.2 线性探测散列算法 290

9.2.1 线性探测散列算法的数据类型 290

9.2.2 线性探测散列基本算法 290

9.3 链地址法散列算法 293

9.3.1 链地址散列算法的数据类型 293

9.3.2 链地址散列基本算法 294

9.4 散列结构的查找性能分析 295

9.5 散列结构应用1——LZW压缩问题 296

9.5.1 LZW压缩问题 296

9.5.2 LZW压缩算法及其算法性能分析 297

9.5.3 LZW解压缩问题 298

9.5.4 LZW解压缩算法及其算法性能分析 299

9.6 散列结构应用2——直接存取文件 300

9.6.1 基本概念 300

9.6.2 直接存取文件的存储结构及类型 301

9.6.3 文件操作1——查找结点算法 301

9.6.4 文件操作2——增加结点算法 302

9.6.5 文件操作3——删除结点算法 303

小结 304

习题 304

第10章 图及其应用 307

10.1 图的概念 307

10.1.1 图的定义 307

10.1.2 图的基础知识 308

10.1.3 图的基本运算 311

10.2 图的存储结构及其基本算法 312

10.2.1 邻接矩阵及其数据类型 312

10.2.2 邻接矩阵的基本算法 314

10.2.3 邻接表及其数据类型 315

10.2.4 邻接表的基本算法 317

10.2.5 逆邻接表 318

10.2.6 十字链表及其数据类型 319

10.2.7 十字链表的基本算法 320

10.2.8 邻接多重表及其数据类型 321

10.2.9 邻接多重表的基本算法 322

10.3 图的遍历及算法 323

10.3.1 深度优先搜索遍历 324

10.3.2 深度优先搜索遍历算法 324

10.3.3 广度优先搜索遍历 325

10.3.4 广度优先搜索遍历算法 326

10.4 有向图的连通性和最小生成树 327

10.4.1 有向图的连通性分析 327

10.4.2 连通网的最小生成树问题——通信网络问题 328

10.5 图的（最小）生成树问题 328

10.5.1 图的生成树 328

10.5.2 最小生成树算法——普利姆算法 329

10.5.3 最小生成树算法——克鲁斯卡尔算法 331

10.6 非连通图的生成森林算法 332

10.7 最短路径 335

10.7.1 最短路径问题 335

10.7.2 从某源点到其余各项点之间的最短路径问题——迪杰斯特拉算法 336

10.7.3 每一对顶点之间的最短路径问题——弗洛伊德算法 338

10.8 有向无环图及其应用 340

10.8.1 有向无环图及其应用问题实例 340

10.8.2 AOV网及其特性 342

10.8.3 拓扑排序及其算法 343

10.8.4 AOE网 345

10.8.5 关键路径及有关概念 345

10.8.6 关键路径求解及其算法思想 346

10.8.7 AOE网关键路径求解算法的数据类型 347

10.8.8 AOE网中求解关键路径的算法 347

10.8.9 关键路径求解算法分析 349

小结 350

习题 351

第11章 算法性能分析和算法设计方法简介 357

11.1 算法和程序 357

11.1.1 算法与程序分析 357

11.1.2 空间复杂性分析 358

11.1.3 时间复杂度分析 359

11.2 再谈算法性能问题 360

11.2.1 时间复杂度的上限值 361

11.2.2 定理11.2的证明 361

11.2.3 时间复杂度的下限值 362

11.2.4 有关渐进符号的计算 362

11.3 算法性能测量问题 363

11.3.1 算法性能测量问题分析 363

11.3.2 算法性能测量实例 363

11.4 算法设计方法简介 364

11.4.1 分而治之算法设计方法 365

11.4.2 最优化问题简介 365

11.4.3 贪婪算法设计方法 366

11.4.4 回溯算法设计方法 368

11.5 NP问题简介 369

11.6 散列表查找性能 370

11.7 讨论题 371

附录A 本书算法源程序 373

参考文献 414