算法与数据结构（C++语言版）

作者: 冯广慧

出版社: 电子工业出版社

出版时间: 2018-10

版次: 1

ISBN: 9787121350719

定价: 56.00

装帧: 其他

分类: 计算机与互联网

本书按照“全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综合考试大纲”的要求编写，基本涵盖所有知识点，并加入部分高校及全国统一考试真题作为自测题，同时给出参考答案和题目解析。本书主要介绍各种常用的经典数据结构（如线性表、栈、队列、串、数组、树、图、集合等）和算法，并在时间复杂度和空间复杂度之间进行平衡与取舍。
  本书将C++语言作为数据结构的算法描述语言，将数据结构与面向对象技术有机结合。书中的算法讲解都有完整的C++代码实现，并在Visual Studio 2010环境下编译通过。冯广慧，2004年毕业于吉林大学获工学学士学位，2007年毕业于吉林大学研究生院获工学硕士学位，自2007年起一直从事于《算法与数据结构》课程的一线教学和考研辅导工作，对该课程有深入研究，参编《C语言程序设计教程》、《Access数据库程序设计真题考点分析与讲解》等多部著作。第1章  概论1

1.1  什么是数据结构1

1.2  基本概念和术语4

1.3  算法和算法分析7

1.3.1  算法的定义及特性7

1.3.2  算法的设计要求8

1.3.3  算法效率的衡量方法9

1.3.4  算法的时间复杂度10

1.3.5  算法的空间复杂度15

1.4  抽象数据类型16

习题18

第2章  线性表20

2.1  线性表的类型定义20

2.1.1  线性表的概念20

2.1.2  线性表的抽象数据类型21

2.2  线性表的顺序表示和实现22

2.2.1  线性表的顺序表示22

2.2.2  顺序表基本运算的实现23

2.3  线性表的链式表示和实现28

2.3.1  线性表的链式表示29

2.3.2  单链表上基本运算的实现32

2.4  双链表40

2.5  循环链表44

2.6  线性表实现方法的比较46

2.7  算法设计举例47

习题52

第3章  栈和队列55

3.1  栈55

3.1.1  栈的类型定义55

3.1.2  顺序栈的表示和实现57

3.1.3  链栈的表示和实现60

3.2  栈的应用举例62

3.2.1  十进制数转换为其他进制数62

3.2.2  表达式中括号的匹配检查63

3.2.3  表达式求值64

3.2.4  利用栈消除递归72

3.3  队列77

3.3.1  队列的类型定义77

3.3.2  循环队列—队列的顺序表示和

实现78

3.3.3  链队列—队列的链式表示和

实现82

3.4  算法设计举例83

习题87

第4章  串90

4.1  串的基本概念90

4.2  串的表示和实现91

4.2.1  串的顺序存储结构91

4.2.2  串的链式存储结构94

4.3  串的模式匹配95

4.3.1  朴素的模式匹配算法95

4.3.2  KMP算法96

习题101

第5章  数组104

5.1  数组的基本概念104

5.2  矩阵的压缩存储107

5.2.1  特殊矩阵107

5.2.2  稀疏矩阵110

5.3  算法设计举例117

习题121

第6章  树和二叉树124

6.1  树的概念124

6.2  二叉树的概念和性质126

6.2.1  二叉树的概念和抽象数据

类型126

6.2.2  二叉树的性质129

6.3  二叉树的表示和实现131

6.3.1  二叉树的存储结构131

6.3.2  二叉树的遍历运算133

6.3.3  二叉树的其他基本运算140

6.4  树和森林142

6.4.1  树的存储结构143

6.4.2  树、森林和二叉树的相互

转换146

6.4.3  树和森林的遍历运算148

6.4.4  树和森林的其他基本运算151

*6.5  线索二叉树154

6.5.1  线索二叉树的概念154

6.5.2  线索二叉树的基本运算157

6.6  算法设计举例161

习题162

第7章  树和二叉树的应用166

*7.1  表达式树166

7.2  哈夫曼树和哈夫曼编码171

7.2.1  哈夫曼树171

7.2.2  哈夫曼编码175

7.3  堆和优先级队列178

7.3.1  堆178

7.3.2  优先级队列179

*7.4  并查集184

7.5  算法设计举例187

习题189

第8章  图191

8.1  图的概念191

8.2  图的存储结构196

8.2.1  邻接矩阵196

8.2.2  邻接表200

*8.2.3  十字链表205

*8.2.4  邻接多重表205

8.3  图的遍历206

8.3.1  深度优先遍历207

8.3.2  广度优先遍历209

8.3.3  图的连通分量和生成树212

习题213

第9章  图的应用217

9.1  最小生成树217

9.1.1  最小生成树的概念217

9.1.2  Prim算法218

9.1.3  Kruskal算法222

9.2  有向无环图及其应用225

9.2.1  拓扑排序225

9.2.2  关键路径230

9.3  最短路径236

9.3.1  单源点最短路径236

9.3.2  每对顶点之间的最短路径240

习题243

第10章  集合与查找247

10.1  基本概念247

10.2  静态查找表上的查找248

10.2.1  顺序查找248

10.2.2  折半查找250

10.2.3  分块查找254

10.3  动态查找表上的查找256

10.3.1  二叉查找树256

10.3.2  平衡二叉树263

*10.3.3  B树275

*10.3.4  B+树280

*10.3.5  字典树281

10.4  算法设计举例282

习题285

第11章  散列表288

11.1  散列表的概念288

11.2  构造散列函数的方法289

11.2.1  直接定址法289

11.2.2  折叠法289

11.2.3  数字分析法289

11.2.4  平方取中法290

11.2.5  除留余数法290

11.3  解决冲突的方法291

11.3.1  闭散列法291

11.3.2  开散列法293

11.4  散列表的实现294

11.4.1  闭散列表的表示和实现294

11.4.2  开散列表的表示和实现298

11.4.3  闭散列表与开散列表的

比较302

11.5  散列表的查找性能分析302

习题303

第12章  排序306

12.1  排序的基本概念306

12.2  插入排序307

12.2.1  直接插入排序307

12.2.2  折半插入排序308

12.2.3  希尔排序309

12.3  交换排序310

12.3.1  冒泡排序310

12.3.2  快速排序311

12.4  选择排序315

12.4.1  直接选择排序315

12.4.2  堆排序316

*12.4.3  锦标赛排序320

12.5  归并排序320

*12.6  基数排序322

12.7  各种内部排序方法的比较324

*12.8  外部排序327

12.8.1  置换选择排序328

12.8.2  多路归并排序330

习题331

附录A  上机实验参考题目334

参考文献336
内容简介:
本书按照“全国硕士研究生招生考试计算机科学与技术学科联考计算机学科专业基础综合考试大纲”的要求编写，基本涵盖所有知识点，并加入部分高校及全国统一考试真题作为自测题，同时给出参考答案和题目解析。本书主要介绍各种常用的经典数据结构（如线性表、栈、队列、串、数组、树、图、集合等）和算法，并在时间复杂度和空间复杂度之间进行平衡与取舍。
本书将C++语言作为数据结构的算法描述语言，将数据结构与面向对象技术有机结合。书中的算法讲解都有完整的C++代码实现，并在Visual Studio 2010环境下编译通过。
作者简介:
冯广慧，2004年毕业于吉林大学获工学学士学位，2007年毕业于吉林大学研究生院获工学硕士学位，自2007年起一直从事于《算法与数据结构》课程的一线教学和考研辅导工作，对该课程有深入研究，参编《C语言程序设计教程》、《Access数据库程序设计真题考点分析与讲解》等多部著作。
目录:
第1章  概论1

1.1  什么是数据结构1

1.2  基本概念和术语4

1.3  算法和算法分析7

1.3.1  算法的定义及特性7

1.3.2  算法的设计要求8

1.3.3  算法效率的衡量方法9

1.3.4  算法的时间复杂度10

1.3.5  算法的空间复杂度15

1.4  抽象数据类型16

习题18

第2章  线性表20

2.1  线性表的类型定义20

2.1.1  线性表的概念20

2.1.2  线性表的抽象数据类型21

2.2  线性表的顺序表示和实现22

2.2.1  线性表的顺序表示22

2.2.2  顺序表基本运算的实现23

2.3  线性表的链式表示和实现28

2.3.1  线性表的链式表示29

2.3.2  单链表上基本运算的实现32

2.4  双链表40

2.5  循环链表44

2.6  线性表实现方法的比较46

2.7  算法设计举例47

习题52

第3章  栈和队列55

3.1  栈55

3.1.1  栈的类型定义55

3.1.2  顺序栈的表示和实现57

3.1.3  链栈的表示和实现60

3.2  栈的应用举例62

3.2.1  十进制数转换为其他进制数62

3.2.2  表达式中括号的匹配检查63

3.2.3  表达式求值64

3.2.4  利用栈消除递归72

3.3  队列77

3.3.1  队列的类型定义77

3.3.2  循环队列—队列的顺序表示和

实现78

3.3.3  链队列—队列的链式表示和

实现82

3.4  算法设计举例83

习题87

第4章  串90

4.1  串的基本概念90

4.2  串的表示和实现91

4.2.1  串的顺序存储结构91

4.2.2  串的链式存储结构94

4.3  串的模式匹配95

4.3.1  朴素的模式匹配算法95

4.3.2  KMP算法96

习题101

第5章  数组104

5.1  数组的基本概念104

5.2  矩阵的压缩存储107

5.2.1  特殊矩阵107

5.2.2  稀疏矩阵110

5.3  算法设计举例117

习题121

第6章  树和二叉树124

6.1  树的概念124

6.2  二叉树的概念和性质126

6.2.1  二叉树的概念和抽象数据

类型126

6.2.2  二叉树的性质129

6.3  二叉树的表示和实现131

6.3.1  二叉树的存储结构131

6.3.2  二叉树的遍历运算133

6.3.3  二叉树的其他基本运算140

6.4  树和森林142

6.4.1  树的存储结构143

6.4.2  树、森林和二叉树的相互

转换146

6.4.3  树和森林的遍历运算148

6.4.4  树和森林的其他基本运算151

*6.5  线索二叉树154

6.5.1  线索二叉树的概念154

6.5.2  线索二叉树的基本运算157

6.6  算法设计举例161

习题162

第7章  树和二叉树的应用166

*7.1  表达式树166

7.2  哈夫曼树和哈夫曼编码171

7.2.1  哈夫曼树171

7.2.2  哈夫曼编码175

7.3  堆和优先级队列178

7.3.1  堆178

7.3.2  优先级队列179

*7.4  并查集184

7.5  算法设计举例187

习题189

第8章  图191

8.1  图的概念191

8.2  图的存储结构196

8.2.1  邻接矩阵196

8.2.2  邻接表200

*8.2.3  十字链表205

*8.2.4  邻接多重表205

8.3  图的遍历206

8.3.1  深度优先遍历207

8.3.2  广度优先遍历209

8.3.3  图的连通分量和生成树212

习题213

第9章  图的应用217

9.1  最小生成树217

9.1.1  最小生成树的概念217

9.1.2  Prim算法218

9.1.3  Kruskal算法222

9.2  有向无环图及其应用225

9.2.1  拓扑排序225

9.2.2  关键路径230

9.3  最短路径236

9.3.1  单源点最短路径236

9.3.2  每对顶点之间的最短路径240

习题243

第10章  集合与查找247

10.1  基本概念247

10.2  静态查找表上的查找248

10.2.1  顺序查找248

10.2.2  折半查找250

10.2.3  分块查找254

10.3  动态查找表上的查找256

10.3.1  二叉查找树256

10.3.2  平衡二叉树263

*10.3.3  B树275

*10.3.4  B+树280

*10.3.5  字典树281

10.4  算法设计举例282

习题285

第11章  散列表288

11.1  散列表的概念288

11.2  构造散列函数的方法289

11.2.1  直接定址法289

11.2.2  折叠法289

11.2.3  数字分析法289

11.2.4  平方取中法290

11.2.5  除留余数法290

11.3  解决冲突的方法291

11.3.1  闭散列法291

11.3.2  开散列法293

11.4  散列表的实现294

11.4.1  闭散列表的表示和实现294

11.4.2  开散列表的表示和实现298

11.4.3  闭散列表与开散列表的

比较302

11.5  散列表的查找性能分析302

习题303

第12章  排序306

12.1  排序的基本概念306

12.2  插入排序307

12.2.1  直接插入排序307

12.2.2  折半插入排序308

12.2.3  希尔排序309

12.3  交换排序310

12.3.1  冒泡排序310

12.3.2  快速排序311

12.4  选择排序315

12.4.1  直接选择排序315

12.4.2  堆排序316

*12.4.3  锦标赛排序320

12.5  归并排序320

*12.6  基数排序322

12.7  各种内部排序方法的比较324

*12.8  外部排序327

12.8.1  置换选择排序328

12.8.2  多路归并排序330

习题331

附录A  上机实验参考题目334

参考文献336

查看详情

算法与数据结构（C++语言版）

内容简介:

作者简介:

目录: