内容简介
本书是“CCF全国青少年信息学奥林匹克竞赛教程”丛书的第二册，旨在普及计算机科学与程序设计知识。书中遵循由浅入深、逻辑严密的编写思路，辅以丰富的实例解析，引领读者逐步提升计算思维能力。全书共四章，涉及C++程序设计进阶、数据结构及其应用、算法设计、数学运用等内容，全面覆盖NOI竞赛大纲所要求的基础知识。根据竞赛的特点，书中还对一些常见的难点和易错点进行了深入的解析。 本书可作为信息学奥林匹克竞赛的教学用书，也可作为青少年学习计算机科学知识、了解信息学奥赛的参考资料。
目录
丛书序
前言第一章 C++程序设计进阶第一节 二维数组3一、情境导航3
二、问题抽象3
三、知识探究4
（一） 二维数组的定义4
（二） 二维数组的输入、输出4
（三） 贪吃蛇问题5
四、实践应用6
五、总结提升9第二节 多维数组11一、情境导航11
二、问题抽象12
三、知识探究12
（一） 三维数组的定义12
（二） 三维数组的输入、输出13
（三） 统计石头问题13
四、实践应用15
五、总结提升19第三节 常用数学函数23一、情境导航23
二、问题抽象23
三、知识探究24
（一） 绝对值函数24
（二） 四舍五入函数24
（三） 取下整函数（地板函数）25
（四） 取上整函数（天花板函数）26
（五） 平方根函数26
（六） 常用三角函数27
（七） 对数函数27
（八） 幂函数28
四、实践应用29
五、总结提升31第四节 自定义函数的参数33一、情境导航33
二、问题抽象33
三、知识探究34
（一） 形参和实参34
（二） 参数的传递方式34
四、实践应用36
五、总结提升38第五节 结构体与联合体42一、情境导航42
二、问题抽象43
三、知识探究44
（一） 结构体的引入44
（二） 结构体的定义44
（三） 创建结构体变量45
（四） 访问结构体变量的成员45
（五） 初始化结构体变量的成员45
（六） 结构体数组46
（七） 结构体作为函数参数46
（八） 图书馆里的寻书游戏46
四、实践应用48
五、总结提升51第六节 指针类型60一、情境导航60
二、问题抽象60
三、知识探究61
（一） 什么是指针61
（二） 如何声明指针61
（三） 指针的初始化62
（四） 使用指针62
（五） 指针和函数63
（六） 指针的算术运算63
（七） 指针与数组63
（八） 动态分配内存64
四、实践应用66
五、总结提升68第七节 STL（标准模板库）——算法函数72一、情境导航72
二、问题抽象72
三、知识探究73
（一） 什么是STL73
（二） 算法函数max、min、swap73
（三） 算法函数sort75
四、实践应用77
五、总结提升80第八节 STL（标准模板库）——线性容器85一、情境导航85
二、问题抽象86
三、知识探究87
（一） STL的线性容器87
（二） STL的向量(vector)87
（三） 向量的成员函数89
（四） STL的链表（list）90
（五） STL的队列（queue）92
（六） STL的栈（stack）93
（七） 线性容器相关函数总结95
四、实践应用96
五、总结提升98第二章 数据结构及其运用第一节 线性结构——链表103一、情境导航103
二、问题抽象103
三、知识探究104
（一） 链表的基本概念104
（二） 链表的分类104
（三） 链表的操作105
（四） 链表操作的STL list实现105
（五） 链表操作的数组模拟实现106
（六） 双向链表操作的数组模拟实现109
（七） 循环链表操作的数组模拟实现111
（八） 为什么学习链表操作的数组模拟实现112
四、实践应用112
五、总结提升116第二节 线性结构——队列和栈116一、情境导航116
二、问题抽象117
三、知识探究117
（一） 什么是队列117
（二） 队列的基本操作117
（三） 队列操作的STL queue实现118
（四） 队列操作的数组实现119
（五） 与队列类似的栈121
（六） 栈的基本操作121
（七） 栈操作的STL stack实现121
（八） 栈操作的数组实现122
四、实践应用124
五、总结提升130第三节 树的引入133一、情境导航133
二、问题抽象134
三、知识探究134
（一） 什么是树134
（二） 树的表示与存储135
（三） 树的基本操作136
四、实践应用137
五、总结提升139第四节 二叉树141一、情境导航141
二、问题抽象142
三、知识探究142
（一） 什么是二叉树142
（二） 二叉树的性质143
（三） 二叉树的表示与存储143
（四） 二叉树的基本操作144
四、实践应用144
五、总结提升146第五节 二叉搜索树150一、情境导航150
二、问题抽象151
三、知识探究151
（一） 什么是二叉搜索树151
（二） 二叉搜索树的插入操作152
（三） 二叉搜索树的查找操作153
（四） 二叉搜索树的遍历操作154
四、实践应用155
五、总结提升157第六节 哈夫曼树160一、情
前言/序言
在信息学的广阔天地中，编程不仅是一种技术，更是一门艺术。自1984年中国计算机学会举办青少年信息学奥林匹克竞赛以来，编程逐渐成为青少年科技教育的重要组成部分。这种教育不仅培养了无数青少年的编程能力，也激发了他们对计算机科学的热情和探索欲望。
近年来，CCF组织编撰了《全国青少年信息学奥林匹克系列竞赛大纲》（以下简称“NOI竞赛大纲”）、《信息学奥林匹克辞典》，本书正是在此基础之上编写而成的，旨在为广大青少年提供一本深入浅出、实用高效的编程教材。我们发现，尽管已经出版了不少相关书籍，但真正能够契合青少年学习特点、兼顾理论深度与实践应用、精准覆盖NOI竞赛大纲的教材仍然稀缺。因此，我们希望通过这本“不一样”的书，为读者搭建一座从概念理解到实际运用的桥梁，让中小学编程爱好者能够迅速成长。
本书具有以下几个突出特点：
1循序渐进，深入浅出
我们精心设计了一条由浅入深的学习路径。通过“情境导航”环节，从生活常识出发，引入问题。通过丰富的图示和通俗易懂的语言讲解核心概念，再逐步过渡到更复杂的算法实现。这种渐进式的学习方法旨在激发读者的学习兴趣，建立直观的算法和数据结构认识，并避免因概念陡增引起的畏难情绪。
2问题导向，实践驱动
通过“问题抽象”环节，从分析问题入手，抽象出知识或概念。每节都从一个实际问题（有些是经典竞赛题）出发，引导读者分析问题、思考解决方案，然后学习相关算法原理，找出解决问题的基本方法，最后通过程序代码来巩固所学知识。这种问题导向的方法不仅能激发读者的学习兴趣，更能培养他们解决实际问题的能力。
3强调思维训练
除了传授具体的算法知识之外，我们十分注重培养读者的算法思维。每节都设有“知识探究”“实践应用”“总结提升”等环节，引导并鼓励读者独立思考、大胆假设、认真求证。通过这种方式，我们希望读者不仅学会“是什么”，更能理解“为什么”。通过给出注意事项和拓展方向，引导读者进一步钻研，最终达到举一反三、触类旁通的目的。
4紧扣竞赛实战
作为一本面向信息学竞赛的教材，我们特别关注了竞赛中的重点和难点。本书围绕着信息学竞赛的核心需求编写，精选了很多经典的竞赛题目，通过详尽的解析和丰富的实例，向读者展示从问题分析到解决方案的全过程。此外，根据竞赛的特点，对一些常见的竞赛难点和易错点进行了深入的剖析和讲解。我们希望这些内容能够帮助读者更快地适应竞赛节奏，提高解题速度和准确率。
5注重知识体系构建
在信息学领域，编程和算法是两项不可或缺的核心技能。本书作为系列教材的基础篇，涵盖了NOI竞赛大纲中入门级的算法与数据结构知识，这些知识是构建信息学竞赛完整知识体系的重要环节。本书适合参加信息学奥林匹克竞赛的学生使用，同时也适合对信息学算法感兴趣的读者阅读。我们希望本书能够帮助读者在竞赛中取得更好的成绩，同时也为他们未来的学习和发展打下坚实的基础。
本书是一把开启智慧之门的钥匙，是一本培养学习方法和思维习惯的教科书。我们希望每一位读者在学习本书的过程中，不仅能学会编程，更能学会如何思考和探索。
作为编者，我们深知编写一本好的教材何等艰难。尽管我们倾注了大量心血，仍难免存在疏漏和不足。我们真诚地希望能得到广大读者、教育工作者和业内专家的批评指正，以便在后续版本中不断完善。
最后，感谢所有为本书付出努力的人。感谢朱全民、宋新波等专家的指导和帮助，感谢所有读者对本书的关注和支持。希望本书能够成为你备战信息学奥林匹克竞赛的良师益友，陪伴你一起迎接挑战，创造辉煌。
让我们共同在信息学的世界中探索未知，享受解决问题的乐趣，不断前行！
江 涛
2024年7月
