数据结构与算法

第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.3.3 C++程序的典型构架5

1.3.4 C++的类和对象6

1.3.5 C++的友元函数7

1.3.6 运算符重载9

1.3.7 C++的参数传递12

1.3.8 C++的输入输出14

1.3.9 有关C++的动态存储分配15

1.3.1 0结构与类17

1.3.1 1C++的模板17

1.4 算法和算法分析19

1.4.1 算法19

1.4.2 算法分析20

1.5 实用程序软件包23

1.6 实例研究31

1.6.1 生命游戏31

1.6.2 计算任意位数的π31

1.7 深入学习导读38

习题138

上机实验题139

第2章 线性表41

2.1 线性表的逻辑结构41

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

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

2.3.1 单链表51

2.3.2 循环链表59

2.3.3 双向链表63

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

2.4 实例研究78

2.4.1 一元多项式的表示78

2.4.2 计算任意大整数的阶乘83

2.5 深入学习导读86

习题287

上机实验题287

第3章 栈和队列88

3.1 栈88

3.1.1 栈的基本概念88

3.1.2 顺序栈89

3.1.3 链式栈94

3.2 队列100

3.2.1 队列的基本概念100

3.2.2 链队列102

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

3.2.4 队列应用——显示二项式(a+b)i的系数111

3.3 优先队列112

3.4 实例研究116

3.4.1 表达式求值116

3.4.2 事件驱动模拟119

3.5 深入学习导读124

习题3125

上机实验题3125

第4章 串127

4.1 串类型的定义127

4.2 字符串的实现128

4.3 字符串模式匹配算法134

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

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

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

4.4 实例研究141

4.4.1 文本编辑141

4.4.2 查找子序列142

4.5 深入学习导读143

习题4143

上机实验题4143

第5章 数组和广义表144

5.1 数组144

5.1.1 数组的基本概念144

5.1.2 数组的顺序存储方式144

5.1.3 数组的类定义147

5.2 矩阵150

5.2.1 矩阵的定义和操作150

5.2.2 特殊矩阵152

5.2.3 稀疏矩阵157

5.3 广义表167

5.3.1 基本概念167

5.3.2 广义表的存储结构169

5.4 实例研究179

5.4.1 稳定伴侣问题179

5.4.2 m元多项式的表示179

5.5 深入学习导读182

习题5183

上机实验题5183

第6章 树和二叉树184

6.1 树的基本概念184

6.1.1 树的定义184

6.1.2 基本术语184

6.2 二叉树186

6.2.1 二叉树的定义186

6.2.2 二叉树的性质188

6.2.3 二叉树的存储结构190

6.3 二叉树遍历199

6.3.1 遍历的定义199

6.3.2 遍历算法200

6.3.3 二叉树遍历应用举例206

6.4 线索二叉树211

6.4.1 线索的概念211

6.4.2 线索二叉树的实现213

6.5 树和森林221

6.5.1 树的存储表示221

6.5.2 树的显示228

6.5.3 森林的存储表示228

6.5.4 树和森林的遍历233

6.5.5 树和森林与二叉树的转换235

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

6.6.1 哈夫曼树的基本概念238

6.6.2 哈夫曼树构造算法239

6.6.3 哈夫曼编码239

6.6.4 哈夫曼树的实现241

6.7 树的计数245

6.8 实例研究247

6.8.1 树与等价关系247

6.8.2 Huffman压缩算法251

6.9 深入学习导读256

习题6256

上机实验题6257

第7章 图258

7.1 图的定义和术语258

7.2 图的存储表示262

7.2.1 邻接矩阵262

7.2.2 邻接表267

7.3 图的遍历274

7.3.1 深度优先搜索275

7.3.2 广度优先搜索276

7.4 图的最小代价生成树277

7.4.1 Prim算法278

7.4.2 Kruskal算法280

7.5 有向无环图及应用284

7.5.1 拓扑排序284

7.5.2 关键路径287

7.6 最短路径291

7.6.1 单源点最短路径问题291

7.6.2 所有顶点之间的最短路径294

7.7 实例研究296

7.7.1 周游世界问题——哈密尔顿圈296

7.7.2 一笔画问题——欧拉问题298

7.8 深入学习导读299

习题7299

上机实验题7301

第8章 查找302

8.1 查找的基本概念302

8.2 静态表的查找305

8.2.1 顺序查找305

8.2.2 有序表的查找306

8.3 动态查找表309

8.3.1 二叉排序树309

8.3.2 二叉平衡树319

8.3.3 B树和B+树343

8.4 散列表345

8.4.1 散列表的概念345

8.4.2 构造散列函数的方法345

8.4.3 处理冲突的方法346

8.4.4 散列表的实现347

8.5 实例研究352

8.5.1 查找3个数组的最小共同元素352

8.5.2 查找最小元素353

8.6 深入学习导读354

习题8354

上机实验题8355

第9章 排序356

9.1 概述356

9.2 插入排序357

9.2.1 直接插入排序357

9.2.2 Shell排序358

9.3 交换排序360

9.3.1 起泡排序360

9.3.2 快速排序361

9.4 选择排序364

9.4.1 简单选择排序364

9.4.2 堆排序365

9.5 归并排序368

9.6 基数排序373

9.6.1 多关键排序373

9.6.2 基数排序373

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

9.8 外部排序378

9.8.1 外部排序基础378

9.8.2 外部排序的方法378

9.9 实例研究380

9.9.1 宴会中来宾数目的最大值380

9.9.2 各种排序算法运行时间测试382

9.9.3 用堆实现优先队列385

9.10 深入学习导读388

习题9388

上机实验题9389

第10章 文件390

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

10.2 各种常用文件结构390

10.2.1 顺序文件390

10.2.2 索引文件391

10.2.3 散列文件392

10.3 实例研究392

10.3.1 VSAM文件392

10.3.2 多关键字文件393

10.4 深入学习导读395

习题10395

上机实验题10395

第11章 算法设计与分析397

11.1 算法设计397

11.1.1 递归算法397

11.1.2 分治算法401

11.1.3 动态规划算法407

11.1.4 贪心算法422

11.1.5 回溯算法425

11.1.6 分支限界法430

11.2 算法分析440

11.2.1 递归分析440

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

11.3 可计算性问题445

11.3.1 归约445

11.3.2 难解问题、N问题、NP问题和NP完全性问题446

11.3.3 不可编程问题447

11.4 实例研究449

11.4.1 图着色问题449

11.4.2 多边形游戏451

11.5 深入学习导读455

习题11 456

上机实验题11 456

附录A 调和级数458

附录B 泊松分布459

附录C 配套的软件包460

附录D 课程设计项目466

附录E 实验报告格式471

附录F 课程设计报告格式472

参考文献473

书结合C++面向对象程序设计的特点，构建了数据结构与算法，对所有算法都在Visual C++ 6.0、Visual C++ 2005、Visual C++ 2005 Express、Dev-C++和MinGW Developer Studio开发环境中进行了严格的测试，作者教学网站（http://cs.scu.edu.cn/~youhongyue）提供了大量的教学支持内容。同时本书配有《数据结构与算法（C++版）实验和课程设计教程》 (ISBN 978-7-302-17503-2）供读者学习参考。本书共分11章，第1章是基础知识，介绍了基本概念及其术语，并讨论了实用程序软件包；第2章引入线性表；第3章介绍了栈和队列，用栈实现了表达式求值；第4章介绍串，详细讨论了串的存储结构与模式匹配算法；第5章介绍数组和广义表，首次提出了广义表的使用空间表存储结构；第6章介绍了树结构，应用哈夫曼编码实现了压缩软件；第7章介绍图结构，实现了图的常用存结构，讨论了图的相关应用，并实现了相应算法；第8章介绍查找，讨论了静态查找表、动态查找表与散列表，实现了所有算法；第9章介绍排序，以简洁方式实现各种排序算法；第10章介绍了文件，讨论了各种常用文件结构；第11章介绍了算法设计技术、分析技术与可计算问题。 通过本书的学习，不但能迅速提高数据结构与算法的水平，同时还能提高C++程序设计的能力，经过适当的选择，本书能作为高等院校计算机及相关专业“数据结构”、“数据结构与算法”、“数据结构与算法分析”和“数据结构与算法设计”等课程的教材，也可供其他从事软件开发工作的读者参考。

通过《数据结构与算法(C++版)》的学习，不但能迅速提高数据结构与算法的水平，同时还能提高C++程序设计的能力，经过适当的选择，《数据结构与算法(C++版)》能作为高等院校计算机及相关专业“数据结构”、“数据结构与算法”、“数据结构与算法分析”和“数据结构与算法设计”等课程的教材，也可供其他从事软件开发工作的读者参考。