前言

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

本教材是清华大学出版社出版的清华大学计算机系列教材《数据结构（用面向对象方法与C++描述）》（第3版）的配套教材，并对相应的第2版教材做了较大的修改。修改的目的有3个： 一是响应主教材的修改，在内容上做了适当的删减，对所有入选的习题做了归类；二是适应计算机类学科的学生考研的需要，增加了题型和内容，将历年全国计算机学科硕士研究生入学联考的绝大多数数据结构的真题吸收到了本教材中（在题目前加了“ ”标志），学生可以通过这些习题了解考研的难度；三是针对一些IT大厂的入职面试的数据结构方面的考核，挖掘课程的某些边边角角的知识点，适当补充一些相关的概念题。因此，本教材对于复习和准备考试的学生有一定参考价值。但对于正在学习数据结构课程的学生，应以掌握知识和培养能力为主，不应过多地依赖现成的习题解答。

学习好数据结构，必须抓住重点。首先要明确课程考查目标。

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

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

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

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

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

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

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

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

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

（1） 必须注意使用C/C++语言编写小程序时的语法规则和方法，为算法分析和算法设计题的求解打下基础。

在学习C/C++语言时，要注意： 

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

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

③ 自定义结构的定义方式。可以简单些，但解题时不能回避C/C++中的动态存储分配和回收方式。

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

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

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

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

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

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

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

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

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

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

（3） 在设计一个程序以实现一个数据结构和算法时，还要考虑更多的实现要求。

① 程序的可读性和可理解性问题。一个程序是否具有可读性，关系到该程序的生存期。业界有一个测试可读性的方法，拿一个程序（100行左右）给一个有经验的程序员看，如果10分钟没能看懂这个程序，则请程序作者拿回去重写。程序看得懂，才能够合理修改，否则改1个错出10个错，这个程序必然会被新的程序替代。

② 程序的结构化和模块化问题。程序划分模块，是为了控制程序的出错率。任何人也不能保证他所编写的程序没有错误。今天没有发现问题不等于以后也不会发现问题。有的是算法逻辑问题（如控制变量失控导致的数据对象状态异常），有的是系统问题（如运行时存入数组的元素个数超出数组的边界），有的是程序结构问题（如if语句的嵌套出现二义性）等，结构化和模块化可控制修改范围最小，出错影响范围最小。

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

由于作者水平有限，书中会有一些错误和疏漏，恳请广大读者多多指正。

作者

2025年4月于清华园·荷清苑