前言

编程竞赛介绍

随着计算机逐步深入人们生活的各个方面，利用计算机及其程序设计来分析、解决问题的算法在计算机科学乃至整个科学界的作用日益明显。相应地，各类以算法为主的编程竞赛也层出不穷：在国内，有全国青少年信息学奥林匹克联赛（National Olympiad in Informatics in Provinces，NOIP），该联赛与全国中学生生物学联赛、全国中学生物理竞赛、全国高中数学联赛、全国高中学生化学竞赛对高中生而言是含金量最高的竞赛；在国际上，有面向中学生的国际信息学奥林匹克竞赛（International Olympiad in Informatics，IOI）、面向亚太地区在校中学生的信息学科竞赛即亚洲与太平洋地区信息学奥林匹克（Asia-Pacific Informatics Olympiad，APIO），以及由国际计算机学会（Association for Computing Machinery，ACM）主办的面向大学生的国际大学生程序设计竞赛（International Collegiate Programming Contest，ICPC）等。

因为各类编程竞赛要求参赛选手不仅要有深厚的计算机算法功底、快速并准确编程的能力和创造性的思维，而且要有团队合作精神和抗压能力，所以编程竞赛逐渐得到高校、IT公司和其他社会团体的认同和重视。编程竞赛的优胜者更是Microsoft、Google、百度、Facebook（已更名为Meta）等全球知名IT公司争相高薪招募的对象。因此，除了各类参加编程竞赛的选手，很多不参加此类竞赛的研究人员和从事IT行业的人士，也都希望能得到这方面的专业训练并从中取得一定的收获。

为什么要学习数据结构

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。数据结构是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构、物理结构和它们之间的关系，数据结构会对这些结构定义相适应的运算，设计出相应的算法，确保经过运算以后得到的新结构仍保持原来的结构类型。数据结构往往与高效的检索算法和索引技术有关。

据统计，当今处理非数值计算性问题占用了85%以上的机器时间，这类问题涉及的数据结构更为复杂，数据元素之间的相互关系一般无法用数学方程加以描述。因此，解决这类问题的关键不再是优化数学分析和计算方法，而是要设计出合适的数据结构。通常情况下，精心设计的数据结构可以带来更高的运行效率或者存储效率。

数据结构是计算机科学与技术、计算机信息管理等专业的基础课程，是十分重要的核心课程。所有的计算机系统软件和应用软件都要用到各种类型的数据结构，学习和掌握数据结构的相关知识，使我们能够更好地运用计算机来解决实际问题。可以说，数据结构是计算机学科知识结构的核心和技术体系的基石。

本书的特色及用法

本书包含了NOIP中常用的数据结构类型，如堆栈、队列、树、图等，适用于NOIP级别的竞赛选手学习。

为了提高读者的学习效率，本书直接以各类竞赛真题入手，以精练而准确的语言，全面、细致地介绍编程竞赛中常用的数据结构类型。考虑读者接受水平的差异，一般在引入包含新知识点的题目时，本书会提供该题目的完整参考代码以供读者参考，但随着读者对知识点的理解逐步加深，后续的同类型题目将逐步向仅提供思路、提供伪代码和无任何提示的方式转变。此外，对于一些思维跨度较大的题目，本书会酌情给予读者一定的提示。

本书的内容是按照难易程度划分的，但是并不建议读者严格按照本书既有的顺序逐步学习，因为这很容易导致学到后面的内容时，就忘了前面学习过的内容。一个比较好的学习建议是，读者在掌握某个章、节的大部分内容后，可以先学习后面章、节的内容，剩下的部分和没有做过的较难的题目，可以在后面的复习巩固中完成。

本书的配套资源

本书精心安排了由浅入深的相关例题与习题，让读者能进一步掌握数据结构相关知识。对于例题，本书给出了详细的算法分析和参考代码，题目对应的数字（如402001）为配套题库网站中的题目编号，网址为www.magicoj.com，读者可在该网站通过题目编号查找对应题目并进行在线评测。因篇幅所限，对于习题，本书仅提供配套题库网站的题目编号，请读者到配套题库网站上完成习题。

本书有配套的源代码、课件，读者可登录“异步社区”网站搜索本书，在本书的页面中进行相关资源的下载。

适合阅读本书的读者

本书可以作为本系列书的读者后续的学习教材，也可以作为有一定编程基础的读者学习数据结构的参考用书。

本书可作为NOIP的复赛教材和ICPC的参考与学习用书，还可作为计算机专业的学生、IT工程师、科研人员、算法爱好者的参考和学习用书。

致谢

感谢全国各中学、大学的信息学奥赛指导教师们，他们对本书的编写提出了许多真诚而有益的建议，并对笔者在写书过程中遇到的一些困惑和问题给予了热心的解答。

本书使用了NOIP的部分原题、在线评测网站的部分题目，并参考和收集了其他创作者发表在互联网、杂志等媒体上的相关资料，无法一一列举，在此对相关人员一并表示衷心的感谢。

感谢卷积文化传媒（北京）有限公司的CEO高博先生和他的同事。

最后要说的话

由于笔者水平所限，书中难免存在不妥之处，欢迎读者赐正。读者如果在阅读过程中发现任何问题，请发送电子邮件到hiapollo@sohu.com，希望读者能对本书提出建设性意见，以便重印时改进。

希望本书的出版，能够给学有余力的中学生、计算机专业的大学生、程序算法爱好者和IT从业者提供一些新思路。

广州市第六中学强基计划基地教材编委会
2024年1月