高中 CSP初试精讲精练 第二节 数据结构（基础）.pptxVIP

CSP-J/S初赛知识点精讲精练第二讲数据结构基础04九月2024

线性表线性结构在数据元素存在非空有限集中：存在唯一的一个被称为“第一个”的数据元素。存在唯一的一个被称为“最后一个”的数据元素。除了第一个外，集合中每个数据元素都只有一个前趋元素。除了最后一个外，集合中每个数据元素都只有一个后继元素。

线性表线性表有n个数据元素的有限序列，同一个线性表中的元素必定有相同特性，元素之间存在序偶关系。线性表中的元素个数n(n=0)定义为该表的长度，当n==0时称为空表，非空表中每个数据元素都有一个确定的位置。线性表是一个相当灵活的数据结构，它的长度可以根据需要增长或缩短。

线性表线性表(List)有n个数据元素的有限序列，同一个线性表中的元素必定有相同特性，元素之间存在序偶关系。线性表中的元素个数n(n=0)定义为该表的长度，当n==0时称为空表，非空表中每个数据元素都有一个确定的位置。线性表是一个相当灵活的数据结构，它的长度可以根据需要增长或缩短。依据存储结构不同的分类顺序存储结构的顺序表链式存储结构的链表（单链表、静态链表、循环链表、双向链表）

线性表线性表的特点：1.数据元素的个数n定义为表的长度。2.n=0时为空表。3.将非空的线性表(n0)记作：(a1,a2,…an)4.数据元素ai(1=i=n)只是一个抽象的符号，其具体含义在不同情况下不同。5.同一线性表中的元素必定具有相同特性，数据元素间的关系是线性关系。线性表是典型的线性结构。

顺序表概念：用一组地址连续的存储单元依次存储线性表的数据元素，这种存储结构的线性表称为顺序表。特点：逻辑上相邻的数据元素，物理次序也是相邻的。只要确定好了存储线性表的起始位置，线性表中任一数据元素都可以随机存取，所以线性表的顺序存储结构是一种随机存取的储存结构，因为高级语言中的数组类型也是有随机存取的特性，所以通常我们都使用数组来描述数据结构中的顺序储存结构，用动态分配的一维数组表示线性表。顺序表的优缺点优点：无须为表中元素之间的逻辑关系而增加额外的存储空间；可以快速存取表中任一位置元素。缺点：插入和删除操作需要移动大量元素；当线性表长度较大时，难以确定存储空间的容量；造成存储空间的“碎片”。

链表在链式结构中，除了要存储数据元素的信息外，还要存储它的后继元素的存储地址。因此，为了表示每个数据元素ai与其直接后继元素ai+1之间的逻辑关系，对数据ai来说，除了存储其本身的信息之外，还需要存储一个指示其直接后继的信息（即直接后继的存储位置）。我们把存储数据元素信息的域称为数据域，把存储直接后继位置的域称为指针域。指针域中存储的信息称做指针或链。这两部分信息组成数据元素ai的存储映像，称为结点（Node）。

例题一链表不具有的特点是（）A.插入删除不需要移动元素B.不必事先估计存储空间C.所需空间与线性表长度成正比D.可随机访问任一元素D

栈与队列栈（Stack）支持push与pop两种操作的数据结构。从顶端放入，从顶端取出。最后入栈的数据最先被取出，被称为LastInFirstOut，简称LIFO表。栈顶：栈最顶端的元素。栈底：栈最底端的元素。

栈与队列栈（Stack）stack头文件stackinta声明int型栈aa.push(x)往栈顶前添加一个元素x。a.pop()从栈顶弹出（删除）一个元素。a.top()返回栈顶的值。a.empty()返回是否为空。（1为空，0为非空）a.size()返回栈里的元素个数。

例题二某个车站呈狭长形，宽度只能容下一台车，并且只有一个出入口。已知某时刻该车站状态为空，从这一时刻开始的出入记录为：“进，出，进，进，进，出，出，进，进，进，出，出”。假设车辆入站的顺序为1，2，3，……，则车辆出站的顺序为（）A.1,2,3,4,5B.1,2,4,5,7C.1,4,3,7,6D.1,4,3,7,2C

栈与队列队列（Queue）支持push与pop两种操作的数据结构。从队尾放入，从队首取出。最初放入的数据最先被取出，被称为FirstInFirstOut，简称FIFO表。队首/队头：队列的第一项。队尾：队列的最后一项。

栈与队列队列（Queue）queue头文件queueinta声明int型队列aa.push(x)往队尾后添加一个元素x。a.pop()从队首弹出（删除）一个元素。a.front()返回队首的值。a.back()返回队尾的值。a.empty()返回是否为空。（1为空，0为非空）a.size()返回队列里的元素个数。

树树是n（n=0）个结点的有限集。当n=0时，称为空树。在任意一棵非空树中应满足：有且仅有一个特定的称