前  言

“数据结构”是有关计算技术及信息管理技术专业的一门必修的核心课程。数据结构课程的任务是讨论在应用问题求解时数据的逻辑组织、在计算机中的存储实现以及相关操作的算法设计。数据结构课程的目的是使学生掌握在实际问题解决过程中组织数据、存储数据和处理数据的基本方法，为以后从事软件开发和应用，为进一步学习后续课程打下坚实的基础。

本教材是清华大学出版社出版的清华大学计算机系列教材《数据结构（用面向对象方法和C++描述）》（第2版）的配套教材，它给出了主教材中全部习题的参考答案和解题分析，并针对学生对基本概念的掌握程度，补充了一些知识性的练习。本教材对于复习和准备考试的学生有一定参考价值，但对于正在学习数据结构课程的学生，应以掌握知识和培养能力为主，不应过多地依赖现成的习题解答。本教材只应作为一个参考，不应当做拐杖。

如何复习好数据结构，从作者的经验来看，必须抓住重点。首先应明确课程考查目标。

(1) 理解数据结构的基本概念，掌握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。

(2) 在掌握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。

(3) 能够选择合适的数据结构和方法进行问题求解。

换句话说，课程考查的目标有两个： 知识和技能。

在知识方面，应从数据结构的结构定义和使用以及存储表示和操作的实现两个层次，系统地考查。

(1) 掌握常用的基本数据结构（包括顺序表、链接表、栈与队列、数组、二叉树、堆、树与森林、图、查找结构、索引结构、散列结构）及其不同的实现。

(2) 掌握分析、比较和选择不同数据结构、不同存储结构、不同算法的原则和方法。

在技能方面，应系统地学习和掌握基本数据结构的设计方法，掌握选择结构的方法和算法设计的思考方式及技巧，提高分析问题和解决问题的能力。

为了能够在有限的时间内学习和复习好这门课程，应当注意以下几点。

(1) 必须注意复习在用C/C++/Java语言编写小程序时的语法规则和方法。为算法的分析和算法设计题的求解打下基础。

在复习C/C++语言时，要注意以下几个问题。

① 函数的概念和相关问题。包括函数类型、函数特征、函数参数传递、函数返回值类型等。特别注意传值参数和引用参数在使用上的区别。

② 函数中传值参数的作用域。特别注意在函数中对传值形参的任何改变，在退出函数过程时不能通过参数返回。

③ 自定义结构的定义方式。可以简单些，但解题时不能回避。

④ 在C/C++中的动态存储分配和回收方式。

⑤ 在C/C++中的输入输出文件的定义和使用。特别注意文件的打开、关闭、读入、写出操作的使用。

(2) 在学习“数据结构”时，要注意知识体系。

数据结构课程中的知识本身具有良好的结构性，有些结构是面向应用的，有些结构是面向实现的。在复习时要注意这两个层次以及它们之间的联系。

① 注意比较。在复习中应当注意从横向和纵向进行对比,以加深理解。

纵向对比将一种结构与它的各种不同的实现加以比较，理解不同实现方式的优点和相应的问题；横向对比包括对同属一类逻辑结构的不同数据结构（如线性表、栈、队列）的比较，具有相同功能的不同算法的比较等，了解数据结构与算法实现之间的关系。

② 注意复习和重读。读者在初读时有些内容难以透彻理解或熟练掌握，或看起来似乎很明白，但用的时候却想不起如何用。在继续复习的过程中如遇到或用到有关内容时，应当及时复习或重读，这往往能够化难为易，温故知新。

③ 注意循序渐进。在复习数据结构的定义和各种操作的实现之前，需首先领会基本概念、基本思想，这一点极为重要。特别是在阅读算法之前，一定要先弄清其基本设计思想和基本步骤，这将大大降低理解算法的难度。如果只是读“懂”了算法而不知其基本思想，仍不能算是真懂。读者可以通过实例学习以加深理解。 

④ 注意练习。只看书不做题，不可能真正学会有关知识，更不能达到技能培养的目的。另一方面，做题也是自我检查的重要手段。在做算法设计类型的习题时，应优先考虑数据结构的定义，可以直接使用以前定义的数据结构和相应操作。

⑤ 提高算法设计的能力。编写算法可能是学生比较棘手的问题，特别是在考试这样一个环境中，时间又短促，想编出一个好算法不太容易。笔者一个建议是首先仔细阅读试题，了解它到底要你干什么。然后用一个简单的例子走一下，总结每一步向下走用什么语句，再做归纳。也可以按照结构化程序设计的方法，先搭框架，再根据例子填入细节。

在设计一个算法解决具体问题时，要考虑数据结构内容的系统性、问题解决方案的多样性、算法的适用性、问题对算法选择的限制。选择合适的数据结构，设计有效的算法。最后应当强调的是，学习方法主要靠自己摸索、多总结、多思考、勤练习、勤交流。

作者教授数据结构课程，从1987年开始，已经有20多年。在教授大学计算机专业本科数据结构课程之外，还教授过大学自学考试本科“数据结构”课程、进行过软件水平考试数据结构课程辅导、全国计算机学科硕士研究生入学专业考试“数据结构”课程辅导。积累了较为丰富的经验，因此在本习题解析中作为学习难点和重点，挖掘了许多学生容易忽略或混淆的概念。并在算法设计方面精心安排了一些题解。这些对于希望深入了解“数据结构”课程知识，特别是应对考研的学生，会有一些帮助。

由于作者在水平上的局限，以及在录入方面可能的疏忽，书中还会有许多错误和疏漏，恳请广大读者多多指正。

2011年3月于清华园·荷清苑