现代科学技术的飞速发展，改变了世界，也改变了人类的生活。作为新世纪的大学生，应当站在时代发展的前列，掌握现代科学技术知识，调整自己的知识结构和能力结构，以适应社会发展的要求。新世纪需要具有丰富的现代科学知识，能够独立解决面临的任务，充满活力，有创新意识的新型人才。

掌握计算机知识和应用，无疑是培养新型人才的一个重要环节。计算机技术已深入到人类生活的各个角落，与其他学科紧密结合，成为推动各学科飞速发展的有力的催化剂。无论学什么专业的学生，都必须具备计算机的基础知识和应用能力。计算机既是现代科学技术的结晶，又是大众化的工具。学习计算机知识，不仅能够掌握有关的知识，而且能培养人们的信息素养。它是高等学校全面素质教育中极为重要的一部分。

高校计算机基础教育应当遵循的理念是： 面向应用需要；采用多种模式；启发自主学习；重视实践训练；加强创新意识；树立团队精神，培养信息素养。

计算机应用人才队伍由两部分人组成：一部分是计算机专业出身的计算机专业人才，他们是计算机应用人才队伍中的骨干力量；另一部分是各行各业中应用计算机的人员。这后一部分人一般并非计算机专业毕业，他们人数众多，既熟悉自己所从事的专业，又掌握计算机的应用知识，善于用计算机作为工具解决本领域中的任务。他们是计算机应用人才队伍中的基本力量。事实上，大部分应用软件都是由非计算机专业出身的计算机应用人员编制的。他们具有的这个优势是其他人难以代替的。从这个事实可以看到在非计算机专业中深入进行计算机教育的必要性。

非计算机专业中的计算机教育，无论目的、内容、教学体系、教材、教学方法等各方面都与计算机专业有很大的不同，绝不能照搬计算机专业的模式和做法。全国高等院校计算机基础教育研究会自1984年成立以来，始终不渝地探索高校计算机基础教育的特点和规律。2004年，全国高等院校计算机基础教育研究会与清华大学出版社共同推出了《中国高等院校计算机基础教育课程体系2004》(简称CFC2004)，由清华大学出版社正式出版发行。

1988年起，我们根据教学实际的需要，组织编写了《计算机基础教育丛书》，邀请有丰富教学经验的专家、学者先后编写了多种教材，由清华大学出版社出版。丛书出版后，迅速受到广大高校师生的欢迎，对高等学校的计算机基础教育起了积极的推动作用。广大读者反映这套教材定位准确，内容丰富，通俗易懂，符合大学生的特点。

1999年，根据新世纪的需要，在原有基础上组织出版了《新世纪计算机基础教育丛书》。由于内容符合需要，质量较高，被许多高校选为教材。丛书总发行量突破1000多万册，这在国内是罕见的。

最近，我们又对丛书做进一步的修订，根据发展的需要，增加了新的书目和内容。本丛书有以下特点：

(1) 内容新颖。根据21世纪的需要，重新确定丛书的内容，以符合计算机科学技术的发展和教学改革的要求。本丛书除保留了原丛书中经过实践考验且深受群众欢迎的优秀教材外，还编写了许多新的教材。在这些教材中反映了近年来迅速得到推广应用的一些计算机新技术，以后还将根据发展不断补充新的内容。

(2) 适合不同学校组织教学的需要。本丛书采用模块形式，提供了各种课程的教材，内容覆盖高校计算机基础教育的各个方面。既有供理工类专业用的，也有供文科和经济类专业用的；既有必修课的教材，也包括一些选修课的教材。各类学校都可以从中选择到合适的教材。

(3) 符合初学者的特点。本丛书针对初学者的特点，以应用为目的，以应用为出发点，强调实用性。本丛书的作者都是长期在第一线从事高校计算机基础教育的教师，对学生的基础、特点和认识规律有深入的研究，在教学实践中积累了丰富的经验。可以说，每一本教材都是他们长期教学经验的总结。在教材的写法上，既注意概念的严谨和清晰，又特别注意采用读者容易理解的方法阐明看似深奥难懂的问题，做到例题丰富，通俗易懂，便于自学。这一点是本丛书一个十分重要的特点。

(4) 采用多样化的形式。除了教材这一基本形式外，有些教材还配有习题解答和上机指导，并提供电子教案。

总之，本丛书的指导思想是内容新颖、概念清晰、实用性强、通俗易懂、教材配套。简单概括为：“新颖、清晰、实用、通俗、配套”。 我们经过多年实践形成的这一套行之有效的创作风格，相信会受到广大读者的欢迎。

本丛书多年来得到各方面人士的指导、支持和帮助，尤其是得到全国高等院校计算机基础教育研究会的各位专家和各高校的老师们的支持和帮助，我们在此表示由衷的感谢。

本丛书肯定有不足之处，竭诚希望得到广大读者的批评指正。

欢迎访问谭浩强网站

丛 书 主  编

全国高等院校计算机基础教育研究会会长

谭 浩 强

数据结构是一门学科，其内容是计算机软件技术的基础。随着计算机技术的发展，数据结构的内容也在不断地更新，到目前为止，数据结构的内容已经比较系统，基本反映了计算机软件技术中最基础的知识。

    本书的书名为《实用数据结构（C++描述）（第二版）》，作者认为，“实用”有两方面的含义：一是书中的内容要实用，二是内容的表现形式要实用。此次对本书的修订主要是后者。书中所有的算法均采用C++语言描述。由于C++语言既可用于面向过程的程序设计，又支持面向对象的程序设计，因此，作者在对算法进行描述时，尽量采用最合适的程序设计方法。例如，对于基本的数据结构（如顺序存储与链式存储的线性表、栈、队列等）采用面向对象的方法，将数据与运算封装成类，以便在其他应用程序中直接使用；而对于同一批数据进行同类操作的各种算法（如对线性表的各种排序方法）采用面向过程的方法，将各种不同的算法用普通函数来描述。这样，书中的所有算法就可以直接在实际应用中方便地使用。

    本书实例丰富，内容精练，叙述通俗易懂，每章后面都有大量的习题，可作为高等院校非计算机专业的学生学习数据结构的教材，也可作为数据结构的培训班教材或自学教材。

由于时间紧迫与水平有限，书中难免有错误或不妥之处，恳请读者批评指正。

作者2006年9月

关于数据结构的书已经很多，但是有一个问题始终没有解决，即学习数据结构应具备哪些预备知识。是否一定要学习Pascal语言或C语言后才能学习数据结构？在学习数据结构前是否一定要有一些离散数学或集合论方面的基本概念与知识？学习本书所介绍的数据结构，这些预备知识都可以不要。本书的起点很低，适用的读者面很广。书中对每一种常用的数据结构都没有从抽象的定义出发，也没有涉及基本理论与计算机的专业知识。在介绍一种数据结构时，总是从实例出发，通过对实例的分析、讲解来掌握数据结构的基本概念，总结出每一种数据结构的特点及其应用。当然，为了更有效地学习数据结构，读者应已经初步学会了一种程序设计语言，但并不局限于Pascal语言或C语言。在本书中，用一种最简单的描述语言来描述对数据结构的运算，但也为了方便于学过C语言的读者，对每一个算法都给出了C语言的描述。如果读者没有学过C语言，可以不看C语言的描述，也可以通过阅读用C语言描述的算法顺便学习C语言。

    本书强调实用，书中所有的算法都用C语言编程调试通过。

    全书共分9章。

    第1章从两个实例着手，介绍了数据结构的基本概念，讨论了算法方面的考虑，并给出了本书主要使用的一种算法描述语言。

    第2章介绍了一般的线性表、栈、队列等最基本的数据结构，并讨论了它们在顺序存储结构下的主要运算，介绍了栈与队列的主要应用，最后还讨论了字符串匹配的问题。

    第3章介绍了线性表的链式存储结构及其运算，并主要讨论了线性链表在多项式运算中的应用。

    第4章讨论了数组的顺序存储结构、规则矩阵的压缩以及稀疏矩阵的三列二维数组表示与十字链表表示。

    第5章介绍了树与二叉树的基本概念，并主要讨论了二叉树的性质、二叉树的存储结构及其二叉树的遍历，最后还介绍了穿线二叉树的概念、表达式线性化的过程、最优二叉树用于编码等问题。

    第6章简要介绍了图的基本概念、图的存储方式、图的两种主要遍历方法，最后讨论了最短距离问题的求解。

    第7章介绍了工程中常用的查找方法，包括顺序查找、对分查找、分块查找、二叉排序树查找以及多层索引树查找等。

    第8章介绍了Hash表的基本概念，重点介绍了几种常用的Hash表。

    第9章介绍了各种排序的方法，还求解了拓扑分类的问题。

由于时间紧迫与水平有限，书中难免有错误或不妥之处，恳请读者批评指正。

作者1999年11月