本书主要阐释了数据结构和算法两大部分，内容包括数据结构的各种基本概念以及各种算法的概念与方法，并对各种算法都给出了详细的示例。
数据结构与算法
吴 跃 主编 李树全 尚明生 陈端兵 参编
本书主要内容
“数据结构”是计算机科学技术专业的一门基础理论课程，是计算机学科的核心课程之一。在计算机科学技术的各个领域，选择合适的数据结构都是一个重要问题。通过数据结构与算法的学习，读者能进一步提高软件设计与程序编写的能力，提高应用计算机技术解决实际问题的能力。
本书是根据《高等学校计算机科学与技术专业公共核心知识体系与课程》的指导思想编写而成的，涵盖了“数据结构”公共核心课程的知识单元。
本书以基本数据结构和算法设计策略为知识单元，系统地介绍了数据结构的知识与应用、计算机算法的设计与分析方法。书中分为数据结构和算法两大部分。其中，数据结构部分（第1~4章）按数据元素之间存在的对应关系进行划分，分为表示一对一关系的线性表、表示一对多关系的树以及表示多对多关系的图和广义表；算法部分（第5~7章）以查找和排序算法作为常用算法，所以该部分由算法设计策略、查找和排序组成。
本书为教师配有电子教案和习题答案，可登录华章网站（www.hzbook.com)下载。
作者简介
吴 跃 四川省学术和技术带头人、国务院政府特殊津贴专家、教育部计算机科学与技术专业教学指导委员会委员、四川省教学名师、四川省高等学校省级教学团队计算机专业核心课程教学团队带头人。从事数据结构与算法课程的教学工作20余年，主持了国家863、教育部博士点基金、国防重点和省科技攻关等十余项科研项目，发表学术论文70余篇，获省部级科研奖5项、国家级教学成果奖2项，已编著出版《计算机操作系统》教材一部。
什么是数据结构？数据结构又有什么作用？什么是算法？算法又有哪些行之有效的基本策略？什么是程序设计的基础？程序设计的能力又可以从哪些方面去提高？这是计算机专业的学生在学习中经常感到困惑的问题，也是利用计算机解决具体应用问题的程序员需要明白的问题，还是计算机教育工作者应该深思的问题。弄清楚了这些基本问题，以及它们之间的相互关系，无论是对学生的学习、教师的施教还是程序员的应用，都具有重要的意义和极大的帮助。
早在1976年，著名的计算机科学家、Pascal程序设计语言之父、结构化程序设计首创者、1984年图灵奖获得者沃斯(Niklaus Wirth)就提出了Algorithms + Data Structures = Programs（算法＋数据结构＝程序），在这个著名的公式中，“+”生动地表达了算法和数据结构的相互作用，是程序设计的精髓；“=”言简意赅地刻画了算法和数据结构是构成计算机程序的两个关键要素。
我们认为，程序设计包括算法、数据结构和程序设计语言三部分。算法是求解问题的过程描述;数据结构是对所要求解问题中的数据的存储和算法策略实现的支持；程序设计语言是使用计算机求解问题，是在计算机上实现算法和数据结构。
本书是根据《高等学校计算机科学与技术专业公共核心知识体系与课程》的指导思想编写而成的，涵盖了“数据结构”公共核心课程的知识单元。本书共七章，分为数据结构和算法两大部分。其中，数据结构部分（第1～4章）按数据元素之间存在的对应关系进行划分，分为表示一对一关系的线性表、表示一对多关系的树以及表示多对多关系的图和广义表，可以以线性表作为基本数据结构，从多个方向和层面上进行拓广，引出线性表的各类变形，将栈、队列、串视为线性表的特例，将数组、广义表、树和图视为线性表的扩展，如图1所示；算法部分（第5～7章）以查找和排序算法作为常用算法，所以该部分由算法设计策略、查找和排序组成。
图1 数据结构关联图
各章具体内容如下：
第1章绪论，由吴跃编写。该章通过迷宫问题给出了数据结构的两大用途：存放要处理的数据和实现算法策略。该章还定义了数据结构的概念和相关术语，给出了算法和算法分析的概念。
第2章线性表，由尚明生编写。线性表表示数据元素之间一对一的关系。本章以线性表作为基本数据结构，从多个方向和层面进行拓广：引出线性表的各类变形，将栈、队列、串视为线性表的特例，将数组视为线性表在维数上的扩展。
第3章树，由陈端兵编写。树表示数据元素之间一对多的关系。本章以二叉树的性质、存储结构和遍历算法为基础，逐步拓展到二叉树的各类变形、树和森林以及树的变形。最后举例说明了树的应用。
第4章图和广义表，由李树全编写。图和广义表表示数据元素之间多对多的关系。本章分别介绍了图和广义表的概念、存储结构和遍历算法，并给出了图的经典应用。
第5章算法设计策略，由李树全编写。本章分别介绍了直接法、分治法、贪心法、动态规划法、回溯法、分支限界法6大类算法的设计策略、思想、应用特点和步骤，并举例说明了这些算法策略的应用。
第6章查找，由尚明生编写。在许多应用中都需要查找，可以将其视为一类基本而常用的算法，本章分别介绍了顺序表、索引表和散列表上的查找算法。
第7章排序，由陈端兵编写。和查找一样，在许多应用中也都需要排序，可以将其视为一类基本而常用的算法，本章分别介绍了插入、交换、选择、归并和基数5大类排序算法。
掌握了基本数据结构和算法策略，有助于选择和设计适合应用的数据结构，有助于设计更高效的算法，有助于提高编程能力。本书每章都有学习目标，还配有一定量的填空题、选择题、简答题和算法设计题，供读者练习。本书适用于高等院校计算机专业、信息技术类专业和软件工程相关专业的学生学习，也可供程序员参考。
最后，让我们一起一页一页地翻开这本丰富多彩的书，像一只漫游在数据结构这棵大树上的小虫，去领略各类数据结构的功用和风采，去品味各种算法策略的精妙和乐趣，去夯实计算机专业的基础，去提高编程的能力，去收获学习的果实。
编 者
2009年11月
“数据结构”是计算机科学技术专业的一门基础理论课程，是计算机学科的核心课程之一。在计算机科学技术的各个领域，选择合适的数据结构都是一个重要问题。通过数据结构与算法的学习，读者能进一步提高软件设计与程序编写的能力，提高应用计算机技术解决实际问题的能力。
本书是根据《高等学校计算机科学与技术专业公共核心知识体系与课程》的指导思想编写而成的，涵盖了《数据结构》公共核心课程的知识单元。
本书以基本数据结构和算法设计策略为知识单元，系统地介绍了数据结构的知识与应用、计算机算法的设计与分析方法。书中分为数据结构和算法两大部分。其中，数据结构部分（第1~4章）按数据元素之间存在的对应关系进行划分，分为表示一对一关系的线性表、表示一对多关系的树以及表示多对多关系的图和广义表；算法部分（第5~7章）以查找和排序算法作为常用算法，所以该部分由算法设计策略、查找和排序算法组成。
本书为教师配有电子教案和习题答案，可登录华章网站（www.hzbook.com)下载。
近20年里，计算机学科有了很大的发展，人们普遍认为，“计算机科学”这个名字已经难以涵盖该学科的内容，因此，改称其为计算学科（Computing Discipline）。在我国本科教育中，1996年以前曾经有计算机软件专业和计算机及应用专业，之后被合并为计算机科学与技术专业。2004年以来，教育部计算机科学与技术专业教学指导分委员会根据我国计算机专业教育和计算学科的现状，为更好地满足社会对计算机专业人才的需求，发布了《高等学校计算机科学与技术专业发展战略研究报告暨专业规范（试行）》（以下简称《规范》），提出在计算机科学与技术专业名称之下，构建计算机科学、计算机工程、软件工程和信息技术四大专业方向。《规范》中四大专业方向的分类，在于鼓励办学单位根据自己的情况设定不同的培养方案，以培养更具针对性和特色的计算机专业人才。
为配合《规范》的实施，落实中央“提高高等教育质量”的精神，我们规划了“面向计算机科学与技术专业规范系列教材”。本系列教材面向全新的计算学科，针对我国高等院校逐步向新的计算机科学与技术专业课程体系过渡的趋势编写，在知识选择、内容组织和教学方法等方面满足《规范》的要求，并与国际接轨。本套教材具有以下几个特点：
（1） 体现《规范》的基本思想，满足其课程要求。为使教材符合我国高等院校的教学实际，编委会根据《规范》的要求规划本套教材，广泛征集在国内知名高校中从事一线教学和科研工作、经验丰富的优秀教师承担编写任务。
（2） 围绕“提高教育质量”的宗旨开发教材。为了确保“精品”，本系列教材的出版不走盲目扩大的路子，每本教材的选题都将由编委会集体论证，并由一名编委担任责任编委，最大程度地保证这套教材的编写水准和出版质量。
（3） 教材内容的组织科学、合理，体系得当。本套教材的编写注重研究学科的新发展和新成果，能够根据不同类型人才培养需求，合理地进行内容取舍、组织和叙述，还精心设计了配套的实验体系和练习体系。
（4） 教材风格鲜明。本套教材按4个专业方向统一规划，分批组织，陆续出版。教材的编写体现了现代教育理念，探讨先进的教学方法。
（5） 开展教材立体化建设。根据需要配合主教材的建设适时开发实验教材、教师参考书、学生参考书、电子参考资料等教辅资源，为教学实现多方位服务。
我们衷心希望本系列教材能够为我国高等院校计算机科学与技术等专业的教学作出贡献，欢迎广大读者广为选用。
“面向计算机科学与技术专业规范系列教材”编委会
吴跃 主编 李树全 尚明生 陈端兵 参编：吴跃教授是四川省学术和技术带头人、国务院政府特殊津贴专家、教育部计算机科学与技术专业教学指导委员会委员、四川省教学名师、四川省高等学校省级教学团队计算机专业核心课程教学团队带头人。从事数据结构与算法课程的教学工作20余年，主持了国家863、教育部博士点基金、国防重点和省科技攻关等十余项科研项目，发表学术论文70余篇，获省部级科研奖5项、国家级教学成果奖2项，已编著出版《计算机操作系统》教材一部。
出版者的话
序 言
前 言
教学建议
第1章 绪论1
1.1 计算机问题求解过程1
1.2 迷宫问题2
1.3 数据结构4
1.3.1 数据结构研究的内容4
1.3.2 数据结构概念6
1.4 算法10
1.4.1 算法概念及特性10
1.4.2 算法描述11
1.4.3 算法分析12
1.5 本章小结14
1.6 习题14
第2章 线性表16
2.1 线性表16
2.1.1 线性表的定义16
2.1.2 线性表的顺序存储20
2.1.3 线性表的链式存储28
2.1.4 链表的各种变形37
2.1.5 线性表的应用40
2.2 栈45
2.2.1 栈的定义45
2.2.2 栈的顺序存储46
2.2.3 栈的链式存储49
2.2.4 栈的应用51
2.3 队列55
2.3.1 队列的定义55
2.3.2 队列的顺序存储56
2.3.3 队列的链式存储59
2.3.4 优先队列61
2.3.5 队列的应用62
2.4 数组65
2.4.1 数组的定义66
2.4.2 数组的表示和实现66
2.4.3 数组的应用77
2.5 本章小结79
2.6 习题80
第3章 树82
3.1 二叉树83
3.1.1 二叉树的基本概念和性质 …83
3.1.2 二叉树的存储结构86
3.1.3 二叉树的遍历88
3.2 二叉树的变形93
3.2.1 线索二叉树93
3.2.2 二叉排序树96
3.2.3 平衡二叉树100
3.2.4 赫夫曼树及赫夫曼编码105
3.3 树和森林109
3.3.1 树和森林的定义109
3.3.2 树和森林的存储结构110
3.3.3 树和森林的基本操作112
3.4 树的变形115
3.4.1 四叉树115
3.4.2 B树122
3.4.3 2-3树127
3.5 树的应用128
3.5.1 算术表达式128
3.5.2 堆排序129
3.5.3 决策分析131
3.6 本章小结134
3.7 习题134
第4章 图和广义表137
4.1 图简介137
4.1.1 基本概念和术语138
4.1.2 图的应用139
4.2 图的存储结构140
4.2.1 图的顺序存储结构140
4.2.2 图的链式存储结构141
4.3 图的遍历145
4.3.1 深度优先遍历145
4.3.2 广度优先遍历147
4.4 图的应用148
4.4.1 最小生成树148
4.4.2 拓扑排序155
4.4.3 关键路径158
4.4.4 最短路径163
4.5 广义表167
4.5.1 广义表的定义167
4.5.2 广义表的存储结构169
4.5.3 广义表的遍历170
4.5.4 广义表的运算172
4.6 本章小结175
4.7 习题175
第5章 算法设计策略179
5.1 算法分析技术179
5.2 直接法183
5.2.1 穷举法183
5.2.2 递推法184
5.2.3 迭代法185
5.3 分治法186
5.3.1 分治法的基本思想187
5.3.2 斯特拉森矩阵乘法188
5.4 贪心法190
5.4.1 贪心法的基本思想190
5.4.2 背包问题191
5.5 动态规划法193
5.5.1 动态规划法的基本思想193
5.5.2 矩阵连乘问题196
5.6 回溯法198
5.6.1 回溯法的基本思想198
5.6.2 回溯法的形式化描述199
5.6.3 八皇后问题200
5.7 分支限界法202
5.7.1 分支限界法的基本思想202
5.7.2 货郎担问题203
5.8 本章小结206
5.9 习题206
第6章 查找209
6.1 顺序表的查找209
6.1.1 顺序查找209
6.1.2 二分查找211
6.2 索引表的查找212
6.2.1 索引表的基本概念212
6.2.2 索引表的顺序查找213
6.2.3 索引表的二分查找215
6.2.4 索引表的树组织查找216
6.3 散列表的查找216
6.3.1 基本概念216
6.3.2 散列函数217
6.3.3 冲突处理218
6.3.4 散列查找与性能分析220
6.4 本章小结223
6.5 习题223
第7章 排序226
7.1 排序的基本概念226
7.2 插入排序227
7.2.1 直接插入排序227
7.2.2 二分插入排序228
7.2.3 希尔排序229
7.3 交换排序230
7.3.1 冒泡排序230
7.3.2 快速排序232
7.4 选择排序234
7.4.1 简单选择排序234
7.4.2 树形选择排序235
7.5 2路归并排序236
7.6 基数排序237
7.6.1 多关键字排序237
7.6.2 链式基数排序238
7.7 各排序方法的比较241
7.8 本章小结241
7.9 习题242
参考文献245
