本书共分12章。主要介绍数据的逻辑结构、存储结构与算法的基本概念，线性表、栈、队列、串、数组和广义表、树和二叉树、图、查找和排序等数据结构典型内容。每章都有一个验证性实验（完成一个相对独立的子系统），用以验证各章教学的重点算法；另外每章还提供一个自主设计的实验，每个实验都有明确的实验目的和实验要求，用以提高学生自主设计程序的能力。最后一章数据结构实验系统开发，提出了系统设计的要求，文件的包含处理以及主控模块的设计。本书以C/C++语言作为算法的描述语言，对于书中各章子系统的实验和一些重要的算法均给出了完整的C/C++语言源程序，并全部在VC++环境上运行通过。

“数据结构”课程是计算机及相关专业的一门重要的专业基础课程。它不仅是计算机程序设计的理论基础，还是学习计算机操作系统原理、编译原理、数据库原理等课程的重要基础。数据结构的主要任务是讨论数据的各种逻辑结构和数据在计算机中的存储表示，以及各种非数值运算算法的实现。通过“数据结构”课程的学习，使学生能使用数据结构的基本分析方法来提高编写程序的能力和应用计算机解决实际问题的能力。本书编写的定位是大学本科和高职高专计算机专业的学生，采用“以应用为目的，以够用为度”的原则，从应用实际的需求出发，大胆取舍，注重实用性。本书对数据结构的概念和原理的阐述通俗易懂，例子翔实，习题丰富，对数据结构基本运算的分析注重其实现过程。对于书中的重要算法均给出了完整的C/C++语言源程序，并全部在VC++环境中运行通过。本书以“数据结构实验演示系统”为主线来组织教材的编写。本书的实践性环节分为验证性实验、自主性设计实验、课程实训和课程设计四个层次。本书前10章每章都有一个验证性实验和一个自主设计实验。每一章的验证性实验构成一个相对独立的子系统，主要用来验证各章教学的重点算法；自主设计实验是要求学生自主设计完成的程序，每个实验都有详细的设计要求；课程实训是把各章验证性实验的子系统组装成一个完整的数据结构实验系统，并在此基础上扩充自主设计实验的算法；课程设计的目的则是为了进一步提高和巩固学生分析问题和解决问题的能力，使编程能力得到有效的巩固和提高。本书内容共分12章，第1章绪论，介绍了数据结构与算法的基本概念；第2章至第5章，介绍了线性表、栈、队列、串等线性结构的逻辑特征、存储方法以及常用算法的实现和基本应用；第6章多维数组和广义表介绍了它们的存储方法以及基本算法；第7章和第8章，介绍了树和图两种非线性数据结构的逻辑特征、存储方法以及相关算法的实现和基本应用；第9章查找，主要介绍了顺序查找、二分查找和二叉排序树的查找方法以及散列存储的基本方法；第10章排序，介绍了在计算机中广泛使用的各种排序方法，并对各种排序算法的优劣进行了分析和比较。各章内容相对独立，自成体系。第11章是数据结构课程实训，让学生设计一个主控模块，用以调用第2章至第10章的9个验证性实验的子系统，完成一个数据结构实验系统的组装。本章的作用是学习文件包含处理的基本方法，让学生在学好数据结构基本算法的同时，建立起系统设计的初步概念。第12章是数据结构课程设计，精选了24个数据结构的典型题目，并按照从易到难的顺序分为A、B、C三个类别。其中A类课题6个，B类课题9个，C类课题9个。每个课题都有明确的设计目的、设计内容和设计要求。学生可以根据自己的学习基础选做适当的课程设计题目。《实用数据结构基础》自2003年8月出版，到2007年6月共印刷了7次。《实用数据结构基础（第二版）》由陈元春修订。第二版自2007年8月出版，至2010年6月也印刷了7次。《实用数据结构基础（第三版）》中王中华编写了第12章；重画了第2章、第4章部分插图；修订和增加了第2章、第4章、第7章部分源代码；增加了8.2.3节的十字链表，充实了8.5节的最短路径，增加了8.6节的有向无环图及其应用，并且增加了部分图表和源代码；充实了9.3.2节的平衡二叉树；修订了第10章堆排序的部分内容。陈元春对第11章内容进行了修改，并改名为“数据结构课程实训”；对各章过渡文字和错误进行了修订，并完成全书的定稿工作。学习本课程的学生应具备C或C++的初步编程能力。使用本教材的总学时建议为72学时，其中实验性课程约占32学时。本书集教材、习题、实验、实训和课程设计于一体，使用本书的学生，一册在手就能方便地进行数据结构课程的理论学习和实验、实训、课程设计等实践性环节的训练。本书配套的电子教案中有几十个数据结构演示动画供读者学习使用。由陈元春、王淮亭合编的《实用数据结构基础学习指导》也由中国铁道出版社出版。该书与本教材密切配合，内容包括：各章要点分析；典型习题分析；各章单元练习解答；自主设计实验指导，以及与教学内容紧密配套的六套模拟试卷。中国铁道出版社编辑参与了本书的审稿和编排工作，在此一并表示感谢！由于作者水平有限，书中疏漏或不妥之处在所难免，恳请广大专家和读者不吝赐教。编 者2010年12月

第1章 绪论1
1.1 什么是数据结构1
1.1.1 从数据结构实验演示系统认识数据结构1
1.1.2 数据结构研究的内容2
1.2 数据的逻辑结构4
1.2.1 基本概念5
1.2.2 逻辑结构的描述6
1.3 数据的存储结构7
1.4 算法和算法分析8
1.4.1 算法特性8
1.4.2 算法的效率9
1.4.3 算法效率的评价10
小结11
验证性实验1：数组、指针、结构体练习12
自主设计实验1：学生成绩分析程序13
单元练习114
第2章 线性表18
2.1 线性表的定义与运算18
2.1.1 线性表的定义18
2.1.2 线性表的基本操作19
2.2 线性表的顺序存储20
2.2.1 顺序表20
2.2.2 顺序表上基本运算的实现21
2.3 线性表的链式存储25
2.3.1 线性链表25
2.3.2 线性链表上基本运算的实现26
2.3.3 循环链表33
2.3.4 双向链表34
小结35
验证性实验2：线性表子系统36
自主设计实验2：多项式求和39
单元练习240
第3章 栈45
3.1 栈的定义和运算45
3.1.1 栈的定义45
3.1.2 栈的运算46
3.2 栈的存储和实现46
3.2.1 顺序栈47
3.2.2 链栈49
3.3 栈的应用举例50
3.3.1 数制转换51
3.3.2 表达式求值52
3.3.3 子程序调用55
3.3.4 递归调用56
3.3.5 中断处理和现场保护57
小结58
验证性实验3：栈子系统58
自主设计实验3：后缀表达式求值63|
单元练习363
第4章 队列67
4.1 队列的定义和运算67
4.1.1 队列的定义67
4.1.2 队列的基本运算68
4.2 队列的存储和实现68
4.2.1 顺序队列68
4.2.2 链队列72
4.3 队列应用举例74
小结76
验证性实验4：队列子系统76
自主设计实验4：循环队列的实现和运算80
单元练习481
第5章 串85
5.1 串的定义和运算85
5.1.1 串的定义85
5.1.2 串的输入与输出86
5.1.3 串的运算87
5.2 串的表示和实现87
5.2.1 定长顺序存储88
5.2.2 链接存储89
5.2.3 串的堆分配存储结构89
5.3 串运算的实现91
小结94
验证性实验5：串子系统95
自主设计实验5：字符串分割处理99
单元练习599
第6章 多维数组和广义表104
6.1 多维数组104
6.1.1 逻辑结构104
6.1.2 存储结构105
6.2 特殊矩阵的压缩存储106
6.2.1 对称矩阵107
6.2.2 三角矩阵108
6.3 稀疏矩阵109
6.3.1 稀疏矩阵的存储109
6.3.2 稀疏矩阵的算法111
6.4 广义表115
6.4.1 广义表的定义和运算115
6.4.2 广义表的首尾存储法117
6.4.3 广义表的算法118
小结120
验证性实验6：稀疏矩阵和广义表子系统120
自主性实验6：稀疏矩阵十字链表的存储127
单元练习6127
第7章 树和二叉树131
7.1 树的定义和术语131
7.1.1 树的定义131
7.1.2 基本术语132
7.2 二叉树133
7.2.1 二叉树的定义133
7.2.2 二叉树的性质134
7.2.3 二叉树的存储135
7.3 遍历二叉树和线索二叉树139
7.3.1 遍历二叉树139
7.3.2 恢复二叉树142
7.3.3 线索二叉树144
7.4 二叉树的转换146
7.4.1 一般树转换为二叉树146
7.4.2 森林转换为二叉树148
7.4.3 二叉树转换为树和森林148
7.5 二叉树的应用149
7.5.1 二叉树的基本应用149
7.5.2 标识符树与表达式151
7.6 哈夫曼树及其应用152
7.6.1 哈夫曼树的引入153
7.6.2 哈夫曼树的建立155
7.6.3 哈夫曼编码157
小结158
验证性实验7：二叉树子系统159
自主设计实验7：标识符树与表达式求值165
单元练习7165
第8章 图171
8.1 图的定义和基本操作171
8.1.1 图的定义171
8.1.2 图的相关术语172
8.1.3 图的基本操作173
8.2 图的存储表示174
8.2.1 邻接矩阵174
8.2.2 邻接表175
8.2.3 十字链表178
8.3 图的遍历180
8.3.1 深度优先搜索180
8.3.2 广度优先搜索181
8.4 图的连通性183
8.4.1 无向图的连通分量和生成树183
8.4.2 最小生成树184
8.5 最短路径186
8.6 有向无环图及其应用189
8.6.1 拓扑排序189
8.6.2 关键路径190
小结193
验证性实验8：图子系统194
自主设计实验8：最小生成树198
单元练习8198
第9章 查找203
9.1 查找的基本概念203
9.2 静态查找表204
9.2.1 顺序查找205
9.2.2 二分查找206
9.2.3 分块查找209
9.3 动态查找表210
9.3.1 二叉排序树210
9.3.2 平衡二叉树215
9.4 哈希表218
9.4.1 哈希表与哈希方法218
9.4.2 哈希函数的构造方法219
9.4.3 处理冲突的方法220
小结222
验证性实验9：查找子系统223
自主设计实验9：哈希查找228
单元练习9229
第10章 排序233
10.1 概述233
10.2 插入排序234
10.2.1 直接插入排序234
10.2.2 二分插入排序236
10.2.3 希尔排序237
10.3 快速排序法238
10.3.1 冒泡排序239
10.3.2 快速排序240
10.4 选择排序243
10.4.1 简单选择排序243
10.4.2 树形选择排序244
10.4.3 堆排序245
10.5 归并排序247
10.6 各种排序方法的比较249
小结249
验证性实验10：排序子系统250
自主设计实验10：双向冒泡排序257
单元练习10258
第11章 数据结构课程实训262
11.1 系统设计的要求262
11.1.1 系统总体结构设计263
11.1.2 系统详细设计264
11.1.3 系统调试和维护266
11.2 文件的包含处理267
11.2.1 什么是文件包含267
11.2.2 如何对“数据结构实验系统”进行文件包含269
11.2.3 数据结构实验系统主控模块269
11.3 数据结构课程实训任务书270
第12章 数据结构课程设计272
12.1 课程设计的目的与内容272
12.1.1 课程设计的目的272
12.1.2 课程设计的内容273
12.1.3 课程设计报告273
12.1.4 课程设计的考核274
12.2 课程设计的要求275
12.3 A类题目276
12.3.1 课题A1：多项式运算276
12.3.2 课题A2：求最小生成树（基于邻接矩阵存储）277
12.3.3 课题A3：非递归求解Hanoi问题278
12.3.4 课题A4：迷宫问题279
12.3.5 课题A5：中缀表达式转后缀并求值（运算对象为个位数）280
12.3.6 课题A6：二叉树的层次遍历281
12.4 B类题目282
12.4.1 课题B1：哈希查找的实现与分析282
12.4.2 课题B2：有向无环图的判定及拓扑排序284
12.4.3 课题B3：浮点数的IEEE 754标准格式转换285
12.4.4 课题B4：文件记录读取并排序286
12.4.5 课题B5：大整数运算286
12.4.6 课题B6：平衡二叉树的构造及输出286
12.4.7 课题B7：二叉树的中序线索化及其非栈非递归遍历287
12.4.8 课题B8：稀疏矩阵的运算288
12.4.9 课题B9：基于十字链表有向图的遍历289
12.5 C类题目290
12.5.1 课题C1：求AOE网的关键路径291
12.5.2 课题C2：求有向图的强连通分量292
12.5.3 课题C3：非递归方式遍历二叉树292
12.5.4 课题C4：求最小生成树（基于邻接表存储结构）293
12.5.5 课题C5：Dijkstra算法求最短路径293
12.5.6 课题C6：拼写检查器294
12.5.7 课题C7：中缀表达式转后缀并求值（运算对象为多位数）295
12.5.8 课题C8：哈夫曼编码器296
12.5.9 课题C9：马对棋盘方格的遍历及其复杂性分析298
参考文献300

主要著译者顺序姓名学历职称学科专长通讯地址1陈元春 本科 副教授数据结构、计算机基础工作单位上海机电学院 邮政编码 201100电话15800988923 2 工作单位 邮政编码 电话 3 工作单位 邮政编码 电话 审校者（主审者） 学历 工作单位 邮政编码 电话 职称 工作单位 邮政编码 电话

应用性特别强，案例翔实。本书对数据结构的概念和原理的阐述通俗易懂，例子翔实；对习题的选择，难易适当，题型丰富；对数据结构基本运算的分析，注重其实现的过程。