本书用C语言描述数据结构。全书共分10章，具体内容包括数据结构的基本概念、线性表、栈、队列、字符串、二叉树、树和森林、图状结构、排序、查找，并作了适当延伸。全书内容安排合理，介绍力求透彻、全面，并对学生在编程中经常出现的一些错误给予了重点提示。本书各章中的示例代码均调试通过。书中每章最后都有习题，并提供电子答案。

    本书既可作为高等院校计算机科学与技术专业以及软件工程专业本科生学习数据结构与算法课程的教材，也可作为从事计算机或软件系统开发人员的学习资料。

前    言

　　“数据结构”课程在整个计算机学科领域中具有重要地位和意义。教育部高校计算机科学与技术教学委员会指出：“数据结构与算法是计算机学科本科教学计划中的骨干基础课程，对学生基本的计算机问题求解能力的培养具有重要意义。作为一门必修课程，该课程既是对以往课程的深入和扩展，也可为将来更加深入学习其他专业课程打下基础。课程中所学习的排序问题的算法以及基本的树、图等数据结构，是计算机学科的基本功。B+树、散列等高级数据结构也是数据库、操作系统、编译原理、计算机网络等后续课程的基础。” 

　　数据结构不仅为程序设计提供了方法论的指导，还在更高层次上总结了现实生活中复杂数据的计算机处理方法，是计算机软件开发、应用人员必备的专业知识。

　　数据结构是我国高等院校计算机专业的核心课程之一，也是其他信息类专业，如信息管理、通信工程、信息与计算科学等专业的必修课程之一。正因为它在计算机专业培养计划中的重要地位，计算机专业研究生入学考试将数据结构作为必考课程之一。数据结构理论的应用范围已经渗透到计算机专业的各领域中，如操作系统中要使用队列、存储管理表、目录树，数据库系统中要使用线性表、链表、索引树，编译系统中要使用栈、语法树，人工智能中要使用广义表、检索树、图等。在面向对象的程序设计、计算机图形学、多媒体技术、软件工程等领域，也会用到各种不同的数据结构。数据结构课程中自然而完美地整合了计算问题的数学分析建模、基本算法构建和基于高级程序设计语言的具体实现，从而体现出课程的重要意义和强大魅力。

　　本书是依据教育部制订的关于计算机科学与技术及相关专业的培养目标及教学大纲的要求，通过分析国内外多种同类书籍，结合作者长期的教学与程序设计经验而编写的。本书的算法使用C语言进行描述，并配有相关的解释，以帮助读者理解。

　　本书用C语言描述数据结构。全书共分10章，具体内容包括数据结构的基本概念、线性表、栈、队列、字符串、 二叉树、树和森林、图状结构、排序、查找，并作了适当延伸。全书内容安排合理，介绍力求透彻、全面，并对学生在编程中常见的一些错误给予了重点提示。书中各章后的示例代码均通过调试。书中每章都有习题，各习题都有电子答案。

　　本书既可作为高等院校计算机科学与技术专业以及软件工程专业本科生学习数据结构与算法课程的教材，也可作为从事计算机或软件系统开发人员的学习资料。

　　本书由张永宝执笔，参与本书编写和程序测试的人员还有余健、段德亮、张仁才、仇亚飞、田野、韩忠明、陈嗥、陈运来、代小华等。在本书编写过程中，借鉴了部分国内外优秀教材和相关材料，在此表示衷心感谢。

　　

　　

编  者  

　　

　　

　　

　　

　　

　　

　　

　　

　　

　　

目    录

第1章  数据结构的基本概念 1

1.1  数据结构的产生和发展 1

1.2  何谓数据结构 2

1.3  基本术语 4

1.4  数据的存储结构 7

1.4.1  顺序存储结构 7

1.4.2  链式存储结构 8

1.4.3  其他存储结构 9

1.5  算法及算法分析 9

1.5.1  算法 9

1.5.2  算法的评价 10

1.5.3  常用的数学术语 11

1.5.4  算法分析 11

1.5.5  算法的描述 14

1.6  C语言预备知识 15

1.7  数据结构课程定位 21

习题 21

第2章  线性表 23

2.1  何谓线性表 23

2.2  线性表的抽象数据类型和基本

操作 24

2.3  线性表的顺序存储结构 28

2.3.1  顺序表 28

2.3.2  顺序表应用举例 35

2.4  线性表的链式存储结构 38

2.4.1  单链表 38

2.4.2  双向链表 47

2.4.3  循环链表 52

2.4.4  链表应用举例 53

2.5  顺序表和链表的比较 57

习题 58

第3章  栈 60

3.1  何谓栈 60

3.2  栈的抽象数据类型和基本操作 61

3.3  栈的存储结构 62

3.3.1  栈的顺序存储结构 62

3.3.2  栈的链式存储结构 65

3.4  递归——汉诺塔问题 66

3.4.1  何谓递归 66

3.4.2  汉诺塔问题 68

3.5  栈的应用 70

3.6  习题 75

第4章  队列 77

4.1  何谓队列 77

4.2  队列的抽象数据类型和基本操作 78

4.3  队列的存储结构 78

4.3.1  队列的顺序存储结构 78

4.3.2  顺序队列的改进——循环

队列 83

4.3.3  队列的链式存储结构 84

4.3.4  顺序队列和链式队列的

比较 89

4.3.5  其他队列结构 89

4.4  队列的应用 90

习题 94

第5章  字符串 96

5.1  字符串概述 96

5.2  字符串的抽象数据类型和基本操作 97

5.3  字符串的操作的实现 98

5.3.1  字符串的顺序存储结构 98

5.3.2  字符串的堆存储结构 103

5.3.3  字符串的块链存储结构 106

5.4  模式匹配 107

5.4.1  子串定位操作 107

5.4.2  模式匹配的一种改进算法——

KMP算法 108

5.5  字符串操作应用 111

习题 117

第6章  二叉树 118

6.1  树形结构概述 118

6.1.1  树 118

6.1.2  树形结构的种类 119

6.1.3  树的相关术语 119

6.2  二叉树的概念 120

6.2.1  何谓二叉树 120

6.2.2  满二叉树和完全二叉树 121

6.2.3  二叉树的性质 121

6.2.4  二叉树的抽象数据类型和基本

操作 122

6.3  二叉树的存储结构 123

6.3.1  顺序存储结构 124

6.3.2  链式存储结构 125

6.4  二叉树的遍历 129

6.4.1  前序遍历 129

6.4.2  中序遍历 130

6.4.3  后序遍历 130

6.4.4  层序遍历 131

6.5  线索二叉树 133

6.5.1  何谓线索二叉树 133

6.5.2  中序线索二叉树的构造和

遍历 134

6.6  二叉树的应用 137

6.7  霍夫曼树及其应用 147

6.7.1  何谓霍夫曼树 147

6.7.2  霍夫曼树的应用 151

习题 153

第7章  树和森林 154

7.1  树和森林的概念 154

7.1.1  何谓树 154

7.1.2  树和二叉树的三个主要

差别 155

7.1.3  何谓森林 155

7.2  树的抽象数据类型和基本操作 155

7.3  树和森林的遍历 156

7.3.1  树的遍历 156

7.3.2  森林的遍历 157

7.4  树的存储结构 158

7.5  树、森林与二叉树的转换 165

7.5.1  树与二叉树的相互转换 166

7.5.2  森林与二叉树的相互转换 166

7.6  K叉树 167

习题 168

第8章  图状结构 169

8.1  图的定义与基本术语 169

8.1.1  何谓图 170

8.1.2  图的相关术语 170

8.2  图的抽象数据类型和基本操作 173

8.3  图的存储 174

8.3.1  邻接矩阵 174

8.3.2  邻接链表 179

8.3.3  十字链表 186

8.3.4  邻接多重表 188

8.4  图的遍历 191

8.4.1  深度优先搜索 191

8.4.2  广度优先搜索 194

8.5  最短路径问题 197

8.5.1  最短路径问题的概念 197

8.5.2  单源最短路径问题 198

8.5.3  狄克斯特拉算法 198

8.6  最小生成树 202

8.6.1  最小生成树的概念 202

8.6.2  最小生成树的性质 203

8.6.3  构造最小生成树的算法 203

8.7  AOV网和拓扑排序 213

8.7.1  AOV网 213

8.7.2  拓扑排序 214

习题 216

第9章  排序 218

9.1  排序问题的基本概念 218

9.2  简单排序算法 219

9.2.1  直接插入排序 219

9.2.2  冒泡排序 222

9.2.3  直接选择排序 223

9.2.4  简单排序算法的时间代价

对比 224

9.3  希尔排序 225

9.4  基于分治的排序 227

9.4.1  快速排序 229

9.4.2  归并排序 233

9.5  堆排序 237

9.6  基数排序 241

9.6.1  多关键字排序 241

9.6.2  链式基数排序 242

9.7  各种内排序算法的比较 244

9.8  外排序 246

9.8.1  文件的相关概念 247

9.8.2  二路外排序 248

9.8.3  多路归并——选择树 249

习题 252

第10章  查找 254

10.1  查找的基本概念 254

10.2  静态查找表 256

10.2.1  顺序查找 256

10.2.2  二分查找 259

10.2.3  分块查找 262

10.3  动态查找表 265

10.3.1  二叉排序树 265

10.3.2  平衡二叉排序树 271

10.3.3  B树和B+树 274

10.4  哈希表查找 279

10.4.1  何谓哈希表 279

10.4.2  哈希函数的构造方法 280

10.4.3  处理冲突的方法 283

10.4.4  哈希表的查找 285

10.4.5  哈希表的实现 285

10.4.6  哈希表的查找分析 288

习题 289

参考文献 291