数据结构（C++语言版） 第2版【2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载】

数据结构（C++语言版） 第2版PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第1章 绪论1

1.1计算机与算法2

1.1.1古埃及人的绳索2

1.1.2欧几里得的尺规3

1.1.3起泡排序4

1.1.4算法5

1.1.5算法效率7

1.2复杂度度量8

1.2.1时间复杂度8

1.2.2渐进复杂度9

1.2.3空间复杂度11

1.3复杂度分析11

1.3.1常数σ（1）12

1.3.2对数σ（logn）12

1.3.3线性σ（n）13

1.3.4多项式σ（polynomial（n））14

1.3.5指数σ（2 n）14

1.3.6复杂度层次15

1.3.7输入规模16

1.4递归16

1.4.1线性递归17

1.4.2递归分析17

1.4.3递归模式19

1.4.4递归消除22

1.4.5二分递归23

1.5抽象数据类型26

习题26

第2章 向量31

2.1从数组到向量32

2.1.1数组32

2.1.2向量33

2.2接口33

2.2.1 ADT接口33

2.2.2操作实例34

2.2.3 Vector模板类34

2.3构造与析构36

2.3.1默认构造方法36

2.3.2基于复制的构造方法36

2.3.3析构方法37

2.4动态空间管理37

2.4.1静态空间管理37

2.4.2可扩充向量38

2.4.3扩容38

2.4.4分摊分析39

2.4.5缩容40

2.5常规向量41

2.5.1直接引用元素41

2.5.2置乱器41

2.5.3判等器与比较器42

2.5.4无序查找43

2.5.5插入44

2.5.6删除45

2.5.7唯一化46

2.5.8遍历47

2.6有序向量48

2.6.1比较器48

2.6.2有序性甄别49

2.6.3唯一化49

2.6.4查找51

2.6.5二分查找（版本A）52

2.6.6 Fibonacci查找55

2.6.7二分查找（版本B）58

2.6.8二分查找（版本C）59

2.7排序与下界60

2.7.1有序性60

2.7.2排序及其分类60

2.7.3下界61

2.7.4比较树62

2.7.5估计下界62

2.8排序器63

2.8.1统一入口63

2.8.2起泡排序64

2.8.3归并排序65

习题68

第3章 列表73

3.1从向量到列表74

3.1.1从静态存储到动态存储74

3.1.2由秩到位置75

3.1.3列表75

3.2接口75

3.2.1列表节点75

3.2.2列表76

3.3列表79

3.3.1头、尾节点79

3.3.2默认构造方法79

3.3.3由秩到位置的转换80

3.3.4查找80

3.3.5插入80

3.3.6基于复制的构造82

3.3.7删除83

3.3.8析构84

3.3.9唯一化84

3.3.10遍历85

3.4有序列表85

3.4.1唯一化85

3.4.2查找86

3.5排序器86

3.5.1统一入口86

3.5.2插入排序87

3.5.3选择排序88

3.5.4归并排序89

习题91

第4章 栈与队列93

4.1栈94

4.1.1 ADT接口94

4.1.2操作实例95

4.1.3 Stack模板类95

4.2栈与递归96

4.2.1递归的实现96

4.2.2避免递归98

4.3典型应用99

4.3.1逆序输出99

4.3.2递归嵌套100

4.3.3延迟缓冲103

4.3.4逆波兰表达式107

4.4试探回溯法110

4.4.1试探与回溯110

4.4.2八皇后111

4.4.3迷宫寻径113

4.5队列116

4.5.1概述116

4.5.2 ADT接口116

4.5.3操作实例117

4.5.4 Queue模板类117

4.6队列应用117

4.6.1循环分配器117

4.6.2银行服务模拟118

习题119

第5章 二叉树123

5.1二叉树及其表示124

5.1.1树124

5.1.2二叉树125

5.1.3多叉树126

5.2编码树128

5.2.1二进制编码128

5.2.2二叉编码树130

5.3二叉树的实现131

5.3.1二叉树节点131

5.3.2二叉树节点操作接口133

5.3.3二叉树134

5.4Huffman编码138

5.4.1 PFC编码及解码138

5.4.2最优编码树141

5.4.3 Huff man编码树143

5.4.4 Huffman编码算法145

5.5遍历151

5.5.1递归式遍历151

5.5.2迭代版先序遍历153

5.5.3迭代版中序遍历155

5.5.4迭代版后序遍历159

5.5.5层次遍历161

习题162

第6章 图165

6.1概述166

6.2抽象数据类型169

6.2.1操作接口169

6.2.2 Graph模板类169

6.3邻接矩阵171

6.3.1原理171

6.3.2实现171

6.3.3时间性能173

6.3.4空间性能173

6.4邻接表174

6.4.1原理174

6.4.2复杂度174

6.5图遍历算法概述175

6.6广度优先搜索175

6.6.1策略175

6.6.2实现176

6.6.3实例177

6.6.4复杂度177

6.6.5应用177

6.7深度优先搜索178

6.7.1策略178

6.7.2实现178

6.7.3实例179

6.7.4复杂度181

6.7.5应用181

6.8拓扑排序181

6.8.1应用181

6.8.2有向无环图182

6.8.3算法182

6.8.4实现183

6.8.5实例184

6.8.6复杂度184

6.9双连通域分解184

6.9.1关节点与双连通域184

6.9.2蛮力算法185

6.9.3算法185

6.9.4实现186

6.9.5实例187

6.9.6复杂度188

6.10优先级搜索188

6.10.1优先级与优先级数188

6.10.2基本框架189

6.10.3复杂度189

6.11最小支撑树190

6.11.1支撑树190

6.11.2最小支撑树190

6.11.3歧义性190

6.11.4蛮力算法191

6.11.5 Prim算法191

6.12最短路径193

6.12.1最短路径树193

6.12.2歧义性194

6.12.3 Dijkstra算法194

习题196

第7章 搜索树199

7.1查找201

7.1.1循关键码访问201

7.1.2词条201

7.1.3序与比较器201

7.2二叉搜索树202

7.2.1顺序性202

7.2.2中序遍历序列202

7.2.3 BST模板类203

7.2.4查找算法及其实现203

7.2.5插入算法及其实现205

7.2.6删除算法及其实现206

7.3平衡二叉搜索树208

7.3.1树高与性能208

7.3.2理想平衡与适度平衡209

7.3.3等价二叉搜索树210

7.3.4等价变换与局部调整210

7.4 AVL树211

7.4.1定义及性质211

7.4.2节点插入213

7.4.3节点删除215

7.4.4统一重平衡算法217

习题219

第8章 高级搜索树221

8.1伸展树222

8.1.1局部性222

8.1.2逐层伸展223

8.1.3双层伸展224

8.1.4分摊分析226

8.1.5伸展树的实现228

8.2 B-树232

8.2.1多路平衡查找232

8.2.2 ADT接口及其实现235

8.2.3关键码查找236

8.2.4性能分析238

8.2.5关键码插入239

8.2.6上溢与分裂239

8.2.7关键码删除242

8.2.8下溢与合并243

8.3红黑树247

8.3.1概述248

8.3.2红黑树接口定义250

8.3.3节点插入算法251

8.3.4节点删除算法254

8.4 kd-树259

8.4.1范围查询259

8.4.2 kd-树262

8.4.3基于2d-树的范围查询263

习题265

第9章 词典269

9.1词典ADT271

9.1.1操作接口271

9.1.2操作实例271

9.1.3接口定义272

9.1.4实现方法272

9.2跳转表273

9.2.1 Skiplist模板类273

9.2.2总体逻辑结构274

9.2.3四联表274

9.2.4查找276

9.2.5空间复杂度277

9.2.6时间复杂度278

9.2.7插入279

9.2.8删除282

9.3散列表283

9.3.1完美散列283

9.3.2装填因子与空间利用率284

9.3.3散列函数285

9.3.4散列表289

9.3.5冲突及其排解290

9.3.6闭散列策略292

9.3.7查找与删除295

9.3.8插入296

9.3.9更多闭散列策略297

9.3.10散列码转换299

9.4散列应用301

9.4.1桶排序301

9.4.2最大间隙302

9.4.3基数排序303

习题304

第10章 优先级队列309

10.1优先级队列ADT310

10.1.1优先级与优先级队列310

10.1.2关键码、比较器与偏序关系311

10.1.3操作接口311

10.1.4操作实例：选择排序311

10.1.5接口定义312

10.1.6应用实例：Huffman编码树312

10.2堆314

10.2.1完全二叉堆314

10.2.2元素插入317

10.2.3元素删除319

10.2.4建堆321

10.2.5就地堆排序323

10.3左式堆325

10.3.1堆合并325

10.3.2单侧倾斜326

10.3.3 PQ_LeftHeap模板类326

10.3.4空节点路径长度327

10.3.5左倾性与左式堆327

10.3.6右侧链328

10.3.7合并算法328

10.3.8实例328

10.3.9合并操作merge（）的实现329

10.3.10复杂度330

10.3.11基于合并的插入和删除330

习题331

第11章 串335

11.1串及串匹配336

11.1.1串336

11.1.2串匹配337

11.1.3测评标准与策略338

11.2蛮力算法339

11.2.1算法描述339

11.2.2算法实现339

11.2.3时间复杂度340

11.3 KMP算法341

11.3.1构思341

11.3.2 next表342

11.3.3 KMP算法342

11.3.4 next［0］=-1343

11.3.5 next［j+1］343

11.3.6构造next表344

11.3.7性能分析344

11.3.8继续改进345

11.4 BM算法347

11.4.1思路与框架347

11.4.2坏字符策略348

11.4.3好后缀策略351

11.4.4 GS［］表构造算法353

11.4.5算法纵览356

11.5 Karp-Rabin算法357

11.5.1构思357

11.5.2算法与实现357

习题361

第12章 排序363

12.1快速排序364

12.1.1分治策略364

12.1.2轴点364

12.1.3快速排序算法365

12.1.4快速划分算法365

12.1.5复杂度368

12.1.6应对退化369

12.2选取与中位数371

12.2.1概述371

12.2.2主流数372

12.2.3归并向量的中位数373

12.2.4基于优先级队列的选取376

12.2.5基于快速划分的选取377

12.2.6 k-选取算法378

12.3希尔排序380

12.3.1递减增量策略380

12.3.2增量序列382

习题385

附录387

参考文献388

插图索引391

表格索引398

算法索引399

代码索引400

关键词索引406