（精）2021新浙教版七年级下册《信息技术》第二单元第13课 初识数据结构ppt课件（含教案）.zip

浙教版信息技术七年级下册第浙教版信息技术七年级下册第 1313 课初识数据结构教学设计课初识数据结构教学设计 课题 初识数据结构单元第二单元学科信息技术年级七年级 学习 目标 知识目标：了解数据结构的概念及种类。 技能目标：理解计算机编程中数据的组织、存储和运算方法。 重点数据结构的概念及种类；理解计算机编程中数据的组织、存储和运算方法。 难点理解计算机编程中数据的组织、存储和运算方法。 教学过程 教学环节教师活动学生活动设计意图 导入新课同学们是不是有这样的经历，到图书馆去 借阅、归还图书，通过电脑扫描能准确的知道图 书的所在位置；学校学籍管理员通过电脑可准确 查询每个学生的学籍信息。面对海量的数据，计 算机是什么形式存贮的呢？这节课我们就一块来 学习数据结构。 思考 激发学生学习 兴趣并快速进入 学习状态 讲授新课利用计算机程序解决问题时，与问题有关的 数据往往不仅数量庞大，而且存在着错综复杂的 关系。 为了使计算机更加高效地处理数据，需要对 数据进行有效的组织和管理，并以一定的形式加 以存储和表示。 一、数据结构的概念一、数据结构的概念 数据结构是计算机学科特有的概念，指数据 之间的相互关系，即数据的组织形式。 合理的数据组织方式有利于提高解决问题的 效率 如图书馆对书的存放与管理，根据图书分类 法对图书进行分区、分类存放(如图所示) 并建立索引目录，从而提供快速借阅的服务。 计算机为了快速而高效地处理数据，也需要 根据问题解决的特点对数据进行有效的组织与管 通过教师的讲 解，以小组合 作的方式，开 展探讨交流， 完成任务。 通过小组合作， 加强学生组内团 结、共同完成任 务 理。 如音频播放器用“排队”方式组织播放列表 中的歌曲，可以让先加入播放列表的歌曲先播放。 计算机操作系统采用多级树型目录结构对文 件进行组织与管理(如图所示) 可以实现文件的分类存放和高效检索。 开动脑筋 在日常生活中还有哪些常见的数据组织管理 形式? 亲身体验 在本班同学通讯录中，试着利用数据之间的 关系设计出能快速找到家长电话号码的方法。 二、二、 常见的数据结构常见的数据结构 在算法和程序设计中，需要结合数据和数据 处理的特点，运用合适的数据结构组织数据、存 储数据，才能高效地完成对数据的处理。 常见的数据结构有数组、栈、队列等。 1.数组 现实中表示一批数据，有时不仅需要描述数 据的值，还需要描述数据所处的位置或数据之间 的前后顺序关系 对于这类数据集合的组织，可以用数组这种 数据结构来实现，如图所示。 用数组来组织数据时，既可以通过下标快速 地访问序列中的某个数据元素，如果数组 a 中的 第一个元素保存于 a0 那么 a3就表示数组中的第 4 个元素，也可以 方便地按下标顺序遍历序列中的每个元素。 2.栈 栈是具有“后进入的数据先出去”特点的数 学生小组间讨 论，共同完成 任务。 通过教师的讲 解，以小组合 作的方式，开 展探讨交流， 完成任务。 养学生组间合作 能力 通过小组合作， 加强学生组内团 结、共同完成任 务 据结构，采用的是一种数据进入顺序与数据出去 顺序相反的数据管理方式，如图所示。 类似于在桌上堆放书，放书的时候是从下往 上放(入栈)，最后放的书在最上面 而取书时则从最上面的一本书开始取走(出栈)， 相当于后进入的数据(书)先出去(被取走)。 网页浏览器对用户浏览网页的管理，就采用 了栈对网页数据进行组织。 当用户由一个网页跳转到另一个网页浏览时， 系统将原先的网页数据进行入栈操作 而当用户单击浏览器“后退”按钮时，系统 又将栈中最上方的网页数据出栈 户即可看到刚才浏览过的网页内容。 3.队列 队列是一种具有“先进入的数据先出去”特 点的数据结构，采用的是数据进入顺序与出去顺 序相一致的数据管理方式，如图所示 运用队列进行事物处理的例子 如食堂买饭时的排队、超市收银台付款时的 排队、高铁站的出租车接站排队等。 在计算机中，打印管理程序就是用队列来组 织发送给打印机一系列打印任务的。 打印机会根据收到的打印指令顺序，按照 “先收到先打印”的原则组织打印任务的队列， 再逐个打印文档，直到所有文档打印完毕。 日积月累 现实中要用计算机程序解决的问题是多种多 样，各类问题中数据的相互关系也是多种多样的。 为了高效地解决这些问题，计算机科学家还 发明了链表、树、图等数据结构。 通过教师的讲 解，以小组合 作的方式，开 展探讨交流， 完成任务。 通过教师的讲 解，以小组合 作的方式，开 展探讨交流， 完成任务。 通过小组合作， 加强学生组内团 结、共同完成任 务 通过小组合作， 加强学生组内团 结、共同完成任 务 链表 链表是物理存储单元上非连续的、非顺序的 存储结构 数据元素的逻辑顺序是通过链表的指针地址 实现，每个元素包含两个结点，一个是存储元素 的数据域 (内存空间)，另一个是指向下一个结点 地址的指针域。 根据指针的指向，链表能形成不同的结构， 例如单链表，双向链表，循环链表等。 链表的优点： 链表是很常用的一种数据结构，不需要初始 化容量，可以任意加减元素; 添加或者删除元素时只需要改变前后两个元 素结点的指针域指向地址即可，所以添加，删除 很快; 适用场景： 数据量较小，需要频繁增加，删除操作的场 景 树 树是一种数据结构，它是由 n(n=1)个有限节 点组成一个具有层次关系的集合。 把它叫做 “树” 是因为它看起来像一棵倒 挂的树，也就是说它是根朝上，而叶朝下的。 树的特点： 每个节点有零个或多个子节点; 没有父节点的节点称为根节点; 每一个非根节点有且只有一个父节点; 除了根节点外，每个子节点可以分为多个不 相交的子树; 图 图是由结点的有穷集合 V 和边的集合 E 组成。 通过教师的讲 解，以小组合 作的方式，开 展探讨交流， 完成任务。 通过教师的讲 解，以小组合 通过小组合作， 加强学生组内团 结、共同完成任 务 通过小组合作， 加强学生组内团 其中，为了与树形结构加以区别，在图结构 中常常将结点称为顶点，边是顶点的有序偶对， 若两个顶点之间存在一条边，就表示这两个顶点 具有相邻关系。 按照顶点指向的方向可分为无向图和有向图。 栈和队列的应用回文数 一个自然数如果顺读和倒读都相同，那么该 数就称为回文数。例如，22，383，5445，12321 等都是回文数。 可以借助栈和队列来判断一个数是否为回文 数。 先将该数除 10 取余得到个位上的数，然后同 时入栈和队列，再将该数除 10 取整得到新数 如此循环，直到整除后商为 0 为止。 此时，该数各个数位(从低位到高位)上的数都 已依次入栈和入队，如图所示的是 123454321 入 栈和入队的过程。 入栈示意图 人队列示意图 再利用栈(后进先出)和队列(先进先出)操作的 特点，比较每次出栈、出队的元素是否相同，即 an与 b1是否相同，an-1与 b2是否相同即可判 断该数是否为回文数。 数学界有一些关于回文数的猜想。 例如，人们迄今未找到自然数(除 0 和 1)的五 次方，以及更高次幂的回文数，于是数学家们猜 想：不存在 nk(n2，k5；n、k 均是自然数)形 式的回文数。 人们发现，一个自然数与它的倒序数相加， 作的方式，开 展探讨交流， 完成任务。 结、共同完成任 务 所得的和再与和的倒序数相加如此反复进行 下去，经过有限次步骤，最后能得到一个回文数， 但有些数并不“驯服”， 如 196 这个数，按照上述变换规则重复数十 万次，仍未能得到回文数，但是人们既不能肯定 运算下去永远得不到回文数，也不知道需要再运 算多少步才能得到回文数。 随堂练习随堂练习 1. 结合所学的几种数据结构，试着列举在生 活中或使用计算机时还有哪些类似的数据结构应 用。 学生小组间讨 论，共同完成 任务，并分组 汇报。 培养学生独立完 成练习的能力。 课堂小结分小组总结归纳，教师补充。各组汇报总结， 其他小组成员 做补充。 锻炼学生的总结 能力，逻辑思维、 语言表达能力。 布置作业 1. 什么是数据结构? 板书一、数据结构的概念 二、 常见的数据结构 信息技术浙教版 七年级下 第13课 初识数据结构 新知导入 同学们是不是有这样的经历，到图书馆去借阅、归还图书，通 过电脑扫描能准确的知道图书的所在位置；学校学籍管理员通过 电脑可准确查询每个学生的学籍信息。面对海量的数据，计算机 是什么形式存贮的呢？这节课我们就一块来学习数据结构。 新知讲解 利用计算机程序解决问题时，与问题有关的数据往往不仅 数量庞大，而且存在着错综复杂的关系。 为了使计算机更加高效地处理数据， 需要对数据进行有效的组织和管理，并 以一定的形式加以存储和表示。 新知讲解 一、数据结构的概念 数据结构是计算机学科特有的概念， 指数据之间的相互关系，即数据的组织 形式。 新知讲解 并建立索引目录，从而提 供快速借阅的服务。 合理的数据组织方式有利于提高解决问题的效率 如图书馆对书的存放与管理，根据图书分类法对图书进行分区、分 类存放(如图所示) 如音频播放器用“排队 ”方式组织播放列表中的歌 曲，可以让先加入播放列表 的歌曲先播放。 计算机为了快速而高效地处理数据，也需要根据问 题解决的特点对数据进行有效的组织与管理。 计算机操作系统采用多级树型目录结构对文 件进行组织与管理(如图所示) 可以实现文件的分类 存放和高效检索。 在日常生活中还有哪些常见的数 据组织管理形式? 开动脑筋 在本班同学通讯录中，试着利 用数据之间的关系设计出能快速找 到家长电话号码的方法。 亲身体验 二、 常见的数据结构 在算法和程序设计中，需要结合数据和数据处理的特点，运用 合适的数据结构组织数据、存储数据，才能高效地完成对数据的 处理。 常见的数据结构有数组、栈、队列等。 1.数组 现实中表示一批数据，有时不仅需要描述数据的值，还需要描述数 据所处的位置或数据之间的前后顺序关系 对于这类数据集合的组织，可以用数组这种数据结构来实现，如图 所示。 用数组来组织数据时，既可以通过下标快速 地访问序列中的某个数据元素，如果数组a中的 第一个元素保存于a0 那么a3就表示数组中的第 4个元素，也可以方便地按下标 顺序遍历序列中的每个元素。 2.栈 栈是具有“后进入的数据先出 去”特点的数据结构，采用的是一 种数据进入顺序与数据出去顺序相 反的数据管理方式，如图所示。 而取书时则从最上面的一本书开 始取走(出栈)，相当于后进入的数据( 书)先出去(被取走)。 类似于在桌上堆放书，放书的时候是从下往 上放(入栈)，最后放的书在最上面 网页浏览器对用户浏览网页的管理，就采用了 栈对网页数据进行组织。 当用户由一个网页跳转到另一个网页浏览时，系统将原先 的网页数据进行入栈操作 而当用户单击浏览器“后退”按钮时，系统又将栈中最上方 的网页数据出栈 用户即可看到刚才浏览过的网页内容。 3.队列 队列是一种具有“先进入的数据先出去”特点的数据结构，采用 的是数据进入顺序与出去顺序相一致的数据管理方式，如图所示 如食堂买饭时的排队、超市收银台 付款时的排队、高铁站的出租车接站排 队等。 运用队列进行事物处理的例子 在计算机中，打印管理程序就是用队列来组织发送给打印 机一系列打印任务的。 打印机会根据收到的打印指令顺序，按 照“先收到先打印”的原则组织打印任务 的队列，再逐个打印文档，直到所有文档 打印完毕。 日积月累 现实中要用计算机程序解决的问题是多种多样，各类问题中 数据的相互关系也是多种多样的。 为了高效地解决这些问题，计算 机科学家还发明了链表、树、图等 数据结构。 链表 链表是物理存储单元上非连续的、非顺序的存储结构 数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两 个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个 结点地址的指针域。 根据指针的指向，链表能形成不同的结构，例如单链表，双向 链表，循环链表等。 链表的优点： 链表是很常用的一种数据结构，不需要初始化容量，可以任意加 减元素; 添加或者删除元素时只需要改变前后两个元素结点的指针域指向 地址即可，所以添加，删除很快; 适用场景： 数据量较小，需要频繁增加，删除操作的场景 树 树是一种数据结构，它是由n(n=1)个有限节点组成一个具有层次关系的集合。 把它叫做 “树” 是因为它看起来像 一棵倒挂的树，也 就是说它是根朝上 ，而叶朝下的。 树的特点： 每个节点有零个或多个子节点; 没有父节点的节点称为根节点; 每一个非根节点有且只有一个父节点; 除了根节点外，每个子节点可以分为多个不相交的子树; 图 图是由结点的有穷集合V和边的集合E组成。 其中，为了与树形结构加以区别，在 图结构中常常将结点称为顶点，边是顶点 的有序偶对，若两个顶点之间存在一条边 ，就表示这两个顶点具有相邻关系。 按照顶点指向的方向可分为无 向图和有向图。 栈和队列的应用回文数 一个自然数如果顺读和倒读都相同，那么该数就称为回文数。例 如，22，383，5445，12321等都是回文数。 可以借助栈和队列来判断一个数是否为回文数。 先将该数除10取余得到个位上的数，然后同时入栈和队列，再将 该数除10取整得到新数如此循环，直到整除后商为0为止。 此时，该数各个数位(从低位到高位)上的数都已依 次入栈和入队，如图所示的是123454321入栈和入队 的过程。 入栈示意图人队列示意图 再利用栈(后进先出)和队列(先进先出)操作 的特点，比较每次出栈、出队的元素是否相同 ，即an与b1是否相同，an-1与b2是否相同 即可判断该数是否为回文数。 例如，人们迄今未找到自然数(除0和1)的五次方，以及更高次幂的回文数， 于是数学家们猜想：不存在nk(n2，k5；n、k均是自然数)形式的回文数。 数学界有一些关于回文数的猜想。 人们发现，一个自然数与它的倒序数相加，所得的和再与和的倒序 数相加如此反复进行下去，经过有限次步骤，最后能得到一个回 文数，但有些数并不“驯服”， 如196这个数，按照上述变换规则重复数十万次，仍未能得到回文 数，但是人们既不能肯定运算下去永远得不到回文数，也不知道需要 再运算多少步才能得到回文数。 1. 结合所学的几种数据结构，试着 列举在生活中或使用计算机时还有哪些 类似的数据结构应用。 总结本节课所学内容 1. 什么是数据结构? 作业布置 板书设计 一、数据结构的概念 二、 常见的数据结构