该书结合C++面向对象程序设计的特点，构建了数据结构与算法，对所有算法都在VisualC++6.0、VisualC++2005、VisualC++2005Express、Dev-C++和MinGWDeveloperStudio开发环境中进行了严格的测试，作者教学网站提供了大量的教学支持内容。同时《数据结构与算法(C++版)》配有《数据结构与算法（C++版）实验和课程设计教程》(ISBN978-7-302-17503-2）供读者学习参考。

版权信息

内容简介

目录

版权信息

书 名: 数据结构与算法(C++版)

作　者：唐宁九等

出版社： 清华大学出版社

出版时间： 2009

ISBN: 9787302188940

开本： 16

定价: 45.00 元

内容简介

《数据结构与算法(C++版)》共分11章，第1章是基础知识，介绍了基本概念及其术语，并讨论了实用程序软件包；第2章引入线性表；第3章介绍了栈和队列，用栈实现了表达式求值；第4章介绍串，详细讨论了串的存储结构与模式匹配算法；第5章介绍数组和广义表，首次提出了广义表的使用空间表存储结构；第6章介绍了树结构，应用哈夫曼编码实现了压缩软件；第7章介绍图结构，实现了图的常用存结构，讨论了图的相关应用，并实现了相应算法；第8章介绍查找，讨论了静态查找表、动态查找表与散列表，实现了所有算法；第9章介绍排序，以简洁方式实现各种排序算法；第10章介绍了文件，讨论了各种常用文件结构；第11章介绍了算法设计技术、分析技术与可计算问题。

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

目录

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

1.3.4C++的类和对象6

1.3.5C++的友元函数7

1.3.6运算符重载9

1.3.7C++的参数传递12

1.3.8C++的输入输出14

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

1.3.10结构与类17

1.3.11C++的模板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.3KMP字符串模式匹配算法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.2Huffman压缩算法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.1Prim算法278

7.4.2Kruskal算法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.3B树和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.2Shell排序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.1VSAM文件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

习题11456

上机实验题11456

附录A调和级数458

附录B泊松分布459

附录C配套的软件包460

附录D课程设计项目466

附录E实验报告格式471

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

参考文献473

……