本书对数据结构的概念和原理进行了阐述，对数据结构的基本运算进行了分析，并给出了详细的实现过程。全书共分11章，内容包括：绪论、线性表、栈、队列、串、多维数组和广义表、树和二叉树、图、查找、排序、数据结构课程设计等，并在附录部分介绍了数据结构实验系统的组装。
本书集教学内容、习题、实验和课程设计于一体，书中的重要算法均给出了完整的C/C++语言源程序，并全部在VC++环境中运行通过，一书在手就能方便地进行“数据结构”课程的理论学习和实验、课程设计等实践性环节的训练。
本书适合作为高等院校计算机类专业数据结构课程的教材，也可以作为成人教育、自学考试和从事计算机应用的工程技术人员的参考用书。

《实用数据结构基础（第四版）》是在第三版的基础上修订的，修订以后的教材共有11章教学内容和一个附录组成。
第1章绪论，介绍了数据结构与算法的基本概念；第2章至第5章，介绍了线性表、栈、队列、串等线性结构的逻辑特征、存储方法以及常用算法的实现和基本应用；第6章多维数组和广义表介绍了它们的存储方法以及基本算法；第7章和第8章，介绍了树和图两种非线性数据结构的逻辑特征、存储方法以及相关算法的实现和基本应用；第9章查找，主要介绍了顺序查找、二分查找和二叉排序树的查找方法以及散列存储的基本方法；第10章排序，介绍了在计算机中广泛使用的各种排序方法，并对各种排序算法的优劣进行了分析和比较。各章内容相对独立，自成体系。
第11章是数据结构课程设计，精选了28个数据结构的典型题目。每个课题都有明确的设计目的、设计内容和设计要求，学生可以根据自己的学习基础选做适当的课题。
附录部分是指导学生设计一个主控模块，以调用第2章至第10章的9个验证性实验的子系统，完成一个数据结构实验系统的组装。其作用是学习文件包含处理的基本方法，让学生在学好数据结构基本算法的同时，建立起系统设计的初步概念。
本次改版，除了对各章的内容做了一些修订，重点修改了以下三个方面的内容：
（1）对各章的习题（主要包括判断题、填空题、选择题、编程题）进行了全面的修改和充实。
（2）对原书第12章进行了改写，并变成了第11章数据结构课程设计。
（3）对原书第11章进行了全面压缩，并使之变成了一个附录：数据结构实验系统的组装。
《实用数据结构基础》自2003年8月出版，到2015年5月共印刷了17次。本次改版的第1到第10章，以及附录部分由陈元春修订，第11章由王中华修订，全书由陈元春定稿。
学习本课程的学生应具备C或C++的初步编程能力。使用本教材的总学时建议为72学时，其中实验性课程约占32学时。
本书集教材、习题、实验和课程设计于一体，使用本书的学生，一册在手就能方便地进行数据结构课程的理论学习和实验、课程设计等实践性环节的训练。本书配套的电子教案中有几十个数据结构演示动画供读者学习使用。
由陈元春、王淮亭、王中华合编的《实用数据结构基础学习指导》也由中国铁道出版社重新修订出版。该书与本教材密切配合，内容包括：各章要点分析；典型习题分析；各章单元练习解答；自主设计实验指导；模拟试卷及参考解答；课程设计报告样例。
中国铁道出版社编辑参与了本书的审稿和编排工作，在此一并表示感谢！
由于作者水平有限，书中疏漏或不妥之处在所难免，恳请广大专家和读者不吝赐教。


编 者
2015年5月

1.1 什么是数据结构.......................................................................................... 1
1.1.1 从数据结构实验演示系统认识数据结构.......................................... 1
1.1.2 数据结构研究的内容........................................................................ 2
1.2 数据的逻辑结构.......................................................................................... 5
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
实验...................................................................................................................12
验证性实验1 数组、指针、结构体练习...................................................12
自主设计实验1 学生成绩分析程序...........................................................14
习题1.................................................................................................................14
第 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
实验...................................................................................................................36
验证性实验2 线性表子系统......................................................................36
自主设计实验2 多项式求和......................................................................39
实用数据结构基础 第四版
2
习题2.................................................................................................................40
第 3 章栈 .......................................................................................................... 46
3.1 栈的定义和运算.........................................................................................46
3.1.1 栈的定义和特性..............................................................................46
3.1.2 栈的运算.........................................................................................47
3.2 栈的存储和实现.........................................................................................47
3.2.1 顺序栈.............................................................................................47
3.2.2 链栈................................................................................................50
3.3 栈的应用举例.............................................................................................51
3.3.1 数制转换.........................................................................................52
3.3.2 表达式求值.....................................................................................53
3.3.3 子程序调用.....................................................................................56
3.3.4 递归调用.........................................................................................57
3.3.5 中断处理和现场保护.......................................................................58
小结...................................................................................................................59
实验...................................................................................................................59
验证性实验3 栈子系统.............................................................................59
自主设计实验3 后缀表达式求值..............................................................63
习题3.................................................................................................................64
第 4 章队列....................................................................................................... 68
4.1 队列的定义和运算......................................................................................68
4.1.1 队列的定义和特性..........................................................................68
4.1.2 队列的基本运算..............................................................................69
4.2 队列的存储和实现......................................................................................69
4.2.1 顺序队列.........................................................................................69
4.2.2 链队列.............................................................................................73
4.3 队列应用举例.............................................................................................75
小结...................................................................................................................77
实验...................................................................................................................77
验证性实验4 队列子系统..........................................................................77
自主设计实验4 循环队列的实现和运算...................................................81
习题4.................................................................................................................81
第 5 章串 .......................................................................................................... 86
5.1 串的定义和运算.........................................................................................86
5.1.1 串的定义.........................................................................................86
5.1.2 串的输入与输出..............................................................................87
5.1.3 串的运算.........................................................................................88
目 录
3
5.2 串的表示和实现.........................................................................................88
5.2.1 定长顺序存储..................................................................................88
5.2.2 链接存储.........................................................................................89
5.2.3 串的堆分配存储结构.......................................................................90
5.3 串运算的实现.............................................................................................91
小结...................................................................................................................95
实验...................................................................................................................95
验证性实验5 串子系统.............................................................................95
自主设计实验5 字符串分割处理..............................................................99
习题5...............................................................................................................100
第 6 章多维数组和广义表................................................................................ 105
6.1 多维数组..................................................................................................105
6.1.1 逻辑结构.......................................................................................105
6.1.2 存储结构.......................................................................................105
6.2 特殊矩阵的压缩存储................................................................................107
6.2.1 对称矩阵.......................................................................................108
6.2.2 三角矩阵.......................................................................................108
6.3 稀疏矩阵..................................................................................................110
6.3.1 稀疏矩阵的存储............................................................................110
6.3.2 稀疏矩阵的算法............................................................................113
6.4 广义表......................................................................................................116
6.4.1 广义表的定义和运算.....................................................................116
6.4.2 广义表的首尾存储法.....................................................................118
6.4.3 广义表的算法................................................................................119
小结.................................................................................................................121
实验.................................................................................................................121
验证性实验6 稀疏矩阵和广义表子系统.................................................121
自主设计实验6 稀疏矩阵十字链表的存储..............................................128
习题6...............................................................................................................128
第 7 章树和二叉树.......................................................................................... 132
7.1 树的定义和术语.......................................................................................132
7.1.1 树的定义及表示法........................................................................132
7.1.2 基本术语.......................................................................................133
7.2 二叉树......................................................................................................134
7.2.1 二叉树的定义................................................................................134
7.2.2 二叉树的性质................................................................................135
7.2.3 二叉树的存储................................................................................136
7.3 遍历二叉树和线索二叉树.........................................................................140
7.3.1 遍历二叉树...................................................................................140
实用数据结构基础 第四版
4
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 二叉树的应用...........................................................................................150
7.5.1 二叉树的基本应用........................................................................150
7.5.2 标识符树与表达式........................................................................151
7.6 哈夫曼树及其应用....................................................................................153
7.6.1 哈夫曼树的引入............................................................................153
7.6.2 哈夫曼树的建立............................................................................155
7.6.3 哈夫曼编码...................................................................................157
小结.................................................................................................................158
实验.................................................................................................................159
验证性实验7 二叉树子系统....................................................................159
自主设计实验7 标识符树与表达式求值.................................................165
习题7...............................................................................................................166
第 8 章图 ........................................................................................................ 172
8.1 图的定义和基本操作................................................................................172
8.1.1 图的定义.......................................................................................172
8.1.2 图的相关术语................................................................................173
8.1.3 图的基本操作................................................................................175
8.2 图的存储表示...........................................................................................175
8.2.1 邻接矩阵.......................................................................................175
8.2.2 邻接表...........................................................................................177
8.2.3 十字链表.......................................................................................179
8.3 图的遍历..................................................................................................181
8.3.1 深度优先搜索................................................................................181
8.3.2 广度优先搜索................................................................................182
8.4 图的连通性...............................................................................................183
8.4.1 无向图的连通分量和生成树.........................................................183
8.4.2 最小生成树...................................................................................185
8.5 最短路径..................................................................................................187
8.6 有向无环图及其应用................................................................................189
8.6.1 拓扑排序.......................................................................................190
8.6.2 关键路径.......................................................................................191
小结.................................................................................................................193
实验.................................................................................................................194
验证性实验8 图子系统...........................................................................194
自主设计实验8 最小生成树....................................................................198
目 录
5
习题8...............................................................................................................199
第 9 章查找..................................................................................................... 203
9.1 查找的基本概念.......................................................................................203
9.2 静态查找表...............................................................................................204
9.2.1 顺序查找.......................................................................................204
9.2.2 二分查找.......................................................................................206
9.2.3 分块查找.......................................................................................209
9.3 动态查找表...............................................................................................209
9.3.1 二叉排序树...................................................................................209
9.3.2 平衡二叉树...................................................................................214
9.4 哈希表......................................................................................................217
9.4.1 哈希表与哈希方法........................................................................217
9.4.2 哈希函数的构造方法.....................................................................218
9.4.3 处理冲突的方法............................................................................219
小结.................................................................................................................221
实验.................................................................................................................221
验证性实验9 查找子系统........................................................................221
自主设计实验9 哈希查找........................................................................226
习题9...............................................................................................................227
第 10 章排序................................................................................................... 231
10.1 概述........................................................................................................231
10.2 插入排序................................................................................................232
10.2.1 直接插入排序..............................................................................232
10.2.2 二分插入排序..............................................................................234
10.2.3 希尔排序.....................................................................................235
10.3 快速排序法.............................................................................................236
10.3.1 冒泡排序.....................................................................................236
10.3.2 快速排序.....................................................................................238
10.4 选择排序................................................................................................240
10.4.1 简单选择排序..............................................................................241
10.4.2 树形选择排序..............................................................................242
10.4.3 堆排序.........................................................................................243
10.5 归并排序................................................................................................245
10.6 各种排序方法的比较..............................................................................246
小结.................................................................................................................247
实验.................................................................................................................247
验证性实验10 排序子系统......................................................................247
自主设计实验10 双向冒泡排序..............................................................254
习题10 .............................................................................................................254
实用数据结构基础 第四版
6
第 11 章数据结构课程设计.............................................................................. 259
11.1 课程设计的目的与内容..........................................................................259
11.1.1 课程设计的目的..........................................................................259
11.1.2 课程设计的内容..........................................................................260
11.1.3 课程设计报告..............................................................................260
11.1.4 课程设计的考核..........................................................................261
11.2 课程设计的要求.....................................................................................262
11.3 课程设计题目.........................................................................................263
课题1 多项式运算...................................................................................263
课题2 浮点数的IEEE 754标准格式转换................................................264
课题3 稀疏矩阵的运算...........................................................................264
课题4 非递归求解Hanoi问题................................................................266
课题5 迷宫问题......................................................................................268
课题6 非递归方式遍历二叉树................................................................268
课题7 中缀表达式转后缀并求值............................................................269
课题8 求字符串中最大长度的对称子串.................................................270
课题9 二叉树的中序线索化及其非栈非递归遍历...................................271
课题10 求二叉树中任意两个结点间的距离............................................271
课题11 把二叉排序树转换成有序的双向链表........................................272
课题12 在二叉树中找出和为某一值的所有路径.....................................272
课题13 判断整数序列是否为二叉排序树的后序遍历序列......................273
课题14 有向无环图的判定及拓扑排序...................................................273
课题15 求AOE网的关键路径................................................................274
课题16 求有向图的强连通分量..............................................................275
课题17 基于十字链表有向图的遍历.......................................................276
课题18 求最小生成树.............................................................................277
课题19 Dijkstra算法求最短路径............................................................278
课题20 双拼输入法的快速定位..............................................................278
课题21 连通问题....................................................................................279
课题22 哈希查找的实现与分析..............................................................281
课题23 文件记录读取并排序..................................................................282
课题24 平衡二叉树的构造及输出...........................................................283
课题25 马对棋盘方格的遍历..................................................................283
课题26 求两个字符串的扩展距离...........................................................285
课题27 求汽车最少加油次数问题...........................................................285
课题28 大整数运算.................................................................................286
附录 A数据结构实验系统的组装...................................................................... 287
参考文献............................................................................................................ 292

陈元春：男，1949年生， 上海市人，曾任职于上海电机学院电子信息学院副教授，教学督导，现已退休，从事高等教学工作近30年,先后担任近二十门高等教学课程的授课工作,编写过多种教材和教学参考书,五次被评为上海市机电一局(现电器集团公司)优秀教育工作者和先进工作者。