本书是按高等院校计算机专业及信息管理专业本科四年制教学计划“数据结构”课程教学大纲要求编写的教材。本书还可以作为计算机科技工作者及其有关专业人员的参考书。

“数据结构”发展至今，已成为一门比较成熟的课程。它是计算机系统软件和应用软件研制者的必修课程。数据结构和算法的研究是计算机基础性研究之一，掌握这个领域的知识对于利用计算机资源高效地开发计算机程序是非常必要的。

数据结构理论的应用范围已经深入到编译系统、操作系统、数据库、人工智能、信息科学、系统工程、计算机辅助设计及其他信息管理的应用。数据结构主要解决非数值计算应用问题。

从理论上讲，数据结构的概念严谨、抽象： 每种数据结构类型描述层次清晰可见——概念层、逻辑定义层、物理存储层、运算实现层； 每种数据结构类型描述反映了实现问题的思想，实现的前提以及不同实现方式的特点和优劣； 数据结构描述的内容看上去如同程序，但不是程序，它是程序设计思想的抽象化，一般化，它不依赖于某种物理设备，甚至某种语言系统，受教育者通过《数据结构教程》的学习，不仅能从中学到专业知识，而且能学到一种思维方式。

从实践上讲，数据结构是建立在抽象化描述基础之上的实践性理论，这门学科只有被赋予实践的内容才具有完备性，具体化是该学科的又一特点。计算机系统全面体现着数据结构所在，系统框架结构的构建，程序实现的精巧化都融入了数据结构的理论思想和技术。

本书叙述了各种基本数据结构的概念，包括数据结构的逻辑定义、物理实现及其相应运算，并举例说明怎样用这些抽象的概念来解决实际问题。叙述时回避了复杂的数学定义与推导，力求通俗易懂。通过本书的学习不仅能正确地掌握数据结构的基本理论，并能运用这些理论来解决实际问题。

本书系作者集多年来从事计算机软件设计实践及讲授数据结构课程的体会，并参考分析了国内外数据结构书籍文献编写而成。本书采用广泛使用的C++语言描述算法，并进行了适当的算法复杂性分析。

数据结构不但是一门理论性很强的课程，同时又是一门实践性很强的课程，因此在每一章的最后都安排了适当的习题，供读者练习。

本书共分9章，介绍了线性表和串、栈和队列、树、图、数组、排序、查找、文件等基本数据结构、算法，提供了要应的应用例题。

本书由王少波、孙夫雄编著。王少波负责编写第1~4章及附录B； 孙夫雄负责编写第5~9章及附录A，全书由王少波负责统稿和总纂。

在成书过程中，编者参考了有关书籍，在此向这些书籍的作者表示感谢。

由于编者水平有限，书中错误与疏漏之处，恳请读者不吝指教。

编者

2010年11月