1.2 数据的组织（教学课件）信息技术浙教版2019选择性必修1

第2节 数据的组织（3课时） 第1章 数据与数据的组织 浙教版（2019） 选修一 数据结构的概念 01 常见的数据结构 02 数据结构的作用 03 学习目录 初步理解数据结构的概念及其作用。 01 通过完成数据合并任务，体会数据结构的作用。 03 通过连线活动，比较体会不同数据结构的区别。 02 学习目标 PART 01 数据结构的概念 新课导入 想 想 一 同学们，程序是什么样子的呢？ Vb_man 瑞士计算机科学家 尼古拉斯·沃斯 新课导入 算法+数据结构=程序 在计算机程序设计中，根据问题求解的需要，对数据进行有效的整理和组织，并以一定的形式加以存储和表示的过程称为数据结构的设计。 程 序 是 什 么 ？ 数据结构的概念 一 数据元素 现实问题中的数据往往具有多样性和复杂性的特点，为了有效组织数据，必须对各种数据加以分类，对互相有关联的数据进行合理重组，在此基础上，才能较好地选择、设计数据结构。 数据结构的概念 一 结点 顶点 记录 数据元素 元素 数据元素是数据的基本单位。 数据结构的概念 一 数据元素 有时一个数据元素可以由若干个数据项(也称为字段、域)组成，数据项是具有独立含义的最小数据表示单位。 数据项 数据元素 数据结构的概念 一 这张表一共有多少个数据元素? 第四个数据元素的第五个数据项的名称为什么?值为什么? 10 动态市盈 52.81 数据的表现形式 一 数字类型 数据类型指的是具有相同性质的计算机数据的集合及在这个数据集合上的一组操作。 数据类型可以分为基本数据类型(也称为原子数据类型)和结构数据类型。 基本数据类型里 结构数据类型 A B 基本数据类型由计算机编程环境提供，编程者可以在编程时直接用系统提供的标识符进行定义，如Python编程语言中的整型、实型、布尔型等。 结构数据类型是在程序设计时利用基本数据类型构造出的、复合的新类型，这种新类型由用户根据实际需要定义，能较好地描述数据元素数据项组成以及数据元素之间的逻辑关系方便用户根据数据之间逻辑关系的特点进行数据处理，如很多编程语言中提供的记录类型、集合等。 数据的表现形式 一 逻辑结构 存储结构 或 物理结构 数据的预算 数据结构 数据元素之间的逻辑关系 数据结构指的是数据之间的相互关系，即数据的组织形式。 数据元素及其关系在计算机存储器内的表示 对数据施加的操作 数据结构设计的目的:使数据元素间的相互关系能准确地反映现实问题中的事物逻辑，既确保数据处理的正确性，又提高编程实现和数据处理的效率。 数据的表现形式 一 1.关于数据项与数据元素的描述,下面说法不正确的是( ) A.数据元素可由若干数据项组成 B.同一数据元素中各数据项的数据类型必须相同 C.数据项是数据的最小单位,通常用来描述实体的某种属性 D.数据元素是数据的基本单位,在计算机中通常作为一个整体来处理 2.数据元素及其关系在计算机存储器内的表示,也称为数据的( ) A.线性结构 B.物理结构 C.逻辑结构 D.空间结构 课堂 练习 答案：B 答案：B 常见的数据结构 PART 02 常见的数据结构 二 队列 链表 树 图 栈 数组 常见的 数据结构 数据结构设计是为了解决实际问题而出现的科学，选择合适的数据结构来组织与存储数据，可以达到高效处理数据的目的。 常见的数据结构 二 数组 表示一批数据，不仅可以描述数据本身，还可以描述数据所处的位置或数据之间的前后顺序关系。可以迅速地通过下标精确访问序列中的某个数据元素，又可以通过下标按顺序遍历序列中的每个元素。 所处的位置 数据本身 成一列纵队排队的人 常见的数据结构 二 成一列纵队排队的人 1 2 3 4 李彤 张强 胡洁 杜刚 这批数据序列可用数组“a(1)="李彤"、a(2)="张强"、a(3)="胡洁"、a(4)="杜刚"”来表达。 常见的数据结构 二 遍历 遍历指的是根据数据之间的逻辑结构，遵循一定的顺序 依次对所有数据元素做一次且仅做一次访问。访问某个数据元素时，需要进行的操作依赖于具体实际问题。例如， 当需要计算满足条件的元素之和时，访问每个元素 时首先判断元素是否符合条件，若满足则将其 累加。 拓展 链接 常见的数据结构 二 链表 同样是对一批人员数据进行组织，有时只需知道相邻人员之间的前后顺序关系，而对每个人员的位置信息并不作要求。 吴坚知道自己排在首位，王林知道排在自己前面的是吴坚，黄刚知道排在自己前面的是王林，李丰知道排在自己前面的是黄刚。有了这些相邻人员之间的链接关系，即使休息时大家分散在各处，一旦需要集合，大家可以根据链接关系快速地按照原顺序排成队伍。虽然整队前后每个人员的站位地点发生改变，但相互之间排队的顺序关系是不变的。 整队前的位置和链接关系 常见的数据结构 二 我排队首 吴坚 王林 黄刚 李丰 Vb_man 抽象化后的排队链接关系 组织、处理一批数据时， 若不关心数据实际所处的具体位置，而只需知道数据之间相互链接的顺序时，可以借鉴上面的方法。在计算机科学中,这种方法的具体实现形式就是链表。 常见的数据结构 二 吴坚 王林 黄刚 李丰 ∧ head 链表内存存放方式： head头节点 数据域 指针域 tail None 01 节点 02 head 03 tail 04 None 每个节点有两个部分，左边称为数值域，存放用户数据;右边部分称为指针域，用来存放指向下一个元素的指针(地址)。 head节点永远指向第一个节点 tail永远指向最后一个节点 链表中最后一个节点的指针域为None值 基本元素 常见的数据结构 二 思考:该链表的指针指向的是前面还是后面? 吴坚 王林 黄刚 李丰 ∧ head Vb_man 单向链表 吴坚 head 双向链表 Vb_man 王林 黄刚 李丰 ∧ 吴坚 head 基于单向链表的循环链表 王林 黄刚 李丰 ∧ Vb_man 常见的数据结构 二 只需知道数据之间相互链接的顺序 探讨与讨论 数组的特点？ 1 2 3 链表的特点？ 在数组中插入元素和在链表中插入元素的差别? 数组:整体后移空出位置插入 链表:改变指针 不仅需要描述数据对象本身，还需要描述数据所处的位置或者数据之间的前后顺序关系 只需知道数据之间相互链接的顺序 常见的数据结构 二 指针 在计算机科学中，指针(Pointer)是用来指示一个数据存 储地址(内存或者寄存器)的变量。如图1.2.6所示的head，该 变量存储的是头节点所在的内存地址，或者说存储的 地址指向了头节点，所以形象地称为“指针”。 拓展 链接 常见的数据结构 二 队列 有序排队上车的乘客 有序排队接客的出租车 乘客排队时先到的总是从队伍的头部出去(出队)上车，而后到的乘客则必须在队伍的尾部加入(入队)。同时，为了确保有序，人们总是规定不能从队伍的中间部位插队。 常见的数据结构 二 出队 从队列中删除一个元素的过程。 01 03 02 04 队列 入队 在队列中插入一个元素的过程。 概念 队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首 队列元素 队列中的数据元素。 a1 a2 a3 a4 …………an 队首元素 队尾元素 出队 入队 常见的数据结构 二 用计算机程序处理数据时，有时也需要将数据进行“排队”，并遵循现实中排队的规律，对数据进行“先进先出”FIFO(First In First Out)且中间不能“插队”的组织和操作，计算机科学家由此发明了“队列”这种数据结构。 银行叫号系统 常见的数据结构 二 队列经过一次出队和入队操作后的状态 Vb_man 接下来的时刻窗口2的客户办理结束，接着又有一位新客户在取号机上取了排队号(号码为0012)，则系统会让队首元素(0006号)出队并将号码传输到2号窗口的显示屏，同时将新客户刚取走的号码作为数据元素进行入队操作，操作后的结果如上图所示。 常见的数据结构 二 栈 子弹进出弹匣的过程具有下列特点: ①整个装置只有一端开放(最上端)，而且进、出只能在这一端进行。 ②弹匣中的子弹成一纵队排列。 ③任何子弹进出弹匣的规律是“先进后出、后进先出”，即最先装入弹匣的子弹最后才能被弹出，而最后装入弹匣的子弹则最先被弹出。 栈的示例——弹匣 常见的数据结构 二 栈 栈是一种先进后出的操作受限的线性表，仅允许在表的一端进行插入或删除。 栈底元素 位于栈底位置的元素。 01 03 02 04 队列 栈 底 不进行操作的一端。 栈顶 进行插入或删除操作的一端。 栈顶元素 位于栈顶位置的元素。 概念 常见的数据结构 二 小组讨论 在文字处理软件Word中输入若干文字，然后删除其中部分文字，再输入若干文字。然后进行“撤消”操作(按Ctrl+Z键，或者单击撤消操作快捷按钮“ ”)。 观察各个操作后的现象，回答下列问题。 根据“撤消”操作所产生的结果，说明Word中符号输入及撤消操作中，内部所依托的数据结构是哪种数据结构?为什么? 结合自己的经历，谈谈哪些信息系统中也采用了栈这种数据结构。 常见的数据结构 二 只需知道数据之间相互链接的顺序 探讨与讨论 队列的特点? 1 2 3 栈的特点? 队列和栈有什么共同点? 都是线性关系 先进先出，不能插队 先进后出，后进先出 常见的数据结构 二 树 一个元素前面(或上面)只有一个元素，而后面(或下面)却有多个(0个或多个)元素相邻，所有的数据元素之间的特征就像一棵倒放的树。 常见动物分类图 常见的数据结构 二 如图下图所示，中国图书馆图书分类法将图书分为几大基本部类，各个基本部类又可以分出更细化的分类。 图书馆图书分类法 常见的数据结构 二 1 2 3 子树:树中某个节点下面的所有节点所构成的树。 空树:n=0的树。 节点:集合中的元素。 概念：树是由n (n≧0) 个节点构成的一个有限集合以及在该集合上定义的一种节点关系。 常见的数据结构 二 只需知道数据之间相互链接的顺序 探讨与讨论 分小组讨论，举出在生活和信息系统中用树组织数据的例子，并用树结构描述数据之间的关系特征。 1 计算机操作系统中文件夹的组织与管理、下棋算法中对后续局面的状态表示时，都需要借助树结构来组织、保存和处理数据。 常见的数据结构 二 重点提示 1.数据结构的概念 (1) 数据元素:数据的基本单位，可由若干数据项组成。数据项是具有独立含义的最小数据表示单位。 (2)数据类型:具有相同性质的计算机数据的集合及在这个数据集合上的一组操作。数据类型可分为基本数据类型和结构数据类型。 (3) 数据结构:数据之间的相互关系，即数据的组织形式。主要包含数据的逻辑结构、数据的存储结构和数据的运算。 2.常见的数据结构 常见的数据结构有数组、链表、队列、栈、树和图等。数组、 链表、队列、栈都是线性表的特殊形式。 常见的数据结构 二 课堂 练习 答案 A 答案 D 1.以下关于数据结构的描述，不正确的是( ) A.数据的逻辑结构是指数据元素之间的逻辑排列和对应关系 B.数据的存储结构包括数据元素的存储及数据元素之间关系的存储 C.数据的运算是指对数据施加的操作，包括删除、查找、插入数据等 D.数据结构设计时不需要考虑编程实现和数据处理的效率 2.用一个带盖(另一端封闭)的透明塑料筒来放取乒乓球，且筒的直径只允许一个乒乓球进出，如图，若放入球的编号序列为1、2、 3、4，则取出球的编号序列可能的是( ) A.1、2、3、4 B.3、1、2、4 C.4、2、3、1 D.2、4、1、3 数据结构的作用 三 每个实际问题中的数据之间存在着一定的关系，用计算机程序解决问题时，需要将数据之间的这些关系映射到程序的数据表示中，这样才能有效地用计算机程序解决问题。 对于同一个问题的解决，当依据不同的数据结构来设计算法时，算法的处理效率、程序的实现效率也是不同的。 数据结构的作用 三 （一） 设计算法解决问题离不开数据结构 数据统计前，需要先收集数据并将数据按照既有的逻辑关系进行结构化组织，可以用一张表格来组织数据并表示数据之间的逻辑关系。 数据结构的作用 三 各位选手在各个项目上的得分 根据本问题中数据之间的线性关系特点，可基于数组来设计算法并解决问题。如果不针对数据之间的关系特点设计数据结构，而是直接用一个个简单变量来存储所有学生姓名和各项得分，在此基础上设计算法及编写程序的工作量将变得非常巨大，用计算机处理这些数据就变得毫无意义。 数据结构的作用 三 （二） 不同的数据结构会导致处理效率的不同 1.用一维数组组织数据 程序代码 其中的bjdf(j)表示第j班的总分 当完成对所有选手的遍历时，每位选手的总得分就保存到数组sum中，而每个班级的总分则保存到数组bjdf中 数据结构的作用 三 2.用二维数组组织数据 程序代码 其中的bjdf(j)表示第j班的总分 为了统计每位选手和各班的总得分，基于二维数组的总体算法同样可通过遍历每位选手的相关数据进行，但在用计算机程序设计语言描述算法(编写程序)时，相比于一维数组，二维数组在程序实现效率上要高于前者，特别在每位选手总分统计部分。如果数据项数量增加，那么两者相差会更大。 数据结构的作用 三 一维数组程序实现 二维数组程序实现 数据结构的作用 三 数据合并：生产厂家总会根据各地产品销量的数据分析来预估市场情况，并为后续调整生产规数据合并划、完善营销策略提供依据。 由于数据量巨大，为了充分运用分布式处理的优势，总部会要求各下属地区上报数据时，按各产品销量进行从大到小的排序。总部收到数据后的第一件事是将所有数据合并并按照销量进行降序排序(从大到小)，为了完成数据合并和整理工作，总部数据分析员小刚需要设计合适的数据结构和算法。 分析：小刚可以用一个二维数组存储所有下属地区的产品销量数据，然后直接运用排序算法进行降序排序。如果利用既有数据已是分块有序的特点，设计新的数据结构和算法，则处理效率可以得到相应的提升。 各个地区的数据合并问题可以简化为2个地区的数据合并问题，当2个地区的数据合并完成后，剩余各地区的数据合并就可以按照同样方式完成。因此，接下来着重分析2个地区的数据合并问题。 数据结构的作用 三 第一步抽象与建模 设第1个地区共有n个产品销量数据，第2个地区共有m个产品销量数据。为了简化描述，突出核心部分的分析，考虑将问题抽象为n个有序整数和m个有序整数的合并问题，具体的问题模型如下: 已知一个降序排列的整数数列A:a1，a2，a3，…，an以及一个降序排列的整数数列B:b1，b2，b3，…，bm，将两个数列合并形成一个新的有序数列C，使新数列仍按降序排列，即c1≥c2≥c3≥…≥ck≥ck+1≥.…≥cn+m(其中ck∈A或者ck∈B)。请完成解决该问题的数据结构和算法的设计。 数据结构的作用 三 第二步设计、描述算法 (1)将数组a中所有元素存储到数组c的前n个位置中; 基于数组的算法设计与描述 1 数据结构的作用 三 (2)将数组c右边的m个元素赋值为-1 (c(n+1)直到c(n+m))； 基于数组的算法设计与描述 1 数据结构的作用 三 (3)变量p赋值为0，将表示数组c中有效元素总个数的变量tot赋值为n； 基于数组的算法设计与描述 1 数据结构的作用 三 (4)将数组b中元素b(i)逐个插入到数组c中(1≤ism)； p值增加1; 如果c(p)> b(i)，那么使p值增加1; 如果c(p)=-1，那么直接将b(i)存储到c(p)中，同时tot值增加1; 如果c(p)≤b(i)，那么依次将c(tot)，c(tot-1)，...，c(p)向右移动一个位置，然后将b(i)存储到c(p)中，同时tot值增加1。 数据结构的作用 三 (4)将数组b中元素b(i)逐个插入到数组c中(1≤ism)； p值增加1; 如果c(p)> b(i)，那么使p值增加1; 如果c(p)=-1，那么直接将b(i)存储到c(p)中，同时tot值增加1; 如果c(p)≤b(i)，那么依次将 c(tot)，c(tot-1)，...，c(p) 向右移动一个位置，然后将b(i) 存储到c(p)中，同时tot值增加1。 数据结构的作用 三 (4)将数组b中元素b(i)逐个插入到数组c中(1≤ism)； p值增加1; 如果c(p)> b(i)，那么使p值增加1; 如果c(p)=-1，那么直接将b(i)存储到c(p)中，同时tot值增加1; 如果c(p)≤b(i)，那么依次将 c(tot)，c(tot-1)，...，c(p) 向右移动一个位置，然后将b(i) 存储到c(p)中，同时tot值增加1。 数据结构的作用 三 (4)将数组b中元素b(i)逐个插入到数组c中(1≤ism)； p值增加1; 如果c(p)> b(i)，那么使p值增加1; 如果c(p)=-1，那么直接将b(i)存储到c(p)中，同时tot值增加1; 如果c(p)≤b(i)，那么依次将 c(tot)，c(tot-1)，...，c(p) 向右移动一个位置，然后将b(i) 存储到c(p)中，同时tot值增加1。 p p p tot 数据结构的作用 三 基于链表的算法设计与描述 2 上图 链表的初始状态 数据结构的作用 三 基于链表的算法设计与描述 2 上图 实施1次插入后的链表状态 数据结构的作用 三 小 结 数组的优点 (1)随机访问性强 (2)查找速度快 数组的缺点 (1)插入和删除效率低 (2)可能浪费内存 (3)内存空间要求高， 必须有充足的连续内存空间 (4)数组大小固定，不能动态拓展 链表的优点 (1)插入删除速度快 (2)内存利用率高，不会浪费内存 (3)大小没有固定，拓展灵活 链表的缺点 不能随意查找，必须从第一个开始遍历，查找效率低 谢谢观看 第2节 数据的组织 浙教版（2019） 选修一 $$