计算机技术和计算机的应用技术已经成为信息社会的重要基础设施。高等教育中计算机学科的培养目标，教学计划和课程设置也随着领域的变化在不断地调整，巩固和完善。计算机科学是一种创造性思维活动，其教育必须面向设计。数据结构正是一门面向设计，且处于计算机学科核心地位的技术基础和主干必修课，是计算学科的九个主科目之一。它不仅是计算机科学教育后续课程的理论基础，而且还广泛地用于新兴的技术和研究领域。本书是在国家精品课程“算法与数据结构”的建设过程中，以ACM 和 IEEE/CS Computing Curricula 2005 课程体系及教育部计算机科学与技术教学指导委员会发布的“高等学校计算机科学与技术本科专业规范”中关于算法与数据结构的知识结构和体系为依据编写。数据结构课程的主要特点是既有严格的理论证明，又具有很强的构造性和应用性，因此本书围绕计算学科常用的基本数据结构和基本算法组织教学内容。在概念的编织上，贯穿学科中反复出现的12个基本概念。在内容的组织上，体现计算学科的新概括，融会为学科形态的理论、抽象和设计三个过程。本书的一个明显的特色是在STL (Standard Template Library）的框架下描述数据结构的设计思想和实现方法，使读者循序渐进地理解数据抽象、面向对象设计方法和泛型算法设计三位一体的面向高层次的现代化软件设计风格。全书共分16章。

第1章是算法与数据结构引论，介绍数据结构、抽象数据类型和算法等基本概念，并简要阐述了算法的计算复杂性和用面向对象的C++语言描述算法的方法。介绍了C++标准库中最重要的组成部分标准模板库STL以及与其相关的容器，泛型算法和迭代器等泛型数据结构和算法的基本概念。

第2~16章以抽象数据类型为主线索，以STL的设计理念为描述和实现框架，围绕计算学科中常用的基本数据结构组织内容。

第2~6章依次介绍基于序列的数据结构向量、双端队列、表、栈和队列。

第7章介绍在实际应用中常用的排序与选择算法。

第8章讨论反映层次关系的抽象数据类型树。

第9章的主题是二叉搜索树以及以有序集为基础的抽象数据类型字典的实现方法。

第10章平衡搜索树是第9章内容的延伸，主要从提升二叉搜索树效率的角度来考察搜索树的平衡性。

第11章和第12章讨论的集合和映射是STL中最有用的关联式容器。在这两章中详细讨论了它们的设计思想和实现方法。

第13章讨论散列技术及用散列技术实现符号表，集合和映射的方法。

第14章讨论堆与优先队列的实现方法。

第15章讨论以不相交集合为基础的抽象数据类型并查集及其实现方法。

第16章介绍非线性结构图及相关算法。

数据结构是一门理论性强，而且实践难度较大的专业基础课程。为了使学生在深刻理解课程内容的基础上，灵活运用所学的知识解决实际问题，在每个知识单元都特别设置了“应用举例”作为该知识单元的小结，以期通过本知识单元内容的具体应用来深化学生对学习内容的理解和实际应用的能力。另外每章末有难易适当的习题，并特别设计了数据结构与算法实验题，以强化实践环节，要求学生课后通过上机实验来完成。作者的教学实践表明，这类实验题对学生掌握课堂教学内容有很大帮助，效果非常好。作者还结合国家精品课程建设，建立了教学网站http://ds.fzu.edu.cn，欢迎广大读者访问教学网站，并提出宝贵意见。

数据结构(STL框架)在本书的编写过程中，得到了教育部高等学校计算机科学与技术教学指导委员会的关心和支持。福州大学和泉州师范学院“211工程”计算机与信息工程重点学科实验室为本书的编写提供了优良的设备和工作环境。在此谨向每一位曾经关心和支持本书编写工作的各方面人士表示衷心的谢意！

由于作者的知识和写作水平有限，书稿虽几经修改，仍难免有缺点和错误。热忱欢迎同行专家和读者批评指正。使本书在使用中不断得到改进，日臻完善。

作 者

2009年7月