本书前半部分以案例驱动的方式引入每种数据结构，描述了每种数据结构的定义、抽象数据类型、存储结构和相关算法及应用；后半部分主要讨论查找和排序的各种实现方法及其综合分析比较。本书采用C++作为数据结构和算法的描述语言，对于某种存储方式下的数据结构建立相应的类，类中成员函数就是对这种数据结构的操作，不涉及太多C++语言语法知识。

“数据结构”是一门研究计算机的操作对象、操作对象之间关系和操作对象的操作的学科，是介于数学、计算机硬件和计算机软件三者之间的一门核心课程，属于计算机学科中的一门综合性专业基础课程。它不仅是一般程序设计的基础，而且是设计和实现编译程序、操作系统、数据库系统及其他系统程序和大型应用程序的重要基础。
本书主要介绍线性表、栈、队列、串、广义表和数组、树和二叉树、图等基本数据结构及其应用，以及查找和排序的原理与方法。通过本课程的学习，学生能较熟练地掌握数据结构的基本概念、特性、存储结构及相关算法；熟悉它们在计算机科学中最基本的应用；培养和训练运用高级程序设计语言编写结构清晰、可读性好的算法及初步评价算法的能力；为后续课程的学习，以及计算机软件的研制和开发打下一定的理论基础及实践基础。
本书具有以下特色：
1．案例驱动。在介绍每一种数据结构前，采用案例引入的方式，确定该案例中用到的数据结构，分析案例中对这个数据结构需要进行哪些操作，怎样把现实中的例子转换成抽象的数据结构，并且实现这样的操作，给出大致的实现过程。案例取自现实生活，旨在一开始就引起学生的兴趣，避免在学习过程中理论与实际脱节。
2．“案例引入—数据结构—案例实现”层次清晰。书中第1章绪论比较特殊，第9章和第10章是两种不同操作，也比较特殊。除了这3章外，每一章都讨论一种数据结构，首先引入案例，通过对案例的分析引出相关数据结构的定义、术语、存储结构等知识，这些知识介绍完毕后，再讨论如何实现这个案例。这样组织章节内容，旨在既使学生学到理论知识，又使学生了解这种数据结构的应用实例。
3．C++描述。全书使用面向对象的C++语言描述数据结构和算法，特点是不涉及太多C++语言方面的知识，尽可能少地使用C++的特性。实现每一种数据结构时，首先考虑这种结构用什么存储方式存储。只需创建一个类，在类中定义私有成员和公有函数。公有函数就是这种结构对应的各种操作。实现该结构时，只需定义一个类变量，然后访问这个类变量的成员函数即可。将重点放在如何分析每种算法的思想和复杂度上，了解C++的读者只要了解了算法思想，也一定会灵活运用C++语言实现这样的算法。
本书编者于2009年将“数据结构”建设为校级精品课程，在课程网站上提供了丰富的教学资源。2012年成功申请内蒙古自治区精品课程。
本书适合作为普通高等院校计算机相关专业本科、专科教材，也可以作为研究生入学考试和各类认证证书考试的复习参考书，还可供计算机应用工程技术人员学习参考。
本书由付学良、李宏慧任主编，由董改芳、亢汇涓任副主编。其中第8章由付学良编写，第5章由李宏慧编写，第1、10章由亢汇涓编写，第7章由董改芳编写，第2章由杨婷编写，第3、4章由王艳芬编写，第6、9章由扈华编写。全书由付学良统稿。
由于编者知识水平有限，加上时间仓促，书中难免有不妥与疏漏之处，恳请专家和读者批评指正。
编者
2012年3月

第1章 绪论 1
1.1 引言 1
1.2 数据结构的主要概念与术语 2
1.3 抽象数据类型的概念与描述 4
1.3.1 基本数据类型的概念 4
1.3.2 抽象数据类型 5
1.4 算法的度量 8
1.4.1 算法的定义 8
1.4.2 算法效率的度量 9
1.5 面向对象C++描述工具简介 11
1.5.1 函数的定义格式 11
1.5.2 函数模板 11
1.5.3 类的定义 12
小结 16
习题 17
第2章 线性表 18
2.1 案例引入及分析 18
2.1.1 学生基本信息管理 18
2.1.2 线性表的定义 18
2.1.3 线性表的存储结构 20
2.2 学生基本信息管理之顺序表的实现 22
2.2.1 学生基本信息管理之顺序表类定义 22
2.2.2 学生基本信息管理之顺序表操作实现 23
2.2.3 学生基本信息管理之顺序表的主程序的实现 28
2.2.4 顺序表的其他操作 30
2.3 学生基本信息管理之单链表实现 31
2.3.1 学生基本信息管理之单链表类定义 32
2.3.2 学生基本信息管理之单链表操作实现 32
2.3.3 学生基本信息管理之单链表的主程序的实现 40
2.3.4 单链表的其他操作 42
2.4 算法分析 44
2.5 循环链表和双向链表 46
2.5.1 循环链表 46
2.5.2 双向链表 47
2.5.3 双向链表的类定义 47
2.6 静态链表 51
2.7 顺序结构与链表结构的比较 54
小结 54
习题 55
第3章 堆栈 58
3.1 案例引入及分析 58
3.1.1 提交批改作业 58
3.1.2 堆栈的定义 58
3.1.3 堆栈的存储结构 59
3.2 提交批改作业的顺序实现 64
3.3 提交批改作业的链式实现 65
3.4 算法分析 67
3.5 堆栈的其他应用 67
3.5.1 堆栈与递归的实现 67
3.5.2 表达式求值 69
3.5.3 背包问题 72
小结 75
习题 75
第4章队列 77
4.1 案例的引入及分析 77
4.1.1 看病排队候诊 77
4.1.2 队列的定义 77
4.1.3 队列的存储结构 78
4.2 看病排队候诊的顺序实现 83
4.3 看病排队候诊的链式实现 85
4.4 算法分析 87
4.5 队列的其他应用 87
4.5.1 二进制数转换为十进制数 87
4.5.2 十进制数转换为二进制数 88
小结 89
习题 90
第5章 串 91
5.1 案例引入及分析 91
5.1.1 大整数计算器 91
5.1.2 串的定义 91
5.1.3 串的存储结构 93
5.2 大整数计算器的顺序实现 97
5.3 大整数计算器的链式实现 99
5.4 算法分析 101
5.5 串的其他应用 101
5.5.1 简单模式匹配 101
5.5.2 KMP模式匹配 102
小结 106
习题 106
第6章 广义表和数组 108
6.1 案例引入及分析 108
6.1.1 本科生导师制问题 108
6.1.2 广义表的定义 108
6.1.3 广义表的存储结构 110
6.2 本科生导师制问题的实现 111
6.2.1 实现内容 111
6.2.2 实现过程 112
6.3 数组 120
6.3.1 数组的定义 120
6.3.2 数组的存储结构 122
6.4 矩阵的压缩存储 123
6.4.1 特殊矩阵的压缩存储 123
6.4.2 稀疏矩阵的压缩存储 124
小结 136
习题 136
第7章 树和二叉树 139
7.1 案例引入及分析 139
7.1.1 家谱管理 139
7.1.2 树和二叉树的定义 140
7.1.3 树和二叉树的存储结构 144
7.1.4 树与二叉树的转换 149
7.1.5 森林与二叉树的转换 151
7.1.6 树与森林的遍历 151
7.2 家谱管理的实现 152
7.3 遍历二叉树 154
7.3.1 前序遍历 154
7.3.2 中序遍历 155
7.3.3 后序遍历 156
7.3.4 按层次遍历 156
7.4 线索二叉树 157
7.5 树的其他应用——哈夫曼树及编码 161
7.5.1 哈夫曼树 161
7.5.2 哈夫曼编码 162
小结 163
习题 164
第8章 图 165
8.1 图的基本概念与术语 165
8.1.1 图的基本概念 165
8.1.2 图的基本术语 166
8.1.3 抽象数据类型 169
8.2 图的存储结构 171
8.2.1 邻接矩阵 171
8.2.2 邻接表 173
8.2.3 双链式存储结构 174
8.3 图的ADT设计与实现 179
8.4 图的遍历 180
8.4.1 深度优先搜索 181
8.4.2 广度优先搜索 183
8.5 图的连通性 184
8.5.1 无向图的连通分量和生成树 184
8.5.2 有向图的强连通分量 185
8.5.3 最小生成树 186
8.6 最短路径 192
8.6.1 单源最短路径 192
8.6.2 任意顶点间的最短路径 196
8.7 有向无环图及其应用 196
8.7.1 拓扑排序 196
8.7.2 关键路径 199
小结 202
习题 202
第9章 查找 207
9.1 查找的基本概念 207
9.2 静态查找表 208
9.2.1 顺序查找表 209
9.2.2 有序表的查找 209
9.2.3 静态索引顺序表的查找 212
9.3 动态查找表 213
9.3.1 二叉排序树和平衡二叉树 214
9.3.2 B-树和B+树 226
9.4 哈希表 233
9.4.1 哈希表与哈希函数 233
9.4.2 哈希函数的构造方法 234
9.4.3 解决冲突的方法 236
9.4.4 哈希表的查找及其效率分析 239
小结 241
习题 242
第10章 排序 245
10.1 排序的基本概念 245
10.2 插入排序 246
10.2.1 直接插入排序 246
10.2.2 折半插入排序 247
10.2.3 2--路插入排序 249
10.2.4 表插入排序 250
10.2.5 希尔排序 251
10.3 交换排序 252
10.3.1 冒泡排序 252
10.3.2 快速排序 253
10.4 选择排序 256
10.4.1 简单选择排序 256
10.4.2 堆排序 257
10.5 二路归并排序 259
10.6 基数排序 260
10.6.1 多关键字排序 260
10.6.2 链式基数排序 260
10.6.3 各种排序方法的比较 265
小结 266
习题 266

主要著译者顺序姓名学历职称学科专长通讯地址1 付学良 博士 教授数据结构 工作单位内蒙古农业大学 邮政编码 电话15947617598 2 工作单位 邮政编码 电话 3 工作单位 邮政编码 电话 审校者（主审者） 学历 工作单位 邮政编码 电话 职称 工作单位 邮政编码 电话

采用案例引入的方式，通过分析案例，确定该案例中用到的数据结构就是本章所讲