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

数据结构 C++语言版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常数0（1）12

1.3.2对数0（logn）12

1.3.3线性0（n）13

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

1.3.5指数0（2n）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递归消除21

1.4.5二分递归22

1.5抽象数据类型26

第2章 向量27

2.1从数组到向量28

2.1.1数组28

2.1.2向量29

2.2接口29

2.2.1 ADT接口29

2.2.2操作实例30

2.2.3 Vector模板类30

2.3构造与析构32

2.3.1默认构造方法32

2.3.2基于复制的构造方法32

2.3.3析构方法33

2.4动态空间管理33

2.4.1静态空间管理33

2.4.2可扩充向量34

2.4.3扩容34

2.4.4分摊分析35

2.4.5缩容36

2.5常规向量37

2.5.1直接引用元素37

2.5.2置乱器37

2.5.3判等器与比较器38

2.5.4无序查找39

2.5.5插入40

2.5.6删除40

2.5.7唯一化42

2.5.8遍历43

2.6有序向量44

2.6.1比较器44

2.6.2有序性甄别44

2.6.3唯一化45

2.6.4查找47

2.6.5二分查找（版本A）48

2.6.6 Fibonacci查找52

2.6.7二分查找（版本B）54

2.6.8二分查找（版本C）56

2.7排序与下界57

2.7.1有序性57

2.7.2排序及其分类57

2.7.3下界57

2.7.4比较树58

2.7.5估计下界59

2.8排序器59

2.8.1统一入口59

2.8.2起泡排序60

2.8.3归并排序61

第3章 列表65

3.1从向量到列表66

3.1.1从静态到动态66

3.1.2由秩到位置67

3.1.3列表67

3.2接口67

3.2.1列表节点67

3.2.2列表68

3.3列表71

3.3.1头、尾节点71

3.3.2默认构造方法71

3.3.3由秩到位置的转换72

3.3.4查找72

3.3.5插入72

3.3.6基于复制的构造74

3.3.7删除75

3.3.8析构76

3.3.9唯一化76

3.3.10遍历77

3.4有序列表77

3.4.1唯一化77

3.4.2查找78

3.5排序器78

3.5.1统一入口78

3.5.2插入排序79

3.5.3选择排序80

3.5.4归并排序82

第4章 栈与队列85

4.1栈86

4.1.1 ADT接口86

4.1.2操作实例87

4.1.3 Stack模板类88

4.2栈与递归88

4.2.1函数调用栈88

4.2.2避免递归89

4.3栈的典型应用90

4.3.1逆序输出90

4.3.2递归嵌套91

4.3.3延迟缓冲94

4.3.4逆波兰表达式96

4.4试探回溯法99

4.4.1试探与回溯99

4.4.2八皇后100

4.4.3迷宫寻径102

4.5队列105

4.5.1概述105

4.5.2 ADT接口105

4.5.3操作实例106

4.5.4 Queue模板类106

4.6队列应用107

4.6.1循环分配器107

4.6.2银行服务模拟107

第5章 二叉树109

5.1二叉树及其表示110

5.1.1树110

5.1.2二叉树111

5.1.3多叉树112

5.2编码树114

5.2.1二进制编码114

5.2.2二叉编码树116

5.3二叉树的实现117

5.3.1二叉树节点117

5.3.2二叉树节点操作接口119

5.3.3二叉树120

5.4遍历124

5.4.1递归式遍历124

5.4.2迭代版先序遍历126

5.4.3迭代版中序遍历128

5.4.4迭代版后序遍历132

5.4.5层次遍历133

5.5 Huffman编码136

5.5.1 PFC编码及解码136

5.5.2最优编码树139

5.5.3 Huffman编码树141

5.5.4 Huffman编码算法143

第6章 图149

6.1概述150

6.2抽象数据类型153

6.2.1操作接口153

6.2.2 Graph模板类153

6.3邻接矩阵155

6.3.1原理155

6.3.2实现155

6.3.3时间性能157

6.3.4空间性能157

6.4邻接表158

6.4.1原理158

6.4.2复杂度158

6.5图遍历算法概述159

6.6广度优先搜索159

6.6.1策略159

6.6.2实现160

6.6.3实例161

6.6.4复杂度161

6.6.5应用161

6.7深度优先搜索162

6.7.1策略162

6.7.2实现162

6.7.3实例163

6.7.4复杂度165

6.7.5应用165

6.8拓扑排序165

6.8.1应用165

6.8.2有向无环图166

6.8.3算法166

6.8.4实现167

6.8.5实例168

6.8.6复杂度168

6.9双连通域分解168

6.9.1关节点与双连通域168

6.9.2蛮力算法169

6.9.3可行算法169

6.9.4实现170

6.9.5实例171

6.9.6复杂度172

6.10优先级搜索172

6.10.1优先级与优先级数172

6.10.2基本框架173

6.10.3复杂度174

6.11最小支撑树174

6.11.1支撑树174

6.11.2最小支撑树174

6.11.3歧义性175

6.11.4蛮力算法175

6.11.5 Prim算法175

6.12最短路径178

6.12.1最短路径树178

6.12.2 Dijkstra算法178

第7章 搜索树181

7.1查找183

7.1.1循关键码访问183

7.1.2词条183

7.1.3序与比较器183

7.2二叉搜索树184

7.2.1顺序性184

7.2.2中序遍历序列184

7.2.3 BST模板类185

7.2.4查找算法及其实现185

7.2.5插入算法及其实现188

7.2.6删除算法及其实现189

7.3平衡二叉搜索树191

7.3.1树高与性能191

7.3.2理想平衡与适度平衡192

7.3.3等价变换192

7.3.4旋转调整193

7.4 AVL树194

7.4.1定义及性质194

7.4.2节点插入196

7.4.3节点删除198

7.4.4统一重平衡算法200

第8章 高级搜索树203

8.1伸展树204

8.1.1局部性204

8.1.2逐层伸展205

8.1.3双层伸展206

8.1.4伸展树的实现208

8.2 B-树212

8.2.1多路平衡查找212

8.2.2 ADT接口及其实现215

8.2.3关键码查找216

8.2.4性能分析218

8.2.5关键码插入219

8.2.6上溢与分裂219

8.2.7关键码删除222

8.2.8下溢与合并223

8.3红黑树227

8.3.1概述228

8.3.2红黑树接口定义230

8.3.3节点插入算法231

8.3.4节点删除算法234

8.4 kd-树239

8.4.1范围查询239

8.4.2 kd-树242

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

第9章 词典245

9.1词典ADT247

9.1.1操作接口247

9.1.2操作实例247

9.1.3接口定义248

9.1.4实现方法248

9.2跳转表249

9.2.1 Skiplist模板类249

9.2.2总体逻辑结构250

9.2.3四联表250

9.2.4查找252

9.2.5空间复杂度253

9.2.6时间复杂度254

9.2.7插入255

9.2.8删除258

9.3散列表259

9.3.1完美散列259

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

9.3.3散列函数261

9.3.4散列表264

9.3.5冲突及其排解266

9.3.6闭散列策略268

9.3.7查找与删除271

9.3.8插入272

9.3.9更多闭散列策略273

9.3.10散列码转换275

9.4散列应用277

9.4.1桶排序277

9.4.2最大间隙278

9.4.3基数排序279

第10章 优先级队列281

10.1优先级队列ADT282

10.1.1优先级与优先级队列282

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

10.1.3操作接口283

10.1.4操作实例：选择排序283

10.1.5接口定义284

10.1.6应用实例：Huffman编码树284

10.2堆286

10.2.1完全二叉堆286

10.2.2元素插入289

10.2.3元素删除291

10.2.4建堆292

10.2.5就地堆排序295

10.3左式堆297

10.3.1堆合并297

10.3.2单侧倾斜298

10.3.3 PQ_LeftHeap模板类298

10.3.4空节点路径长度299

10.3.5左倾性与左式堆299

10.3.6最右侧通路300

10.3.7合并算法300

10.3.8实例301

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

10.3.10复杂度303

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

第11章 串305

11.1串及串匹配306

11.1.1串306

11.1.2串匹配307

11.1.3测评标准与策略308

11.2蛮力算法309

11.2.1算法描述309

11.2.2算法实现309

11.2.3时间复杂度310

11.3 KMP算法311

11.3.1构思311

11.3.2 next表312

11.3.3 KMP算法312

11.3.4 next[0]=-1313

11.3.5 next[j+1]313

11.3.6构造next表314

11.3.7性能分析314

11.3.8继续改进315

11.4 BM算法317

11.4.1思路与框架317

11.4.2坏字符策略318

11.4.3好后缀策略321

11.4.4 GS[]表构造算法323

11.4.5算法纵览326

11.5 Karp-Rabin算法327

11.5.1构思327

11.5.2算法与实现328

第12章 排序333

12.1快速排序334

12.1.1分治策略334

12.1.2轴点334

12.1.3快速排序算法335

12.1.4快速划分算法335

12.1.5复杂度338

12.1.6应对退化339

12.2选取与中位数341

12.2.1概述341

12.2.2众数342

12.2.3归并向量的中位数343

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

12.2.5基于快速划分的选取347

12.2.6 k-选取算法348

12.3希尔排序350

12.3.1递减增量策略350

12.3.2增量序列353

附录357

参考文献358

插图索引362

表格索引369

算法索引370

代码索引371

关键词索引377