本书介绍了各种常用的线性结构、树形结构、图形结构的概念、存储结构及各种典型操作在不同存储结构下的算法，然后讨论了各种查找和排序实现方法及其性能分析、比较。全书采用类C语言作为数据结构和算法的描述语言，大部分算法都已通过调试，稍加修改即可作为程序的一部分。本教材可作为计算机或信息类专业学习数据结构与算法的参考教材，适合在学习程序设计语言后使用，也可供从事计算机工程与应用软件开发人员参考。
数据结构
张建林 刘玉铭 申贵成 编著
Data Structures
随着社会发展对人才需求的变化及我国人才培养模式的改变，了解相关的生产技术和管理知识的应用型人才越来越受到社会的关注。本书作者根据数据结构的特点、计算机应用型人才的培养目标、教学实际及学生继续深造的要求，组织编写了本教材。
本书特点
内容介绍深入浅出，通俗易懂，结构清晰合理。全书从简单的概念或读者感兴趣的应用实例入手，逐步深入。
以教学大纲和考研大纲为依据，兼顾应用型和研究型人才培养，兼顾学科知识的广度和深度。
采用抽象数据类型的基本概念，有助于培养学生的抽象思维能力和算法设计能力。
对于各种基本结构，采用类C语言描述其存储结构和算法；而对于一些应用型实例，则采用标准C描述，并提供完整的源代码，便于学生学习和上机调试。
对算法的定性或定量分析，强调实用为主，避免过多的理论推导。
书中所含习题精选于近年来部分考研、高自考及期末试题，知识考查点覆盖全面，有助于读者消化和巩固所学知识。
本书为教师配有教学课件，有需要的教师可登录华章网站（www.hzbook.com）下载。
“数据结构”作为一门计算机领域十分重要的基础课程，不仅是计算机学科，也是其他信息类或理工类专业的专业基础课，是进行程序设计的重要理论基础。随着计算机科学技术的飞速发展，其应用已不再局限于解决那些传统的数值计算，而是更多地应用在数据采集、信息检索、企业管理、工业过程控制、办公自动化、经济管理、社会服务等非数值计算领域。而应用到这些领域，计算机面对的数据具有结构复杂、数据量大，且种类繁多的特点，同时还面对大多数应用中面临的大数据量存取和处理的能力问题。要设计出高效、准确、适应性好和重用强的程序，就必须对待处理的数据自身的特性及数据元素间的关系进行深入的研究。研究内容主要包括数据的逻辑结构、存储结构以及对数据进行有关操作的算法。
我们研究和学习数据结构的目的是为了学会分析、研究计算机加工的数据的结构特征，并为数据选择合适的逻辑结构、存储结构和相应的处理算法，初步掌握算法的时间复杂度分析和空间复杂度分析，并对复杂程序设计进行一定的训练。
现在市面上有关数据结构的教材比较多，主要包括三类：第一类主要以伪代码方式描述算法，强调对数据结构原理的阐述和理解；第二类用结构化语言（C或Pascal）描述算法，强调对数据及数据元素的描述，侧重于算法的实现；第三类是用面向对象语言（C++或Java）描述的，强调对数据和数据类型的抽象。根据我们大量的教学实践经验，这三类教材各有利弊，第一类教材不利于学生掌握算法的实现以及对算法的复杂度分析；第二类教材则容易让学生过分关注程序的实现，而不是算法的分析和研究，不利于学生解决问题能力的培养；第三类教材则让很多对面向对象思想和程序设计理念不熟悉的学生望而却步。
当然除了这三类教材以外，还有很多介于三类之间的教材，但面对日新月异的IT技术、计算机应用范围的不断扩大，学习和使用计算机的人群已不限于计算机专业了，大量非计算机信息类或理工类专业也把数据结构作为一门必修的基础课。同时，随着社会发展对人才的需求变化及我国人才培养模式的改变，强调对相关的生产技术、技术经济和管理知识的了解，应用型人才培养越来越受到社会的欢迎。而应用型人才的培养不仅体现在课堂体系的调整上，而且要在每门课程内容的编排上，通过潜移默化的知识渗透和影响来实现应用型人才的培养。正是基于这种理念，根据计算机应用型人才培养目标、教学实际及学生继续深造的要求，我们组织编写了这本教材。本书的作者均是有十多年数据结构教学经验，而且还拥有其他学科背景的一线老师。
根据数据结构特点及目前绝大多数应用型人才培养的需要，本书采用类C语言作为数据和算法的描述语言。对于每一种基本数据结构，给出相关定义后，用规范化的ADT（抽象数据类型）进行描述，使读者能从面向对象的角度理解和把握概念的本质；在对数据的存储结构和算法进行描述时，尽量采用C语言。这样使得对各种数据结构的定义和实现简洁、清晰，又不拘泥于某种语言，又容易转换成能上机执行的C或C++程序。
本书内容安排合理，详略得当，遵循易于理解的宗旨，讲解时由浅入深；文字表达上力求简练、通俗易懂；实现的算法具体，稍做修改即可上机调试。
全书分8章：第1章是绪论，引入数据结构的概念，并介绍了数据、结构、数据的逻辑结构、数据的存储结构、数据的操作、ADT、算法的概念及特点、算法的复杂度分析等；第2章是线性表，介绍了线性表的基本概念、两种存储结构及其相应存储结构下的操作实现及一些简单应用；第3章是栈与队列，介绍了栈与队列的基本概念、两种存储结构下的操作实现，并例举了一些应用；第4章是数组、串和广义表，介绍了数组的概念、压缩存储的概念和实现、串的概念、串的存储及应用、广义表的基本概念等；第5章是树，介绍了树和二叉树的概念、各种存储结构，以及遍历、线索化二叉树、恢复二叉树、Huffman树的概念与实现；第6章是图，介绍了图的基本概念、图的存储方式，以及图的遍历、最小生成树、拓扑排序、关键路径和最短路径的概念与实现；第7章是查找，介绍了查找的概念与分类、各种查找方法的实现及复杂度分析；第8章是排序，介绍了排序的概念、排序的分类，重点介绍了各种内部排序方法的实现，对各种内部排序方法进行了分析和比较，最后简单介绍了一下外部排序的概念。
本教材可作为高等院校计算机科学与技术、软件工程、信息工程、信息与计算科学、应用数学、信息管理与信息系统、电子商务、教育技术等专业的教材、参考书或考研辅导用书，也可供其他相关理工类专业或工程技术人员参考。对于信息类专业，可讲授64学时，对于非信息类专业，可适当删减，讲授48学时。
本书的第1、2、3、7章由张建林编写，第4、5章由申贵成编写，第6、8章由刘玉铭编写，最后由张建林对全文进行通审和定稿。
在本书的编写过程中，中国石油大学的陈明教授、首都师范大学的王锁柱教授、中央民族大学的曹永存教授对本书的编写提出了宝贵的意见，在此一并表示衷心的感谢。
由于作者水平有限，书中难免有错误和疏漏之处，恳请广大读者赐教。
编者
2010年7月
计算机\数据结构
随着社会发展对人才的需求变化及我国人才培养模式的改变，强调对相关的生产技术、技术经济和管理知识了解的应用型人才培养越来越受到社会的关注。本书作者根据数据结构特点及计算机应用型人才培养目标、教学实际及学生继续深造的要求，组织编写了本教材。
本书特色：
●内容介绍深入浅出，通俗易懂，结构清晰合理。全书从简单的概念或读者感兴趣的应用实例入手，逐步深入。
●以教学大纲和考研大纲为依据，兼顾应用型和研究型人才培养，兼顾学科知识的广度和深度。
●采用抽象数据类型的基本概念，有助于培养学生的抽象思维能力和算法设计能力。
●对于各种基本结构，采用类C语言描述其存储结构和算法；而对于一些应用型实例，则采用标准C描述，并提供完整的源代码，便于学生学习和上机调试。
●对算法的定性或定量的分析，则强调实用为主，避免过多的理论推导。
●书中所含习题精选于近年来部分考研、高自考及期末试题，经典且考查点覆盖广，有助于读者消化和巩固所学知识。
我国高等学校计算机专业建立于20世纪50年代。经过近60年的迅速发展，经历了从精英化教育到大众化教育的发展阶段，目前在校生多达40余万人，已成为我国规模最大的理工科专业，为国家建设培养了大批信息技术人才。2006年，教育部计算机科学与技术专业教学指导委员会发布了《高等学校计算机科学与技术专业发展战略研究报告暨专业规范（试行）》（以下简称《规范》），提出了以“按培养规格分类”为核心思想的专业发展建议，把计算机专业人才划分为研究型、工程型、应用型三种不同类型。在《规范》的方针指导下，培养合格的计算机本科人才。
教育包括知识、能力、素质三个方面。知识是基础、载体和表现形式，能力是技能化的知识及其综合体现，素质是知识和能力的升华。专业教育不仅要重视知识的传授，更应突出专业能力的培养，实施能力导向的教育。如何以知识为载体实现能力的培养和素质的提高，特别是实现专业能力和素质的提高是非常重要的。对计算机专业本科教育而言，要想实现能力导向的教育，首先要分析专业能力的构成并考虑如何将其培养落实到教学实践中。为此，教育部高等学校计算机科学与技术专业教学指导委会开展了计算机科学与技术专业人才专业能力（简称为计算机专业能力）的培养研究。该项研究明确计算机专业本科人才应具有的四大基本能力--计算思维能力、算法设计与分析能力、程序设计与实现能力、系统能力，并将这四大基本能力分解为82个能力点，探讨如何面对不同类型学生的教育需求，在教学活动中进行落实。
针对计算机应用型人才的培养，由于其培养数量巨大、社会需求广泛和多样化，所以培养应用型人才的专业能力在具体教学实践上有其自身的特点。计算机应用型人才的培养目标是为国家、企事业信息系统的建设与运行培养信息化技术型人才。本类型人才应能承担信息化建设的核心任务，掌握各种计算机软、硬件系统的性能，善于进行系统的集成和配置，有能力管理和维护复杂信息系统的运行，研究如何实现服务及方便有效地利用系统进行计算等。计算机应用型人才的培养凸显了职业特征，使企业与学校的合作更加紧密，部分课程设置凸显能力培养特征，教学模式也呈现了职业化趋势。
为体现研究成果在教学活动中的实现，我们根据《高等学校计算机科学与技术专业人才专业能力构成与培养》和计算机应用型人才培养的特点和社会需求出版了这套教材。本套教材面向高等院校计算机应用型人才培养从知识传授向能力培养转型的需求，在内容的选择、体系安排和教学方法按照专业能力培养和职业特征的需要进行了探索和诠释。
本套教材在体系结构上，遵从公共基础课程平台、专业核心课程平台、专业选修课程平台、方向课程平台和基本素质课程平台的体系。专业核心课程主要有程序设计基础、离散数学、数据结构、计算机组成原理、操作系统原理、计算机网络原理、数据库系统原理、编译原理等课程。方向课程分为计算机网络、软件工程、信息系统、程序设计、电子商务、嵌入式系统、多媒体技术和计算机硬件等方向。在教材编写上，汇集作者才智，重点突出对计算机应用能力和应用技术的培养。
本套丛书的出版是在配合计算机应用型人才专业能力的培养和落实方面的初步尝试，在教材组织和编写上还会有许多不足和缺陷，需要进一步完善，我们衷心希望本套教材的出版能起到抛砖引玉的作用，也希望广大教育工作者加入到计算机应用型人才能力培养的研究和实践中来，并对相关的教材建设提出自己的宝贵意见。
丛书主编
出版者的话
丛书序言
丛书编委会
前言
教学建议
第1章 绪论 1
1.1 数据结构的由来与发展 1
1.1.1 什么是数据结构 1
1.1.2 数据结构的发展简史 4
1.2 数据结构的有关概念与术语 5
1.3 抽象数据类型 8
1.4 算法和算法分析 11
1.4.1 算法的概念与性质 11
1.4.2 算法设计的分类 12
1.4.3 算法的设计要求 12
1.4.4 算法分析 12
本章小结 15
习题 16
第2章 线性表 17
2.1 线性表的类型定义 17
2.1.1 线性表的概念 17
2.1.2 线性表的抽象数据类型定义 18
2.2 线性表的顺序表示和实现 20
2.2.1 顺序表 20
2.2.2 顺序表上基本运算的实现 21
2.2.3 顺序表的应用举例 24
2.3 线性表的链式表示和实现 25
2.3.1 线性链表的概念 25
2.3.2 单链表上基本运算的实现 27
2.3.3 线性链表的应用举例 32
2.3.4 循环链表 34
2.3.5 双向链表 34
2.4 静态链表 36
2.5 一元多项式的表示和运算 38
本章小结 40
习题 40
第3章 栈和队列 42
3.1 栈的概念及操作 42
3.1.1 栈的定义 42
3.1.2 栈的抽象数据类型定义 42
3.2 栈的存储和运算实现 43
3.2.1 顺序栈 43
3.2.2 链栈 46
3.3 栈的应用举例 47
3.3.1 数制转换问题 47
3.3.2 表达式中括号匹配的检验 48
3.3.3 栈在递归中的应用 48
3.3.4 表达式求值 52
3.3.5 迷宫问题 54
3.4 队列的概念及操作 57
3.4.1 队列的定义 57
3.4.2 队列的抽象数据类型定义 57
3.4.3 其他操作受限的线性表 58
3.5 队列的存储和运算实现 58
3.5.1 顺序队列 58
3.5.2 链队列 61
本章小结 63
习题 63
第4章 数组、串和广义表 65
4.1 数组 65
4.1.1 数组的概念及其抽象数据类型
定义 65
4.1.2 数组的顺序实现 66
4.1.3 矩阵的压缩存储 70
4.2 串 82
4.2.1 串的概念及其抽象数据类型
定义 82
4.2.2 串的表示与实现 84
4.2.3 串的模式匹配算法 87
4.3 广义表 91
4.3.1 广义表的概念及其抽象数据类型
定义 91
4.3.2 广义表的实现 92
本章小结 96
习题 96
第5章 树 98
5.1 树的基本概念 98
5.2 二叉树 101
5.2.1 二叉树的定义与性质 101
5.2.2 二叉树的存储与实现 104
5.2.3 二叉树的遍历 107
5.3 线索二叉树 112
5.4 树和森林 115
5.4.1 树的存储 115
5.4.2 树、森林与二叉树的转换 117
5.4.3 树和森林的遍历 118
5.5 Huffman树和Huffman编码 118
5.6 等价类问题 121
本章小结 124
习题 124
第6章 图 126
6.1 图的基本概念 126
6.2 图的表示和存储实现方法 128
6.2.1 图的抽象数据类型定义 128
6.2.2 邻接矩阵存储结构 129
6.2.3 邻接表存储结构 130
6.2.4 十字链表存储结构 134
6.2.5 邻接多重表存储结构 135
6.3 图的遍历 136
6.3.1 深度优先遍历 136
6.3.2 广度优先遍历 137
6.4 最小生成树 138
6.4.1 Prim算法 139
6.4.2 Kruskal算法 141
6.5 最短路径 142
6.5.1 无权图的最短路径 143
6.5.2 Dijkstra算法 144
6.5.3 Floyd算法 146
6.6 拓扑排序 146
6.7 关键路径 147
本章小结 150
习题 150
第7章 查找 153
7.1 查找的基本概念 153
7.2 静态查找表 155
7.2.1 顺序表的查找 155
7.2.2 有序表的查找 156
7.2.3 分块查找 160
7.3 动态查找表 162
7.3.1 二叉排序树 162
7.3.2 平衡二叉树 167
7.3.3 B-树 173
7.3.4 B+树 177
7.4 哈希表上的查找 178
7.4.1 哈希表的概念 178
7.4.2 哈希函数的构造方法 180
7.4.3 处理冲突的方法 181
7.4.4 哈希表的查找及其性能分析 183
7.4.5 哈希表的有关算法 185
本章小结 187
习题 187
第8章 排序 189
8.1 概述 189
8.2 插入排序 191
8.2.1 直接插入排序 191
8.2.2 折半插入排序 193
8.2.3 希尔排序 194
8.3 交换排序 195
8.3.1 冒泡排序 195
8.3.2 快速排序 196
8.4 选择排序 198
8.4.1 简单选择排序 198
8.4.2 树选择排序 199
8.4.3 堆排序 200
8.5 归并排序 202
8.6 基数排序 204
8.7 内部排序方法比较 207
8.8 外部排序概述 208
本章小结 209
习题 209
部分习题参考答案或提示 211
参考文献 218
