数据结构与算法（C++版）（第2版）

图书标准信息

• 作者 游洪跃 唐宁九 孙界平 朱宏 张卫华 周欣 杨秋辉 张芮菁
• 出版社 清华大学出版社
• 出版时间 2020-11
• 版次 2
• ISBN 9787302557746
• 定价 69.00元
• 装帧 其他
• 开本 16开
• 纸张 胶版纸

【内容简介】

本书内容包括：线性表、栈和队列、串、数组和广义表、树、图、文件、算法设计技术与分析技术问题。

【作者简介】

唐宁九，教授，硕士生导师，四川省计算机用户协会副秘书长，中国计算机用户协会理事，加拿大滑铁卢大学计算机系访问学者，主持、参与“863项目”、“九.五攻关项目”五项，主持、参与横向科研课题6项，在核心期刊上发表论文三十余篇，主编专著一本，主编教材一本，参加编写教材3本。

【目录】

第1章  绪论1

1.1  数据结构的概念和学习数据结构的必要性1

1.2  数据结构的基本概念2

1.2.1  数据2

1.2.2  数据元素和数据项2

1.2.3  数据结构3

1.3  抽象数据类型及其实现4

1.3.1  数据类型4

1.3.2  抽象数据类型4

1.4  算法和算法分析4

1.4.1  算法4

1.4.2  算法分析5

1.5  实例研究: 生命游戏7

1.6  深入学习导读13

1.7  习题13

 

第2章  线性表14

2.1  线性表的逻辑结构14

2.2  线性表的顺序存储结构16

2.3  线性表的链式存储结构23

2.3.1  单链表23

2.3.2  循环链表32

2.3.3  双向链表35

2.3.4  在链表结构中保存当前位置和元素个数39

2.4  实例研究: 计算任意大整数的阶乘42

2.5  深入学习导读45

2.6  习题45

 

第3章  栈和队列46

3.1  栈46

3.1.1  栈的基本概念46

3.1.2  顺序栈47

3.1.3  链式栈52

3.2  队列59

3.2.1  队列的基本概念59

3.2.2  链队列60

3.2.3  循环队列——队列的顺序存储结构65

3.2.4  队列应用——显示二项式(a b)i的系数70

3.3  优先队列71

3.4  实例研究: 表达式求值75

3.5  深入学习导读79

3.6  习题79

 

第4章  串80

4.1  串类型的定义80

4.2  字符串的实现81

4.3  字符串模式匹配算法86

4.3.1  简单字符串模式匹配算法86

4.3.2  首尾字符串模式匹配算法88

4.3.3  KMP字符串模式匹配算法88

4.4  实例研究: 文本编辑94

4.5  深入学习导读103

4.6  习题103

 

第5章  数组和广义表105

5.1  数组105

5.1.1  数组的基本概念105

5.1.2  数组的顺序表105

5.1.3  数组的类模板定义107

5.2  矩阵111

5.2.1  矩阵的定义和操作111

5.2.2  特殊矩阵113

5.2.3  稀疏矩阵118

5.3  广义表130

5.3.1  基本概念130

5.3.2  广义表的存储结构132

5.4  实例研究: 稳定伴侣问题142

5.5  深入学习导读145

5.6  习题146

 

第6章  树和二叉树147

6.1  树的基本概念147

6.1.1  树的定义147

6.1.2  基本术语147

6.2  二叉树149

6.2.1  二叉树的定义149

6.2.2  二叉树的性质151

6.2.3  二叉树的存储结构153

6.3  二叉树遍历162

6.3.1  遍历的定义162

6.3.2  遍历算法163

6.3.3  二叉树遍历应用举例169

6.4  线索二叉树174

6.4.1  线索的概念174

6.4.2  线索二叉树的实现176

6.5  树和森林的实现184

6.5.1  树的存储表示184

6.5.2  树的显示191

6.5.3  森林的存储表示192

6.5.4  树和森林的遍历197

6.5.5  将树和森林与二叉树相互转换199

6.6  哈夫曼树与哈夫曼编码202

6.6.1  哈夫曼树的基本概念202

6.6.2  哈夫曼树构造算法203

6.6.3  哈夫曼编码204

6.6.4  哈夫曼树的实现205

6.7  树的计数209

6.8  树在等价关系上的应用212

6.9  实例研究: 哈夫曼压缩算法216

6.1  0深入学习导读221

6.1  1习题222

 

第7章  图223

7.1  图的定义和术语223

7.2  图的存储表示227

7.2.1  邻接矩阵227

7.2.2  邻接表232

7.3  图的遍历240

7.3.1  深度优先搜索240

7.3.2  广度优先搜索242

7.4  连通无向网的*小代价生成树244

7.4.1  Prim算法244

7.4.2  Kruskal算法247

7.5  有向无环图及应用250

7.5.1  拓扑排序251

7.5.2  关键路径253

7.6  *短路径257

7.6.1  单源点*短路径问题258

7.6.2  所有顶点之间的*短路径261

7.7  实例研究: 周游世界问题——哈密顿圈263

7.8  深入学习导读265

7.9  习题265

 

第8章  查找267

8.1  查找的基本概念267

8.2  静态表的查找267

8.2.1  顺序查找267

8.2.2  有序表的查找268

8.3  动态查找表272

8.3.1  二叉排序树272

8.3.2  平衡二叉树282

8.3.3  B树和B 树306

8.4  哈希表309

8.4.1  哈希表的概念309

8.4.2  构造哈希函数的方法309

8.4.3  处理冲突的方法309

8.4.4  哈希表的实现311

8.5  实例研究: 查找3个数组的*小共同元素316

8.6  深入学习导读317

8.7  习题317

 

第9章  排序319

9.1  概述319

9.2  插入排序320

9.2.1  直接插入排序320

9.2.2  Shell排序321

9.3  交换排序323

9.3.1  冒泡排序323

9.3.2  快速排序324

9.4  选择排序327

9.4.1  简单选择排序327

9.4.2  堆排序328

9.5  归并排序332

9.6  基数排序336

9.6.1  多关键字排序336

9.6.2  基数排序337

9.7  各种内部排序方法讨论339

9.8  外部排序341

9.8.1  外部排序基础341

9.8.2  外部排序的方法342

9.9  实例研究: 用堆实现优先队列343

9.1  0深入学习导读346

9.1  1习题346

 

第10章  文件348

10.1  主存储器和辅助存储器348

10.2  各种常用文件结构348

10.2.1  顺序文件348

10.2.2  索引文件349

10.2.3  哈希文件350

10.3  实例研究350

10.3.1  VSAM文件350

10.3.2  多关键字文件351

10.4  深入学习导读353

10.5  习题353

 

第11章  算法设计与分析354

11.1  算法设计354

11.1.1  递归算法354

11.1.2  分治算法356

11.1.3  动态规划算法357

11.1.4  贪婪算法358

11.1.5  回溯法359

11.1.6  分支限界法361

11.2  算法分析363

11.2.1  递归分析363

11.2.2  利用生成函数进行分析364

11.3  实例研究: 图着色问题366

11.4  深入学习导读368

11.5  习题368

 

参考文献370

附录A调和级数371

附录B泊松分布372

附录C配套软件包文件索引373

附录D主流C  开发环境的使用方法379