数据结构是计算机专业的重要基础课程，也是该专业的核心课程之一，它是一门集技术性、理论性和实践性于一体的课程。

本书介绍了抽象数据类型和基本数据结构，阐述了各种数据结构内在的逻辑关系，讨论了各种数据结构在计算机中的存储表示，给出了在各种数据结构上的基本运算及算法实现。内容包括：数据结构概述、线性表、栈和队列、串、多维数组与广义表、二叉树与树、图、查找表、内部排序、外部排序、文件和数据结构程序设计方法。书中使用类C语言作为算法描述语言，且所有算法都可以在任何一种C语言的开发环境中实现。书中每一章后面都配有适量的习题，以供读者复习提高自身水平。

本书可以作为高等院校计算机专业及相关专业的教材。对于计算机类专业的学生或从事计算机工程与应用工作的科技工作者，本书也是一本实用的参考教材。

前    言

　　“数据结构”在计算机科学中是一门综合性的专业基础课。数据结构的研究不仅涉及到计算机硬件(特别是编码理论、存储装置和存取方法等)的研究，而且和计算机软件的研究有着更密切的关系，无论是编译程序还是操作系统，都涉及到数据元素在存储器中的分配问题。在研究信息检索时也必须考虑如何组织数据，以便使查找和存取数据元素更为方便。可以认为数据结构是介于数学、计算机硬件和计算机软件三者之间的一个核心内容，是从事计算机科学研究及其应用的科技工作者必须掌握的重要内容。

　　本书在内容组织和编排上力求体现“先理论、后应用、理论与应用相结合”的原则，强调对理论知识的理解和运用。通过对本课程的学习，可掌握各种数据结构的基本概念、逻辑特性和物理表示法，以及相应运算的算法；灵活运用各种数据结构解决实际应用问题，并且为学习后继专业课程打下良好的基础。

　　全书的第1章综述数据、数据结构、抽象数据类型、算法描述及算法分析等概念；第2章~第7章从抽象数据类型的角度介绍了几种常用的数据结构，如线性表、栈、队列、串、多维数组、广义表、二叉树、树及图等，分别讨论了数据的逻辑结构和存储结构，以及相应运算的算法实现；第8章~第10章分别讨论了查找表、内部排序和外部排序的各种实现方法，并着重从时间上进行定性或定量的分析和比较；第11章介绍了常用的文件结构；第12章讲述了数据结构程序设计的方法，并以一个实例做进一步的说明。

　　全书采用了类C语言作为数据结构和操作算法的描述工具，它是C语言的一个精选子集，同时又采用了C++对C语言的非面向对象的增强功能。例如，动态分配和释放顺序存储结构的空间；利用引用参数传递函数运算的结果；使用默认参数以简化函数参数表的描述等。这些措施使数据类型的定义和数据结构相关操作算法的描述更加简明清晰、可读性更好，转变成C程序也极为方便。另一方面又奠定了一个基础，把类型定义和操作算法稍加技术处理，就很容易将其封装成类，并进一步转化成面向对象的程序模型。

　　本书可以作为高等院校计算机专业及相关专业的教材，教授时间可为80学时(包括讲课和上机)。为了便于读者理解，本书对数据结构众多知识点的来龙去脉做了详细的解释和说明，并配有大量的算法应用实例穿插其间。考虑到计算机技术的发展和进步，在内容编排方面尽量做到推陈出新，实例也力求新颖，以适应技术发展的潮流。

　　由于作者水平有限，书中难免有错误，请读者谅解，如果有问题需要与作者联系，请发送电子邮件到：pengbo_cau@sina.com。

　　在编写本书的过程中，孙一林、胡治国、吕小晴、崔永普、许振文、王茜、刘群、张伟娜等同志参加了算法的实现与调试，在此表示感谢。

　　

　　 编  者

　　 2004.1

     

　　

　　

     

　　

　　

目    录

第1章  绪论 1

1.1  数据结构的讨论范畴 1

1.2  数据结构的发展概况 3

1.3  数据结构的相关概念 5

1.3.1  基本概念和术语 5

1.3.2  数据结构 6

1.3.3  数据类型和抽象数据类型 10

1.4  数据结构的算法描述 12

1.4.1  算法 12

1.4.2  算法的描述 13

1.5  数据结构的算法分析 17

1.5.1  算法效率的度量 17

1.5.2  算法的空间需求 19

1.6  习题 20

第2章  线性表 23

2.1  线性表的类型定义 23

2.1.1  线性表的定义 24

2.1.2  线性表的抽象数据类型 24

2.2  线性表的顺序表示与实现 27

2.2.1  线性表的顺序存储表示 28

2.2.2  顺序表中基本操作的实现 28

2.2.3  顺序存储结构小结 34

2.2.4  应用举例 35

2.3  线性表的链式表示与实现 38

2.3.1  线性表的链式存储表示 39

2.3.2  单链表中基本操作的实现 39

2.3.3  循环链表 44

2.3.4  双向链表 44

2.3.5  静态链表 47

2.3.6  链式存储结构小结 48

2.3.7  应用举例 48

2.4  顺序表示与链式表示比较 53

2.4.1  基于空间的考虑 53

2.4.2  基于时间的考虑 54

2.4.3  基于语言的考虑 54

2.5  习题 54

第3章  栈和队列 58

3.1  栈 58

3.1.1  栈的定义 58

3.1.2  栈的抽象数据类型 59

3.1.3  栈的顺序存储表示与实现 60

3.1.4  栈的链式存储表示与实现 63

3.1.5  应用举例 64

3.2  队列 73

3.2.1  队列的定义 73

3.2.2  队列的抽象数据类型 73

3.2.3  队列的顺序存储表示

与实现 74

3.2.4  队列的链式存储表示

与实现 78

3.2.5  应用举例 80

3.3  习题 83

第4章  串 85

4.1  串的类型定义 85

4.1.1  串的定义 85

4.1.2  串的抽象数据类型 86

4.2  串的存储表示与实现 88

4.2.1  定长顺序存储表示 88

4.2.2  堆分配存储表示 91

4.2.3  块链存储表示 95

4.2.4  应用举例 96

4.3  串的模式匹配 97

4.3.1  串的模式匹配BF算法 97

4.3.2  串的模式匹配KMP算法 99

4.4  习题 103

第5章  多维数组与广义表 105

5.1  多维数组 105

5.1.1  数组的定义 105

5.1.2  数组的抽象数据类型 106

5.1.3  数组的顺序存储

表示和实现 107

5.1.4  应用举例 110

5.2  矩阵的压缩存储 111

5.2.1  特殊矩阵 112

5.2.2  稀疏矩阵 114

5.2.3  应用举例 124

5.3  广义表 128

5.3.1  广义表的定义 128

5.3.2  广义表的抽象数据类型 129

5.3.3  广义表的链式存储

表示与实现 130

5.3.4  应用举例 138

5.4  习题 142

第6章  二叉树与树 144

6.1  二叉树 144

6.1.1  二叉树的定义 144

6.1.2  二叉树的基本术语 145

6.1.3  二叉树的抽象数据类型 147

6.1.4  二叉树的基本性质 148

6.1.5  二叉树的存储表示 150

6.2  遍历二叉树 153

6.2.1  遍历二叉树的定义 154

6.2.2  遍历二叉树的递归算法 155

6.2.3  遍历二叉树的非递归算法 156

6.2.4  基于遍历操作的其他算法 162

6.2.5  应用举例 163

6.3  线索二叉树 168

6.3.1  线索二叉树的引出 168

6.3.2  线索二叉树的定义 169

6.3.3  线索二叉树的存储

表示与实现 170

6.3.4  应用举例 176

6.4  树和森林 177

6.4.1  树和森林的定义 177

6.4.2  树的抽象数据类型 178

6.4.3  树的存储表示 179

6.4.4  树和森林与二叉树的转换 183

6.4.5  树和森林的遍历 187

6.4.6  应用举例 189

6.5  Huffman树及其应用 197

6.5.1  Huffman树的定义 197

6.5.2  Huffman算法 199

6.5.3  Huffman树的存储

表示与实现 200

6.5.4  Huffman编码 201

6.5.5  Huffman编码的存储

表示与实现 202

6.5.6  应用举例 203

6.6  习题 205

第7章  图 210

7.1  图的类型定义 210

7.1.1  图的定义 210

7.1.2  图的基本术语 210

7.1.3  图的抽象数据类型 214

7.1.4  应用举例 215

7.2  图的存储表示与实现 216

7.2.1  邻接矩阵表示法 216

7.2.2  邻接表表示法 219

7.2.3  十字链表表示法 222

7.2.4  邻接多重表表示法 224

7.1.5  应用举例 226

7.3  图的遍历 227

7.3.1  深度优先搜索遍历图 227

7.3.2  广度优先搜索遍历图 228

7.3.3  应用举例 229

7.4  最小生成树 230

7.4.1  生成树 230

7.4.2  最小生成树 231

7.4.3  应用举例 237

7.5  最短路径 238

7.5.1  求某个源点到其他顶点

的最段路径 239

7.5.2  求每一对顶点之间的

最短路径 242

7.5.3  应用举例 244

7.6  拓扑排序 245

7.6.1  AOV网 245

7.6.2  拓扑排序 247

7.6.3  应用举例 249

7.7  关键路径 250

7.7.1  AOE 网 250

7.7.2  关键路径的概念 251

7.7.3  求关键路径的算法实现 252

7.7.4  应用举例 254

7.8  习题 255

第8章  查找表 260

8.1  静态查找表 262

8.1.1  静态查找表的抽象

数据类型 262

8.1.2  静态查找表的顺序

存储表示 262

8.1.3  顺序查找 262

8.1.4  折半查找 263

8.1.5  分块查找 265

8.1.6  应用举例 267

8.2  动态查找表 268

8.2.1  动态查找的抽象数据类型 268

8.2.2  动态查找表的存储表示 269

8.2.3  二叉排序树 269

8.2.4  平衡二叉树 274

8.2.5  B-树和B+树 280

8.2.6  键树 288

8.2.7  应用举例 292

8.3  哈希表 298

8.3.1  哈希表的定义 299

8.3.2  哈希函数的构造方法 300

8.3.3  处理冲突的方法 303

8.3.4  哈希表的查找和分析 305

8.3.5  应用举例 308

8.4  习题 310

第9章  内部排序 314

9.1  插入排序法 315

9.1.1  直接插入排序 315

9.1.2  希尔排序 317

9.1.3  应用举例 318

9.2  交换排序法 319

9.2.1  冒泡排序 319

9.2.2  快速排序 320

9.2.3  应用举例 323

9.3  选择排序法 323

9.3.1  直接选择排序 324

9.3.2  堆排序 325

9.3.3  应用举例 331

9.4  归并排序法 331

9.4.1  两个有序序列的归并 331

9.4.2  2-路归并排序 332

9.4.3  应用举例 333

9.5  基数排序法 333

9.5.1  多关键字排序 333

9.5.2  链式基数排序 335

9.5.3  应用举例 339

9.6  各种内部排序法的比较 340

9.7  习题 341

第10章  外部排序 344

10.1  外存储设备简介 344

10.1.1  磁带信息的存取 344

10.1.2  磁盘信息的存取 345

10.1.3  光盘信息的存取 346

10.2  磁带文件归并排序 347

10.2.1  平衡归并排序 347

10.2.2  多步归并排序 348

10.2.3  应用举例 353

10.3  磁盘文件归并排序 356

10.3.1  初始归并段的生成 356

10.3.2  置换选择排序法 357

10.3.3  应用举例 358

10.4  最佳归并树 359

10.4.1  最佳归并树的定义 359

10.4.2  最佳归并树的设计 361

10.4.3  应用举例 362

10.5  习题 362

第11章  文件 364

11.1  基本概念 364

11.1.1  文件的概念 364

11.1.2  文件的分类 365

11.1.3  文件的逻辑结构 365

11.1.4  文件的物理结构 366

11.2  顺序文件 366

11.2.1  顺序文件的查找 367

11.2.2  顺序文件的修改 367

11.2.3  顺序文件的特点 368

11.3  索引文件 368

11.3.1  索引文件的分类 368

11.3.2  索引文件的存储 369

11.3.3  索引文件的操作 369

11.3.4  利用查找表建立

 多级索引 370

11.4  ISAM和VSAM文件 371

11.4.1  ISAM 文件 371

11.4.2  VSAM 文件 374

11.5  哈希文件 376

11.5.1  哈希文件的操作 377

11.5.2  哈希文件的特点 378

11.6  多关键字文件 378

11.6.1  多重表文件 378

11.6.2  倒排文件 380

11.7  应用举例 381

11.8  习题 384

第12章  数据结构程序设计方法 386

12.1  从问题到程序的求解过程 386

12.1.1  建立数据结构模型设计

 抽象数据类型 386

12.1.2  算法设计 387

12.1.3  实现抽象数据类型 388

12.1.4  编制程序代码并进行

 静态测试和动态调试 389

12.2  程序的规范说明 391

12.3  应用举例 392

附录A  部分习题答案 402

参考书目 409