（精）2021新浙教版七年级下册《信息技术》第二单元第14课 线性表ppt课件（含教案）.zip

浙教版信息技术七年级下册第浙教版信息技术七年级下册第 1414 课线性表教学设计课线性表教学设计 课题 线性表单元第二单元学科信息技术年级七年级 学习 目标 知识目标：了解线性表顺序结构应用。 技能目标：掌握线性表的概念及特点，掌握线性表的两种不同分类。 重点掌握线性表的概念及特点；掌握线性表的两种不同分类。 难点掌握线性表的概念及特点；掌握线性表的两种不同分类。 教学过程 教学环节教师活动学生活动设计意图 导入新课前面我们认识了一些数据结构，图片中的 结构是什么结构？今天我们一块来学习表示数据 的一种结构线性表 欣赏视频 思考 激发学生学习 兴趣并快速进入 学习状态 讲授新课线性结构是最基本、最简单，也是最常用的 一种数据结构。 而线性表是一种最基础的线性结构。 一、线性表的概念一、线性表的概念 反映现实世界的数据常具有特定的逻辑关系。 例如，某校 20102019 年七年级的招生人 数可以用如下一组数据表示： (653，669，670，688，669，650，655，667 ，689，680) 当看到这组数据时，会很自然地将年份与这 些数据联系起来，得到以下数据表： 此时， (653，669，670，688，669，650，655，667，689 ，680)就是线性表的一种表示方式。 线性表是由 n(n0)个元素组成的有限序列。 当 n=0 时，表示线性表中没有元素，为空表。 线性表一般的表示方法为： a0，a1，.，ai-1，ai，ai+1，.，an-1) 通过教师的讲 解，以小组合 作的方式，开 展探讨交流， 完成任务。 通过小组合作， 加强学生组内团 结、共同完成任 务 表中数据元素从 a0开始到 an-1结束，则可以 称 a0为首节点， an-1为尾节点。 表中相邻两个元素之间存在顺序关系，如 ai-1 先于 ai， ai又先于 ai+1，则称 ai-1是 ai的前驱， ai+1是 ai的后继。 也就是说，在这个集合中，除 a0和 an-1外， 每个元素都有唯一的前驱和后继，如图所示。 线性表 日积月累 在线性结构中，有且仅有一个开始节点，即 ao，该节点只有后继节点，没有前驱节点； 有且仅有一个结束节点，即 an-1，该节点只有 前驱节点，没有后继节点。 线性表结构特点 1.均匀性：虽然不同数据表的数据元素可以是 各种各样的，但对于同一线性表的各数据元素必 定具有相同的数据类型和长度。 2.有序性：各数据元素在线性表中的位置只取 决于它们的序号，数据元素之前的相对位置是线 性的，即存在唯一的“第一个“和“最后一个” 的数据元素，除了第一个和最后一个外，其它元 素前面均只有一个数据元素(直接前驱)和后面均只 有一个数据元素（直接后继）。 二、线性表的存储结构二、线性表的存储结构 线性表的存储结构一般有两种方式：顺序存 储结构和链式存储结构。 先来看一个生活中的例子 如图所示的五个球分别标记为 1 号、2 号、3 号、4 号、5 号 在需要将这五个球放入收纳架(如图所示) 那么可以如何收纳呢? 通过教师的讲 解，以小组合 作的方式，开 展探讨交流， 完成任务。 通过小组合作， 加强学生组内团 结、共同完成任 务 在收纳架中，一个位置只能摆放一个球。 球的摆放方式有以下两种： 一种是按照每一个球的编号分别按一定的顺 序放入收纳架中，如图所示； 还有一种是随意摆放，如图所示。 按照球的收纳方式的不同，球的摆放方式又 称为顺序存放和非顺序存放。 这种非顺序存放又可以称为链式存放。 如果将 1 一 5 号球想象成计算机中的数据， 那么它们的存储方式就有两种，如图所示。 (1)顺序存储结构 (2)链式存储结构 从图中可以看出，根据数据的存储方式的不 同，线性表的存储结构可以分为顺序存储结构和 链式存储结构。 (1)顺序存储结构 如图所示，将数据按照一定的顺序存储在连 续的整个物理空间中，即逻辑上相邻的两个数据 在物理存储上也相邻，这种存储方式称为顺序存 储结构，简称顺序表。 (2)链式存储结构 如图所示，数据分散地存储在物理空间中， 在表示数据之间的逻辑关系时，每一个元素不仅 需要存储数据信息而且还需要存储其后继数据元 素的位置信息，这种存储结构称为链式存储结构， 简称链表。 知识链接 链表 链表是一种链式存储结构，节点既存储数据 元素本身的信息，又需要存储数据元素之间的链 接信息，即地址域，也叫指针域。 通过教师的讲 解，以小组合 作的方式，开 展探讨交流， 完成任务。 通过教师的讲 解，以小组合 作的方式，开 展探讨交流， 完成任务。 通过小组合作， 加强学生组内团 结、共同完成任 务 通过小组合作， 加强学生组内团 结、共同完成任 务 三、线性结构中的数组列表三、线性结构中的数组列表 线性结构在生活中的应用非常广泛，比如经 常用到的搜索引擎，对字符串的各种查找、索引 的算法等。 数组就是一个用来存储数值的容器，如前面 提及的篮球架。 一般用（a0，a1，.，ai-1，ai，ai+1，.，an-1)来 表示含有 n 个元素的数组 a。 其中，a0的下标是 0。下标即是用来表示数组 元素所在的位置。 如图所示，开辟七个空间来存放 A-G 七个字 母，a0是数组 a 的第一个元素，即是 A，a6的数据 是 G。 数据元素 数组下标 若在数组中，删除下标为 3 的数组空间中的 元素 a3即 D，则插入点后的所有元素都要向前移， 结果为 A-B-C-E-F-G，如图所示。 由于数组空间的长度是固定的，所以 a6地址 单元中元素为空。 接着，在 a4空间中插入元素 H，则插入点后 的所有元素全部都要向后移，结果为 A-B-C-E-H- F-G，如图所示。 开动脑筋 如果在一个顺序表中，后面没有多余的空间 了，那么执行插入操作后会产生怎样的结果呢? 线性表的推广 时间有序表、排序表、和频率有序表都可以 看做是线性表的推广。 如果按照结点到达结构的时间先后，作为确 定结点之间关系的，这样一种线性结构称之为时 通过教师的讲 解，以小组合 作的方式，开 展探讨交流， 完成任务。 通过教师的讲 解，以小组合 作的方式，开 展探讨交流， 完成任务。 通过小组合作， 加强学生组内团 结、共同完成任 务 通过小组合作， 加强学生组内团 结、共同完成任 务 间有序表。 例如，在红灯前停下的一长串汽车，最先到 达的为首结点，最后到达的为尾结点；在离开时 最先到达的汽车将最先离开，最后到达的将最后 离开。 这些汽车构成理一个队列，实际上就是一个 时间有序表。 随堂练习随堂练习 若有以下顺序表，在执行将 33 插入后，需要 几个移动步骤? 学生小组间讨 论，共同完成 任务，并分组 汇报。 培养学生独立完 成练习的能力。 课堂小结分小组总结归纳，教师补充。各组汇报总结， 其他小组成员 做补充。 锻炼学生的总结 能力，逻辑思维、 语言表达能力。 布置作业 1.什么是线性表?按照存储方式的不同，线性 表分成哪两大类?量出 1 毫升的水?请写出算法。 板书一、线性表的概念 二、线性表的存储结构 三、线性结构中的数组列表 信息技术浙教版 七年级下 第14课 线性表 新知导入 前面我们认识了一些数据结构，图片中的结构是什么结构？今 天我们一块来学习表示数据的一种结构线性表 线性结构是最基本、最简单，也是最常用的一种 数据结构。 而线性表是一种最基础的线性结构。 一、线性表的概念 反映现实世界的数据常具有特 定的逻辑关系。 例如，某校20102019年七年级的招 生人数可以用如下一组数据表示： (653，669，670，688，669，650，655，667，689，680) 当看到这组数据时，会很自然地将年份与这些数据联系起来， 得到以下数据表： 2010201120122013 20142015201620172018 2019 653669670688669650655667689680 此时，(653，669，670，688，669，650，655， 667，689，680)就是线性表的一种表示方式。 线性表是由n(n0)个元素组成的有限序列。 当n=0时，表示线性表中没有元素，为空表。 线性表一般的表示方法为： （a0，a1，.，ai-1，ai，ai+1，.，an-1) 表中数据元素从a0开始到an-1结束，则可以称a0为 首节点， an-1为尾节点。 表中相邻两个元素之间存在顺序关系，如ai-1先于ai， ai又先于 ai+1，则称ai-1是ai的前驱， ai+1是ai的后继。 也就是说，在这个集合中，除a0和an-1外，每个元素都有唯一的前驱 和后继，如图所示。 a0a1 . ai-1 aiai+1 线性表 日积月累 在线性结构中，有且仅有一个开始节点，即ao，该 节点只有后继节点，没有前驱节点； 有且仅有一个结束节点，即an-1， 该节点只有前驱节点，没有后继节点。 线性表结构特点 1.均匀性：虽然不同数据表的数据元素可以是各种各样的，但对于 同一线性表的各数据元素必定具有相同的数据类型和长度。 2.有序性：各数据元素在线性表中的位置只取决于它们的序号，数据元 素之前的相对位置是线性的，即存在唯一的“第一个“和“最后一个”的 数据元素，除了第一个和最后一个外，其它元素前面均只有一个数据元素( 直接前驱)和后面均只有一个数据元素（直接后继）。 二、线性表的存储结构 线性表的存储结构一般有两种 方式：顺序存储结构和链式存储 结构。 先来看一个生活中的例子 如图所示的五个球分别标记为1号、2号、3号、4号、5号 在收纳架中，一个位置只能摆放一个球。 球的摆放方式有以下两种： 一种是按照每一个球的编 号分别按一定的顺序放入收 纳架中，如图所示； 在需要将这五个球放入收纳架(如图所示) 那么可以如何收纳呢? 还有一种是随意摆放，如 图所示。 按照球的收纳方式的不同，球的摆放方式又称为 顺序存放和非顺序存放。 这种非顺序存放又可以称为链式存放。 如果将1一5号球想象成计算机中的数据，那么它们 的存储方式就有两种，如图所示。 (1)顺序存储结构 (2)链式存储结构 从图中可以看出， 根据数据的存储方式 的不同，线性表的存 储结构可以分为顺序 存储结构和链式存储 结构。 (1)顺序存储结构 如图所示，将数据按照一定的顺 序存储在连续的整个物理空间中，即 逻辑上相邻的两个数据在物理存储上 也相邻，这种存储方式称为顺序存储 结构，简称顺序表。 (2)链式存储结构 如图所示，数据分散地存储在物理空 间中，在表示数据之间的逻辑关系时，每 一个元素不仅需要存储数据信息而且还需 要存储其后继数据元素的位置信息，这种 存储结构称为链式存储结构，简称链表。 知识链接 链表 链表是一种链式存储结构，节点既 存储数据元素本身的信息，又需要存储 数据元素之间的链接信息，即地址域， 也叫指针域。 三、线性结构中的数组列表 线性结构在生活中的应用非常广 泛，比如经常用到的搜索引擎，对字 符串的各种查找、索引的算法等。 数组就是一个用来存储数值的容器，如前面提 及的篮球架。 一般用（a0，a1，.，ai-1，ai，ai+1，.，an-1)来表示 含有n个元素的数组a。 其中，a0的下标是0。下标即是用来表示数组元素所在的位置。 如图所示，开辟七个空间来存放A-G七个字母，a0 是数组a的第一个元素，即是A，a6的数据是G。 数组下标 数据元素 ABCDEFG 0123456 若在数组中，删除下标为3的数组空间中的 元素a3即D，则插入点后的所有元素都要向前 移，结果为A-B-C-E-F-G，如图所示。 ABCEFG 0123456 由于数组空间的长度是固 定的，所以a6地址单元中元 素为空。 接着，在a4空间中插入元素H，则插入点后的所有元素 全部都要向后移，结果为A-B-C-E-H-F-G，如图所示。 ABCEHFG 0123456 如果在一个顺序表中，后面 没有多余的空间了，那么执行插 入操作后会产生怎样的结果呢? 开动脑筋 线性表的推广 时间有序表、排序表、和频率有序表都可以看做是线性表的推广。 如果按照结点到达结构的时间先后，作为确定结点之间关系的，这样 一种线性结构称之为时间有序表。 例如，在红灯前停下的一长串汽车，最先到达的为首结点，最后到达 的为尾结点；在离开时最先到达的汽车将最先离开，最后到达的将最后 离开。 这些汽车构成理一个队列，实际上就是一个时间有序表。 若有以下顺序表，在执行将33插入后，需要几 个移动步骤? 总结本节课所学内容 1.什么是线性表?按照存储方式 的不同，线性表分成哪两大类? 作业布置 一、线性表的概念 二、线性表的存储结构 三、线性结构中的数组列表