本书以C语言为程序设计语言，通过算法、代码、流程图等多种表现形式详细介绍了数据结构的基本概念、逻辑特性和物理特性，对各种结构定义了相应的抽象数据类型，并给出了应用实例。在各章节末尾，还提供了习题供读者练习。
     本书可作为高等院校计算机及相关专业数据结构课程的教材，也可作为计算机应用开发人员的参考书。

     数据结构是计算机及相关专业的一门专业基础课程，也是重要的核心课程之一。通过数据结构课程的学习，学生应掌握各种基本数据结构的类型、存储方式以及它们的基本操作，同时该课程也培养学生利用所学的概念和理论知识，针对实际问题找到简洁适当的数据结构、存储方式和方法的能力。掌握数据结构知识是对程序设计人员最重要也是最基本的要求。
     数据结构一直给人复杂、难懂的印象，初学者往往对基本结构的操作或者实际问题的处理思路不明确，不知如何下手，导致望而却步。为了减少读者学习数据结构时的畏难情绪，本书用尽量浅显易懂的语言描述基本的概念和基础知识，除了用传统的算法描述基本操作以外，对每个章节的重点操作都引入了C语言的代码描述，读者可以通过直接运行代码查看算法运行的结果，了解操作的过程。本书在介绍理论知识的同时，还引入了典型的实际问题，帮助读者了解具体问题如何用所学的理论知识来解决。算法、代码、流程等多种形式的表现，都旨在提高初学者的程序分析和设计能力。每章节后还附有习题，以便读者进一步练习并检验学习效果。
本书由长期从事数据结构课程教学的老师在总结了多年的教学实践经验的基础上编写而成，旨在提高学生的实践动手能力和理论联系实际的能力。本书根据常规课时限定，删去了部分非本科学生必须掌握的内容，并增加了实际应用内容，教师可在实际教学中进行调整。
     本书可作为高等学校计算机及相关专业数据结构课程的教材，也可以作为计算机应用开发人员的参考书。对于计算机及相关专业，可讲授52～64学时，另进行12学时左右的上机练习；对于其他专业，课时可适当压缩，讲授32～48学时。
本书第1、8章由蔺冰编写，第2、4章由王祖俪编写，第3章由吴春旺编写，第5、6、7章由王翔编写，王祖俪负责校阅各章，并对全书统稿、定稿。
由于作者水平有限，加上计算机科学技术发展迅速，书中难免有不妥和遗漏之处，恳请广大读者赐教。

第1章 绪论 1
1.1 什么是数据结构 1
1.1.1 数据结构基本概念 1
1.1.2 数据结构图形表示 2
1.2 什么是算法 3
1.2.1 算法概念 3
1.2.2 算法设计要求 3
1.2.3 算法复杂度 4
1.3 C语言要点回顾 7
1.3.1 基本数据类型 7
1.3.2 其他复合数据类型 8
1.3.3 指针数据类型 10
1.3.4 常用结构及函数 12
习题 15


第2章 线性表 17
2.1 线性表的逻辑结构 17
2.1.1 线性表的概念 17
2.1.2 线性表的抽象数据类型 18
2.2 线性表的顺序结构及基本运算实现 19
2.2.1 线性表的顺序表示 19
2.2.2 顺序表的基本运算 20
2.3 线性表的链式结构及基本运算实现 32
2.3.1 单链表的表示 32
2.3.2 单链表的操作实现 34
2.3.3 单循环链表 44
2.3.4 双向链表 48
2.3.5 静态链表 49
2.4 线性表综合运用 52
2.4.1 一元多项式的加减法 52
2.4.2 约瑟夫环 55
习题 58
第3章 栈和队列 59
3.1 栈的基本概念 59
3.1.1 栈的定义 59
3.1.2 栈的抽象数据类型 60
3.2 栈的表示与实现 60
3.2.1 栈的顺序表示 60
3.2.2 栈的链式表示 63
3.3 栈的应用 65
3.3.1 整数的数制转换 65
3.3.2 判断字符串是否为回文 69
3.4 队列 70
3.4.1 队列的基本定义与抽象数据类型 70
3.4.2 链队列 72
3.4.3 循环队列 80
习题 87


第4章 数组 88
4.1 数组的概念 88
4.2 数组的顺序存储 89
4.3 矩阵的压缩存储 89
4.3.1 对称矩阵 90
4.3.2 稀疏矩阵 91
习题 100


第5章 树 101
5.1 树的相关基本概念 101
5.1.1 树的定义与基本术语 101
5.1.2 树的抽象数据类型定义 103
5.1.3 树的存储结构表示 105
5.2 二叉树 109
5.2.1 二叉树的定义 109
5.2.2 二叉树的性质 112
5.2.3 二叉树的存储结构 114
5.3 二叉树常用操作 117
5.3.1 二叉链表结构下的常用操作 117
5.3.2 顺序存储结构下的常用操作 139
5.3.3 反推二叉树结构 150
5.4 线索二叉树 151
5.4.1 线索二叉树原理 151
5.4.2 线索二叉树的结构实现 152
5.4.3 线索二叉树的遍历 154
5.5 树、森林和二叉树的转换 156
5.5.1 树转换为二叉树 157
5.5.2 森林转换为二叉树 157
5.5.3 二叉树转换为树 158
5.5.4 二叉树转换为森林 158
5.5.5 树和森林的遍历 159
5.6 哈夫曼树及其应用 159
5.6.1 最优二叉树(哈夫曼树)的定义 159
5.6.2 最优二叉树(哈夫曼树)的应用 160
5.6.3 最优二叉树(哈夫曼树)的创建 163
习题 171


第6章 图 174
6.1 图的基本概念 174
6.1.1 图的定义和术语 174
6.1.2 图的抽象数据类型定义 179
6.2 图的存储结构 181
6.2.1 邻接矩阵表示法 181
6.2.2 邻接表/逆邻接表表示法 186
6.2.3 十字链表表示法 190
6.3 图的遍历 192
6.3.1 深度优先遍历 193
6.3.2 广度优先遍历 199
6.4 最小生成树 202
6.4.1 普里姆(Prim)算法 203
6.4.2 克鲁斯卡尔(Kruskal)算法 209
6.5 有向无环图及其应用 215
6.5.1 拓扑排序问题 215
6.5.2 关键路径问题 219
6.6 最短路径 224
习题 230


第7章 查找 233
7.1 查找表及其相关概念 233
7.2 顺序表的查找 235
7.3 有序表的查找 237
7.4 索引表的查找 243
7.5 二叉排序树 245
7.5.1 二叉排序树的查找 246
7.5.2 二叉排序树的插入和创建 248
7.5.3 二叉排序树的删除 250
7.5.4 二叉排序树的总结 257
7.6 平衡二叉树 257
7.6.1 平衡二叉树实现原理 259
7.6.2 平衡二叉树的实现代码 264
7.7 哈希查找 271
7.7.1 哈希查找概述 271
7.7.2 哈希函数的构造方法 273
7.7.3 处理哈希冲突的方法 275
7.7.4 哈希查找的性能分析 279
习题 280


第8章 排序 282
8.1 排序概述 282
8.2 插入排序 282
8.2.1 直接插入排序 282
8.2.2 希尔排序 284
8.3 交换排序 286
8.3.1 冒泡排序 286
8.3.2 快速排序 288
8.4 选择排序 290
8.4.1 简单选择排序 290
8.4.2 堆排序 292
8.5 归并排序 297
8.6 基数排序 299
8.7 排序方法的总结 306
习题 306