面向算法设计的数据结构(C++语言版)（第2版）

图书标准信息

• 作者 谢勰
• 出版社 清华大学出版社
• 出版时间 2021-12
• 版次 2
• ISBN 9787302590774
• 定价 59.00元
• 装帧 其他
• 开本 16开
• 纸张 胶版纸
• 页数 316页
• 字数 481.000千字

【内容简介】

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

【作者简介】

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

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

【目录】

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  [使用]  vector49

  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  [使用]  stack92

  5.3  stack的实现原理94

  5.4  [实例]  括号匹配95

  5.5  [实例]  路径搜索97

  5.6  习题101

6章  队列103

  6.1  概述103

  6.2  [使用]  queue103

  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  [使用]  urdered_set与urdered_multiset165

  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_queue185

  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和BFS217

    11.5.1  深度优先搜索218

    11.5.2  广度优先搜索218

    11.5.3  若干应用220

  11.6  [实例]  短路径*221

    11.6.1  Dijkstra算法221

    11.6.2  BellmanFordMoore算法222

    11.6.3  FloydWarshall算法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  GMP250

    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