《算法与数据结构》求取 ⇩

第一章 绪论1

第一节 算法的复杂性1

一、比较两对算法的效率1

二、复杂性的计量4

三、复杂性的渐近性态及其阶7

四、复杂性渐近阶的重要性10

五、算法复杂性渐近阶的分析12

六、递归方程解的渐近阶的求法16

第二节 算法表达中的抽象机制26

一、从机器语言到高级语言的抽象26

二、抽象数据类型30

三、使用抽象数据类型带来的好处34

四、数据结构、数据类型和抽象数据类型35

习题36

第二章 表40

第一节 ADT表40

第二节 表的实现42

一、表的数组实现42

二、表的指针实现45

三、表的游标实现48

四、循环链表51

五、双链表52

第三节 栈54

一、ADT栈54

二、栈的数组实现55

三、栈的指针实现57

第四节 队列58

一、ADT队列58

二、用指针实现队列59

三、用循环数组实现队列60

第五节 映射64

一、ADT映射64

二、用数组实现映射64

三、用表实现映射65

习题67

第三章 串71

第一节 ADT串71

第二节 串的实现72

一、串的数组实现72

二、串的指针实现73

三、串的块链表示法73

四、串的堆结构74

第三节 模式匹配75

一、朴素的模式匹配算法75

二、模式匹配的KMP算法76

习题82

第四章 树84

第一节 树的定义84

第二节 二叉对86

第三节 树的遍历88

第四节 ADT树90

第五节 树的实现方法92

一、父亲数组表示法92

二、儿子链表表示法93

三、左儿子右兄弟表示法95

第六节 二叉树的实现及其应用96

一、二叉树的顺序存储结构96

二、二叉树的结点度表示法98

三、二叉树的链式存储结构98

四、果园或森林的二叉树表示99

五、线索二叉树100

六、二叉树的应用102

习题104

第五章 集合108

第一节 以集合为基础的抽象数据类型108

一、集合的定义和记号108

二、定义在集合上的基本运算109

三、集合的简单表示法109

第二节 字典113

一、实现字典的简单方法113

二、用散列表实现字典114

三、用散列表实现映射123

第三节 有序字典124

一、有序字典的定义125

二、用数组实现有序字典125

三、有二叉搜索实现有序字典127

第四节 平衡树134

一、红黑树134

二、2—3树147

第五节 优先队列156

一、优先队列的定义156

二、优先队列的字典式实现157

三、优先级树和堆160

四、用数组实现堆161

第六节 并查集163

一、并查集的定义及其简单实现163

二、并查集的快速实现165

三、并查集的树实现167

第七节 检索树169

一、检索树与检索树结点169

二、用数组表示检索树结点170

三、用链接表表示检索树结点171

四、检索树的效率172

习题173

第六章 算法设计策略与技巧177

第一节 递归技术与分治法177

一、递归技术177

二、分治法的基本思想181

三、大整数的乘法182

四、Strassen矩阵乘法184

五、最接近点对问题186

六、循环赛日程表190

第二节 动态规划191

一、计算矩阵连乘积191

二、动态规划算法的基本要素196

三、最长公共子序列199

四、凸多边形的最优三角剖分203

第三节 贪心算法206

一、活动安排问题206

二、贪心算法的基本要素209

三、哈夫曼编码211

四、贪心算法的理论基础215

第四节 回溯法220

一、回溯法的一般描述220

二、n后问题225

三、子集和问题227

四、图的m-着色问题230

五、回溯法的效率分析233

第五节 限界剪枝法236

一、最小耗费搜索法236

二、限界与剪枝241

三、旅行售贷员问题245

习题248

第七章 排序与选择253

第一节 简单排序算法253

一、冒泡排序253

二、插入排序254

三、选择排序254

四、简单排序算法的计算复杂性255

第二节 快速排序256

一、算法的基本思想及其实现256

二、快速排序的性能258

三、随机快速排序算法258

第三节 堆排序259

一、堆排序算法的基本思想及其实现259

二、堆排序算法的计算复杂性261

第四节 线性时间排序261

一、计数排序262

二、桶排序263

三、基数排序264

第五节 中位数与第k小元素267

一、平均情况下的线性时间选择算法267

二、最坏情况下的线性时间选择算法269

习题271

第八章 图275

第一节 图的基本概念275

一、图及其相关术语275

二、抽象数据类型ADT图277

第二节 图的表示法278

一、邻接矩阵表示法278

二、邻接表表示法279

第三节 图的遍历281

一、深度优先搜索281

二、广度优先搜索283

第四节 图的连通性284

一、深度优先生成森林284

二、无圈有向图285

三、有向图的强连通分支286

四、无向图的割点和双连通分支287

第五节 最小生成树288

一、最小生成树性质289

二、Prim算法289

三、Kruskal算法291

第六节 最短路径293

一、单源最短路径293

二、所有顶点对之间的最短路径295

第七节 图匹配298

习题299

第九章 问题的计算复杂性304

第一节 计算模型304

一、随机存取机RAM305

二、随机存取存储程序机RASP310

三、RAM模型的变形与简化314

四、图灵机317

五、图灵机模型与RAM模型的关系320

第二节 问题的计算时间下界323

一、问题的输入、输出及平凡下界323

二、信息论下界323

三、对手论证方法324

四、Ben_ Or下界定理330

五、问题变换与计算复杂性归约334

第三节 P类与NP类337

一、非确定性图灵机338

二、P类与NP类语言339

三、“证书”与VP类语言341

四、问题和语言342

第四节 NP——完全性343

一、多项式时间变换与NP——完全问题343

二、Cook定理344

三、几个典型的NP——完全问题347

第五节 NP——完全问题的近似解法357

一、近似算法的性能358

二、顶点覆盖问题的近似算法358

三、旅行售货员问题的近似算法360

四、集合覆盖问题的近似算法362

五、子集和问题的近似算法365

习题369

第十章 并行算法372

第一节 并行计算模型372

一、PRAM模型372

二、同步与控制374

三、并行算法的表达374

四、并行算法的性能指标375

五、运行时间和工作量有效性375

第二节 并行算法的基本设计技术376

一、平衡树方法376

二、指针跳越技术377

三、欧拉回路技术380

四、并行分治法382

五、划分原理385

六、流水线技术386

七、接力技术388

八、递归的并行随机消元法390

九、确定性破对称技术393

第三节 EREW算法与CRCW算法的速度比较398

一、并发读对提高速度的作用398

二、并发写对提高速度的作用400

三、CRCW算法速度的上界401

习题403

第十一章 高级专题406

第一节 算法的分摊时间分析406

一、累计方法407

二、记帐方法409

三、势能方法410

四、自适应二叉搜索树412

第二节 可并优先队列418

一、可并优先队列的定义418

二、用二项堆实现可并优先队列419

三、用Fibonacci堆实现可并优先队列430

第三节 数据结构的扩充与联合442

一、动态选择树——红黑树的扩充442

二、数据结构扩充的方法446

三、区间树447

四、数据结构的联合451

第四节 静态数据结构的动态化方法452

一、可分解搜索问题453

二、静态数据结构的半动态化454

三、静态数据结构的另一种半动态化方法458

四、静态数据结构的全动态变换460

五、其他动态化方法461

习题462

参考文献465