本书以算法分析为导向，以算法效率为准绳，着墨于抽象数据类型的选择、使用和组合，从而实现提升算法性能的**目标，凸显“数据结构要为算法服务”的特色。本书基于抽象数据类型的观点来讲解数据结构，力图让读者学会以“积木式”组件方案快速、便捷、高效地构建程序，并在此基础上以迭代器和区间表示动态集合，给出更具一般性的泛型算法。本书代码采用简洁明晰的现代C++语言描述，尽量吸收**语言标准，力求紧跟程序设计语言的时代脉搏，并提供了便于维护的在线形式。全书内容组织以标准模板库（STL）为纲，涵盖了常见的数据结构，并给出实际场景中的案例，真正体现学以致用。此外，本书还特别论及各种容器和泛型算法的时空性能，方便读者对设计方案给出渐近分析。

缘起

    范文澜曾云“板凳要坐十年冷”，古文里也常常可见“十年寒窗”，而Peter Norvig更是写过一篇异曲同工的妙文Teach Yourself Programming in Ten Years。尽管一般人不可能用十年去培养非常专业的功底，但我们希望在有限的学习时间内培养读者的基本技能，并为他们打开程序设计这扇神奇之窗。

    那么如何尽快学会搭建程序呢? 乐高积木为我们提供了一种很好的思路，只需使用基本的“积木式”组件便可迅速完成程序设计。抽象数据类型正是这样的积木，而C++的标准模板库(STL)已为我们准备好了。

    在学会组建程序的基础上，我们要求从算法角度分析效率，而抽象数据类型的简约性更利于在宏观上尽快给出优良的方案设计。因此，贯穿全书的主线是抽象数据类型的选择、使用和组合。

    我们特别强调在抽象数据类型选用时必须以算法分析为导向，以算法效率为准绳。对于以不同抽象数据类型为要素的实现方案，其选择标准是完成整个方案所需的时空开销。此外，我们还会关注同一抽象数据类型在不同数据结构实现下的性能差异。在上述思想指导下，本书力求给出一种全新的模式，让读者尽快学会高效使用抽象数据类型，最终为后续的算法设计课程打下坚实的基础。

特色

    首先，我们希望培养读者的算法思维乃至于计算思维。在长期随意手工计算的影响下,许多人很自然地将自己的行为习惯迁移到算法设计中，其表现有多种: 例如操作方式天马行空，处理数据时充满了人的跳跃性，而毫无“机械式”的章法(或者说“系统化”的处理方式);又如侧重对小规模具体实例优化，而不考虑一般情况。实际上，如今我们处理的许多问题会涉及巨量的数据，如何高效计算则成为关键问题，要突破必须及早培养计算思维。

    其次，本书力图破除很多人“只见树木，不见森林”的程序编写思路。要转为从抽象数据类型的角度思考问题，而不至于过早陷入代码细节中。全书对于数据结构的讲解侧重于如何用好抽象数据类型的各种操作，特别是每项操作的时空效率，而这正是现代算法设计对数据结构知识的要求。至于传统数据结构教程强调的各种数据结构实现则不是我们关注的重点，实际上实现类库的工作相当专业，若非数十年功力绝难完成，君不见迄今为止能经得起推敲的模板库寥寥无几。从这个角度看，学好抽象数据类型并能灵活运用才应该是我们追求的目标。因此，本书着重使用STL类库解决实际问题，让读者能尽快看到数据结构的应用，而不是建立空中楼阁。

    我们还将突出深入计算机内部的思想，尽量让读者把握各个时刻计算机中的实际数据情况，不妨称为{0，1}思维。这种从底层去探究算法运行本质的方法不但有助于理解算法运行情况，更能提高算法设计水平。例如初学者按照此角度可时时提醒自己要按照“机械式”方式给出步骤，而专业人士则能在纷繁复杂的数据和算法步骤中找到规律进而优化。通俗地说，要把自己想象成计算机，这样身临其境方能参透奥秘。

    在许多教材中，算法只是观念上的实现，从而导致教材自身不注重具体代码的编写，即便包含代码也未精化。我们希望能给出清晰高效且具备良好代码风格的C++语言实现，并尽量兼顾学术前沿和工程实践。因此本书在第1版所创建的DSAD项目(https://github.com/xiexiexx/DSAD)会继续更新完善，读者可获取源代码以及全书勘误表。另外，为了便于修订，书中很多程序以在线代码形式呈现(配有网址并附二维码)，阅读时以在线版本为准。

重构

    第2版的修订融入了这几年的一些教学思考，特别是“集合”抽象数据类型和迭代器区间的理念。为此我们重写了第2章并以此为核心重构了全书的写作。

· 泛型抽象: 从集合的观点出发，再配合迭代器，可以将很多算法抽象化，并能方便地转换成其他程序设计语言实现。

· 代码重构: 以更简明的形式改写，并修订了旧版的若干错漏之处。采用现代C++语言描述，程序编写与表达更为自然。

· 学以致用: 更加全面地讲解了STL中的容器功能，同时也尽量利用algorithm库的算法函数构建代码，从而增强本书的实用性。

组织

    教材内容组织安排上遵循以抽象数据类型为核心的思想，突出如何以抽象数据类型搭建算法和应用程序。为此，本书中很多章节标示了分类:

· [使用] 主要讲解STL中容器的功能，解决抽象数据类型如何使用的问题。

· [技巧] 深入剖析算法与编程的技巧，主要关注效率的提升。

· [实例] 针对具体案例给出完整的解决方案，展示数据结构与算法的典型应用场景。

说明

· 本书尽量使用现代C++编写程序，因此请读者下载最新版本的编译器。不过考虑到编程习惯，我们没有完全使用现代C++，例如空指针nullptr。此外，本书中的部分代码还使用了模块(module)形式实现，不妨参阅DSAD项目。

· 除了若干单独执行的程序，书中的其他代码可编译后并链接(例如在IDE中以工程形式组织并整合)，而包含main函数的源文件为DSAD.cpp(见附录)，可调用其中的演示程序查看运行效果，这样使用本书的代码会更加方便。

· 初学者可以略过数学推导较多的部分，特别是算法分析，但得了解常见渐近记号的含义并能加以对比。

· 在一般情况下，本书中log()一般指代log_2()，即我们主要讨论以2为底的对数。此外，这种表示方法意味着渐近记号中对数的底并无实质性影响。

· 不同字体代表不同对象，另外如果同名则意味着指代相同: 例如n表示数学公式中的符号，而n代表程序中使用的变量，不过它们都指代同一个量，例如某个数组的长度。

· 本书仅讲解一些基本的排序和查找内容，并分散于不同章节，而更深入的相关内容留待算法课程中再讨论。

· 书中加星号的章节和习题为选学与选做内容，读者可根据需要取舍。

· 为了突出C/C++语言下标的特色，本书中的代码以编号标注并从0开始(自然数亦是如此)。另外，单行代码或者算法运行步骤以->作为指示。

· 每章的注释部分提供了“代码延伸阅读”，作为进阶学习之用。

致谢

    在本书的写作过程中，得到了诸多朋友的大力支持(初稿写作的致谢名单详见第1版)，特别是在微博以及GitHub上的网络互动带来的教学相长(恕我无法一一列出)。感谢本书编辑龙启铭先生对作者的耐心包容。感谢我的父亲为本书题字。特别还要感谢试用本书的各位同学，正是他们促进了这本书的不断完善。

    由于作者水平所限，恳请大方之家对本书指正建言。发现书中问题的读者朋友将获得一张签名电子明信片(以提交时间次序为准)，并会列入致谢名单。在发送您的意见和建议之前，请先查阅勘误表(https://github.com/xiexiexx/DSAD)。

谢勰

2021年6月

于“算法时空”

第1章  算法------1

  1.1  概述------1

  1.2  [实例]  二分查找------3

  1.3  程序性能与算法分析------5

    1.3.1  运行时间------7

    1.3.2  占用空间------8

  1.4  渐近记号------9

  1.5  [技巧]  阶的快速比较*------13

    1.5.1  加和型无穷大量阶的比较------14

    1.5.2  乘积型无穷大量阶的比较------15

    1.5.3  对数型无穷大量阶的比较------16

  1.6  习题------18

第2章  抽象数据类型------21

  2.1  概述------21

  2.2  [实例]  查找问题------22

    2.2.1  缺点一: 长度受限制------23

    2.2.2  缺点二: 有序则难变------25

    2.2.3  缺点三: 查变难两全------26

    2.2.4  抽象数据类型视角------27

  2.3  集合------28

  2.4  功能与实现------30

    2.4.1  向量简介------31

    2.4.2  有序向量实现------32

    2.4.3  无序向量实现------35

    2.4.4  对比------38

  2.5  [技巧]  组装使用------39

  2.6  STL容器一览------41

  2.7  设计模式------44

    2.7.1  迭代器------44

    2.7.2  适配器------45

    2.7.3  组合------45

  2.8  习题------47

第3章  向量------49

  3.1  概述------49

  3.2  [使用]  vector------49

  3.3  vector的实现原理------53

  3.4  加倍技术*------54

  3.5  [技巧]  物理存储与进制换算------56

    3.5.1  一维数组------56

    3.5.2  二维数组------56

    3.5.3  多维向量------57

  3.6  [技巧]  自然数映射与下标------59

  3.7  [实例]  矩阵的向量实现------61

    3.7.1  矩阵的简易实现------61

    3.7.2  稀疏矩阵------64

  3.8  习题------67

第4章  递归------71

  4.1  概述------71

  4.2  [技巧]  递归设计与归纳证明------72

  4.3  递归与进程模型------75

  4.4  递归算法性能分析------76

  4.5  [实例]  排列生成器*------79

    4.5.1  利用vector传值实现------81

    4.5.2  利用vector引用实现------82

  4.6  [实例]  乐高铺砖------84

  4.7  习题------89

第5章  栈------91

  5.1  概述------91

  5.2  [使用]  stack------92

  5.3  stack的实现原理------94

  5.4  [实例]  括号匹配------95

  5.5  [实例]  路径搜索------97

  5.6  习题------101

第6章  队列------103

  6.1  概述------103

  6.2  [使用]  queue------103

  6.3  [技巧]  循环向量设计------104

    6.3.1  使用两个位置指示------105

    6.3.2  使用计数信息------107

    6.3.3  缓冲区------107

  6.4  queue的实现原理------110

  6.5  [实例]  贾宪三角------112

  6.6  [技巧]  排队组织与内蕴次序------115

  6.7  习题------116

第7章  链------119

  7.1  概述------119

  7.2  [使用]  list ------120

  7.3  [技巧]  用于链接的指针------124

    7.3.1  利用指针实现链接功能------124

    7.3.2  使用真实链首元素指针------125

    7.3.3  使用哑结点解决空链判断问题------127

  7.4  链的变种------129

    7.4.1  单链------129

    7.4.2  单循环链------129

    7.4.3  双循环链------129

  7.5  list的实现原理------130

  7.6  [技巧]  基于归纳的初始条件选取------131

  7.7  [实例]  归并排序------133

  7.8  习题------137

第8章  二叉树------139

  8.1  概述------139

  8.2  二叉树与树------140

  8.3  [技巧]  二叉树遍历------143

  8.4  [技巧]  递归处理二叉树------149

  8.5  [实例]  二叉查找树------153

    8.5.1  特性------153

    8.5.2  查找------154

    8.5.3  插入------155

    8.5.4  删除------155

    8.5.5  迭代器------157

    8.5.6  效率------157

  8.6  习题------158

第9章  集合------161

  9.1  概述------161

  9.2  [使用]  set与multiset ------162

  9.3  [使用]  unordered_set与unordered_multiset------165

  9.4  [实例]  寻找宝藏------169

  9.5  [技巧]  哨兵------171

    9.5.1  线性查找中的哨兵------171

    9.5.2  二叉查找树中的哨兵------173

  9.6  [技巧]  集合与序关系------174

    9.6.1  排序------175

    9.6.2  中位数------175

  9.7  [技巧]  不相交集------176

  9.8  习题------183

第10章  优先级队列------185

  10.1  概述------185

  10.2  [使用]  priority_queue------185

  10.3  [技巧]  维护最大元------187

  10.4  priority_queue的实现原理------190

  10.5  [实例]  堆排序------193

    10.5.1  数据组织与排序------193

    10.5.2  建堆算法------194

  10.6  [实例]  Huffman编码------196

  10.7  习题------204

第11章  图------205

  11.1  概述------205

  11.2  图的表示------207

    11.2.1  邻接矩阵------208

    11.2.2  邻接表------209

    11.2.3  选用------210

  11.3  图类------210

  11.4  [技巧]  编号与反向映射------214

  11.5  [技巧]  DFS和BFS------217

    11.5.1  深度优先搜索------218

    11.5.2  广度优先搜索------218

    11.5.3  若干应用------220

  11.6  [实例]  最短路径*------221

    11.6.1  Dijkstra算法------221

    11.6.2  Bellman-Ford-Moore算法------222

    11.6.3  Floyd-Warshall算法------223

  11.7  [实例]  最小生成树------224

    11.7.1  Kruskal算法------225

    11.7.2  Prim算法------226

  11.8  习题------228

第12章  实验------229

  12.1  多维求和------229

    12.1.1  一维部分和------229

    12.1.2  实验要求------230

    12.1.3  评注与引申------230

  12.2  幻方计数------231

    12.2.1  排列------231

    12.2.2  实验要求------232

    12.2.3  评注与引申------233

  12.3  随机行走------233

    12.3.1  伪随机数生成------233

    12.3.2  实验要求------234

    12.3.3  评注与引申------236

  12.4  纸牌游戏------237

    12.4.1  可数集------237

    12.4.2  实验要求------238

    12.4.3  评注与引申------241

  12.5  迷宫生成------242

    12.5.1  隔板型迷宫------242

    12.5.2  实验要求------243

    12.5.3  评注与引申------243

  12.6  数据压缩------243

    12.6.1  存储数据------243

    12.6.2  实验要求------244

    12.6.3  评注与引申------244

  12.7  会场安排------245

    12.7.1  时间格式------245

    12.7.2  实验要求------246

    12.7.3  评注与引申------246

  12.8  排序测试------247

    12.8.1  随机置换------247

    12.8.2  实验要求------248

    12.8.3  评注与引申------249

  12.9  大数运算------250

    12.9.1  GMP------250

    12.9.2  实验要求------251

    12.9.3  评注与引申------252

附录A  编程技巧------253

  A.1  循环不变式------253

  A.2  逻辑表达式优化------255

附录B  代码进阶------263

  B.1  计时类------263

  B.2  代码整合------264

  B.3  动态数组------274

  B.4  双循环链*------281

参考文献------297

以算法分析为导向，以算法效率为准绳，着墨于抽象数据类型的选择、使用和组合，从而实现提升算法性能的**目标，凸显“数据结构要为算法服务”的特色

姓名：谢勰 单位：西安邮电大学 职务、职称：副教授 性别：男  年龄：39

主要从事算法与数据结构相关课程的教学，多年以来承担《信息安全算法设计》、《信息论基础》和《现代编码技术》等多门课程。作为副主编所编写教材《离散信息论基础》获陕西普通高等学校优秀教材一等奖并入选“十二五”普通高等教育本科国家级规划教材，翻译出版了算法设计领域的经典著作《算法设计指南》(The Algorithm Design Manual)，以信息安全专业为试点编写了较为新颖的《面向算法设计数据结构（C++语言版）》。积极将算法与数学理论成果实用化，带队多次荣获美国大学生数学建模竞赛(MCM)一等奖。