数据结构（Java语言描述）

图书标准信息

• 作者 丁海军 编
• 出版社 电子工业出版社
• 出版时间 2015-12
• 版次 1
• ISBN 9787121275302
• 定价 39.80元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 304页
• 字数 486千字

【内容简介】

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

【作者简介】

丁海军，河海大学河海大学计算机及信息工程学院（常州）计算机系副教授、副主任。研究方向为人工智能及智能算法。

【目录】

第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