C算法（第一卷 基础、数据结构、排序和搜索）

第一部分　基础知识

第1章 导论 2

1.1 算法 2

1.2 问题示例：连通性（connectivity） 4

练习 7

1.3 并集—查找算法 7

练习 17

1.4 展望 18

练习 19

1.5 小结 19

第2章 算法分析原理 22

2.1 实现与试验分析 22

练习 25

2.2 算法分析 25

练习 27

2.3 函数增长 27

练习 32

2.4 O记号 32

练习 35

2.5 基本递推式 36

练习 38

2.6 算法分析示例 39

练习 43

2.7 保证、预测与限制 44

练习 46

第一部分参考文献 47

第二部分　数据结构

第3章 基本数据结构 49

3.1 基石 50

练习 57

3.2 数组 57

练习 63

3.3 链表 64

练习 69

3.4 基本表处理 70

练习 77

3.5 表的内存分配 77

练习 80

3.6 串 80

练习 84

3.7 复合数据结构 84

练习 92

第4章 抽象数据类型 93

4.1 抽象对象与对象集合 95

练习 97

4.2 下推栈ADT 97

练习 99

4.3 栈ADT客户程序示例 99

练习 104

4.4 栈ADT实现 105

练习 108

4.5 创建新ADT 109

练习 111

4.6 FIFO队列及广义队列 111

练习 117

4.7 重复项和索引项 118

练习 121

4.8 一级ADT 122

练习 130

4.9 ADT应用示例 131

练习 134

4.10 展望 135

第5章 递归和树 136

5.1 递归算法 136

练习 141

5.2 分治 142

练习 155

5.3 动态规划 156

练习 160

5.4 树 163

练习 168

5.5 二叉树的数学性质 169

练习 171

5.6 树遍历 172

练习 175

5.7 递归二叉树算法 177

练习 181

5.8 图遍历 182

练习 187

5.9 展望 188

第二部分参考文献 189

第三部分　排序

第6章 基本排序方法 191

6.1 游戏规则 192

练习 195

6.2 选择排序 196

练习 197

6.3 插入排序 198

练习 199

6.4 冒泡排序 200

练习 201

6.5 基本排序的性能特征 201

练习 206

6.6 希尔排序 206

练习 212

6.7 其他数据类型的排序 214

练习 217

6.8 索引与指针排序 218

练习 223

6.9 链表的排序 223

练习 225

6.10 键索引计数 226

练习 228

第7章 快速排序 229

7.1 基本算法 229

练习 233

7.2 快速排序的性能特征 233

练习 236

7.3 栈大小 236

练习 239

7.4 小子文件 239

练习 240

7.5 三元素中值法划分 242

练习 245

7.6 重复键 245

练习 246

7.7 串和向量 248

练习 249

7.8 选择 249

练习 251

第8章 归并和归并排序 253

8.1 二路归并 254

练习 255

8.2 抽象就位归并 255

练习 256

8.3 自顶向下归并 257

练习 259

8.4 基本算法的改进 259

练习 261

8.5 自底向上归并排序 261

练习 265

8.6 归并排序的性能特征 265

练习 266

8.7 归并排序的链式实现 267

练习 269

8.8 回顾递归 270

练习 271

第9章 优先队列与堆排序 272

练习 274

9.1 基本实现方法 274

练习 276

9.2 堆数据结构 277

练习 278

9.3 堆的算法 278

练习 284

9.4 堆排序 285

练习 291

9.5 优先队列ADT 292

练习 295

9.6 索引项的优先队列 295

练习 298

9.7 二项式队列 298

练习 306

第10章 基数排序 307

10.1 位（bit）、字节（byte）和字（word） 308

练习 310

10.2 二分快速排序 310

练习 314

10.3 MSD基数排序 315

练习 321

10.4 三路基数快速排序 321

练习 325

10.5 LSD基数排序 325

练习 329

10.6 基数排序的性能特征 329

练习 332

10.7 亚线性时间排序 332

练习 335

第11章 特殊目的排序方法 336

11.1 巴切奇偶归并排序 337

练习 341

11.2 排序网络 341

练习 347

11.3 外部排序 349

练习 353

11.4 排序归并的实现 353

练习 358

11.5 并行排序归并 359

练习 361

第三部分参考文献 362

第四部分　搜索

第12章 符号表和二叉搜索树 365

12.1 符号表抽象数据类型 366

练习 369

12.2 键索引搜索 370

练习 372

12.3 顺序搜索 372

练习 376

12.4 二分搜索 377

练习 381

12.5 二叉搜索树（BST） 381

练习 387

12.6 BST的性能特征 388

练习 390

12.7 符号表的索引实现 392

练习 394

12.8 在BST根部的插入 395

练习 399

12.9 其他ADT函数的BST实现 400

练习 406

第13章 平衡树 408

练习 410

13.1 随机BST 410

练习 415

13.2 分裂BST 416

练习 422

13.3 自顶向下2-3-4树 422

练习 427

13.4 红-黑树 427

练习 434

13.5 跳表 436

练习 443

13.6 性能特征 443

练习 445

第14章 哈希方法 446

14.1 哈希函数 446

练习 453

14.2 分离链 454

练习 457

14.3 线性探测法 458

练习 461

14.4 双哈希法 462

练习 466

14.5 动态哈希表 467

练习 469

14.6 展望 470

练习 473

第15章 基数搜索 474

15.1 位搜索树 474

练习 478

15.2 Trie 479

练习 485

15.3 Patricia Tries 486

练习 492

15.4 多路trie和TST 493

练习 504

15.5 文本串索引算法 506

练习 508

第16章 外部搜索 510

16.1 游戏规则 511

16.2 索引顺序访问 512

练习 515

16.3 B树 515

练习 524

16.4 可扩展哈希法 525

练习 533

16.5 展望 534

练习 534

第四部分参考文献 536