课程介绍

学习资料

来源：常州青少年信息学奥赛编程培训学校时间：2023/3/15 17:37:21

湖塘镇哪有信息学奥赛编程c++培训班

　　湖塘镇哪有信息学奥赛编程c++培训班--为您推荐常州信息学奥赛培训机构

　　信息学初赛数据结构相关考点
　　1数据结构总述
　　在前面的内容中，我们学习了数据结构的相关概念，学习了一些基础的线性结构，包括：
　　普通线性表：顺序表、链表
　　受限制的线性表：栈、队列
　　特殊线性表：
　　接下来，让我们一起来详细复习一下重点内容吧！
　　2线性结构总结
　　1、顺序表
　　顺序表是较基本的线性结构，我们经常用数组来描述它。但是顺序表又和普通数组不一样，顺序表和普通数组的差别在如下几个方面：
　　顺序表要包含：数据域、长度、容量
　　顺序表的容量是可调节的
　　顺序表的优缺点如下：
　　【优点】
　　1、可以实现随机存取，访问数据效率高；
　　2、只需要定义结构存储数据，占用内存空间小。
　　【缺点】
　　1、增删数据时，需要移动大量元素，增删数据效率低；
　　2、需要计算机内存中有较大的完整空间，无法利用比顺序表容量小的空间，造成大量空间碎片。
　　我们可以使用STL库中的vector数组来实现顺序表。
　　2、链表
　　链表是线性表使用链式存储的经典代表，其优缺点如下：
　　【优点】
　　1、增删数据时，无需移动元素，增删数据效率高；
　　2、节点无需相邻，对空间利用率更高。
　　【缺点】
　　1、顺序存取，访问数据需要从一个往后顺序寻找，效率低；
　　2、需要定义额外的空间，存储指向其后续节点的指针，浪费大量空间。
　　3、栈
　　栈是一种受限制的线性表，只能在一端插入与删除，不能在另一端做操作。栈是先进后出的结构。
　　在STL库中，我们提供了stack来实现栈。栈较常用的操作就是获取栈顶元素，入栈和出栈。
　　4、队列
　　队列是一种受限制的线性表，普通队列只能在一端插入，另一端删除。栈是先进先出的结构。
　　在一些特定场景，会有一些特殊的队列，例如双端队列可以实现在两端的插入和删除。循环队列可以解决普通队列中出队导致空间浪费的问题。
　　在STL库中，我们提供了deque来实现双端队列。提供queue来实现普通队列，通过结合取余运算实现循环队列。
　　5、字符串
　　作为特殊的线性表，字符串也有其独特的性质，也有独立的方法，包括字符串的插入、截取、删除、获取字符串长度、比较等等。

信息学奥赛编程

信息学奥赛（青少年信息学奥林匹克联赛（NOIP））的竞赛辅导课程，是面向及以上的中学生，主要使用C++语言培训。学员可参加NOIP比赛。