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

第一部分预备知识1

第1章数据结构和算法1

1.1数据结构的原则1

1.1.1学习数据结构的必要性1

1.1.2代价与效益2

1.1.3本书的目的3

1.2抽象数据类型和数据结构3

1.3问题、算法和程序5

1.4算法的效率7

1.5深入学习导读7

1.6习题8

第2章数学预备知识11

2.1集合11

2.2常用数学术语12

2.3对数13

2.4递归14

2.5级数求和与递归16

2.6数学证明方法18

2.6.1反证法18

2.6.2数学归纳法18

2.7评估21

2.8深入学习导读22

2.9习题22

第3章算法分析25

3.1概述25

3.2最佳、最差和平均情况27

3.3换一台更快的计算机，还是换一种更快的算法？29

3.4渐近分析31

3.4.1上限31

3.4.2下限32

3.4.3？表示法33

3.4.4简化法则34

3.5程序运行时间的计算34

3.6问题的分析38

3.7多参数问题38

3.8空间代价39

3.9实际操作中的一些因素41

3.10深入学习导读43

3.11习题43

3.12项目设计45

第二部分基本数据结构47

第4章线性表、栈和队列47

4.1线性表47

4.1.1顺序表的表示法49

4.1.2链表52

4.1.3线性表实现方法的比较60

4.1.4元素的表示61

4.1.5双链表62

4.1.6循环链表65

4.2栈66

4.2.1顺序栈66

4.2.2链式栈67

4.2.3顺序栈与链式栈的比较68

4.2.4递归的实现69

4.3队列69

4.3.1顺序队列70

4.3.2链式队列73

4.2.3顺序队列与链式队列的比较74

4.4习题74

4.5项目设计76

第5章二叉树77

5.1定义及主要特性77

5.1.1满二叉树定理79

5.1.2二叉树结点的抽象数据类型80

5.2周游二叉树81

5.3二叉树的实现81

5.3.1使用指针实现二叉树81

5.3.2空间开销85

5.3.3使用数组实现完全二叉树86

5.4Huffman编码树87

5.4.1建立Huffman编码树88

5.4.2Huffman编码及其用法92

5.5二叉检索树94

5.6堆与优先队列100

5.7深入学习导读106

5.8习题106

5.9项目设计108

第6章树110

6.1树的定义与术语110

6.1.1树结点的抽象数据类型110

6.1.2树的周游110

6.2父指针表示法112

6.3树的实现117

6.3.1子结点表表示法117

6.3.2左子结点／右兄弟结点表示法118

6.3.3动态结点表示法118

6.3.4动态“左子结点／右兄弟结点”表示法120

6.4K叉树120

6.5树的顺序表示法121

6.6深入学习导读123

6.7习题123

6.8项目设计125

第7章图126

7.1术语和表示法126

7.2图的实现129

7.3图的周游133

7.3.1深度优先搜索134

7.3.2广度优先搜索135

7.3.3拓扑排序136

7.4最短路径问题139

7.4.1单源最短路径139

7.4.2每对顶点间的最短路径142

7.5最小支撑树144

7.5.1Prim算法144

7.5.2Kruskal 算法147

7.6深入学习导读149

7.7习题149

7.8项目设计150

第三部分排序和检索151

第8章内排序151

8.1排序的术语及记号151

8.2三种代价为？（n2）的排序算法152

8.2.1插入排序152

8.2.2起泡排序154

8.2.3选择排序155

8.2.4交换排序算法的时间代价156

8.3Shell排序157

8.4快速排序158

8.5归并排序164

8.6堆排序166

8.7分配排序和基数排序167

8.8对各种排序算法的实验比较173

8.9排序算法的下限174

8.10深入学习导读177

8.11习题177

8.12项目设计180

第9章文件管理和外排序181

9.1主存储器和辅助存储器181

9.2磁盘和磁带183

9.2.1磁盘访问开销186

9.2.2磁带188

9.3缓冲区和缓冲池188

9.4程序员的文件视图190

9.5外排序191

9.6外排序的简单方法193

9.7置换选择排序195

9.8多路归并198

9.9深入学习导读200

9.10习题200

9.11项目设计202

第10章检索204

10.1检索已排序的数组205

10.2自组织线性表205

10.3集合的检索209

10.4散列方法209

10.4.1散列函数210

10.4.2开散列方法212

10.4.3闭散列方法214

10.5深入学习导读222

10.6习题222

10.7项目设计224

第11章索引技术225

11.1线性索引226

11.2ISAM229

11.3树形索引230

11.4 2-3树231

11.5B树237

11.5.1B＋树238

11.5.2B树分析244

11.6深入学习导读244

11.7习题244

11.8项目设计246

第四部分应用与高级技术247

第12章线性表和数组的深入研究247

12.1跳跃表247

12.2广义表251

12.3矩阵的表示方法253

12.4存储管理256

12.4.1动态存储分配257

12.4.2失败策略和无用单元收集263

12.5深入学习导读266

12.6习题267

12.7项目设计268

第13章高级树结构269

13.1Trie结构269

13.2伸展树272

13.3空间数据结构275

13.3.1k-d树277

13.3.2PR四分树280

13.3.3其他空间数据结构282

13.4深入学习导读283

13.5习题284

13.6项目设计284

第14章算法分析技术286

14.1求和技术286

14.2递归关系288

14.2.1估计上下限288

14.2.2扩展递归289

14.2.3分治法递归290

14.2.4快速排序平均情况分析291

14.3缓冲分析292

14.4深入学习导读294

14.5习题294

14.6项目设计296

第15章计算的限制298

15.1概述298

15.2归约298

15.3难解问题301

15.3.1NP完全性302

15.3.2绕过NP完全性问题304

15.4不可解问题305

15.4.1不可数性306

15.4.2停机问题的不可解性308

15.4.3确定程序行为是不可解的310

15.5深入学习导读310

15.6习题311

15.7项目设计312

附录AC和Pascal程序员的C＋＋导引313

A.1例1：线性表的ADT314

A.2例2：顺序表的实现317

A.3例3：链表的实现320

A.4例4：可利用空间表323

A.5例5：转化为模板325

A.6例6：虚函数328

附录B参考书目331