本书以线性表、树、图为中轴，以逻辑结构、物理结构、基本算法和应用实例为路线，合理架构教材体系；以基础知识、基本思想和基本方法为准绳，选择和组织教材内容；以结构设计、算法设计和应用设计为中心，鲜明突出教材重点。因此本书的特点是，内容上侧重基础，侧重常用；技术上突出应用，强化实践，注重能力；表述上由浅入深、由简到繁、由易到难；文字上深入浅出，文句流畅，文图兼施。

“数据结构”是计算机专业的重要基础课程。说它重要，是因为数据结构是计算机的灵魂和精髓；说它基础，是因为从计算机硬件设计到软件运行都以数据结构及其算法为其核心。瑞士计算机科学家尼•沃思提出的著名公式“数据结构+算法=程序”，以及他的经典论述“计算机科学就是研究算法的学问”充分说明了这个道理。
说到课程，其主体是教材和教学过程。教材是教学内容的规范；教学过程是授体（教师）向受体（学生）展示内容的延续进程。一本优秀的教材和一位优秀的教师是保证课程教学成功的关键要素。教材必须具有适合特定受体的架构体系、实现课程目标的知识内容、深化技能掌握的实践活动，以及激发受体想象力和创造力的空间。教材只具有一般性品格；而一位经验丰富的优秀教师会针对面向的受体把教材体现于课程教学大纲。课程教学大纲是授体向受体传输课程内容的管道和实现课程教学过程的路线图。因此，课程教学大纲与所依据教材的结合才是一次教学过程的纲领。
本书是一本以普通高等院校计算机专业学生为受体的“数据结构”课程教材，它与研究专著或论文汇集有本质的区别。任何一种教材都要与教学对象所属层次、培养目标、认知能力密切相关，而不能包罗万象。只有有针对性的教材才是有生命力的教材。鉴于此，在编写本书时，编者树立“以线性表、树和图为中轴，以逻辑结构、物理结构、基本算法和常见应用为路线”科学架构教材体系的理念，确立“以基础知识为中心、以基本要素为重点”合理规划教材内容的原则，采用“删繁就简、突出重点、深入浅出、循序渐进、图文兼施”的表述手法，力图使教材具有鲜明的特色。
首先，本书设计了三纵四横的教材体系，紧扣线性表、树和图这3种基本数据结构，并把相关知识（如排序和查找等）按处理方式分派捆绑到相应结构中，而不单独设章。对每种数据结构都按“逻辑结构、物理结构、基本算法、应用举例”的路线，分层次、由表及里、由浅入深地展开知识内容和技术要领。对出现的算法问题都按“函数标识、操作含义、算法思路、算法描述、算法评说”的顺序进行细致介绍、引导分析、实际设计，最后给出算法描述实体，并对其作画龙点睛的评价。在应用问题部分还配有实例演示，以体现数据结构与算法设计的实践意义。这样做的好处是条理清楚、分析透彻、有示范性。
其次，以基础知识、基本要素为基点选择教材内容，侧重常用数据结构问题。遵循“伤其十指不如断其一指”原则，侧重逻辑结构概念，突出物理设计与算法设计，强调基础知识和基本方法介绍，以保证学生初步建立起数据结构逻辑思维方式，掌握常用数据结构问题及其设计能力，为其进一步深化学习、扩展研究和创新思维提供必备的基础。
第三，强化实践，注重能力，特别着重于算法设计过程的分析。在设计算法时注意设计方法的选择和思路，注意数据结构基本运算的优先调用。书中还给出了一些可运行的实例程序，供学生学习、验证、实验与模仿，希望学生能借助实例举一反三。更多算法的C语言程序留给学生自己在任课教师指导下设计、编码和调试。每章末都配备了丰富的、多种题型的习题，供学生复习或检验学习效果。
第四，在全书的表述上注意做到运词准确、文句流畅、文图并茂、通俗易懂，以期达到 “一看就懂，一学就会，一练就通”的目的。
全书共分7章：第1章 绪论，介绍数据结构的基本概念，作为学习数据结构的知识铺垫；第2章 线性表，介绍一般线性表结构；第3章 受限的线性表和第4章 推广的线性表，介绍栈、队列、串、数组、矩阵存储和广义表；第5章 树与二叉树，重点介绍二叉树及其应用；第6章图，介绍图的存储结构和几个常见应用的算法；第7章 散列，介绍线性表的散列存储结构。
本书适合作为普通高等学校计算机专业及计算机相关专业数据结构课程教材，也可作为计算机应用系统开发人员及相关人员的学习参考书或培训教材。
根据不同教学层次和课程目标，建议安排48或64学时授课时间，外加16学时的实习。
本书由史九林编著。南京大学徐洁磐教授审阅了全书并跟踪了本书写作的全过程，提出了许多宝贵建议和独到见解；陶静老师协助调试了书中部分C语言程序；在此一并表示感谢。
由于时间仓促，编者水平有限，书中疏漏和不足之处在所难免，恳请读者批评指正。编者电子邮箱：jlshi@nju.edu.cn。
编 者
2012年9月

第1章 绪论 1
1.1 一个简单的数据结构问题 1
1.2 数据结构概述 2
1.2.1 数据与数据对象 2
1.2.2 数据元素与数据类型 3
1.2.3 数据的逻辑结构 6
1.2.4 数据的物理结构 8
1.2.5 数据结构的基本运算 15
1.2.6 数据结构的定义 16
1.3 算法 17
1.3.1 算法的定义 18
1.3.2 对算法的基本要求 18
1.3.3 如何设计一个算法 19
1.3.4 怎样描述一个算法 21
1.3.5 从算法到程序 23
1.4 浅谈算法分析 24
1.4.1 一个好的算法 24
1.4.2 算法的效率分析 25
1.5 数据结构应用价值 27
1.6 怎样学好数据结构 28
小结 29
习题 30
第2章 线性表 32
2.1 一个教务员的一天 32
2.2 线性表的基本概念 34
2.2.1 线性表的定义 34
2.2.2 线性表上的基本运算 35
2.3 线性表的顺序结构 36
2.3.1 顺序表 36
2.3.2 线性表基本运算在顺序表上的实现算法 37
2.3.3 建立一个顺序表 42
2.4 线性表的链式结构 43
2.4.1 单向链表 43
2.4.2 线性表基本运算在单向链表上的实现算法 45
2.4.3 建立一个单向链表 51
2.4.4 循环链表 53
2.4.5 双向链表 54
2.5 线性表的应用及其算法设计 56
2.5.1 数据查重 56
2.5.2 有序表的归并 59
2.6 基于线性表的查找 63
2.6.1 查找的定义 64
2.6.2 顺序查找算法 64
2.7 基于线性表的排序 68
2.7.1 排序的定义 69
2.7.2 简单排序算法 71
2.8 给教务员的一个解答 77
小结 80
习题 82
第3章 受限的线性表——栈、队列和串 85
3.1 栈 85
3.1.1 几个栈结构实例 86
3.1.2 栈的定义及其基本运算 87
3.1.3 顺序栈及其基本运算的实现算法 88
3.1.4 链栈及其基本运算的实现算法 91
3.1.5 栈结构的应用实例 93
3.2 队列 99
3.2.1 队列的定义及其基本运算 100
3.2.2 顺序队列及其基本运算的实现算法 100
3.2.3 循环队列及其基本运算的实现算法 103
3.2.4 链队列及其基本运算的实现算法 105
3.2.5 队列结构的应用实例 108
3.3 串 113
3.3.1 串的定义及其基本运算 114
3.3.2 串的顺序存储结构及其基本运算算法 115
3.3.3 串表达式 120
3.3.4 串匹配 121
3.3.5 串的应用 127
小结 129
习题 130
第4章 推广的线性表——数组和广义表 133
4.1 数组 133
4.1.1 数组的定义 133
4.1.2 低维数组及其地址映射 134
4.1.3 高维数组及其地址映射 137
4.1.4 数组的基本运算 137
4.2 矩阵与数组 138
4.2.1 矩阵及其存储结构 138
4.2.2 特殊矩阵及其存储结构 138
4.3 广义表 142
4.3.1 广义表的定义 142
4.3.2 广义表的表示 143
4.3.3 广义表的存储结构 144
4.4 数组和矩阵、广义表的应用 145
4.4.1 数组和矩阵的应用实例 145
4.4.2 广义表的应用实例 150
小结 151
习题 152
第5章 树与二叉树 155
5.1 两个常见的问题 155
5.2 树的基本概念及其基本运算 156
5.2.1 树的定义 156
5.2.2 树的几个术语 157
5.2.3 树的结构特点 158
5.2.4 树的表示方法 158
5.2.5 树的基本运算 159
5.2.6 树的存储结构 159
5.2.7 树的遍历 163
5.3 二叉树 165
5.3.1 二叉树的基本概念与基本运算 165
5.3.2 二叉树的基本操作 167
5.3.3 二叉树的存储结构 168
5.3.4 二叉树的遍历 169
5.3.5 从遍历序列构造二叉树 173
5.3.6 线索二叉树 174
5.3.7 从树、森林到二叉树 177
5.4 哈夫曼树 179
5.4.1 哈夫曼树的概念和定义 179
5.4.2 哈夫曼树的生成算法 181
5.4.3 哈夫曼编码技术 183
5.4.4 哈夫曼判定树 184
5.5 基于树的查找 185
5.5.1 折半查找与折半判定二叉树 185
5.5.2 二叉排序树 187
5.5.3 平衡二叉树 190
5.5.4 B+树 192
5.6 基于树的排序 194
5.6.1 快速排序与二叉树 194
5.6.2 归并排序 197
5.6.3 堆排序 199
5.7 树在操作系统中的应用 202
小结 202
习题 203
第6章 图 206
6.1 几个与图有关的实际问题 206
6.2 图的基本概念 208
6.2.1 图的定义 208
6.2.2 关于图的若干术语 209
6.2.3 图的基本性质 211
6.2.4 图的基本操作 211
6.3 图的存储结构 211
6.3.1 邻接矩阵法 212
6.3.2 基于邻接矩阵法的基本运算算法 214
6.3.3 邻接表法 215
6.3.4 基于邻接表法的基本运算算法 217
6.4 图的遍历 219
6.4.1 深度优先遍历 220
6.4.2 广度优先遍历 221
6.5 几个典型问题的算法设计 223
6.5.1 最小代价生成树问题 223
6.5.2 拓扑排序问题 227
6.5.3 最短路径问题 229
小结 236
习题 238
第7章 散列 241
7.1 散列的概念 241
7.1.1 从一个例子认识散列结构 241
7.1.2 散列结构 242
7.1.3 冲突 243
7.2 散列函数设计 243
7.2.1 散列函数的设计原则 244
7.2.2 设计散列函数的常用方法 244
7.3 解决冲突 246
7.3.1 对冲突的分析 246
7.3.2 冲突的几个常用解决方案 246
7.4 基本运算的算法实现 249
7.4.1 基于线性探查法的算法 249
7.4.2 基于同义词链表法的算法 252
7.5 散列的应用 254
7.5.1 散列在编译系统中的应用 254
7.5.2 散列在文件系统中的应用 255
7.5.3 散列在中医开处方中的应用 257
小结 260
习题 260
参考文献

主要著译者顺序姓名学历职称学科专长通讯地址1史九林 副教授 工作单位金肯职业技术学院 邮政编码 电话13915936091 2 工作单位 邮政编码 电话 3 工作单位 邮政编码 电话 审校者（主审者） 学历 工作单位 邮政编码 电话 职称 工作单位 邮政编码 电话

本书设计了三纵四横的教材体系；紧扣线性表、树和图这三种基本数据结构，并把相关知识（如排序和查找等）按处理方式分派捆绑到相应结构中，而不单独设章，这在数据结构教材编写中是一项创新。本书以基础知识、基本要素为基点选择教材内容，侧重常用数据结构问题。强化实践，注重能力，特别着力于算法设计过程的分析。