本书系统地介绍了各种常用的数据结构以及排序、查找的各种算法，阐述了各种数据结构的逻辑关系、存储表示及运算操作，涵盖了研究生入学考试大纲的所有内容。全书采用C语言作为数据结构和算法的描述语言，并对C语言描述的算法作了详细的注解和简要的性能分析。
数据结构及应用
C语言描述
沈 华 等编著
本书系统地介绍了各种常用的数据结构以及排序、查找的各种算法，阐述了各种数据结构的逻辑关系、存储表示及运算操作，基本涵盖了研究生入学考试大纲的所有内容。
本书特点
基础与应用并重。本书不仅对什么是数据结构，什么是算法，它们之间有着怎样的联系，如何鉴定一个算法的好坏，数据结构有哪些常用的线性结构和非线性结构，它们各有什么特点和应用，有哪些经典的查找和排序算法等问题进行清晰、全面的阐述，而且关注应用，利用众多实例帮助读者加深对基本知识的理解并灵活运用。
图文并茂，生动有趣。本书为了帮助读者直观、正确地理解各种数据结构和算法的要旨，利用大量的图表进行诠释，以通俗易懂的方式介绍复杂的概念。
积极引导，活跃思维。本书在介绍完重要知识点后会设置一些思考题，引导读者对数据结构的应用进行深入思考和理解，训练读者的发散性思维。
读者对象广泛。本书内容丰富、概念清楚、逻辑推理严谨、通俗易懂，既便于教学，又适合自学，可作为计算机及相关专业本科生的教材，也可作为计算机专业硕士研究生入学考试的复习用书，还可作为广大工程技术人员的参考资料。
本书为教师提供教学课件及课后习题答案，有需要者可登录华章网站（www.hzbook.com）下载。
在国外是从1968年才开始将“数据结构”作为一门独立的课程的。1968年，美国唐纳德E.克努特教授开创了数据结构的最初体系，他所著的《计算机程序设计艺术：第1卷基本算法》是第一本较系统地阐述数据的逻辑结构和存储结构及其操作的著作。“数据结构”是计算机科学与技术、信息类相关专业的一门重要的综合性专业基础课。它是介于数学、计算机硬件和计算机软件三者之间的一门核心课程。当用计算机解决实际问题时，必然会涉及信息表示和信息处理的问题，而这正是“数据结构”课程主要的研究内容。“数据结构”不仅是一般程序设计（特别是非数值性程序设计）的基础，也是编译程序、操作系统、数据库系统等系统程序的重要基础。
本书分六部分共14章，如下图所示。
第一部分包括第1章和第2章，主要介绍数据结构的概念、算法的概念、数据结构和算法之间的密切联系以及简单的算法分析。
第二部分包括第3章，主要介绍C语言中的函数参数传递及函数处理结果返回、结构体、指针等相关内容，两种递归方式，以及操作系统为一个准备运行的程序分配内存空间的情况。
第三部分包括第4章至第8章，这一部分以“线性表”为主线分别详细讨论六种常见的线性结构。
第四部分包括第9章和第10章，重点介绍两种重要的非线性结构——树和图。
第五部分包括第11章和第12章，讨论两种重要的运算——查找和（内部）排序，在介绍各种经典的查找算法和（内部）排序算法的同时，展现各种数据结构的完美应用。
第六部分包括第13章和第14章，讨论数据在外存上的存储形式，以及如何对外存中的文件进行排序。这部分内容为选学内容，章名前以“*”号指示。
本书主要采用面向过程的C语言作为数据结构和算法的描述手段，在保持C语言优点的同时，尽量使算法描述简单清晰。
本书配套的教辅资源包括：电子课件以及课后习题参考答案。
在本书的编写过程中，机械工业出版社负责本书的编辑为本书的出版付出了大量辛勤的劳动。何炎祥教授在百忙之中认真审阅了全书，提出了许多宝贵和中肯的意见。在此，谨向每一位关心和支持本书编写工作的各位朋友、老师表示衷心的谢意！
由于作者的知识和写作水平有限，书中难免有错误和不足之处，恳请各位专家、读者批评指正。作者E-mail：nancy78733@126.com。
沈华
2010年8月于武汉南湖
计算机\数据结构
本书系统地介绍了各种常用的数据结构以及排序、查找的各种算法，阐述了各种数据结构的逻辑关系、存储表示及运算操作，基本涵盖了研究生入学考试大纲的所有内容。
本书特点：
基础与应用并重。本书不仅对什么是数据结构，什么是算法，它们之间有着怎样的联系，如何鉴定一个算法的好坏，有哪些常用的线性结构和非线性结构，它们各有什么特点和应用，有哪些经典的查找和排序算法等问题进行清晰、全面的阐述，而且关注应用，利用众多实例帮助读者加深对基本知识的理解并灵活运用。
图文并茂，生动有趣。本书为了帮助读者直观、正确地理解各种数据结构和算法的要旨，利用大量的图表进行诠释，以通俗易懂的方式介绍复杂的概念。
积极引导，活跃思维。本书在介绍完重要知识点后会提出一些思考题，引导读者对相关知识点进行深入思考和理解，训练读者的发散性思维。
读者对象广泛。本书内容丰富、概念清楚、逻辑推理严谨、通俗易懂，既便于教学，又适合于自学，可作为计算机及相关专业本科生的教材，也可作为计算机专业硕士研究生入学考试的复习用书，还可作为广大工程技术人员的参考资料。
本书为教师提供教学课件及课后习题答案，有需要者可登录华章网站（www.hzbook.com）下载。
沈华 杨晓艳 马驰 杨华 编著：沈华，武汉大学计算机学院计算机软件与理论专业博士，师从何炎祥教授。具有十余年的数据结构教学经验；曾参加多项纵向和横向项目，具有丰富的数据结构实践经验。CCF会员，担任CCF YOCSEF武汉学术秘书（2009年度和2010年度）。主要研究方向是数据结构、算法、服务计算、移动计算。
序
前言
教学建议
第一部分概论
第1章数据结构3
1.1什么是数据3
1.2什么是数据结构3
1.2.1数据的逻辑结构3
1.2.2数据的存储结构4
1.2.3数据的运算5
1.3什么是数据类型5
1.4知识点小结6
习题6
第2章算法7
2.1什么是算法7
2.2算法的描述7
2.3算法分析8
2.3.1时间复杂度8
2.3.2渐近符号9
2.3.3空间复杂度10
2.3.4复杂度分析举例10
2.4知识点小结13
习题13
第二部分预备知识
第3章C语言、递归及存储分配方式16
3.1C语言的相关内容16
3.1.1函数的参数传递与结果返回16
3.1.2结构体类型17
3.1.3指针18
3.2递归18
3.3存储分配方式19
3.4知识点小结20
习题20
第三部分线性结构
第4章线性表22
4.1线性表的类型定义22
4.1.1线性表的逻辑结构22
4.1.2线性表的基本运算22
4.2线性表的顺序存储表示23
4.2.1顺序表23
4.2.2顺序表中基本运算的实现24
4.3线性表的链式存储表示30
4.3.1单链表30
4.3.2单链表中基本运算的实现31
4.4线性表的其他链式存储表示38
4.4.1静态单链表38
4.4.2双（向）链表41
4.4.3循环单（向）链表43
4.4.4循环双（向）链表46
4.5线性表的应用举例47
4.6顺序表和链表的比较48
4.7知识点小结49
习题49
第5章栈51
5.1栈的类型定义51
5.1.1栈的逻辑结构51
5.1.2栈的基本运算52
5.2栈的顺序存储表示52
5.2.1顺序栈52
5.2.2顺序栈中基本运算的实现53
5.3栈的链式存储表示55
5.3.1链栈55
5.3.2链栈中基本运算的实现55
5.4两个方向生长的栈56
5.5栈的应用举例57
5.6知识点小结61
习题61
第6章队列63
6.1队列的类型定义63
6.1.1队列的逻辑结构63
6.1.2队列的基本运算63
6.2队列的链式存储表示64
6.2.1链队列64
6.2.2链队列中基本运算的实现65
6.3队列的顺序存储表示66
6.3.1顺序队列66
6.3.2循环队列69
6.3.3循环队列中基本运算的实现71
6.4双端队列74
6.5队列的应用举例74
6.6知识点小结75
习题76
第7章串77
7.1串的类型定义77
7.1.1串的逻辑结构77
7.1.2串的基本运算77
7.2串的顺序存储表示78
7.3串的堆分配存储表示80
7.4串的块链存储表示81
7.5串的模式匹配82
7.6知识点小结88
习题88
第8章数组及广义表89
8.1数组的类型定义89
8.1.1数组的定义89
8.1.2数组的性质89
8.1.3数组的基本运算89
8.2数组的顺序存储表示90
8.3特殊矩阵的压缩存储92
8.3.1特殊形状矩阵的压缩存储93
8.3.2随机稀疏矩阵的压缩存储及其运算95
8.4广义表104
8.4.1广义表的基本概念104
8.4.2广义表的基本运算105
8.4.3广义表的存储结构106
8.5知识点小结108
习题108
第四部分非线性结构
第9章树110
9.1概述110
9.1.1树的定义及基本术语110
9.1.2树的存储结构112
9.2二叉树123
9.2.1二叉树的定义123
9.2.2二叉树的性质123
9.2.3二叉树的存储结构128
9.3二叉树的遍历132
9.3.1遍历操作132
9.3.2先序遍历132
9.3.3中序遍历133
9.3.4后序遍历134
9.3.5层次遍历135
9.3.6二叉树遍历的应用举例136
9.4线索二叉树144
9.4.1二叉树的线索化145
9.4.2线索二叉树上的运算149
9.5二叉树的应用156
9.5.1哈夫曼树及其应用156
9.5.2二叉排序树161
9.5.3平衡二叉树163
9.6树、森林与二叉树的相互转换166
9.6.1树与二叉树的相互转换166
9.6.2森林与二叉树的相互转换168
9.7树、森林的遍历169
9.7.1树的遍历169
9.7.2森林的遍历169
9.8树的应用举例170
9.9知识点小结171
习题172
第10章图173
10.1概述173
10.1.1图的定义及基本术语173
10.1.2图的存储结构179
10.1.3图的创建184
10.2图的遍历187
10.2.1深度优先搜索遍历187
10.2.2广度优先搜索遍历191
10.2.3图遍历的应用举例193
10.3生成树194
10.3.1连通图的生成树194
10.3.2连通网的最小生成树195
10.4最短路径197
10.4.1单源最短路径197
10.4.2每对顶点间的最短路径201
10.5有向无环图及其应用205
10.5.1AOV网与拓扑排序205
10.5.2AOE网与关键路径207
10.6知识点小结209
习题209
第五部分两种重要运算
第11章查找212
11.1查找的基本概念212
11.2主要查找方法简介213
11.3静态查找213
11.3.1顺序查找213
11.3.2二分查找215
11.3.3分块查找219
11.4动态查找220
11.5散列查找227
11.5.1散列表的概念228
11.5.2散列函数的构造方法228
11.5.3处理冲突的方法229
11.5.4散列表的查找232
11.6知识点小结234
习题235
第12章内排序236
12.1排序的基本概念236
12.2插入排序237
12.2.1直接插入排序237
12.2.2希尔排序241
12.3交换排序242
12.3.1冒泡排序242
12.3.2快速排序244
12.4选择排序247
12.4.1直接选择排序247
12.4.2树形选择排序248
12.4.3堆排序249
12.5归并排序254
12.6分配排序255
12.6.1箱排序255
12.6.2基数排序255
12.7各种内排序法的比较257
12.8知识点小结257
习题258
第六部分文件的组织结构及排序
第13章文件260
13.1文件的基本概念260
13.2顺序文件260
13.3索引文件261
13.4索引顺序文件262
13.5散列文件267
13.6多关键字文件268
13.7知识点小结268
习题268
第14章外排序269
14.1多路平衡归并269
14.2置换选择排序272
14.3归并树及最佳归并树274
14.4知识点小结275
习题275
参考文献276
