本书涵盖了《数据结构》的主要内容，具体介绍了数据结构、算法以及应用，介绍了线性表、栈、队列、串、数组、树和二叉树、图等常用数据结构，讨论了常用的排序技术和查找，给出了具体不同种类的数据结构的应用实例。本书低理论，重实践，重实用，充分考虑了高职高专学生的特点；每章前列出重点和难点，每章后列出知识巩固和实训演练，给学生的学生提供了方向性参考作用；除第1章外，每章基本内容介绍完后，都安排了一节经典的实用实例；本书讲授建议72个课时，理论课36节，实践课36节。本书适用于高职高专院校计算机类专业的学生。

“数据结构”是计算机学科各个专业的一门专业基础课，旨在培养学生在软件设计领域的科学思维方式，以及程序设计能力与程序调试能力。同时，它也是软件设计师认证和计算机专业研究生入学考试的首选课程。该课程的重点是数据的逻辑结构、物理结构及其各种操作的算法实现和应用。但是，由于这门课程自身的特点，学生普遍反映理论难懂，实践复杂。针对这种情况，编者编写了本书，希望能将理论和实践有机结合，帮助学生轻松地掌握数据结构中的主要内容。本书对读者的技术背景要求比较低，比较容易上手，只要学过一门高级编程语言，例如C、C++、Java、C#、VB等，就可以开始阅读本书。
本书的主要特色如下：
1．低理论、重实践、重实用
低理论，用浅显的语言把复杂的理论简单化、通俗化，让学生觉得理论原来这么简单；重实践，描述算法时用已经学过的C语言函数，学生只作简单转换，就能上机调试，验证算法的正确性，并分析算法；重实用，尽可能介绍算法在日常生活中的用途，让学生觉得算法有用，从而提高学习兴趣。
2．经典应用实例
除第1章外，每章基本内容介绍完毕后，都安排了一节经典应用实例。在这一节中，主要安排一些日常生活方面的实例，实例中用到了这一章介绍的数据结构，并详细介绍如何用数据结构的理念解决问题，采取“问题描述—数据结构分析—实体模拟—算法实现”的思路来进行。
3．知识巩固和实训演练
每章结束后，根据该章内容，设置了知识巩固和实训演练。知识巩固主要有加强理解概念的选择题、判断题，还有帮助理解算法思想的简答题。实训演练主要是培养算法设计能力的算法应用题和算法设计题。
4．重点和难点
每章开头列出了本章的重点和难点，给学生的学习提供了方向性参考。
本书由多年来从事数据结构教学的教师编写，是他们集体智慧和经验的结晶。本书由徐新爱、刘日华、胡佳任主编，由赵福生、王洪发、万里勇任副主编，由聂承启主审。全书的统稿由徐新爱完成，参与编写的老师还有黄昌伟、陈江兵、卢昕和吴瑜鹏等。同时，江西师范大学聂承启教授对本书的写作提出了宝贵意见。
本书在编写与出版过程中，得到了编委会和中国铁道出版社的大力支持和帮助，特别是中国铁道出版社的领导和编辑对我们的编写工作给予了大量的指导和帮助，在此向他们表示衷心的感谢！同时，对教材中引用和参考的文献资料的作者一并致谢。
本书建议授课72课时，理论课和实践课各36课时。
在本书编写和实践过程中，编者做了大量的努力，但由于时间紧迫，编者水平有限，书中难免存在不足和疏漏之处，真诚地欢迎各位专家和广大读者提出宝贵的意见和建议。

编 者
2012年8月

第1章 绪论 1
1.1 数据结构概述 1
1.1.1 基本概念 1
1.1.2 数据结构 2
1.2 算法 5
1.2.1 算法的概念 5
1.2.2 算法的描述 7
1.3 算法分析 11
1.3.1 时间复杂度 11
1.3.2 空间复杂度 13
小结 13
知识巩固 13
实训演练 14
第2章 线性表 16
2.1 线性表的定义及操作 16
2.1.1 线性表的定义 16
2.1.2 线性表的操作 17
2.2 线性表运算 17
2.2.1 顺序存储实现 18
2.2.2 链式存储实现 21
2.2.3 循环链表实现 24
2.2.4 双向循环链表 25
2.2.5 顺序表与链表的比较 27
2.3 经典应用实例 28
2.3.1 约瑟夫问题 28
2.3.2 多项式求和 32
小结 37
知识巩固 38
实训演练 39
第3章 栈 41
3.1 栈的定义及基本运算 41
3.1.1 栈的定义 41
3.1.2 栈的基本运算 42
3.2 栈的顺序存储实现 42
3.2.1 栈的顺序存储 42
3.2.2 栈的基本运算在顺序
栈上的实现 43
3.2.3 栈的应用 44
3.3 栈的链式存储实现 45
3.3.1 栈的链式存储 45
3.3.2 栈的基本运算在
链栈上的实现 45
3.4 经典应用实例 46
3.4.1 数制转换 46
3.4.2 表达式求值 48
小结 55
知识巩固 56
实训演练 57
第4章 队列 58
4.1 队列的定义及基本运算 58
4.1.1 队列的定义 58
4.1.2 队列的基本运算 59
4.2 队列的顺序存储实现 59
4.2.1 队列的顺序存储 59
4.2.2 队列的基本运算在
顺序存储上的实现 60
4.2.3 循环队列 60
4.3 队列的链式存储实现 62
4.3.1 队列的链式存储 62
4.3.2 队列的基本运算在
链式存储上的实现 63
4.4 经典应用实例 64
4.4.1 迷宫问题 64
4.4.2 模拟就诊过程 68
小结 72
知识巩固 72
实训演练 74
第5章 串 75
5.1 串的概念与操作 75
5.1.1 串的概念 75
5.1.2 串的操作 76
5.1.3 malloc( )和free( )函数 77
5.2 串的顺序存储结构与运算 78
5.2.1 串的顺序存储结构 78
5.2.2 串的基本运算及算法 78
5.2.3 常用的字符串
处理函数 79
5.3 串的链式存储结构与运算 81
5.3.1 串的链式存储结构 81
5.3.2 串的基本运算 82
5.4 经典应用实例 84
5.4.1 测试串的基本操作 84
5.4.2 模式匹配 91
小结 94
知识巩固 94
实训演练 95
第6章 数组和广义表 97
6.1 数组 97
6.1.1 一维数组 97
6.1.2 二维数组 98
6.1.3 多维数组 99
6.2 矩阵的压缩存储 99
6.2.1 三角矩阵 99
6.2.2 对称矩阵 101
6.2.3 稀疏矩阵 101
6.2.4 带状矩阵 103
6.3 广义表 104
6.3.1 广义表的概念 104
6.3.2 广义表的存储结构 104
6.3.3 广义表的运算 105
6.4 经典应用实例 106
6.4.1 矩阵鞍点 106
6.4.2 稀疏矩阵相加 108
小结 113
知识巩固 113
实训演练 114
第7章 树 115
7.1 树的定义及基本概念 115
7.1.1 树的定义 115
7.1.2 树的基本术语 116
7.1.3 树的存储结构 117
7.2 二叉树 118
7.2.1 二叉树的定义 118
7.2.2 二叉树的性质 118
7.2.3 二叉树的存储结构 120
7.3 二叉树的遍历及算法 122
7.3.1 二叉树的遍历 122
7.3.2 二叉树遍历算法 124
7.4 树、森林与二叉树的转换 125
7.4.1 树转换为二叉树 125
7.4.2 森林转换为二叉树 126
7.4.3 二叉树转换为树 128
7.4.4 二叉树转换为森林 128
7.4.5 树和森林的遍历 129
7.5 哈夫曼树 129
7.5.1 哈夫曼树及其构造 129
7.5.2 哈夫曼树的应用 131
7.6 经典应用实例 133
7.6.1 二叉树的操作 133
7.6.2 信息编码 136
小结 142
知识巩固 142
实训演练 143
第8章 图 145
8.1 基本概念 145
8.1.1 图的实际背景 145
8.1.2 图的定义和术语 146
8.2 图的存储结构 148
8.2.1 图的顺序存储—
邻接矩阵 148
8.2.2 图的链式存储—
邻接表 150
8.3 图的遍历 151
8.3.1 深度优先搜索遍历 151
8.3.2 广度优先搜索遍历 152
8.4 生成树 154
8.4.1 最小生成树 154
8.4.2 最小生成树算法 157
8.5 拓扑排序 159
8.5.1 拓扑排序的概念 159
8.5.2 拓扑序列 160
8.5.3 拓扑排序算法 160
8.6 经典应用实例 161
8.6.1 最短路径 161
8.6.2 教学计划编制 166
小结 169
知识巩固 169
实训演练 170
第9章 内部排序 172
9.1 基本概念 172
9.2 插入排序 173
9.2.1 直接插入排序 174
9.2.2 折半插入排序 175
9.2.3 希尔排序 176
9.3 交换排序 177
9.3.1 冒泡排序 177
9.3.2 快速排序 179
9.4 选择排序 180
9.4.1 直接选择排序 181
9.4.2 堆排序 182

主要著译者顺序姓名学历职称学科专长通讯地址1徐新爱 研究生 工作单位九江学院计算机系教研室主任 邮政编码 电话 2 工作单位 邮政编码 电话 3 工作单位 邮政编码 电话 审校者（主审者） 学历 工作单位 邮政编码 电话 职称 工作单位 邮政编码 电话

本书介绍数据结构，算法及其应用，除第1章外，每章都有一节经典的实用实例，低理论，重实践，重实用．