F  O R E W O R D

前言

随着计算机技术的发展，STL(标准模板库)的应用越来越广泛。实际上，STL的vector对应于数据结构的顺序表； list对应于链表； stack对应于栈； queue对应于队列； string对应于串。我们在教材中介绍的顺序表、链表、栈、队列和串，虽然有完整的程序来实现，但真正用于实际编程中，却有一定困难。其原因是，一个完备的类，往往需要定义深拷贝构造函数以及重载运算符等［3］。这样就增大了程序的规模。更重要的是，增加的程序规模又冲淡了数据结构的主要内容(增加的内容不属于数据结构，属于C++语言)。

作者根据多年的授课经验，逐渐总结出一套解决上述矛盾的教学方法，既能简单明了地讲解数据结构的内容，又能使学生初步掌握STL。方法是在详细介绍每种数据结构之后，即介绍相应的STL的语法及应用，并且在后续的应用中使用介绍过的STL。引导学生自然而然地过渡到使用STL编程，为今后的职业生涯打下良好的基础。

在掌握了数据结构的原理后，使用STL会收到事半功倍的效果。例如在图的结构中，作者使用组合的vector和list构架图的存储结构，获得的效果是结构清晰，两种图存储结构的共性和特性一目了然，并且简化了编码。在基数排序中使用vector，在外部排序中使用优先队列，都使得原本看起来非常复杂的算法变得相当简单。

本书秉承作者的一贯风格，采用图文并茂的方式解释算法并提供大量的与算法的语句逐一对应的演示课件(该演示课件在教育部举办的“第十四届全国多媒体课件大赛”中获得高教工科组三等奖)。作者始终认为，结构问题用图来说明是最好的。本书的代码是基于面向对象的C++的，尽量将模板、虚函数、友类、基类、派生类、继承等面向对象的概念应用到程序中。本书不仅会帮助读者轻松学好数据结构，同时还会使读者在掌握C++和STL方面有长足的进步。

本书增添了一些新的算法，包括BoyerMoore模式匹配算法，AVL树、B树、键树和哈希表的删除算法。

本书所有程序都在Microsoft Visual C++6.0和Visual Studio C++2012下运行通过，稍做修改也可以在UNIX下运行通过。这些程序和算法演示课件都可通过清华大学出版社网站(www.tup.tsinghua.edu.cn)下载。

在编写本书时，同事李鹏以他精湛的C++功底，给作者提供了巨大的帮助，在此表示衷心的感激。

算法演示课件的工作量巨大，非作者一人能够完成。我的许多学生参与了课件的编写工作，他们的名字都出现在所做的课件中。借此机会，向他们表示衷心的感谢！

尽管作者尽了最大努力，但限于水平，书中疏漏之处在所难免，希望读者不吝赐教，以便借助清华大学出版社网站及时改正。读者可通过505810175@qq.com与作者取得联系。

作者2016年5月于长安大学