3.2数据与结构 第2课时课件-2021-2022学年高中信息技术教科版（2019）必修一

第三单元 认识数据 3.2 数据与结构 第2课时 ——线性数据结构 学习目标 1. 掌握数据结构的定义，知道常见的三种数据结构。 2. 掌握线性结构的基本操作（队列）。 数据结构 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。常用的数据结构有：数组，栈，链表，队列，树，图，堆，散列表等，如图所示：  数据结构有很多种，一般来说，按照数据的逻辑结构对其进行简单的分类，包括线性结构和非线性结构两类。 1、线性结构 线性，是说数据在逻辑结构上具有线性关系。将具有线性关系的数据存储到计算机中所使用的存储结构称为线性表。 线性结构又称为线性表。在线性数据结构中，除首元素没有前驱元素，尾元素没有后继元素外，其余的元素都只有一个前驱元素和一个后继元素。 线性表中数据元素之间是一对一的关系。 线性关系指的是数据一个挨着一个，总体呈线性分布。 好比“老鹰捉小鸡”游戏中，小鸡们全都手拉着手，它们之间的关系就可以称为线性关系。 生活中关于线性结构的例子有哪些呢？ 想一想 存储的数据本身的类型一定保持相同，是int型就都是int型，是结构体就都是一种结构体。 数据一旦用线性表存储，各个数据元素之间的相对位置就固定了。 用线性表存储的数据有两个特点： 2、常见的线性数据结构 常见的线性结构有：栈、队列和串等都属于线性结构。 （1） 栈 栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。 栈的特点是：从栈顶放入元素的操作叫入栈，取出元素叫出栈。 先进后出，后进先出 练一练1 若进栈序列为1,2,3,4，则下列不可能的出栈序列为（ ） A. 1，4， 3， 2 B. 2，3， 4， 1 C. 3，1， 4， 2 D. 3，4， 2， 1 C 2、队列 队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素，也就是：先进先出。从一端放入元素的操作称为入队，取出元素为出队， 生活中关于队列。典型的例子有哪些呢？ 想一想 如超市里排队付款的队伍。 ……………… 放学排队离校 去医院挂号就医 每周做核酸检测 练一练2 栈和队列的共同点是（ ） A. 都是先进先出 B. 都是后进先出 C. 都只允