内容简介

《数据结构与算法（第2版）/计算机系列教材》系统地介绍了各种数据结构的特点、存储结构及相关算法。书中采用C语言描述算法。主要内容包括数据结构的基本概念、算法描述和算法分析初步；线性表、堆栈、队列、串、数组、树、图等结构；查找、排序等。每章后面配有小结、习题、讨论题。《数据结构与算法（第2版）/计算机系列教材》有配套的完整的习题与实验指导书，每一章节都给出了完整的C语言和C++源程序示例。
《数据结构与算法（第2版）/计算机系列教材》叙述清晰，深入浅出，注意实践，便于教学与实践。
《数据结构与算法（第2版）/计算机系列教材》既可作为高等院校计算机专业的教材，也可供从事计算机应用与工程工作的科技工作者自学参考。

目录

目录
第1章绪论1
1.1数据结构的概念2
1.1.1引言2
1.1.2数据结构的有关概念与术语5
1.2抽象数据类型7
1.3算法描述与分析11
1.3.1什么是算法11
1.3.2算法分析技术初步13
1.4基本的算法策略17
1.4.1穷举法17
1.4.2递推法与迭代法18
1.4.3分治法20
1.4.4贪心算法22
1.4.5动态规划22
1.5案例分析25
1.6小结26
讨论小课堂127
习题128第2章线性表30
2.1线性表的定义及其运算30
2.1.1线性表的定义30
2.1.2线性表的抽象数据类型31
2.2线性表的顺序存储结构及实现32
2.2.1顺序存储结构32
2.2.2线性表在向量中基本运算的实现34
2.3线性表的链表存储结构39
2.3.1单链表39
2.3.2线性链表基本运算的实现42
2.4循环链表和双向链表49
2.4.1循环链表49
2.4.2双向链表50
2.4.3顺序存储结构与链表存储结构的综合分析与比较51
2.5单链表的应用52
2.5.1多项式相加的链表存储结点52
2.5.2多项式相加的算法实现53
2.6小结54
讨论小课堂255
习题255第3章栈和队列57
3.1栈57
3.1.1栈的定义57
3.1.2栈的抽象数据类型58
3.2栈的顺序存储结构及实现59
3.2.1栈的顺序存储结构59
3.2.2顺序栈的定义60
3.3栈的链表存储结构及实现62
3.4栈的应用65
3.4.1表达式的计算65
3.4.2子程序的嵌套调用67
3.4.3递归调用68
3.5队列69
3.5.1队列的定义及运算69
3.5.2队列的抽象数据类型70
3.6队列的顺序存储结构及实现70
3.7队列的链表存储结构及实现74
3.8队列的应用77
3.9算法实例——Hanoi塔问题78
3.10小结79
讨论小课堂380
习题381第4章串83
4.1串的基本概念83
4.1.1串的定义83
4.1.2串的抽象数据类型84
4.2串的存储与基本操作的实现85
4.2.1定长顺序串86
4.2.2堆串86
4.2.3块链串87
4.2.4串操作的实现88
4.3串的模式匹配91
4.3.1朴素模式匹配算法92
4.3.2模式匹配的KMP算法92
4.4串的应用举例：文本编辑97
4.5小结99
讨论小课堂499
习题4100第5章数组和广义表101
5.1数组102
5.1.1数组的基本概念102
5.1.2二维数组102
5.1.3数组的顺序存储方式103
5.2矩阵的压缩存储104
5.2.1特殊矩阵104
5.2.2稀疏矩阵107
5.3广义表112
5.3.1广义表的定义112
5.3.2广义表的存储结构113
5.4案例分析116
5.4.1概述和方法116
5.4.2算法和程序118
5.5小结120
讨论小课堂5120
习题5120第6章树与二叉树122
6.1树的概念及术语123
6.1.1树的定义123
6.1.2树的抽象数据类型124
6.1.3树的表示方式125
6.2二叉树125
6.2.1二叉树的定义125
6.2.2二叉树的抽象数据类型126
6.2.3二叉树的重要性质127
6.2.4二叉树的存储结构128
6.3二叉树的遍历130
6.3.1先序遍历131
6.3.2中序遍历131
6.3.3后根遍历132
6.3.4按层遍历133
6.3.5非递归遍历算法133
6.3.6二叉树的建立136
6.3.7二叉树遍历的应用举例137
6.4二叉树与树、森林的转换139
6.4.1树与二叉树的转换139
6.4.2森林与二叉树的转换140
6.5树的存储结构141
6.5.1树的双亲表示法142
6.5.2孩子表示法142
6.5.3孩子兄弟表示法143
6.6树的遍历144
6.6.1一般树的遍历144
6.6.2森林的遍历145
6.7二叉树的应用146
6.7.1哈夫曼树146
6.7.2哈夫曼树的构造146
6.7.3哈夫曼树的实现算法148
6.7.4哈夫曼编码149
6.8小结150
讨论小课堂6150
习题6150第7章图153
7.1图的基本概念153
7.1.1图的定义153
7.1.2图的术语155
7.1.3图的抽象数据类型156
7.2图的存储结构157
7.2.1图的邻接矩阵157
7.2.2邻接矩阵表示法的描述159
7.2.3邻接矩阵表示下的基本操作的实现160
7.2.4图的邻接链表161
7.2.5图的邻接表表示法的描述162
7.2.6邻接表表示下基本操作的实现163
7.3图的遍历与图的连通性165
7.3.1图的深度优先遍历166
7.3.2图的广度优先遍历168
7.3.3非连通图和连通分量170
7.4图的最小生成树170
7.4.1最小生成树的基本概念170
7.4.2普里姆(Prim)算法171
7.4.3克鲁斯卡尔（Kruskal）算法174
7.5最短路径175
7.5.1从某顶点到其余各顶点的最短路径175
7.5.2每对顶点之间的最短路径178
7.6拓扑排序与关键路径180
7.6.1拓扑排序180
7.6.2关键路径183
7.7图的应用189
7.7.1图在路由器寻径中的应用189
7.7.2图在物流信息系统中应用190
7.8小结190
讨论题7191
习题7191第8章查找193
8.1查找的基本概念194
8.2静态查找表195
8.2.1顺序表的查找195
8.2.2有序表的折半查找196
8.2.3索引顺序表查找200
8.3动态查找表201
8.3.1二叉排序树201
8.3.2平衡二叉树210
8.4案例分析214
8.4.1直方图问题214
8.4.2箱子装载问题216
8.5小结218
讨论小课堂8218
习题8219第9章排序220
9.1排序的基本概念220
9.2插入排序221
9.2.1直接插入排序221
9.2.2折半插入排序222
9.2.3希尔排序222
9.3交换排序224
9.3.1冒泡排序224
9.3.2快速排序225
9.4选择排序229
9.4.1简单选择排序229
9.4.2堆排序230
9.5归并排序233
9.6基数排序235
9.7小结239
讨论小课堂9240
习题9240第10章索引结构与哈希242
10.1静态索引结构242
10.1.1索引表242
10.1.2索引表查找242
10.2动态索引结构（B-树和B+树）245
10.2.1B-树的定义245
10.2.2B-树的运算246
10.2.3B+树249
10.3键树及Trie树250
10.3.1键树的定义250
10.3.2双链树251
10.3.3Trie树252
10.4哈希表及其查找253
10.4.1哈希表与哈希函数253
10.4.2构造哈希函数的常用方法254
10.4.3解决冲突的主要方法256
10.4.4哈希查找的性能分析260
10.5小结261
讨论小课堂10262
习题10262参考文献265

前言/序言

前言
数据结构与算法是计算机专业重要的专业基础课程与核心课程之一。从理论上讲，通过学习数据结构可以使学生掌握对不同数据结构的组织方法和对具体数据结构所实施的若干算法，并能分析算法的优劣。学习数据结构与算法的最终目的是提高学生的程序设计水平和能力。
对于应用型人才培养应该注重能力的培养，而不是只满足于理论的掌握。因此，在《数据结构与算法（第2版）/计算机系列教材》的编写过程中遵循谭浩强教授提出的新三部曲“提出问题—解决问题—归纳分析”的写法，强调从实践中获取知识。《数据结构与算法（第2版）/计算机系列教材》给出了能够解决实际问题的大量算法，希望学生在阅读和总结这些算法的基础上提高程序设计的水平。因此，《数据结构与算法（第2版）/计算机系列教材》的大部分算法只要经过简单的修改就能上机运行，具有很好的实用价值，也给学习者带来了方便。
（1）深入浅出，通俗易懂。对数据结构的基本概念、基本理论的阐述注重科学严谨。同时从应用出发，对新概念的引入从实例着手。对各种基本算法描述尽量详细，叙述清楚。《数据结构与算法（第2版）/计算机系列教材》在讲解数据的存储结构时，使用了大量的图示和表格，有助于学生对数据结构的理解。
（2）理论联系实际。为了巩固所学的理论知识，每章都附有练习题和讨论题，供学生进行书面练习、上机作业时选用和讨论。针对学生中普遍存在的“只懂概念不懂编程”的问题，配套有完整的习题与实验指导书，每一章节都给出了完整的C语言和C++源程序示例，供学生参考模拟，从而提高学生的程序设计能力。数据结构课程的一个重要任务是培养学生进行复杂程序设计的能力，目的在于提高学生的程序设计能力和进行规范化程序设计的素养。
（3）循序渐进，逐步加深。由于采用了C语言和C++语言面向对象的方法描述数据结构，对于低年级学生来说存在一定难度。为了使读者更好地学习数据结构自身的知识内容，克服描述工具所带来的困难，《数据结构与算法（第2版）/计算机系列教材》对此做了独特处理。
《数据结构与算法（第2版）/计算机系列教材》可以作为普通高等院校计算机专业本科和专升本的教材。由于资源翔实、通俗易懂，对书中内容适当取舍之后，也可作为高等职业技术和专科教育的计算机专业教材。同时，《数据结构与算法（第2版）/计算机系列教材》还可作为研究生考试和各类认证考试的复习参考书，以及计算机应用工作者和工程技术人员的参考书。
《数据结构与算法（第2版）/计算机系列教材》由汪沁、奚李峰主编。其中，第1～3章、第9章和实验指导由汪沁、奚李峰编写；第6章、第10章由邓芳编写；第4章、第7章由刘晓利编写；第5章、第8章由金冉、陈慧编写。《数据结构与算法（第2版）/计算机系列教材》由汪沁、奚李峰统编。考虑到在数据结构与算法的学习中，教师需要在课堂上对大量的算法进行讲解，而学生应该在此基础上大量阅读并理解数据结构经典算法，因此《数据结构与算法（第2版）/计算机系列教材》对算法都进行了较为详细的注释。对一些难度比较大的算法，在用语言描述之前，还对算法进行了分析。
由于编者水平有限，疏漏在所难免，欢迎广大读者批评指正并提出宝贵意见。
编者2018年5月


其他推荐