高等学校计算机课程规划教材：数据结构与算法（C++版）

图书标准信息

• 作者 唐宁九 编
• 出版社 清华大学出版社
• 出版时间 2009-02
• 版次 1
• ISBN 9787302188940
• 定价 45.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 473页
• 字数 749千字
• 正文语种 简体中文
• 丛书 高等学校计算机课程规划教材

【内容简介】

　　本书结合C++面向对象程序设计的特点，构建了数据结构与算法，对所有算法都在VisualC++6.0、VisualC++2005、VisualC++2005Express、Dev-C++和MinGWDeveloperStudio开发环境中进行了严格的测试，作者教学网站提供了大量的教学支持内容。同时本书配有《数据结构与算法（C++版）实验和课程设计教程》(ISBN978-7-302-17503-2）供读者学习参考。
　　本书共分11章，第1章是基础知识，介绍了基本概念及其术语，并讨论了实用程序软件包；第2章引入线性表；第3章介绍了栈和队列，用栈实现了表达式求值；第4章介绍串，详细讨论了串的存储结构与模式匹配算法；第5章介绍数组和广义表，首次提出了广义表的使用空间表存储结构；第6章介绍了树结构，应用哈夫曼编码实现了压缩软件；第7章介绍图结构，实现了图的常用存结构，讨论了图的相关应用，并实现了相应算法；第8章介绍查找，讨论了静态查找表、动态查找表与散列表，实现了所有算法；第9章介绍排序，以简洁方式实现各种排序算法；第10章介绍了文件，讨论了各种常用文件结构；第11章介绍了算法设计技术、分析技术与可计算问题。
　　通过本书的学习，不但能迅速提高数据结构与算法的水平，同时还能提高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.2m元多项式的表示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