(共22张PPT)
数据与结构
2019教科版
高中信息技术
高一，1班
一、情境导入
观看视频并思考：
什么是数据类型？
有哪些数据类型？
二、知识讲授
数据类型
二、知识讲授
数据类型
不同的程序语言，其数据类型构造略有不同，但是整体结构通用统一。
简单数据类型和复合数据类型
简单数据类型不能分解成更小的数据类型。
复合数据类型则由简单数据类型或者复合数据类型组成。
在Python语言中，整数、浮点数、字符串、布尔属于简单数据类型，列表、字典等属于复合数据类型。
二、知识讲授
数据类型
二、知识讲授
数据结构
数据结构
是存在特定关系的数据元素的集合。在解决有些问题时，一些相关联的数据将集中在一起，形成一个数据的集合，这种集合能够单独或作为一个整体被访问和处理。
这里的数据结构也称为逻辑结构，主要有集合结构、线性结构、树结构和图结构（又称网状结构）四种类型。
二、知识讲授
数据结构
这里的数据结构也称为逻辑结构，主要有集合结构、线性结构、树结构和图结构（又称网状结构）四种类型。
二、知识讲授
线性-数据结构
线性数据结构
又称为线性表
在线性数据结构中，除首元素没有前趋元素、尾元素没有后继元素外，其他元素都只有一个前趋元素和一个后继元素。
二、知识讲授
线性数据结构-队列
队列
是一种有限制的线性结构，它的数据元素只能在一端依次添加（进队），在另一端依次删除（出队）。典型的例子如超市里排队付款的队伍。
许多程序设计语言定义了复杂数据类型，以实现对数据结构更高层级的抽象。复杂数据类型可以封装并隐藏数据结构中的操作细节，让程序设计者更多地关注数据结构能做什么，便于利用数据结构解决问题。
二、知识讲授
队列
线性数据结构-队列
二、知识讲授
树-数据结构
树结构
是一种具有层次关系的非线性结构。
树是由n（n≥0）个节点组成的有限集合。若n=0，则称为空树。
任何一个非空树均满足以下两个条件：
（1）仅有一个称为根的节点；
（2）当n>0时，其余节点可分为m（m≥0）个互不相交的有限集合，其中每个集合又是一棵树，并称为根的子树。
二、知识讲授
数据
树
二、知识讲授
图-数据结构
图结构
是由一组节点（称为顶点）和一组节点间的连线（称为边或弧）构成的一种数据结构。图结构中的每个顶点都可以与其他顶点有边相连，图结构中数据元素之间是多对多的关系。
在物流网络中，分拨中心、配送中心、货物需求点等可以抽象为图的顶点，城市道路、各级铁路等可以抽象为图的边，如城市以及城市之间的运输道路就是图结构。利用图结构，我们还可以解决物流中的许多问题，如道路网络分析、车辆运营安排等。
二、知识讲授
无向图
有向图
图-数据结构
二、知识讲授
图-数据结构
生产供应网络结构
仓储网络结构
二、知识讲授
线性与非线性结构
结构类型 节点关系 实例 图示
线性结构 一对一 队列 日常生活中的排队
树形结构 一对多 学科知识归纳
图结构 多对多 物流网络 人机关系网络
画出各“数据结构类型”的图示
三、问题探究
赫夫曼树
自主查阅资料并小组探究如何将数组
[5,14,2,8,36,25,10]构造为一颗赫夫曼树，并且计算其带权路径长度WPL。
提示：什么是赫夫曼树？
什么是wpl？
如何将数组转化为树形结构？
100
39
61
25
36
15
24
7
8
10
14
2
5
Wpl=2×4+5×4+3×8+3×10+3×14+2×25+2×36
赫夫曼树
三、问题探究
问题探究的解答过程
赫夫曼树
三、问题探究
赫夫曼树原理
赫夫曼树
当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”。
对于给定的有各自权值的 n 个结点，构建哈夫曼树有一个行之有效的办法：
在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和；
在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推；
重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。
构建哈夫曼树时，首先需要确定树中结点的构成。由于哈夫曼树的构建是从叶子结点开始，不断地构建新的父结点，直至树根
三、问题探究
赫夫曼树原理
路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径。图 1 中，从根结点到结点 a 之间的通路就是一条路径。
路径长度：在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第 i 层结点的路径长度为 i - 1 。图 1 中从根结点到结点 c 的路径长度为 3。
结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权。例如，图 1 中结点 a 的权为 7，结点 b 的权为 5。
结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。
三、问题探究
四、课后作业
1、一般的数据类型有哪些？
2、数据结构有有哪些？其结构图示是怎样的？
3、赫夫曼树的原理和wpl如何计算？教学单元 认识数据 教学主题 数据与结构
教学目标
知识与技能 知道常见数据类型，区别简单数据类型和复合数据类型 理解数据结构的内涵 掌握并能在生活中运用各类数据结构 过程与方法 通过创设生活情境让学生深入理解数据结构的概念，基于问题探究挑战赫夫曼树的构造原理，能够最大程度激发学生的学习兴趣。 情感态度价值观 数据结构中的逻辑结构有利于培养学生的逻辑思维能力和概念推理能力。
核心素养培养
概念之间的逻辑关系、生活中场景都用到了简易的数据结构类型，通过数据结构。
教学内容
数据类型；数据结构及其类型；赫夫曼树
教学媒体
电子白板、PPT
教学过程
教学环节 教师活动 学生活动 设计意图
情境导入 播放数据类型的科普视频。 【提问】 观看视频并思考： 什么是数据类型？ 有哪些数据类型？ 观看视频并回答问题。 数据类型是基于二进制之后更加抽象的计算机处理数据的概念，因此通过视频导入，让学生能够理解简单的数据类型。
课堂讲授 【知识点一、数据类型】
一般的数据类型包括以下： 布尔类型：逻辑值0和1； 数值类型：整型，int 浮点类型：float，double等 数组类型：array 列表类型：list 不同的程序语言，其数据类型构造略有不同，但是整体结构通用统一。 简单数据类型和复合数据类型 简单数据类型不能分解成更小的数据类型。 复合数据类型则由简单数据类型或者复合数据类型组成。 在Python语言中，整数、浮点数、字符串、布尔属于简单数据类型，列表、字典等属于复合数据类型。 查找资料并说明不同的数据类型所使用的范围、作用，并举例。 不同的数据类型能够延伸到很深入的概念知识，但是只需要学生理解不同的数据类型、常见常用的数据类型其意义和用途，如此理解数据类型即可。
【知识点二、数据结构及其类型】
1、数据结构 是存在特定关系的数据元素的集合。在解决有些问题时，一些相关联的数据将集中在一起，形成一个数据的集合，这种集合能够单独或作为一个整体被访问和处理。 这里的数据结构也称为逻辑结构，主要有集合结构、线性结构、树结构和图结构（又称网状结构）四种类型。 记录笔记并画出各数据结构图示 数据结构是很抽象的概念，但是通过图示就能一目了然其结构样式。因此需要先将图示呈现，再让学生理解各类数据结构之间的概念。 其次让学生模仿画图能够更加理解生活中的数据结构场景。 最后通过完成表格更够进一步区别节点关系、实例和图示。
2、数据结构类型 这里的数据结构也称为逻辑结构，主要有集合结构、线性结构、树结构和图结构（又称网状结构）四种类型。 3、线性数据结构： 又称为线性表 在线性数据结构中，除首元素没有前趋元素、尾元素没有后继元素外，其他元素都只有一个前趋元素和一个后继元素。 队列 是一种有限制的线性结构，它的数据元素只能在一端依次添加（进队），在另一端依次删除（出队）。典型的例子如超市里排队付款的队伍。 许多程序设计语言定义了复杂数据类型，以实现对数据结构更高层级的抽象。复杂数据类型可以封装并隐藏数据结构中的操作细节，让程序设计者更多地关注数据结构能做什么，便于利用数据结构解决问题。 4、树结构 是一种具有层次关系的非线性结构。 树是由n（n≥0）个节点组成的有限集合。若n=0，则称为空树。 任何一个非空树均满足以下两个条件： 仅有一个称为根的节点； 当n>0时，其余节点可分为m（m≥0）个互不相交的有限集合，其中每个集合又是一棵树，并称为根的子树。 5、图结构 是由一组节点（称为顶点）和一组节点间的连线（称为边或弧）构成的一种数据结构。图结构中的每个顶点都可以与其他顶点有边相连，图结构中数据元素之间是多对多的关系。 在物流网络中，分拨中心、配送中心、货物需求点等可以抽象为图的顶点，城市道路、各级铁路等可以抽象为图的边，如城市以及城市之间的运输道路就是图结构。利用图结构，我们还可以解决物流中的许多问题，如道路网络分析、车辆运营安排等。 【任务】
问题探究 赫夫曼树： 自主查阅资料并小组探究如何将数组 [5,14,2,8,36,25,10]构造为一颗赫夫曼树，并且计算其带权路径长度WPL。 提示： 什么是赫夫曼树？ 什么事wpl？ 如何将数组转化为树形结构？ Wpl=2×4+5×4+3×8+3×10+3×14+2×25+2×36 首先让学生自主学习、查找资料，了解赫夫曼树的概念、原理和wpl的机制，培养其问题探究能力。 其次能够按照相应内容在教师辅导下完成问题探究，实现探究学习。
播放学习赫夫曼树视频： 赫夫曼树 当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”。 对于给定的有各自权值的 n 个结点，构建哈夫曼树有一个行之有效的办法：
在 n 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和； 在原有的 n 个权值中删除那两个最小的权值，同时将新的权值加入到 n–2 个权值的行列中，以此类推； 重复 1 和 2 ，直到所以的结点构建成了一棵二叉树为止，这棵树就是哈夫曼树。 构建哈夫曼树时，首先需要确定树中结点的构成。由于哈夫曼树的构建是从叶子结点开始，不断地构建新的父结点，直至树根 路径：在一棵树中，一个结点到另一个结点之间的通路，称为路径。图 1 中，从根结点到结点 a 之间的通路就是一条路径。 路径长度：在一条路径中，每经过一个结点，路径长度都要加 1 。例如在一棵树中，规定根结点所在层数为1层，那么从根结点到第 i 层结点的路径长度为 i - 1 。图 1 中从根结点到结点 c 的路径长度为 3。 结点的权：给每一个结点赋予一个新的数值，被称为这个结点的权。例如，图 1 中结点 a 的权为 7，结点 b 的权为 5。 结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。 认真记笔记，并查找资料，学习赫夫曼树。
学习评价 1、一般的数据类型有哪些？ 2、数据结构有有哪些？其结构图示是怎样的？ 3、赫夫曼树的原理和wpl如何计算？ 练习、评价和总结巩固知识。
