书结合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++面向对象的观点介绍数据结构与算法，并使用模板程序设计技术，与采用面向过程的传统观点相比优势较大，使所设计的程序更容易实现代码重用，在提供通用性和灵活性的同时，又保证了效率。本书已将面向对象程序设计的思想融合到数据结构与算法中，读者通过学习可进一步提高面向对象程序设计的能力。
全书共分为11章。
第1章是基础知识，介绍了基本概念及其术语，抽象数据类型的实现，还讨论算法的概念和算法分析的简单方法。作为预备知识，读者应具有一定的C++程序设计的基础。但是为了降低读者的门槛，本章还介绍了要用的C++的主要知识点，并介绍了实用程序软件包。
第2章引入线性表，详细讨论线性表的顺序存储结构与链式存储结构。在讨论链式存储结构时，首先仿照传统方法实现线性表，然后在此基础之上，在链表结构中保存当前位置和元素个数。这样，在难度增加不大的情况下提高算法效率，使学生逐步体会改进算法的途径与方法。
第3章介绍了栈和队列，讨论了栈和队列的顺序存储结构与链式存储结构，用栈实现了表达式求值。通过学习能掌握各种栈和队列的实现与使用方法，对后继课程（如操作系统原理和编译原理）的学习打下良好的基础。本章还讨论了优先队列，使队列应用更加广泛。
第4章介绍串，详细讨论了串的存储结构与模式匹配算法，为开发串应用（如实现文本编辑软件）软件打下坚实的基础。
第5章介绍数组和广义表，详细讨论了数组，特殊矩阵，稀疏矩阵和广义表的存储结构及实现方法，首次提出了广义表的使用空间表存储结构，并使用广义表实现了m元多项式的表示。
第6章介绍了树结构，讨论了二叉树、线索二叉树、树、森林及其哈夫曼树的结构及其实现，还应用哈夫曼编码实现了压缩软件。
第7章介绍图结构，实现了图的常用存储结构，并讨论了图的相关应用，实现了相应算法（如求最小生成树的Prim算法与Kruskal算法，求最短路径的Dijkstra算法与Floyd算法）.
第8章介绍查找，讨论了静态查找表、动态查找表与散列表，还讨论了二叉排序树、二叉平衡树与B树，并实现了所有算法。
第9章介绍排序，以简洁方式实现各种排序算法，还测试了各种排序算法的实际运行时间。
第10章介绍了文件，讨论了主存储器和辅助存储器，以及各种常用文件结构，还特别介绍了在数据库中经常采用的VSAM文件，对读者研究与学习数据库有一定的帮助。
第11章介绍了算法设计技术、分析技术与可计算问题，详细讨论了各种算法设计技术（如贪心算法、分治算法、回溯算法）的使用方法并实现了各种算法，对算法分析技术和可计算问题也进行了深入浅出的讨论。对读者的算法设计和分析的理论和实践都有极大的帮助。
对于初学者，要完全独立编写数据结构与算法的代码是相当困难的。因此，本书讨论的数据结构与算法都加以实现并进行了严格测试，提供了完整的测试程序，读者可参考这些测试程序编写相关算法。但是，如果只会使用已有的数据结构编写简单的程序也不利于读者对数据结构与算法的深入理解，以及研究新数据结构与算法的能力。因此，本书的习题不但包括了基本练习题，还包括了仿照书中数据结构构造新数据结构的题目，或改造已有算法的题目，这样使读者具有构造新结构及改造或改进算法的能力。
本书各章还提供了实例研究，主要提供给那些精力充沛的学生深入学习与研究，这些实例包括对正文内容的补充（例如第9.9.3小节中的用堆实现优先队列），读者可能感兴趣但感到无从下手的算法（例如第1.6.2小节中的计算任意位数的π) 、离散数学中学习的著名算法的实现（例如第7.7.1小节中的周游世界问题--哈密尔顿圈与第7.7.2小节中的一笔画问题--欧拉问题）以及应用所学知识解决实际问题（例如第6.8.2小节中的Huffman压缩算法）. 通过读者对实例研究的学习，可提高实际应用数据结构与算法的能力。当然，这可能有一定的难度，但应比读者想象的更易学习与掌握。
现在，各校在开设“数据结构与算法”课时都安排有上机实验课时，因此本书每章都安排有上机实验题，这些实验题不但包括读者感兴趣的实验（例如纸牌游戏-- "21点”) ，数据结构与算法基本应用的实验（例如编写一个程序读入一个字符串，统计字符串中出现的字符及次数，然后输出结果，要求用一个二叉排序树来保存处理结果，结点的数据元素由字符与出现次数组成，关键字为字符），对课本数据结构与算法改进的实验（例如改进本书实现的求最小生成树的Kruskal算法，用最大优先队列来实现按照边的权值顺序处理，用等价关系判断两个结点是否属于同一棵自由树以及合并自由树），还包括了解决实际问题的实验（例如采用散列文件实现电话号码查找系统），通过实验能极大地提高读者对数据结构与算法的应用能力。
为了进一步提高读者运用数据结构与算法的水平，现在很多学校还开设了“数据结构与算法课程设计”。为此，本书的附录提供了11个课程设计项目，这些项目包括了接近实际课题的题目（例如开发排课软件与公园导游系统）、容易引起读者兴趣的项目（例如理论计算机科学家族谱的文档／视图模式）与需要通过查找资料进一步提高的题目（例如采用自适应形式的哈夫曼编码方案开发压缩软件）。课程设计项目一般都提供功能的扩展方法，基础较差的读者可只实现基础功能，对数据结构与算法有兴趣的读者可实现更强的功能，这样使不同层次的读者都会有所收获，通过做这些项目能快速提高读者解决实际问题的能力。
为了尽快提高读者的学习能力，本书各章还提供了深入学习导读，包含了本书作者实现相关数据结构与算法的最原始思想的资料来源，也包括了进一步学习的参考资料，极大地方便读者与教师查阅资料。
本教材在内容组织上特别考虑了读者的可接受性；在算法实现时，重点考虑了程序的可读性，为实现更强的功能，一般采用启发的方式在习题、上机实验或课程设计中实现，这样容易培养起读者的学习兴趣，使读者感到自己具有发展或改进已有算法的能力，也会使读者感到自己已达到计算机高手的自信心。
本书作者都活跃在教学研究第一线上，同时有的作者还具有深厚的数学功底。因此，本书不但完成了所有算法的测试程序，对算法分析的相关公式进行了严格的数学推理，还独立地从数学上严格推出了一种产生泊松随机数的算法（见附录B) 。事实上，用同样的方法可产生任何离散随机分布（例如二项分布），本书作者还首次对本书中关于计算任意位数π的算法作了严格的理论推导。
本书采用了模板程序设计技术，现在模板技术已成为现代C++语言的风格基础，C++98(1998年标准化的C++)提供的标准程序库中有80%的成分是使用模板机制实现的STL(Standard Template Library，标准模板库)。而国内现阶段教学并未重视C++的模板程序设计，书籍资料也不是很多。作者认为在C++中，只要模仿本书算法，读者会在不知不觉中掌握模板程序设计技巧。
现在来讨论一下在国外“数据结构与算法”课程上机教学时喜欢采用的STL。实际上，STL是ATandT贝尔实验室和HP研究实验室的研究人员将模板程序设计和面向对象程序设计的原理结合起来，创造的一套研究数据结构与算法的一种统一的方法，现在已成为C++标准库的一部分。STL提供了实现数据结构的新途径，它将(数据)结构(即组织数据的存储结构)抽象为容器，将之分为3类：序列容器、关联容器和适配器容器。通过使用模板和迭代器，STL使得程序员能够将广泛的通用算法应用到各种容器类上。通过本书作者的研究与了解，STL只覆盖了数据结构中的线性结构和树结构，并没有覆盖图部分。因此，对数据结构来讲，STL并不完备。同时，如果读者上机编程都只使用STL解决数据结构的相关算法，可能使读者在数据结构编程方面，只会使用STL，而不能独自设计新数据结构。本书采用模板方法实现了书中所有的数据结构算法，应比STL更完备。同时，STL中包含的源代码可读性差，不适合作为教学使用，本书的算法源程序首要强调可读性，使读者容易接受与模仿，并且读者可进行改进或修改算法实现。因此，在某种意义上讲，本书提供的关于数据结构与算法实现的类模板与函数模板是一种GTL (General Template Library）或OSGTL (Open Source General Template Library) 。读者也可由作者个人主页提供的软件包（具体内容请参看附录C）来进行实际数据结构与算法方面的软件开发。当然，通过本书的学习，再返回来学习STL的应用，将会达到事半功倍的效果。读者只要找一本介绍STL的书籍或上网找一些介绍使用STL的文档，并用STL试着编程即可完全掌握STL的使用。
现在谈谈有关C++编译器的问题，在C++之外的任何编程语言中，编译器都没有受到过如此重视。这是因为C++是一门非常复杂的语言，以至于编译器也难于构造。我们常用的编译器都不能完全符合C++标准，以至于本书的部分测试不得不使用条件编译技术来适应不同C++编译器，下面介绍一些常用的优秀C++编译器。
(1) Visual C++编译器：由微软开发，现在主要流行Visual C++ 6.0、Visual C++ 2005以及Visual C++ 2005 Express，特点是集成开发环境用户界面友好，信息提示准确，调试方便，对模板支持最完善。Visual C++ 6.0对硬件环境要求低，现在安装的计算机最多，但对标准C++兼容只有83.43%. Visual C++ 2005与Visual C++ 2005 Express在软件提示信息上做了进一步的优化与改进，并且对标准C++兼容达到了98%以上的程度，但对硬件的要求较高。同时，Visual C++ 2005 Express是一种轻量级的Visual C++软件，易于使用。对于编程爱好者、学生和初学者来说，Visual C++ 2005 Express是很好的编程工具，微软在2006年4月22日正式宣布 Visual Studio 2005 Express版永久免费。
(2) GCC编译器：著名的开源C++编译器。是类UNIX操作系统（例如Linux）下编写C++程序的首选，有非常好的可移植性，可以在非常广泛的平台上使用，也是编写跨平台、嵌入式程序很好的选择。GCC 3.3与标准C++兼容大概能够达到96.15%。现已有一些移植在Windows环境下使用GCC编译器的IDE（集成开发环境），例如Dev-C++与MinGW Developer Studio。其中，Dev-C++是能够让GCC在Windows下运行的集成开发环境，提供了与专业IDE相媲美的语法高亮、代码提示、调试等功能；MinGW Developer Studio是跨平台下的GCC集成开发环境，目前支持 Windows、Linux和 FreeBSD。根据作者的实际使用，感觉使用GCC编译器的IDE错误信息提示的智能较低，错误提示信息不太准确，还有就是对模板支持较差，对语法检查较严格，在Visual C++编译器中编译通过的程序可能在GCC编译器的IDE还会显示有错误信息。
本书所有算法都同时在Visual C++ 6.0、Visual C++ 2005、Visual C++ 2005 Express、Dev-C++和MinGW Developer Studio中通过测试。读者可根据实际情况选择适当的编译器，建议选择Visual C++ 2005.
教师可采取多种方式来使用本书讲授数据结构，数据结构与算法分析，数据结构与算法设计，数据结构与算法等课程，应该根据学生的背景知识以及课程的学时数来进行内容的取舍。为满足不同层次的教学需求，本教材使用了分层的思想，分层方法如下：没有加星号（）及双星号（）的部分是基本内容，适合所有读者学习；加星号的部分适合计算机专业的读者深入学习；加有双星号的部分适合于感兴趣的同学研究，尤其适合于那些有志于ACM竞赛的读者加以深入研究。下面给出了几种可能的课程安排，建议习题及实验的主要形式是让学生编写并调试一些程序。开始时程序可以比较短，随着课程的深入，程序将逐渐变大。学生应根据课堂上所讲授的主题同步阅读课本相关内容。学 分大约课时数内 容232选讲第1章~第9章中没有打星号（）及双星号（）的内容348第1章~第10章中没有打星号（）及双星号（）的内容464第1章~第11章中没有打星号（）及双星号（）的内容580第1章~第11章中没有打星号（）及双星号（）的内容，选讲部分打有星号（）的内容696第1章~第11章中没有打双星号（）的内容，选讲部分打有双星号（）的内容 作者为本书提供了全面的教学支持，如果在教学或学习过程中发现与本书有关的任何问题都可以与作者联系（E-mail: youhongyue@cs.scu.edu.cn)，作者将尽力满足读者的要求，并可能将解答公布在作者的教学网站（http://cs.scu.edu.cn/~youhongyue）上。另外，在作者的教学网站上还将提供如下内容。
(1) 提供书中所有算法在Visual C++ 6.0、Visual C++ 2005、Visual C++ 2005 Express、Dev-C++和MinGW Developer Studio开发环境中的测试程序，今后还会提供当时流行的C++开发环境的测试程序，每种开发环境还将提供基本开发过程的文档；还提供本书作者开发的软件包（包含所有本书所讲的数据结构与算法的类模板与函数模板）.
(2) 提供教学用PowerPoint幻灯片PPT课件。
(3) 向教师提供所有习题、上机实验题与课程设计项目的解答或参考程序，对学生来讲，将在每学期期末（第15周~第20周）公布解压密码。
(4) 数据结构与算法问答专栏。
(5) 提供至少8套数据结构与算法模拟试题及其解答，以供学生期末及其考研复习，也可供教师出考题时参考。
(6) 提供数据结构与算法相关的其他资料（例如作者收集的计算任何位数π的资料，Dev-C++与MinGW Developer Studio软件，流行免费C++编译器的下载网址）.
希望各位读者能够抽出宝贵的时间将建议或意见（当然也可以发表对国内外“数据结构与算法”课程教学的任何意见）寄给作者，为我们修订教材提供重要参考。
孙界平、张卫华、邹昌文、王文昌、周焯华、胡开文、沈洁、周德华与欧阳等人对本书做了大量的工作，包括提供资料，调试算法，以及参与部分章节的编写；作者还要感谢为本书提供直接或间接帮助的每一位朋友，由于他们热情的帮助与鼓励，激发了写好本书的信心以及热情。
在此还要感谢清华大学出版社的编辑及评审专家，他们为本书的出版倾注了大量热情。正是由于他们具有前瞻性的眼光才让读者有机会看到本书。
尽管作者秉着负责任的态度编写这本书，并尽了最大努力，但由于水平有限，书中难免有不妥之处，因此，敬请各位读者不吝赐教，以便作者不断提高，提高写作水平。
作 者2009年2月
目 录
第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.10 结构与类17
1.3.11 C++的模板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
习题11456
上机实验题11456附录A 调和级数458附录B 泊松分布459附录C 配套的软件包460附录D 课程设计项目466附录E 实验报告格式471附录F 课程设计报告格式472参考文献473
精品教材 更多
