本书是在多年讲授数据结构讲义的基础上整理而成的，内容包括数据结构概述、线性表、栈和队列、串、数组与广义表、二叉树、树与森林、图、查找、排序等知识点。全书共分10章，各章都配有一定数量的习题，方便读者巩固所学知识。 本书的特点是：除了阐述“数据结构”学科的基本概念、基本理论和基本方法以外，特别强调数据建模和求解算法的思想方法，重点培养学生的抽象建模能力、算法设计能力、算法的语言描述能力、数据结构的应用创新能力。本书的编写坚持语言流畅、通俗易懂的指导思想，力求概念表述严谨，算法分析深入浅出，适合作为高校计算机及相关专业的教材使用，同时也可作为自学参考书。

        FOREWORD



        用计算机解决实际问题一般要经过分析问题、建立模型、定义数据、寻找算法、编写程序、测试计算、分析结果七个步骤。分析问题的任务是在弄清、理解问题的基础上，明确问题是什么，问题要求做什么，找出问题域和约束条件等；建立模型的任务是站在计算机的角度上，将问题域中的对象、属性、关系以及操作抽象成适合于计算机处理的计算模型，即建立数据的逻辑结构；定义数据的任务是将问题域中的对象、属性、关系等数据化，用计算机能够识别、接收、存储、计算的格式把数据确切地定义出来，即把数据的逻辑结构映射成存储结构；寻找算法的任务是在已定义的数据存储结构基础上，将各种操作实现过程的具体步骤和顺序确切地表示出来，使每一步操作都能在计算机上实现；编写程序的任务是选择合适的程序设计语言，将算法精确地表示成计算机可执行的代码；测试计算的任务是将程序代码和数据输入计算机内，进行调试、纠错，直到没有错误为止，最后进行实际计算，并输出问题的求解结果；分析结果的任务是判断计算机计算的结果与实际问题要求的结果是否相符，若满足要求则结束，若与实际问题要求有差距则返回，从头开始逐步检查每一个步骤是否存在错误，若发现问题则重新修改。以上七个步骤是一个不断重复的循环过程，其重复的次数取决于人们的智力、知识、经验、能力、技术、技巧等多方面的因素。由此不难体会到，用计算机解决实际问题的七个步骤中，其中的六个步骤都是由人工完成的，可见人为因素占主导地位。



        用计算机解决问题各个步骤的难易程度是不同的。确定问题是基础，建立模型是关键，这两个步骤可能涉及许多专业领域知识，单纯由计算机专业人员是难以完成的，往往需要与专业领域的专家或客户合作才能完成任务。定义数据相对比较简单，而寻找算法是最为困难的一步。许多问题没有现成的模型和算法可以借鉴、参考，完全靠设计者探索寻找，这是一项具有创新性、挑战性的任务。编写程序可以说是难度最小的一个步骤，一般编程人员都可以胜任工作，有些甚至可以自动生成。测试计算看起来似乎简单，但实际做起来却是一件非常烦琐和复杂的工作。调试程序实际上就是查错和纠错，需要测试人员有一定的智慧和丰富的经验才能进行。分析结果也是不可缺少的一个步骤，因为只有当结果符合实际问题和客户要求时，才算圆满完成任务，否则必须找出原因和对策。



        从以上对利用计算机求解实际问题各个步骤的分析不难看出，“数据结构”这门课程对于用计算机解决实际问题具有非常重要的作用。



        数据结构对于计算机科学与技术学科各专业的学生来说，既是一门理论性较强的基础课，又是一门实践性较强的专业技术课。它所研究的问题是计算机程序设计中的数据元素、数据对象、数据元素之间的关系以及非数值计算性的数据处理问题；所研究的主要内容包括数据的逻辑组织（即逻辑结构）、存储表示（即存储结构）、算法实现以及算法效率问题等。其中,数据的逻辑结构分为集合结构、线性结构、树形结构和图状结构四种类型，它们分别描述了数据元素之间的无关系、1对1关系、1对多关系和多对多关系。数据的存储结构是逻辑结构在计算机内部的存储映像，其存储方式主要有顺序存储、链式存储、索引存储和散列存储四种，每种存储结构各有自己的优点、缺点和适用场合。数据的操作主要包括查找、插入、删除、排序和遍历等非数值性计算，如何在适当的存储结构下实现这些操作算法是数据结构研究的核心问题。不同的数据结构所能施加的运算不同，不同的存储结构直接影响运算算法的实现和效率。数据的运算定义取决于逻辑结构，数据的运算算法依赖于存储结构。这就是为什么要研究数据的各种逻辑结构和存储结构的根本原因。数值计算问题在“数值分析”（也称“计算数学”或“数值计算”）学科中专门研究；数据结构中研究的是非数值计算问题，如遍历、查找、排序、插入、删除、归并等。正因为这类操作不能用数学方法计算，所以成为数据结构讨论的主要问题。



        数据结构的理论知识、思想方法和设计技术不仅在应用计算机解决实际问题的整个过程之中具有重要意义，而且对培养人的分析问题和解决问题能力、抽象的数据建模能力、良好的算法设计和编程能力等也具有不可替代的作用。这也是人们要重视数据结构教学的根本原因所在。



        1?数据结构的学习意义



        为什么要学习数据结构这门课程？主要基于以下两方面的原因：



        （1）数据结构的概念、理论、技术和方法在计算机应用中具有重要的指导意义和实用价值。众所周知，用计算机解决实际问题通常要经过分析定义问题、建立数据模型、寻找求解算法、编程上机实现和分析计算结果等多个步骤，其中数据建模、算法设计和编程实现几个步骤都需要数据结构的知识。所以，学好数据结构对于从事计算机软件设计开发是非常有用的。



        （2）数据结构在计算机科学与技术学科中的地位。数据结构是计算机科学与技术各专业的核心课程，它既是理论性较强的基础课，又是实践性很强的专业技术课，在计算机学科领域的主干课程中具有承上启下的作用。它的先行课程有离散数学、程序设计语言、计算机硬件基础等；它的后继课程是操作系统、数据库原理、编译原理、软件开发技术等。有人提出：计算机科学技术专业有两门“顶天立地”的课程，其中“顶天”的课程是离散数学，“立地”的课程是数据结构。离散数学的知识贯穿计算机科学技术领域的各门学科之中，所以是顶天的；而数据结构是许多计算机理论课的基础，所以是立地的。



        （3）数据结构的作用。学习数据结构对于培养人的抽象思维能力、数据建模能力、算法创新能力、程序设计能力、语言描述能力、综合应用能力等具有特定的作用。在信息社会高速发展的时代，信息素质是一个人适应信息社会生存和发展的最基本、最重要的素质之一。而学习数据结构，对于提高人们的信息素质和综合能力具有重要的、其他课程不可替代的作用。



        2?数据结构的学习特点



        数据结构的学习特点主要体现在以下三个方面：



        （1）内容多。数据结构研究的问题非常广泛，内容极为丰富。著名的美国算法大师，1974年图灵奖得主唐·欧·克努特教授编写了一套巨著《程序设计的艺术》，计划出版7卷，目前已发行4卷，每卷500~600页，后几卷还在编著过程中。该书是研究算法与数据结构的权威名著，有人把它比喻为计算机科学技术领域的“圣经”。由此不难看出，数据结构研究的内容之多令人惊叹。



        （2）难度大。由于计算机只能进行数据处理，不能直接解决现实世界中的具体问题，必须由人将现实问题抽象成计算机能够接受并处理的数据模型才能实现，这个过程称为数据建模，其难度较大，不仅需要熟练掌握计算机科学技术的许多知识，还要具备不同领域和学科的专业知识，不仅需要深入的洞察能力和高度的抽象思维能力，还要具有高超的算法创新能力及精湛的表达实现能力。对初学者来说，建立信息模型和探求问题算法是两大难关。



        （3）交叉性。数据结构是由数学、计算机软件和硬件知识交叉形成的一门学科，学习该课程需要具备的知识较多，因而更增加了学习的难度。

尽管数据结构课程学习的难度较大，但只要认真努力地学习，总能学会。



        3?数据结构的学习方法



        数据结构的地位、作用重要，且学习的难度较大，如何学好“数据结构”这门课程？在此提出如下参考性建议：



        （1）深刻领会数据结构的基本概念。一门学科的知识实际上就是反映该学科领域的一组概念的逻辑体系。数据结构概念较多，理解起来有一定难度，每个概念包括内涵和外延两个方面，概念的内涵揭示对象的本质特征，是区分不同事物的根本标志，概念的外延反映了概念所包含对象的集合，是理解概念之间关系的依据。在学习过程中，应该深入体会每一个概念的实质，深刻理解概念的内涵和外延。



        （2）熟练掌握数据模型及建模方法。用计算机解决实际问题的一般步骤是：分析定义问题、建立数据模型、寻找操作算法、编写程序代码、进行测试调试、运行维护系统。此过程的核心是数据建模、算法描述、编程实现，这些都与数据结构有密切关系。数据结构按其数据元素之间的逻辑关系不同，将数据的逻辑结构化分为四种基本类型：集合结构、线性结构、树形结构和图状结构。四种逻辑结构的存储映像构成数据的存储结构，按映像的方式不同可分为顺序存储结构和链式存储结构两类。更详细地又可分为顺序存储结构、链式存储结构、索引存储结构和散列存储结构四种。对每种数据结构定义操作、存储映像、讨论算法、描述实现构成了数据结构研究的主要内容。因此，熟练数据模型思想、掌握建模方法是学好数据结构的基础。

        

        （3）牢固树立算法思想和实现过程。算法就是对求解某个具体问题的过程和步骤的实现描述。算法设计既是解决问题的关键，又是求解过程的难点。究其原因，一是对同一个问题，解决的途径有多条，求解的方法可以有多种，正所谓“条条大路通罗马”，如何找到最优化、最经济的方法。二是在多数情况下，所求解的问题是全新的，既没有固定的方法，又没有现成的模式可以借鉴，需要独立探索发现，这是一个完全创新的过程，需要人的创新思维。三是数据建模和算法设计必须站在计算机的角度考虑问题，因为数据结构和算法描述最终都必须在计算机上实现，每一种数据模型都必须映射成存储模型，每一个算法都必须表示成计算机所能执行的指令，因此需要计算机工作原理和实现机制。在数据结构中，将已经总结概括出的每一种逻辑数据结构，定义相应的一组操作，构成数据类型，对每种操作选择适当的存储结构，寻找某种操作的算法并将算法的步骤用某种语言确切地描述实现。通过学习，不仅要掌握这些已有知识，更重要的是学习数据建模和算法设计的思想方法，养成创新思维习惯，提高创新能力，这也是学习数据结构的最终落脚点。



        （4）高度重视上机实践和课程设计。数据结构不仅是一门理论性的专业课，同时还是一门具有较强实践性的技术课。上机实践是学习数据结构的重要环节。每学习一种数据类型，都需要用编成语言定义数据的存储结构，编写高效的程序代码，并上机调试实现。通过上机实践，深刻体会实现过程，可以进一步理解、掌握、巩固所学知识。



        （5）善于比较、总结归纳和融会贯通。在学习数据结构课程时，要善于总结归纳，对每一节、每一章和整个课程进行不同阶段、不同层次的总结，理出一条知识要点线索，归纳出知识体系结构，用树形结构将知识点与逻辑关系表示成知识体系树，这样既容易理解掌握，又便于记忆，因为人的大脑神经元结构就是树，树与树之间联结形成神经网络，将知识体系整理成知识树最适合大脑的记忆。学会比较也是学好数据结构的重要方法。通过对不同概念、不同性质、不同结构、不同算法的比较，发现它们的相同或相似之处，找出彼此之间的差别及内、外在联系，从而更加深刻地理解知识体系的结构特性与完整统一。对知识理解的举一反三与知识应用的融会贯通是学习知识达到的最高境界。学习一种数据模型，应该会用该类型解决一类问题，学习一种算法，能用此算法思想解决类似的问题，能对算法适当修改、扩展以解决更广泛的问题。通过不断的比较总结、应用尝试和经验积累，最终提高综合能力。



        （6）注意多读多思多练和不耻下问。学习数据结构的另一种途径是：多读教材和有关参考资料中的算法，领会他人的思想和技巧，吸收应用到自己的工作中；对重点知识内容和常用算法多思考，深刻领会其实质，透彻理解，纳入自己的知识系统中。
        编者2008年9月

第1章数据结构概述1

1.1数据结构研究的问题1

1.1.1计算机解决实际问题的一般步骤1

1.1.2数据结构学科概念及其所研究的内容2

1.1.3数据结构的建模举例2

1.2数据结构的有关概念5

1.2.1数据的有关概念5

1.2.2数据结构的相关术语6

1.2.3数据类型的概念8

1.3算法与算法性能分析9

1.3.1算法概念及特点10

1.3.2算法的设计要求12

1.3.3算法的性能分析13

1.4数据结构与算法描述工具简介17

习题19

第2章线性表22

2.1线性表的类型定义22

2.1.1线性表的概念与逻辑结构22

2.1.2线性表的ADT定义23

2.2线性表的顺序存储结构及其算法实现25

2.2.1线性表的顺序存储结构25

2.2.2顺序表的基本算法实现27

2.2.3顺序表应用举例30

2.3线性表的链式存储与算法实现33

2.3.1单链表存储结构33

2.3.2单链表基本运算的实现37

2.3.3双向链表44

2.3.4循环链表46

2.3.5静态链表47

2.3.6单链表应用举例48

习题52

第3章栈和队列56

3.1栈56

3.1.1栈的概念及ADT定义56

3.1.2栈的存储表示与算法实现57

3.2栈的应用举例63

3.3队列78

3.3.1队列的定义及ADT定义78

3.3.2队列的存储结构及算法实现80

习题86
数据结构（C语言版）目录第4章串90

4.1串的概念及其ADT定义90

4.1.1串的基本概念及术语90

4.1.2串的ADT定义90

4.2串的定长顺序存储及基本运算92

4.2.1串的定长顺序存储表示及其算法实现92

4.2.2定长顺序串的基本运算93

4.3串的堆存储结构及算法实现95

4.3.1串的堆存储结构96

4.3.2堆串的算法实现97

4.4串的匹配算法99

4.4.1简单匹配算法99

4.4.2KMP匹配算法101

4.4.3串的其他存储映像105

习题107

第5章数组与广义表110

5.1数组110

5.1.1数组类型与存储结构110

5.1.2数组的内存映像111

5.2特殊矩阵的压缩存储114

5.2.1对称矩阵114

5.2.2三角矩阵115

5.2.3带状矩阵117

5.3稀疏矩阵117

5.3.1稀疏矩阵的三元组存储结构与矩阵的转置和乘法118

5.3.2稀疏矩阵的十字链表存储与矩阵的加法和减法124

5.4广义表128

5.4.1广义表的概念与ADT定义128

5.4.2广义表的存储131

5.4.3广义表的基本操作算法133

5.4.4广义表的应用举例136

习题138

第6章二叉树142

6.1二叉树的概念与性质142

6.1.1二叉树的定义及相关术语142

6.1.2二叉树的性质146

6.2二叉树的存储结构与创建算法148

6.2.1二叉树的存储结构148

6.2.2二叉树的创建算法152

6.3二叉树的遍历算法及其应用153

6.3.1二叉树的递归遍历算法153

6.3.2二叉树的非递归遍历算法155

6.3.3二叉树遍历算法的应用159

6.3.4由遍历序列恢复二叉树162

6.4线索二叉树165

6.4.1线索二叉树的定义及结构166

6.4.2线索二叉树的基本操作算法168

6.5哈夫曼树173

6.5.1哈夫曼树的概念与构造算法173

6.5.2哈夫曼的应用177

习题182

第7章树与森林187

7.1树的概念与ADT定义187

7.1.1树的定义及其相关术语187

7.1.2树的ADT定义190

7.1.3树与森林的性质191

7.2树与森林的存储结构192

7.3树、森林与二叉树的转换197

7.3.1树转换成二叉树197

7.3.2森林转换成二叉树198

7.3.3二叉树转换成树或森林199

7.4树和森林的遍历200

7.4.1树的遍历200

7.4.2森林的遍历201

7.5树的应用201

7.5.1集合的表示201

7.5.2求等价类问题203

习题204

第8章图207

8.1图的基本概念与类型定义207

8.1.1图的概念与相关术语207

8.1.2图的ADT定义211

8.2图的存储表示与创建算法212

8.2.1邻接矩阵存储表示与创建算法212

8.2.2邻接表存储表示与创建算法215

8.2.3有向图的十字链表存储表示与创建算法217

8.2.4无向图的邻接多重表存储表示219

8.3图的遍历算法220

8.3.1深度优先搜索算法221

8.3.2广度优先搜索算法222

8.4图的连通性224

8.4.1无向图的连通性224

8.4.2有向图的连通性225

8.4.3生成树和生成森林225

8.4.4关结点和重连通分量227

8.5最小生成树230

8.5.1最小生成树的概念230

8.5.2构造最小生成树的Prim算法231

8.5.3构造最小生成树的Kruskal算法234

8.6最短路径问题236

8.6.1从一个源点到其他各顶点的最短路径236

8.6.2每一对顶点之间的最短路径239

8.7有向无环图及其应用241

8.7.1有向无环图的概念241

8.7.2AOV网与拓扑排序242

8.7.3AOE网与关键路径247

习题251

第9章查找256

9.1查找概述256

9.1.1查找表的有关概念256

9.1.2查找表的类型说明257

9.1.3查找算法的性能分析258

9.2静态查找表258

9.2.1静态查找表的结构258

9.2.2顺序表的查找259

9.2.3有序表的查找260

9.2.4有序表的其他查找方法265

9.2.5静态树表的查找267

9.3动态查找表270

9.3.1二叉排序树271

9.3.2平衡二叉树(AVL树)277

9.3.3B树和B+树286

9.4哈希表查找296

9.4.1哈希表与哈希方法296

9.4.2哈希函数的常用构造方法297

9.4.3处理冲突的方法299

9.4.4哈希表的查找分析301

习题304

第10章排序308

10.1基本概念308

10.2插入排序309

10.2.1直接插入排序310

10.2.2折半插入排序312

10.2.3表插入排序313

10.2.4希尔排序315

10.3交换排序317

10.3.1冒泡排序317

10.3.2快速排序319

10.4选择排序322

10.4.1简单选择排序322

10.4.2树形选择排序324

10.4.3堆排序(heap sort)325

10.5二路归并排序328

10.6基数排序329

10.6.1多关键字排序329

10.6.2链式基数排序330

10.6.3计数排序333

10.7各种排序算法的比较334

10.8外排序335

10.8.1外部排序的方法335

10.8.2多路平衡归并的实现336

习题339

参考文献342

无