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

全书采用面向对象的观点讨论数据结构技术，并以兼有面向过程和面向对象双重特色的C++语言作为算法的描述工具，强化基本知识和基本能力的双基训练。全书条理清晰，通俗易懂，图文并茂，适于自学。

与本书配套的《数据结构习题解析——用面向对象方法与C++语言描述》一书已经由清华大学出版社出版。本书适合大专院校计算机、软件专业本科生使用，也可作为教师和有关科研人员的参考书。

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

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

全书采用面向对象的观点讨论数据结构技术，并以兼有面向过程和面向对象双重特色的C++语言作为算法的描述工具，强化基本知识和基本能力的双基训练。全书条理清晰，通俗易懂，图文并茂，适于自学。

与本书配套的《数据结构习题解析——用面向对象方法与C++语言描述》一书已经由清华大学出版社出版。本书适合大专院校计算机、软件专业本科生使用，也可作为教师和有关科研人员的参考书。

第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初始归并段的生成（run generation）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