“数据结构”是计算机专业的核心课程，是从事计算机软体开发和套用人员必备的专业基础。随着计算机的日益普及，“数据结构”课程也在不断地发展。

本书按照清华大学计算机系本科“数据结构”大纲的要求，从面向对象的概念、对象类设计的风格和数据结构的层次开始,从线性结构到非线性结构，从简单到复，深入地讨论了各种数据结构内在的逻辑关係及其在计算机中的实现方式和使用。此外，对常用的叠代、递归、回溯等算法设计技巧，搜寻和排序算法等都做了详尽的描述，并引入了简单的算法分析。

第1章数据结构概论1

1.1数据结构的概念1

1.1.1数据结构举例1

1.1.2数据与数据结构2

1.1.3数据结构的分类3

1.1.4数据结构课程的内容4

1.2数据结构的抽象形式6

1.2.1数据类型6

1.2.2数据抽象与抽象数据类型7

1.3作为ADT的C++类9

1.3.1面向对象的概念9

1.3.2C++中的类10

1.3.3C++中的对象12

1.3.4C++的输入输出13

1.3.5C++中的函式14

1.3.6动态存储分配17

1.3.7C++中的继承18

1.3.8多态性19

1.3.9C++的模板23

1.4算法定义24

1.5算法性能分析与度量26

1.5.1算法的性能标準26

1.5.2算法的后期测试26

1.5.3算法的事前估计27

1.5.4算法的渐进分析32

1.5.5最坏、最好和平均情况36

习题37

第2章线性表43

2.1线性表43

2.1.1线性表的概念43

2.1.2线性表的类定义44

2.2顺序表45

2.2.1顺序表的定义和特点45

2.2.2顺序表的类定义及其操作45

2.2.3顺序表的性能分析50

2.2.4顺序表的套用52

2.3单鍊表52

2.3.1单鍊表的概念53

2.3.2单鍊表的类定义54

2.3.3单鍊表中的插入与删除56

2.3.4带附加头结点的单鍊表59

2.3.5单鍊表的模板类60

2.4线性鍊表的其他变形66

2.4.1循环鍊表66

2.4.2双向鍊表69

2.5单鍊表的套用：多项式及其运算73

2.5.1多项式的表示74

2.5.2多项式的类定义75

2.5.3多项式的加法77

2.5.4多项式的乘法79

2.6静态鍊表80

习题83

第3章栈和伫列88

3.1栈88

3.1.1栈的定义88

3.1.2顺序栈89

3.1.3链式栈92

3.1.4栈的套用之一——括弧匹配94

3.1.5栈的套用之二——表达式的计算95

3.2栈与递归101

3.2.1递归的概念101

3.2.2递归过程与递归工作栈105

3.2.3用回溯法求解迷宫问题109

3.3伫列114

3.3.1伫列的概念114

3.3.2循环伫列114

3.3.3链式伫列118

3.3.4伫列套用举例：列印二项展开式(a+b)i的係数120

3.3.5伫列套用举例：电路布线121

3.4优先权伫列124

3.4.1优先权伫列的概念124

3.4.2优先权伫列的存储表示和实现125

3.5双端伫列126

3.5.1双端伫列的概念126

3.5.2双端伫列的数组表示128

3.5.3双端伫列的鍊表表示129

习题131

第4章数组、串与广义表135

4.1多维数组的概念与存储135

4.1.1多维数组的概念135

4.1.2多维数组的存储表示136

4.2特殊矩阵138

4.2.1对称矩阵的压缩存储138

4.2.2三对角线/多对角线矩阵的压缩存储140

4.3稀疏矩阵141

4.3.1稀疏矩阵及其三元组数组表示141

4.3.2稀疏矩阵的转置145

4.3.3稀疏矩阵的相加和相乘147

4.3.4矩阵的正交鍊表表示152

4.4字元串153

4.4.1字元串的概念153

4.4.2C++有关字元串的库函式154

4.4.3字元串的实现156

4.4.4字元串的自定义类158

4.4.5字元串操作的实现159

4.4.6字元串的模式匹配161

4.4.7字元串的存储方法167

4.5广义表169

4.5.1广义表的定义与性质169

4.5.2广义表的表示170

4.5.3广义表存储结构的实现170

4.5.4广义表的递归算法174

4.5.5三元多项式的表示181

习题183

第5章树186

5.1树的基本概念186

5.1.1树的定义和术语186

5.1.2树的抽象数据类型188

5.2二叉树189

5.2.1二叉树的定义189

5.2.2二叉树的性质190

5.2.3二叉树的抽象数据类型191

5.3二叉树的存储表示192

5.3.1二叉树的数组存储表示192

5.3.2二叉树的鍊表存储表示193

5.4二叉树遍历及其套用198

5.4.1二叉树遍历的递归算法198

5.4.2二叉树遍历的套用200

5.4.3二叉树遍历的非递归算法203

5.4.4二叉树的计数207

5.5线索二叉树210

5.5.1线索210

5.5.2中序线索二叉树的建立和遍历211

5.5.3中序线索二叉树的插入与删除216

5.5.4前序与后序的线索化二叉树218

5.6树与森林220

5.6.1树的存储表示220

5.6.2森林与二叉树的转换225

5.6.3树与二叉树的转换227

5.7树与森林的遍历及其套用227

5.7.1树与森林的深度优先遍历227

5.7.2树和森林的广度优先遍历230

5.7.3树遍历算法的套用231

5.7.4其他基于遍历序列的几种存储表示232

5.8堆235

5.8.1最小堆和最大堆235

5.8.2堆的建立236

5.8.3堆的插入与删除238

5.9Huffman树及其套用240

5.9.1路径长度240

5.9.2Huffman树241

5.9.3Huffman树的套用：最优判定树243

5.9.4Huffman树的套用：Huffman编码244

习题246

第6章集合与字典251

6.1集合及其表示251

6.1.1集合的基本概念251

6.1.2用位向量实现集合抽象数据类型252

6.1.3用有序鍊表实现集合的抽象数据类型257

6.2并查集与等价类262

6.2.1并查集的定义及其实现262

6.2.2并查集的套用：等价类划分267

6.3字典268

6.3.1字典的概念269

6.3.2字典的线性表描述270

6.4跳表273

6.4.1跳表的概念273

6.4.2跳表的类定义274

6.4.3跳表的搜寻、插入和删除276

6.5散列279

6.5.1散列表与散列方法279

6.5.2散列函式280

6.5.3处理冲突的闭散列方法282

6.5.4处理冲突的开散列方法291

6.5.5散列表分析293

习题294

第7章搜寻结构297

7.1静态搜寻结构298

7.1.1静态搜寻表298

7.1.2顺序搜寻300

7.1.3基于有序顺序表的顺序搜寻和折半搜寻302

7.1.4基于有序顺序表的其他搜寻方法307

7.2二叉搜寻树308

7.2.1二叉搜寻树的概念309

7.2.2二叉搜寻树上的搜寻310

7.2.3二叉搜寻树的插入311

7.2.4二叉搜寻树的删除313

7.2.5二叉搜寻树的性能分析314

7.2.6最优二叉搜寻树317

7.3AVL树320

7.3.1AVL树的概念321

7.3.2平衡化旋转321

7.3.3AVL树的插入326

7.3.4AVL树的删除329

7.3.5AVL树的性能分析333

7.4伸展树334

7.5红黑树337

7.5.1红黑树的概念和性质337

7.5.2红黑树的搜寻338

7.5.3红黑树的插入338

7.5.4红黑树的删除339

习题342

第8章图346

8.1图的基本概念346

8.1.1与图有关的若干概念346

8.1.2图的抽象数据类型348

8.2图的存储结构349

8.2.1图的邻接矩阵表示350

8.2.2图的邻接表表示355

8.2.3图的邻接多重表表示361

8.3图的遍历363

8.3.1深度优先搜寻364

8.3.2广度优先搜寻365

8.3.3连通分量366

8.3.4重连通分量368

8.4最小生成树370

8.4.1Kruskal算法371

8.4.2Prim算法373

8.5最短路径375

8.5.1非负权值的单源最短路径376

8.5.2任意权值的单源最短路径379

8.5.3所有顶点之间的最短路径381

8.6用顶点表示活动的网路（AOV网路）383

8.7用边表示活动的网路（AOE网路）388

习题392

第9章排序397

9.1排序的概念及其算法性能分析397

9.1.1排序的概念397

9.1.2排序算法的性能评估398

9.1.3排序表的类定义400

9.2插入排序401

9.2.1直接插入排序401

9.2.2折半插入排序403

9.2.3希尔排序404

9.3快速排序405

9.3.1快速排序的过程406

9.3.2快速排序的性能分析407

9.3.3快速排序的改进算法409

9.3.4三路划分的快速排序算法412

9.4选择排序413

9.4.1直接选择排序413

9.4.2锦标赛排序414

9.4.3堆排序419

9.5归併排序422

9.5.1归併422

9.5.2归併排序算法423

9.6基于鍊表的排序算法425

9.6.1鍊表插入排序425

9.6.2鍊表归併排序427

9.6.3鍊表排序结果的重排428

9.7分配排序431

9.7.1桶式排序431

9.7.2基数排序432

9.7.3MSD基数排序433

9.7.4LSD基数排序435

9.8内部排序算法的分析437

9.8.1排序方法的下界437

9.8.2各种内部排序方法的比较439

习题440

第10章档案、外部排序与搜寻444

10.1主存储器和外存储器444

10.1.1磁带444

10.1.2磁碟存储器446

10.1.3缓冲区与缓冲池448

10.2档案组织449

10.2.1档案的概念449

10.2.2档案的存储结构450

10.3外排序459

10.3.1外排序的基本过程459

10.3.2k路平衡归併与败者树461

10.3.3初始归併段的生成（rungeneration）466

10.3.4并行操作的缓冲区处理470

10.3.5最佳归併树473

10.4多级索引结构475

10.4.1静态的ISAM方法475

10.4.2动态的m路搜寻树476

10.4.3B树478

10.4.4B树的插入480

10.4.5B树的删除482

10.4.6B+树486

10.4.7VSAM489

10.5可扩充散列490

10.5.1二叉Trie树490

10.5.2将二叉Trie树转换为目录表491

10.5.3目录表扩充与收缩493

10.5.4性能分析494

10.6Trie树494

10.6.1Trie树的定义494

10.6.2Trie树的搜寻495

10.6.3在Trie树上的插入和删除496

习题497

附录A程式索引500

附录B辞彙索引504

参考文献512