【信息技术 】数据与结构（课件） 高一信息技术同步课件（教科版2019必修1）

数据与结构2019教科版高中信息技术一、情境导入观看视频并思考：什么是数据类型？有哪些数据类型？二、知识讲授数据类型二、知识讲授数据类型不同的程序语言，其数据类型构造略有不同，但是整体结构通用统一。简单数据类型和复合数据类型简单数据类型不能分解成更小的数据类型。复合数据类型则由简单数据类型或者复合数据类型组成。在Python语言中，整数、浮点数、字符串、布尔属于简单数据类型，列表、字典等属于复合数据类型。二、知识讲授数据类型二、知识讲授数据结构数据结构是存在特定关系的数据元素的集合。在解决有些问题时，一些相关联的数据将集中在一起，形成一个数据的集合，这种集合能够单独或作为一个整体被访问和处理。这里的数据结构也称为逻辑结构，主要有集合结构、线性结构、树结构和图结构（又称网状结构）四种类型。二、知识讲授数据结构这里的数据结构也称为逻辑结构，主要有集合结构、线性结构、树结构和图结构（又称网状结构）四种类型。二、知识讲授线性-数据结构线性数据结构又称为线性表在线性数据结构中，除首元素没有前趋元素、尾元素没有后继元素外，其他元素都只有一个前趋元素和一个后继元素。二、知识讲授线性数据结构-队列队列是一种有限制的线性结构，它的数据元素只能在一端依次添加（进队），在另一端依次删除（出队）。典型的例子如超市里排队付款的队伍。许多程序设计语言定义了复杂数据类型，以实现对数据结构更高层级的抽象。复杂数据类型可以封装并隐藏数据结构中的操作细节，让程序设计者更多地关注数据结构能做什么，便于利用数据结构解决问题。二、知识讲授队列线性数据结构-队列二、知识讲授树-数据结构树结构是一种具有层次关系的非线性结构。树是由n（n≥0）个节点组成的有限集合。若n=0，则称为空树。任何一个非空树均满足以下两个条件：（1）仅有一个称为根的节点；（2）当n>0时，其余节点可分为m（m≥0）个互不相交的有限集合，其中每个集合又是一棵树，并称为根的子树。二、知识讲授数据树二、知识讲授图-数据结构图结构是由一组节点（称为顶点）和一组节点间的连线（称为边或弧）构成的一种数据结构。图结构中的每个顶点都可以与其他顶点有边相连，图结构中数据元素之间是多对多的关系。在物流网络中，分拨中心、配送中心、货物需求点等可以抽象为图的顶点，城市道路、各级铁路等可以抽象为图的边，如城市以及城市之间的运输道路就是图结构。利用图结构，我们还可以解决物流中的许多问题，如道路网络分析、车辆运营安排等。二、知识讲授无向图有向图图-数据结构二、知识讲授图-数据结构生产供应网络结构仓储网络结构二、知识讲授线性与非线性结构结构类型节点关系实例图示线性结构一对一队列日常生活中的排队树形结构一对多学科知识归纳图结构多对多物流网络人机关系网络画出各“数据结构类型”的图示三、问题探究赫夫曼树自主查阅资料并小组探究如何将数组[5,14,2,8,36,25,10]构造为一颗赫夫曼树，并且计算其带权路径长度WPL。提示：什么是赫夫曼树？什么是wpl？如何将数组转化为树形结构？10039612536152478101425Wpl=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。结点的带权路径长度：指的是从根结点到该结点之间的路径长度与该结点的权的乘积。树的带