图书详情

配套资源图书内容样章/电子教材图书评价

配套资源

本书资源

本书暂无资源

会员上传本书资源

图书内容

内容简介

本书以作者多年数据结构课程教学经验为基础编写而成。全书共9章，第1章介绍了数据结构的基本概念及算法复杂度分析的详细框架和步骤；第2~5章是对线性结构的详细介绍，这一部分是整个数据结构的基础，包括顺序表、链表、栈、队列、稀疏矩阵以及线性表的查找和排序等内容；第6~8章主要研究树结构，第6章介绍了二叉树及树的性质、遍历算法及其应用，第7章研究了查找二叉树及相关算法，第8章介绍了堆结构及其应用；第9章介绍了图结构及关于图的几个基础算法。本书以Java语言作为数据结构及算法的描述语言，以Java环境的集合框架为参照组织教学内容，便于读者更好地将课程内容运用到实际的软件开发过程中。本书配套有PPT、习题解答等。

图书详情

ISBN：9787121275302

开本：16开

页数：304

字数：486

本书目录

第1章  绪  论	1
1.1  数据结构的概念	1
1.1.1  为什么要学习数据结构	2
1.1.2  有关概念和术语	4
1.1.3  数据结构的三要素	5
1.2  抽象数据类型	6
1.2.1  数据类型	6
1.2.2  抽象数据类型	7
1.3  算法概念及算法设计的问题	8
1.3.1  什么是算法	8
1.3.2  算法特性	10
1.3.3  算法的结构和表示方法	10
1.3.4  算法设计原则	11
1.3.5  几种基本的算法设计方法和策略	12
1.3.6  编程解决问题的一般步骤	12
1.4  算法分析	13
1.4.1  时间复杂度分析的两类方法	13
1.4.2  时间复杂度分析的理论框架	14
1.4.3  非递归算法时间复杂度分析步骤	19
1.4.4  典型非递归算法的时间复杂度类型	20
1.4.5  递归算法时间复杂度分析步骤	22
1.4.6  空间复杂度	23
1.5  数据结构课程的内容	23
1.6  习题	24
第2章  线性表	27
2.1  线性表的逻辑结构	27
2.2  顺序表概念及存储特点	29
2.2.1  顺序表的逻辑特点	29
2.2.2  顺序表面向对象描述	29
2.3  顺序表的重要算法及实现	31
2.3.1  初始化	31
2.3.2  顺序表容量管理	31
2.3.3  数据存取	32
2.3.4  向顺序表中插入元素	33
2.3.5  删除顺序表中的元素	34
2.3.6  查找元素	35
2.3.7  顺序表中元素的有序插入与排序	36
2.3.8  顺序表转换为数组	37
2.3.9  顺序表转换为字符串	38
2.4  单链表概念及类定义	38
2.4.1  单链表基本概念	38
2.4.2  链表面向对象描述	41
2.5  单链表重要算法实现	44
2.5.1  数据存取	44
2.5.2  向链表中插入元素	44
2.5.3  删除链表节点	47
2.5.4  查找节点	49
2.5.5  向链表中有序插入节点	50
2.5.6  链表排序	52
2.5.7  链表转换为字符串和数组	53
2.6*  链表迭代器	54
2.6.1  迭代器的概念	54
2.6.2  与迭代器有关的Java语言特性	55
2.6.3  链表类LinkList迭代器的实现	56
2.7  循环链表与双向链表	58
2.7.1  循环链表	58
2.7.2  双向链表	59
2.8*  顺序表和链表的比较	60
2.9  习题	61
第3章  特殊的线性结构	64
3.1  栈	64
3.1.1  基本概念	64
3.1.2  链栈——栈的链表实现	65
3.1.3  顺序栈——栈的数组实现	66
3.1.4  表达式求值	68
3.2  队列	72
3.2.1  队列概念	72
3.2.2  链式队列	73
3.2.3  顺序队列	74
3.2.4  循环队列	75
3.2.5  队列应用	76
3.3  特殊矩阵	78
3.3.1  矩阵存储方式	78
3.3.2  对称矩阵和三角矩阵	79
3.3.3  对角矩阵	80
3.4  稀疏矩阵	81
3.4.1  三元组	81
3.4.2  矩阵抽象数据类型	82
3.4.3  稀疏矩阵的三元组顺序表表示	83
3.4.4  稀疏矩阵的行链表表示	88
3.4.5  稀疏矩阵的十字链表表示	91
3.5  广义表	92
3.5.1  广义表的定义和基本运算	93
3.5.2  广义表的存储结构	95
3.6  习题	96
第4章  线性查找算法	99
4.1  查找的基本概念	99
4.1.1  什么是查找及查找结构	99
4.1.2  查找结构的分类	100
4.1.3  平均查找长度	100
4.2 线性查找表	100
4.2.1  顺序查找	100
4.2.2  二分查找	100
4.2.3  分块查找	102
4.2.4  顺序表三种查找方法的比较	103
4.3  哈希查找	103
4.3.1  哈希表	103
4.3.2  哈希函数的构造方法	104
4.3.3  处理冲突的方法	106
4.3.4  哈希查找算法性能分析	109
4.4  哈希映射	109
4.4.1  映射（Map）概念	109
4.4.2  哈希表实现映射	110
4.5  串匹配	112
4.5.1  简单的模式匹配算法	112
4.5.2  KMP模式匹配算法	114
4.6  习题	118
第5章  排序算法	122
5.1  基本概念	122
5.2  插入排序	122
5.2.1  算法设计	123
5.2.2  时间复杂度分析	124
5.3  选择排序	124
5.3.1  算法设计	124
5.3.2  时间复杂度分析	125
5.4  冒泡排序	126
5.4.1  算法设计	126
5.4.2  时间复杂度分析	127
5.5  快速排序	127
5.5.1  快速排序的思想	127
5.5.2  快速排序算法实现	128
5.5.3  时间复杂度分析	129
5.6  归并排序	130
5.6.1  有序表的合并算法	130
5.6.2  递归归并排序	131
5.6.3  迭代归并排序	132
5.6.4  时间复杂度分析	133
5.7  基数排序	134
5.7.1  桶排序	134
5.7.2  基数排序应用举例	134
5.8* 希尔排序	135
5.8.1  排序过程与算法设计	135
5.8.2  时间复杂度分析	137
5.9  习题	138
第6章  二叉树与树	145
6.1  树与二叉树一般概念	145
6.1.1  树	145
6.1.2  二叉树	146
6.2  二叉树的性质	148
6.3  二叉树存储结构	150
6.3.1  顺序存储	150
6.3.2  链式存储	151
6.4  二叉树遍历	152
6.4.1  二叉树遍历概念	152
6.4.2  先序遍历（DLR）	153
6.4.3  中序遍历（LDR）	154
6.4.4  后序遍历（LRD）	154
6.4.5  层次遍历	155
6.4.6  遍历的应用	156
6.4.7  根据已知的遍历序列恢复二叉树	157
6.5  哈夫曼（Huffman）树及其应用	159
6.5.1  最优二叉树（Huffman树）概念	159
6.5.2  Huffman树的构造方法	160
6.5.3  Huffman编码	162
6.5.4  Huffman编码、码算法实现	164
6.6  递归	172
6.6.1  递归调用树	172
6.6.2  递归栈	176
6.6.3  二叉树遍历的非递归算法	179
6.7  树和森林	182
6.7.1  基本概念	182
6.7.2  树的存储结构	182
6.7.3  树的遍历	185
6.7.4  树的深度优先搜索与回溯法	186
6.7.5  树与并查集	190
6.8  习题	192
第7章  查找树	198
7.1  二叉查找树概念	198
7.1.1  二叉查找树定义	198
7.1.2  二叉查找树的面向对象描述	199
7.2  二叉查找树主要算法	202
7.2.1  求最大、最小值算法	202
7.2.2  查找算法	202
7.2.3  插入算法	204
7.2.4  删除算法	206
7.2.5  时间复杂度分析	209
7.3  AVL平衡二叉树	210
7.3.1  平衡二叉树的概念	211
7.3.2  平衡调整	214
7.3.3  AVL树的查找算法	218
7.3.4  AVL树的插入算法	218
7.3.5  AVL树删除算法	219
7.3.6  AVL树时间复杂度分析	220
7.4  B-树	222
7.4.1  分块索引查找	222
7.4.2  B-树定义	222
7.4.3  B-树查找	223
7.4.4  B-树的插入	225
7.4.5  B-树删除	226
7.5  B+树	228
7.6  习题	229
第8章  堆与优先队列及堆排序	233
8.1堆	233
8.1.1  堆的基本算法	234
8.1.2  堆的实现	237
8.2  优先队列	239
8.3  堆排序	240
8.4  习题	241
第9章  图结构及相关算法	242
9.1  图的概念	242
9.1.1  什么是图	242
9.1.2  图论的基本概念	243
9.1.3  树和森林	246
9.2  图的基本操作与图的存储结构	246
9.2.1  图的基本操作	247
9.2.2  图的存储结构概述	250
9.2.3  图的邻接矩阵存储	250
9.2.4  图的邻接表存储	255
9.2.5  图的边集数组存储	260
9.3  图的遍历	261
9.3.1  深度优先遍历	261
9.3.2  广度优先遍历	263
9.3.3  利用图遍历算法研究图的连通性	264
9.4  最小生成树问题	266
9.4.1  图的生成树和生成森林	266
9.4.2  图的最小生成树概念	267
9.4.3  构造最小生成树的Prim算法	268
9.4.4  构造最小生成树的Kruskal算法	271
9.5  最短路径问题	273
9.5.1  从一个源点到其他各点的最短路径	274
9.5.2  所有点对之间的最短路径	278
9.6  拓扑排序问题	280
9.6.1  偏序关系	280
9.6.2  拓扑排序	280
9.6.3  拓扑排序应用	281
9.7*  关键路径问题	283
9.7.1  AOE网（Activity On Edge network）	283
9.7.2 关键路径	284
9.8  习题	287

展开

前言

数据结构是计算机科学与技术及相关专业的专业基础课程，该课程是软件设计与开发的重要理论与实践基础。对于计算机相关专业学生来说，数据结构课程是最有价值的课程之一。数据结构课程是一门理论与实践并重的课程，要求学生既要掌握数据结构的基本概念、基础理论，同时还要求学生掌握程序的设计、编写、调试、测试等技能；另外数据结构课程概念多，许多内容理论深奥，学习难度比较大，一直是计算机专业比较困难的课程之一。
对于计算机专业学生来说，区别于其他专业的核心能力有两个方面，其一是算法设计能力；其二是软件工程能力。由于历史原因，目前数据结构课程偏重于算法设计能力的学习和训练，而对软件工程能力的培养考虑则普遍不足。
本书精选课程内容，突出重点。希望在训练学生计算机专业核心能力方面起到一定作用。概括起来说，本书主要特色主要包括以下几个方面。
1．内容相对全面，注重基础，突出重点和难点
（1）本书包含了传统数据结构课程的主要内容，删除已经很少使用的线索二叉树、外排序等内容。对广义表只做概念性介绍，对于字符串只介绍匹配算法。增加了一般教材涉及较少但应用广泛的并查集、堆、优先队列等内容。
（2）对重点和难点内容花费更多的篇幅进行解释。对递归的深入理解历来是学习难点，我们将二叉树、栈与递归融合起来讲解。对哈夫曼编码解码算法、排序二叉树的删除算法、AVL平衡二叉树的平衡调节算法等传统的难点内容给出了更加详细的讲解和程序实现，以便于深入理解算法思想。
（3）将稀疏矩阵和图的存储统一起来。将图的各种存储表示方法看成是稀疏矩阵的表示，这样既贯通了知识点之间的联系，学生也更容易理解。
2．采用Java语言描述
现在绝大多数数据结构教材都采用C语言描述，我们选择Java作为课程描述语言主要基于以下几点考虑：
（1）希望学生在大学四年的学习中一以贯之地以某一种语言长期进行编程实践。在教学中我们发现，大学低年级学生一般使用C语言作为课程作业和实践的编程语言，但是到高年级进入到软件开发时，更多地使用Java、C#等这类表达能力更强的面向对象语言工具，这样往往会出现学生对程序设计语言学习了很多，但是精通的很少，基础教学与实践应用脱节的现象。因此我们希望从低年级开始在就使用Java作为编程语言和平台，从而为学生未来进行软件开发提供足够的训练。
（2）Java语言是一门工业级的面向对象的语言。其完善的面向对象特性对于描述各种复杂的数据结构特别适用。Java语言具有更好的抽象描述能力，描述抽象数据类型比较方便。Java语言是一种完善的但是比C++容易理解的面向对象的语言，面向对象语言比C语言这类单纯面向过程语言更便于描述各种复杂的数据结构。
（3）Java语言更加规范，适合尽早训练学生的工程意识。
3．注重算法和软件工程的平衡
传统的数据结构教材更多地从算法这个视角描述数据结构，这当然没有问题，毕竟“程序 = 数据结构+算法”，但是很多时候有意或无意地忽视了数据结构本身的描述和组织，不能从更为全局或者抽象的角度描述数据的结构和组织方式，忽视软件单元的重用、接口标准化等这样一些软件工程基本要素。从软件工程的角度看，如果我们在课程的学习过程中能潜移默化地培养学生有关软件工程的思维，将抽象、标准化、软件重用、设计模式等软件工程要素融合到数据结构的学习过程，可以更好地培养学生的工程意识。
本书中我们给出了一些主要数据结构的完整的程序代码，使学生在不冲淡算法学习这个主题的情况下，能学到从头设计基础类库的思维过程及需要考虑的一些因素。
我们给出的主要数据结构Java类尽可能与Java标准集合框架（Collection Frame）相对应，学生在学完本课程之后，对Java集合框架的内部实现细节会有一个基本的了解。同时也学会了如何逐渐设计一个复杂的基础类库。
程序设计能力的训练有其自身的规律，不可能一蹴而就，也没有捷径可走。计算机专业学生必须具有该专业的基本素质，熟练掌握一门程序设计语言，在此基础上掌握数据结构、算法的重要设计思想和一些常用算法。同时还要掌握一些重要的软件工程方法，只有这样才能为未来的职业生涯打好坚实基础。
本书除了算法的伪代码外，所有程序都在Java 7 和Java 8环境下调试通过。
本书由丁海军编著，在编写过程中，得到教育部“卓越工程师培养计划”和教育部“专业综合改革试点”项目的支持。
感谢电子工业出版社任欢欢编辑的支持鼓励。



丁海军    
2015年10月

展开

作者简介

本书暂无作者简介

样章试读

查看样章电子教材
图书评价我要评论

本书资源

会员上传本书资源

内容简介

图书详情

本书目录

前 言

作者简介

前言